27. Булева алгебра. Основные свойства операций булевой алгебры. Понятие двойственной и самодвойственной логической функции.

Двойственность. Принцип двойственности.

Функция f^*(x_n) называется двойственной функции f(x_n), если она построена по правилу: f^*(x_n)=not( f(x₁, x₂, …,x_n) )= f(x_n). Чтобы построить f* на нуле, мы должны посмотреть, чему равно значение функции на 1 и инвертировать: f^*(0)= f(1). Столбец функции f^* получается из столбца функции f переписыванием последнего в обратном порядке, одновременно инвертируя двоичные цифры. Очевидно, что (f^*)^*= f. Если функция f= f^*, то она называется самодвойственной функцией. Рассмотрим функции, двойственные к элементарным: (xy)*=xy, 0*=1,1*=0, (xy)*=xy, (x/y)*=xy.

Теорема1: если функция f зависит от переменной xi фиктивно, то и двойственная к функции f зависит от xi фиктивно. Пусть R – система БФ, которые используются для реализации функции f и будем говорить, что f реализована над системой R.

Теорема2(1-й принцип двойственности): если функция f реализована над системой R, то заменой каждого символа операции в f на двойственный получится формула, которая реализует двойственную функцию f*. Заметим, что порядок выполнения действий при замене операций на двойственные сохраняется, поэтому в нужных местах проставление скобок обязательно.

Теорема3: если функция f, то и f **.

28. Алгебра Жегалкина. Основные свойства операций алгебры Жегалкина.

  Определение. Алгеброй Жегалкина называется алгебра над множеством логических функций и переменных, сигнатура которой содержит две бинарные операции   &   и    , и две нульарные операции – константы 0 и 1.

            В алгебре Жегалкина выполняются следующие соотношения:

1.   x   y = y   x;

2.   x ( y   z )  =  x y   x z;

3.   x   x = 0; 

                                                                                                          (1.4)

4.   x     = 1; 

5.   x   0 = x.

            Эти соотношения легко проверить табличным способом. Кроме перечисленных соотношений в алгебре Жегалкина выполняются соотношения булевой алгебры относительно конъюнкции и констант

29. Алгебра Жегалкина. Представление логических функций полиномом Жегалкина.

Полином Жегалкина — полином(многочлен) над  , то есть полином с коэффициентами вида 0 и 1, где в качестве произведения берется конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве удобного средства для представления функций булевой логики.

Полином Жегалкина представляет собой сумму по модулю два (операция Исключающее ИЛИ) произведений неинвертированных переменных, а также (если необходимо) константы 1. Формально полином Жегалкина можно представить в виде

или в более формализованном виде как

Примеры полиномов Жегалкина:

30. Разложение логической функции по переменным. Понятие совершенной дизъюнктивной нормальной формы логической функции. Понятие совершенной конъюнктивной нормальной формы логической функции.

Теорема 4.2. (о разложении функций по переменным). Каждую функцию алгебры логики f(x₁,…,x_n) при любом m,1 m n, можно представить в следующей форме: ,           (4.1)

где дизъюнкция берется по всем возможным наборам значений переменных x₁,…,x_m.      Это представление называется разложением функции по m переменным x₁,…,x_m.

СДНФ (Совершенная Дизъюнктивная Нормальная Форма) — это такая ДНФ, которая удовлетворяет трём условиям:

• в ней нет одинаковых элементарных конъюнкций

• в каждой конъюнкции нет одинаковых пропозициональных букв

• каждая элементарная конъюнкция содержит каждую пропозициональную букву из входящих в данную ДНФ пропозициональных букв, причем в одинаковом порядке.

Для любой функции алгебры логики существует своя СДНФ, причем единственная.

СКНФ (Совершенная Конъюнктивная Нормальная Форма) — это такая КНФ, которая удовлетворяет трём условиям:

• в ней нет одинаковых элементарных дизъюнкций

• в каждой дизъюнкции нет одинаковых пропозициональных букв

• каждая элементарная дизъюнкция содержит каждую пропозициональную букву из входящих в данную КНФ пропозициональных букв.