Представление функции формулой, полные системы функций — различия между версиями
Phil (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
| (не показаны 4 промежуточные версии 3 участников) | |||
| Строка 3: | Строка 3: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | + | Если выбрать некоторый набор [[Определение булевой функции|булевых функций]] <tex>A</tex>, то с использованием выбранных функций можно записать некоторые другие булевы функции. Такая запись булевой функции называется '''формулой'''.}} | |
| − | |||
| − | |||
| − | Если выбрать некоторый набор булевых функций <tex>A</tex>, то с использованием выбранных функций можно записать некоторые другие булевы функции. Такая запись булевой функции называется '''формулой'''.}} | ||
Например, если <tex>A = \left\{\land,\neg\right\}</tex>, то функция <tex>a \lor b</tex> представляется в виде <tex>\neg(\neg a \land \neg b)</tex> | Например, если <tex>A = \left\{\land,\neg\right\}</tex>, то функция <tex>a \lor b</tex> представляется в виде <tex>\neg(\neg a \land \neg b)</tex> | ||
| Строка 17: | Строка 14: | ||
'''Замыканием''' множества функций называется минимальное замкнутое подмножество всех функций, содержащее данное множество функций.}} | '''Замыканием''' множества функций называется минимальное замкнутое подмножество всех функций, содержащее данное множество функций.}} | ||
{{Определение | {{Определение | ||
| + | |id=def1 | ||
|definition= | |definition= | ||
Множество <tex>A</tex> функций алгебры логики называется '''полной системой''', если замыкание этого множества совпадает с множеством всех функций.}} | Множество <tex>A</tex> функций алгебры логики называется '''полной системой''', если замыкание этого множества совпадает с множеством всех функций.}} | ||
| − | [[Теорема Поста о полной системе функций|Критерий Поста]] формулирует необходимое и достаточное условие полноты системы булевых функций: | + | [[Теорема Поста о полной системе функций|Критерий Поста]] формулирует необходимое и достаточное условие полноты системы булевых функций: |
| − | '''Система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов <tex>T_0</tex>, <tex>T_1</tex>, <tex>S</tex>, <tex>M</tex>, <tex>L</tex>.''' | + | |
| + | '''Система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов <tex>T_0</tex>, <tex>T_1</tex>, <tex>S</tex>, <tex>M</tex>, <tex>L</tex>.''' | ||
| + | |||
В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать штрих Шеффера. | В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать штрих Шеффера. | ||
Текущая версия на 19:14, 4 сентября 2022
Представление функции формулой
| Определение: |
| Если выбрать некоторый набор булевых функций , то с использованием выбранных функций можно записать некоторые другие булевы функции. Такая запись булевой функции называется формулой. |
Например, если , то функция представляется в виде
Полные системы функций
| Определение: |
| Замкнутым множеством функций называется такое множество, что любая функция алгебры логики, выражаемая с помощью содержащихся в множестве функций, уже содержится в этом множестве. |
| Определение: |
| Замыканием множества функций называется минимальное замкнутое подмножество всех функций, содержащее данное множество функций. |
| Определение: |
| Множество функций алгебры логики называется полной системой, если замыкание этого множества совпадает с множеством всех функций. |
Критерий Поста формулирует необходимое и достаточное условие полноты системы булевых функций:
Система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов , , , , .
В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать штрих Шеффера.
Широко известны такие полные системы булевых функций:
- (конъюнкция, дизъюнкция, отрицание);
- (конъюнкция, сложение по модулю 2, константа 1).
Первая система используется, например, для представления функций в виде дизъюнктивных и конъюнктивных нормальных форм, вторая — для представления в виде полиномов Жегалкина.
| Определение: |
| Полная система функций называется безызбыточной, если она перестаёт быть полной при исключении из неё любого элемента. |
Первая из упоминавшихся выше полных систем безызбыточной не является, поскольку согласно законам де Моргана либо дизъюнкцию, либо конъюнкцию можно исключить из системы и восстановить с помощью остальных двух функций. Вторая система является безызбыточной — все три её элемента необходимы для полноты. Максимально возможное число булевых функций в базисе — 4.
Иногда говорят о системе функций, полной в некотором замкнутом классе, и соответственно о базисе этого класса. Например, систему можно назвать базисом класса линейных функций.
