Представление функции формулой, полные системы функций — различия между версиями
Melnik (обсуждение | вклад) |
Melnik (обсуждение | вклад) (→Полные системы функций) |
||
| Строка 14: | Строка 14: | ||
'''Замыканием''' множества функций называется минимальное замкнутое подмножество всех функций, содержащее данное множество функций.}} | '''Замыканием''' множества функций называется минимальное замкнутое подмножество всех функций, содержащее данное множество функций.}} | ||
{{Определение | {{Определение | ||
| + | |id=def1 | ||
|definition= | |definition= | ||
Множество <tex>A</tex> функций алгебры логики называется '''полной системой''', если замыкание этого множества совпадает с множеством всех функций.}} | Множество <tex>A</tex> функций алгебры логики называется '''полной системой''', если замыкание этого множества совпадает с множеством всех функций.}} | ||
Версия 03:27, 18 октября 2011
Представление функции формулой
| Определение: |
| Если выбрать некоторый набор булевых функций , то с использованием выбранных функций можно записать некоторые другие булевы функции. Такая запись булевой функции называется формулой. |
Например, если , то функция представляется в виде
Полные системы функций
| Определение: |
| Замкнутым множеством функций называется такое множество, что любая функция алгебры логики, выражаемая с помощью содержащихся в множестве функций, уже содержится в этом множестве. |
| Определение: |
| Замыканием множества функций называется минимальное замкнутое подмножество всех функций, содержащее данное множество функций. |
| Определение: |
| Множество функций алгебры логики называется полной системой, если замыкание этого множества совпадает с множеством всех функций. |
Критерий Поста формулирует необходимое и достаточное условие полноты системы булевых функций:
Система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов , , , , .
В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать штрих Шеффера.
Широко известны такие полные системы булевых функций:
- (конъюнкция, дизъюнкция, отрицание);
- (конъюнкция, сложение по модулю 2, константа 1).
Первая система используется, например, для представления функций в виде дизъюнктивных и конъюнктивных нормальных форм, вторая — для представления в виде полиномов Жегалкина.
| Определение: |
| Полная система функций называется безызбыточной, если она перестаёт быть полной при исключении из неё любого элемента. |
Первая из упоминавшихся выше полных систем безызбыточной не является, поскольку согласно законам де Моргана либо дизъюнкцию, либо конъюнкцию можно исключить из системы и восстановить с помощью остальных двух функций. Вторая система является безызбыточной — все три её элемента необходимы для полноты. Максимально возможное число булевых функций в базисе — 4.
Иногда говорят о системе функций, полной в некотором замкнутом классе, и соответственно о базисе этого класса. Например, систему можно назвать базисом класса линейных функций.
