78
правок
Изменения
→Полные системы функций
== Представление функции формулой ==
{{Определение
|definition=
Если выбрать некоторый набор [[Определение булевой функции|булевых функций]] <tex>A</tex>, то с использованием выбранных функций можно записать некоторые другие булевы функции. Такая запись булевой функции называется '''формулой'''.}}
Например, если <tex>A = \left\{\land,\neg\right\}</tex>, то функция <tex>a \lor b</tex> представляется в виде <tex>\neg(\neg a \land \neg b)</tex>
== Полные системы функций ==
{{Определение
|definition=
{{Определение
|definition=
'''Замыканием''' множества функций называется минимальное замкнутое подмножество всех функций, содержащее данное множество функций.}}
{{Определение
|id=def1
|definition=
Множество <tex>A</tex> функций алгебры логики называется '''Замкнутым множествомполной системой''' функций называется такое множество, что любая функция алгебры логики, выражаемая если замыкание этого множества совпадает с помощью содержащихся в множестве множеством всех функций, уже содержится в этом множестве.}}[[Теорема Поста о полной системе функций|Критерий Поста]] формулирует необходимое и достаточное условие полноты системы булевых функций:<br/> '''Система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов <tex>T_0</tex>, <tex>T_1</tex>, <tex>S</tex>, <tex>M</tex>, <tex>L</tex>.'''<br />
В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать штрих Шеффера.
* <tex>\left\{\land,\oplus,1\right\}</tex> (конъюнкция, сложение по модулю 2, константа 1).
Первая система используется, например, для представления функций в виде [[СДНФ|дизъюнктивных]] и [[СКНФ|конъюнктивных нормальных форм]], вторая — для представления в виде [[полином Жегалкина|полиномов Жегалкина]].
{{Определение
|definition=
Полная система функций называется '''базисомбезызбыточной''', если она перестаёт быть полной при исключении из неё любого элемента.
}}
Первая из упоминавшихся выше полных систем базисом безызбыточной не является, поскольку согласно законам де Моргана либо дизъюнкцию, либо конъюнкцию можно исключить из системы и восстановить с помощью остальных двух функций. Вторая система является базисом безызбыточной — все три её элемента необходимы для полноты.
Максимально возможное число булевых функций в базисе — 4.
Иногда говорят о системе функций, полной в некотором замкнутом классе, и соответственно о базисе этого класса. Например, систему <tex>\left\{\oplus,1\right\}</tex> можно назвать базисом класса линейных функций.
== Представление функции формулой Источники==Если задана какая-либо полная система функций <math>A<http:/math>, то '''любую''' функцию можно выразить, составив формулу, содержащую только функции из множества <tex>A</tex>ru. Например, если <tex>A = \left\{\land,\neg\right\}</tex>, то функция <tex>a \lor b</tex> представляется в виде <tex>\neg(\neg a \land \neg b)</tex>wikipedia.org
