81
правка
Изменения
м
== Критерий Поста ==
Критерий Поста — одна из центральных теорем в теории булевых функций, устанавливающая необходимое и достаточное условие для того, чтобы некоторый набор булевых функций обладал достаточной выразительностью, чтобы представить любую булеву функцию. Впервые сформулирован американским математиком Эмилем Постом в 1941г.
исправлены мелкие ошибки
== Полная система функций ==
{{Определение|definition=Система [[Определение булевой функции|булевых функций]] называется '''полной''', если можно построить их [[Суперпозиции|суперпозицию]], тождественную любой другой заранее заданной функции. Говорят ещё, что замыкание данной системы совпадает с множеством <mathtex>P_2</mathtex>.}}
Американский математик Эмиль Пост ввёл в рассмотрение следующие замкнутые классы булевых функций:
* Функции, сохраняющие константу <math>T_0</math> и <math>T_1</math>;
Заметим, что существуют функции, не входящие ни в один из классов Поста. Любая такая функция сама по себе образует полную систему. В качестве примеров можно назвать штрих Шеффера или стрелку Пирса.
== Замкнутые классы булевых функций ==
Класс функций <tex>T_0</tex>.
{{Определение
|definition=Говорят, что функция '''сохраняет константу 0''', если <tex>f(0, 0, \dots, 0) = 0</tex>.
}}
Класс функций <tex>T_1</tex>.
{{Определение
|definition=Говорят, что функция '''сохраняет константу 1''', если <tex>f(1, 1, \dots, 1) = 1</tex>.
}}
Класс самодвойственных функций <tex>S</tex>.
{{Определение
|definition=Говорят, что функция '''самодвойственна''', если <tex>f(\overline{x_1},\dots,\overline{x_n})=\overline{f(x_1,\dots,x_n)}</tex>. Иными словами, функция называется самодвойственной, если на противоположных наборах она принимает противоположные значения.
}}
Класс монотонных функций <tex>M</tex>.
{{Определение
|definition=Говорят, что функция '''монотонна''', если <tex>\forall i (a_i\le b_i) \Rightarrow f(a_1,\dots,a_n)\le f(b_1,\dots,b_n)</tex>.
}}
Класс линейных функций <tex>L</tex>.
{{Определение
|definition=Говорят, что функция '''линейна''', если существуют такие <tex>a_0, a_1, a_2, \dots, a_n</tex>, где <tex>a_i \in \{0, 1\}, \forall i=\overline{1,n}</tex>, что для любых <tex>x_1, x_2, \dots, x_n</tex> имеет место равенство:
:<tex>f(x_1, x_2, \dots, x_n) = a_0\oplus a_1\cdot x_1\oplus a_2\cdot x_2 \oplus\dots\oplus a_n\cdot x_n</tex>.
}}
Функция является линейной тогда, и только тогда, когда в ее полиноме [[Полином_Жегалкина|Жегалкина]] присутствуют слагаемые, каждое из которых зависит не более чем от одной переменной. Построить полином Жегалкина можно с помощью [[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина|преобразования Мебиуса]].
== Критерий Поста ==
Критерий Поста — одна из центральных теорем в теории булевых функций, устанавливающая необходимое и достаточное условие для того, чтобы некоторый набор булевых функций обладал достаточной выразительностью, чтобы представить любую булеву функцию. Впервые сформулирован американским математиком Эмилем Постом в 1941г.
== Формулировка и доказательство критерия ==
== Примеры полных систем булевых функций от двух переменных ==
Широко известна [[Представление функции формулой, полные системы функций|полная система функций]] <tex>\left\{\land,\lor,\neg\right\}</tex>. Однако, эта система функций не является безызбыточной, т. к. функцию <tex>\land</tex> можно выразить через <tex>\lor</tex> и <tex>\neg</tex>. Система функций <tex>\left\{\lor,\neg\right\}</tex> безызбыточнаяполная, т. к. функция <tex>\lor</tex> является несамодвойственной и нелинейной, а функция <tex>\neg</tex> не сохраняет 0, не сохраняет 1 и немонотонна. Система функций <tex>\left\{\land,\neg\right\}</tex> также является полной, т. к. функция <tex>\land</tex> является несамодвойственной и нелинейной, а функция <tex>\neg</tex> не сохраняет 0, не сохраняет 1 и немонотонна. Система функций <tex>\left\{\land,\lor,\neg\right\}</tex> используется для представления функций в [[СДНФ|СДНФ]] и [[СКНФ|СКНФ]].
Также существуют полные системы функций, состоящие только из одной функции. Это штрих Шеффера (<tex>\triangledown</tex> ) и стрелка Пирса(<tex>\downarrow</tex>).
