Представление функции формулой, полные системы функций
Представление функции формулой
| Определение: |
| Булева функция от переменных — отображение → , где — булево множество. |
| Определение: |
| Если выбрать некоторый набор булевых функций , то с использованием выбранных функций можно записать некоторые другие булевы функции. Такая запись булевой функции называется формулой. |
Например, если , то функция представляется в виде
Полные системы функций
| Определение: |
| Замкнутым множеством функций называется такое множество, что любая функция алгебры логики, выражаемая с помощью содержащихся в множестве функций, уже содержится в этом множестве. |
| Определение: |
| Замыканием множества функций называется минимальное замкнутое подмножество всех функций, содержащее данное множество функций. |
| Определение: |
| Множество функций алгебры логики называется полной системой, если замыкание этого множества совпадает с множеством всех функций. |
Критерий Поста формулирует необходимое и достаточное условие полноты системы булевых функций:
Система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов , , , , .
В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать штрих Шеффера.
Широко известны такие полные системы булевых функций:
- (конъюнкция, дизъюнкция, отрицание);
- (конъюнкция, сложение по модулю 2, константа 1).
Первая система используется, например, для представления функций в виде дизъюнктивных и конъюнктивных нормальных форм, вторая — для представления в виде полиномов Жегалкина.
| Определение: |
| Полная система функций называется безызбыточной, если она перестаёт быть полной при исключении из неё любого элемента. |
Первая из упоминавшихся выше полных систем безызбыточной не является, поскольку согласно законам де Моргана либо дизъюнкцию, либо конъюнкцию можно исключить из системы и восстановить с помощью остальных двух функций. Вторая система является безызбыточной — все три её элемента необходимы для полноты. Максимально возможное число булевых функций в базисе — 4.
Иногда говорят о системе функций, полной в некотором замкнутом классе, и соответственно о базисе этого класса. Например, систему можно назвать базисом класса линейных функций.
