Представление функции формулой, полные системы функций

Представление функции формулой

Определение:

Булева функция от [math]n[/math] переменных — отображение [math]B_n[/math] → [math]B[/math], где [math]B = \{0, 1\}[/math] — булево множество.

Определение:

Если выбрать некоторый набор булевых функций [math]A[/math], то с использованием выбранных функций можно записать некоторые другие булевы функции. Такая запись булевой функции называется формулой.

Например, если [math]A = \left\{\land,\neg\right\}[/math], то функция [math]a \lor b[/math] представляется в виде [math]\neg(\neg a \land \neg b)[/math]

Полные системы функций

Определение:

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

Определение:

Замыканием множества функций называется минимальное замкнутое подмножество всех функций, содержащее данное множество функций.

Определение:

Множество [math]A[/math] функций алгебры логики называется полной системой, если замыкание этого множества совпадает с множеством всех функций.

Критерий Поста формулирует необходимое и достаточное условие полноты системы булевых функций:

Система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов [math]T_0[/math], [math]T_1[/math], [math]S[/math], [math]M[/math], [math]L[/math].

В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать штрих Шеффера.

Широко известны такие полные системы булевых функций:

• [math]\left\{\land,\lor,\neg\right\}[/math] (конъюнкция, дизъюнкция, отрицание);
• [math]\left\{\land,\oplus,1\right\}[/math] (конъюнкция, сложение по модулю 2, константа 1).

Первая система используется, например, для представления функций в виде дизъюнктивных и конъюнктивных нормальных форм, вторая — для представления в виде полиномов Жегалкина.

Определение:

Полная система функций называется безызбыточной, если она перестаёт быть полной при исключении из неё любого элемента.

Первая из упоминавшихся выше полных систем безызбыточной не является, поскольку согласно законам де Моргана либо дизъюнкцию, либо конъюнкцию можно исключить из системы и восстановить с помощью остальных двух функций. Вторая система является безызбыточной — все три её элемента необходимы для полноты. Максимально возможное число булевых функций в базисе — 4.

Иногда говорят о системе функций, полной в некотором замкнутом классе, и соответственно о базисе этого класса. Например, систему [math]\left\{\oplus,1\right\}[/math] можно назвать базисом класса линейных функций.

Источники

http://ru.wikipedia.org