81
правка
Изменения
объединен с конспектом "полные системы функций"
== Представление функции формулой == {{Определение|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> функций алгебры логики называется '''полной системой''', если замыкание этого множества совпадает с множеством всех функций.}} {{Определение|definition=Полная система функций ==называется '''безызбыточной''', если она перестаёт быть полной при исключении из неё любого элемента.}} Американский математик Эмиль Пост сформулировал необходимое и достаточное условие [[Представление функции формулой, полные системы функций|полноты системы булевых функций]]. Для этого он ввёл ввел в рассмотрение следующие замкнутые классы булевых функций:
* Функции, сохраняющие константу <math>T_0</math> и <math>T_1</math>;
* Самодвойственные функции <math>S</math>;
В итоге получаем функцию '''НЕ''', а также либо функцию '''И''', либо функцию '''ИЛИ''', но '''НЕ''' образует базис и с той и с другой функциями. Из того, что через функции '''F''' можно выразить базис, следует, что '''F''' {{---}} полная система функций, что и требовалось доказать.
}}
== Примеры ==
Согласно критерию Поста система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов <tex>T_0</tex>, <tex>T_1</tex>, <tex>S</tex>, <tex>M</tex>, <tex>L</tex>.
В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать штрих Шеффера или стрелку Пирса.
Широко известны такие полные системы булевых функций:
* <tex>\left\{\land,\lor,\neg\right\}</tex> (конъюнкция, дизъюнкция, отрицание);
* <tex>\left\{\land,\oplus,1\right\}</tex> (конъюнкция, сложение по модулю 2, константа 1).
Первая система используется, например, для представления функций в виде [[СДНФ|дизъюнктивных]] и [[СКНФ|конъюнктивных нормальных форм]], вторая — для представления в виде [[полином Жегалкина|полиномов Жегалкина]].
Первая из упоминавшихся выше полных систем безызбыточной не является, поскольку согласно законам де Моргана либо дизъюнкцию, либо конъюнкцию можно исключить из системы и восстановить с помощью остальных двух функций. Вторая система является безызбыточной — все три её элемента необходимы для полноты.
Максимально возможное число булевых функций в базисе — 4.
Иногда говорят о системе функций, полной в некотором замкнутом классе, и соответственно о базисе этого класса. Например, систему <tex>\left\{\oplus,1\right\}</tex> можно назвать базисом класса линейных функций.
== Источники ==
