Главная   Онлайн инструменты по математической логике   Мат. логика теория   Как считает компьютер?   Схемы для ЭВМ    

Полином Жегалкина

Определение булевой функции
Элементарные булевы функции
Задание булевых функций посредством элементарных
Существенные и несущественные переменные
Эквивалентные функции
Основные эквивалентности
Функциональная полнота
Нормальные формы
Совершенные нормальные формы
Минимизация ДНФ методом Квайна
Карты Карно
Полином Жегалкина
Высказывания
Предикаты
Кванторы
Определение формальной теории
Исчисление высказываний
Теорема о дедукции. Полнота ИВ
Автоматическое доказательство теорем
Метод резолюций в ИВ
Определение алгоритма
Машина Тьюринга
Рекурсивные функции
Алгоритмически неразрешимые задачи
Алгоритмы и их сложности



     Множество булевых функций, заданный в базисе Жегалкина S4={⊕,&,1} называется алгеброй Жегалкина.
     Основные свойства.
     1. коммутативность
     H1⊕H2=H2⊕H1
     H1&H2=H2&H1
     2. ассоциативность
     H1⊕(H2⊕H3)=(H1⊕H2)⊕H3
     H1&(H2&H3)=(H1&H2)&H3
     3. дистрибутивность
     H1&(H2⊕H3)=(H1&H2)⊕(H1&H3)
     4. свойства констант
     H&1=H
     H&0=0
     H⊕0=H
     5. H⊕H=0
     H&H=H
     Утверждение. Через операции алгебры Жегалкина можно выразить все другие булевы функции:
     ¬X=1⊕X
     XvY=X⊕Y⊕XY
     X∼Y=1⊕X⊕Y
     X→Y=1⊕X⊕XY
     X↓Y=1⊕X⊕Y⊕XY
     X|Y=1⊕XY
     Определение. Полиномом Жегалкина (полиномом по модулю 2) от n переменных X1,X2 ... Xn называется выражение вида:
     C0⊕C1X1⊕C2X2⊕ ... ⊕CnXn⊕C12X1X2⊕ ... ⊕C12 ... nX1X2 ... Xn,
     где постоянные Ck могут принимать значения 0 ли 1.
     Если полином Жегалкина не содержит произведений отдельных переменных, то он называется линейным (линейная функция).
     Например, f=X⊕YZ⊕XYZ и f1=1⊕X⊕Y⊕Z - полиномы, причем вторая является линейной функцией.
     Теорема. Каждая булева функция представляется в виде полинома Жегалкина единственным образом.
     Приведем основные методы построения полиномов Жегалкина от заданной функции.
     1. Метод неопределенных коэффициентов. Пусть P(X1,X2 ... Xn) - искомый полином Жегалкина, реализующий заданную функцию f(X1,X2 ... Xn). Запишем его в виде
     P=C0⊕C1X1⊕C2X2⊕ ... ⊕CnXn⊕C12X1X2⊕ ... ⊕C12 ... nX1X2 ... Xn
     Найдем коэффициенты Ck. Для этого последовательно придадим переменным X1,X2 ... Xn значения из каждой строки таблицы истинности. В итоге получим систему из 2n уравнений с 2n неизвестными, имеющую единственное решение. Решив ее, находим коэффициенты полинома P(X1,X2 ... Xn).
     2. Метод, основанный на преобразовании формул над множеством связок {¬,&}. Строят некоторую формулу Ф над множеством связок {¬,&}, реализующую данную функцию f(X1,X2 ... Xn). Затем заменяют всюду подформулы вида ¬A на A⊕1, раскрывают скобки, пользуясь дистрибутивным законом (см. свойство 3), а затем применяют свойства 4 и 5.
     Пример. Построить полином Жегалкина функции f(X,Y)=X→Y
     Решение.
     1. (метод неопределенных коэффициентов). Запишем искомый полином в виде:
     P=C0⊕C1X⊕C2Y⊕C12XY
     Пользуясь таблицей истинности

X0011
Y0101
X→Y1101

     получаем, что
     f(0,0)=P(0,0)=C0=1
     f(0,1)=P(0,1)=C0⊕C2=1
     f(1,0)=P(1,0)=C0⊕C1=0
     f(1,1)=P(1,1)=C0⊕C1⊕C2⊕C12=1
     Откуда последовательно находим, C0=1, C1=1, C2=0, C12=1
     Следовательно: x→y=1⊕X⊕XY.
     2. (Метод преобразования формул.). Имеем:
     X→Y=¬XvY=¬(X¬Y)=(X(Y⊕1))⊕1=1⊕X⊕XY
     Заметим, что преимущество алгебры Жегалкина (по сравнению с другими алгебрами) состоит в арифметизации логики, что позволяет выполнять преобразования булевых функций довольно просто. Ее недостатком по сравнению с булевой алгеброй является громоздкость формул.

@ 2010 - 2016 tablica-istinnosti.ru Рейтинг@Mail.ru