Изменения

'''Замкнутым множествомфункций''' функций называется такое множество, что любая [[Определение булевой функции|булева функция алгебры логики]], [[Суперпозиции|выражаемая ]] с помощью содержащихся в множестве функций, уже содержится в этом множестве.}}

'''Замыканием''' множества функций называется минимальное замкнутое такое подмножество всех булевых функций, содержащее данное множество что любую из этих функцийможно выразить через функции исходного множества.}}

Множество <tex>A</tex> булевых функций алгебры логики называется '''полной системой''', если замыкание этого множества совпадает с множеством всех функций.}}

Полная система функций называется '''безызбыточной''', если она перестаёт перестает быть полной при исключении из неё любого элемента.

|definition=Говорят, что функция '''сохраняет константу 0''', если <tex>f(0, 0, \dots, 0) = 0</tex>.

|definition=Говорят, что функция '''сохраняет константу 1''', если <tex>f(1, 1, \dots, 1) = 1</tex>.

Очевидно, что количество Количество линейных функций от <tex>n</tex> переменных равно <tex>~2^{n+1}</tex>. Функция является линейной тогда, и только тогда, когда в ее полиноме [[Полином_Жегалкина|Жегалкина]] присутствуют слагаемые, каждое из которых зависит не более чем от одной переменной. Построить полином Жегалкина можно с помощью [[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина|преобразования Мебиуса]].

== Критерий Поста ==Критерий Поста — одна из центральных теорем в теории булевых функцийФункция является линейной тогда, устанавливающая необходимое и достаточное условие для тоготолько тогда, чтобы некоторый набор булевых функций обладал достаточной выразительностьюкогда в ее [[Полином_Жегалкина|полиноме Жегалкина]] присутствуют слагаемые, чтобы представить любую булеву функциюкаждое из которых зависит не более чем от одной переменной. Впервые сформулирован американским математиком Эмилем Постом в 1941гПостроить полином Жегалкина можно с помощью [[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина|преобразования Мебиуса]].

== Формулировка и доказательство критерия Поста ==

Система Набор булевых функций F K является полной полным тогда и только тогда, когда она он не содержится полностью ни в одном из классов <tex> S,M,L,T_0,T_1 </tex>, т.е. когда в ней нем имеется хотя бы одна функция, не сохраняющая 0, хотя бы одна функция, не сохраняющая 1, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.

Рассмотрим функцию, несохраняющую не сохраняющую 0 {{---}} <tex>f_0</tex>. <tex>f_0(0) = 1</tex>. <tex>f_0(1)</tex> может принимать два значения:

Рассмотрим функцию, несохраняющую не сохраняющую 1 {{---}} <tex>f_1</tex>. <tex>f_1(1) = 0</tex>. <tex>f_1(0)</tex> может принимать два значения:

1) Мы получили функцию '''НЕ'''. Используем несамодвойственную функцию <tex>f_s</tex>.

2)Мы получили '''НЕ''' и <tex>0</tex>. <tex>\lnot 0 = 1</tex>.

3)Мы получили '''НЕ''' и <tex>1</tex>. <tex>\lnot 1 = 0</tex>.

В итоге имеем три функции: '''НЕ''', <tex>0</tex>, <tex>1</tex>.

Используем нелинейную функцию <tex>f_l</tex>. Среди нелинейных членов <tex>f_l</tex>, выберем тот, в котором минимальное количество элементов, все элементы, кроме двух, в этом члене, сделаем равными 1, оставшиеся 2 назовем <tex>x_1</tex> и <tex>x_2</tex>, а все элементы, не входящие в данный член, сделаем равными 0'''.''' Тогда <tex>f_l g_l = x_1 \land x_2 [ \oplus x_1] [\oplus x_2][ \oplus ~1]</tex>, где в квадратных скобках указаны члены, которые могут и не присутствовать.

# Присутствует член <tex>\oplus ~1</tex>. Возьмем отрицание от <tex>f_lg_l</tex> и член <tex>\oplus ~1</tex> уберется.# Присутствуют 3 члена, без <tex>\oplus ~1</tex>: <tex>f_l g_l= x_1 \land x_2 \oplus x_1 \oplus x_2</tex>. Составив таблицу истинности для этой функции, нетрудно заметить, что она эквивалентна функции '''ИЛИ'''.# Присутствуют 2 члена, без <tex>\oplus ~1</tex>. Построив две таблицы истинности, для двух различных вариантов, видим, что в обоих случаях функция истинна только в одной точке, следовательно, СДНФ будет состоять только из одного члена, а если это так, то не составляет труда выразить '''И''', через '''НЕ''' и <tex>f_lg_l</tex>. # Присутствует 1 член. Выразим '''И''', через '''НЕ''' и <tex>f_lg_l</tex>.

В итоге получаем функцию '''НЕ''', а также либо функцию '''И''', либо функцию '''ИЛИ'''. Поскольку функцию '''И''' можно выразить через '''ИЛИ''' и '''НЕ''', а функцию '''ИЛИ''' через '''И''' и '''НЕ''', то мы получили базис '''И, ИЛИ, НЕ'''. Любую булеву функцию, не равную тождественному нулю, можно представить в форме [[СДНФ]], т. е. с помощью данного базиса. Если же функция равна тождественному нулю, то ее можно представить в виде <tex>x \land \overline{x}</tex>. Значит, полученные функции образуют полную систему, т. к. с их помощью можно выразить любую булеву функцию. Из этого следует, что '''F''' K {{---}} полная система функций, что и требовалось доказать.

В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать [[Определение_булевой_функции|штрих Шеффера ]] или [[Определение_булевой_функции|стрелку Пирса]].