Базисы функций алгебры логики

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

А) - называемый избыточным базисом.

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

Если набор функций (А) базисный, то (по закону де-Моргана) базисными являются также наборы (Б) и (В) |

Б) , т.к.

В) , т.к.

Если набор функций (Б) базисный, то базисным является также набор (Г)

Г) , т.к.

Если набор функций (В) базисный, то базисным является также набор (Д)

Д) , т.к.

Если набор функций (Г) базисный, то базисным является также набор (Е)

Е) |, т.к.

Если набор функций (Д) базисный, то базисным является также набор (Ж)

Ж) , т.к.

Пример 4

. Построить представление функции импликации во всевозможных базисах.

В избыточном базисе (А) в виде СДНФ, либо в виде СКНФ.

Для получения функции в базисе (Б) надо избавиться от операций дизъюнкции. Приэтом естественно исходить из представления, где употребление этой операции ниже, т.е. использовать СДНФ функции).

Для получения функции в базисе (В) надо избавиться от операций конъюнкции,. используяь СКНФ).

Исходя из вида функции в базисе (Б), получим ее вид в базисах (Г) и (Е)

А исходя из вида функции в базисе (В), получим ее вид в базисах (Д) и (Ж) |

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

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

Алгоритм построения полинома Жегалкина

Для произвольной логической функции от n - переменных:

1. записать в общем виде полином Жегалкина с неопределенными коэффициентами;

Например, для функции 2-х переменных общий вид полинома

2. решить систему.из линейных уравнений относительно неизвестных коэффициентов, образуемую путем подстановки значений функции на наборах таблицы истинности;

1. полученные значения коэффициентов подставить в полином.

Пример 5. Построить полином Жегалкина для функции из примера 1.

Общий вид полинома от 3-х переменных

Таким образом ПЖ

Заметим, что возможность представления любой функции в виде полинома Жегалкина указывает на базисность набора функций - «базис Жегалкина».