Изменения

Система булевых функций называется ''полной'', если можно построить их [[Суперпозиции|суперпозицию]], тождественную любой другой заранее заданной функции. Говорят ещё, что замыкание данной системы совпадает с множеством <math>P_2</math>.

Критерий Поста — одна из центральных теорем в теории [[Определение булевой функции|булевых функций]], устанавливающая необходимое и достаточное условие для того, чтобы некоторый набор булевых функций обладал достаточной выразительностью, чтобы представить любую булеву функцию. Впервые сформулирован американским математиком Эмилем Постомв 1941г. == Замкнутые классы булевых функций ==* Класс функций <tex>T_0</tex>, сохраняющих константу 0:  <tex>f(0, 0, \dots, 0) = 0</tex> Функция сохраняет 0 тогда, и только тогда, когда первое значение в ее таблице истинности равно 0. * Класс функций <tex>T_1</tex>, сохраняющих константу 1:  <tex>f(1, 1, \dots, 1) = 1</tex> Функция сохраняет 1 тогда, и только тогда, когда последнее значение в ее таблице истинности равно 1. * Класс самодвойственных функций <tex>S</tex>: <tex>f(\overline{x_1},\dots,\overline{x_n})=\overline{f(x_1,\dots,x_n)}</tex> Пусть <tex>a(i)</tex> — i-я строка таблицы истинности <tex>f(i)</tex>. В таких обозначениях функция <tex>f(i)</tex> является самодвойственной тогда, и только тогда, когда <tex>a(i)=\overline{a(N+1-i)}</tex>, где <tex>N — </tex> количество строк в таблице истинности. Т. е. функция является самодвойственной, если значения, расположенные в таблице истинности симметрично относительно центра, не равны. * Класс монотонных функций <tex>M</tex>: <tex>\forall i (a_i\le b_i) \Rightarrow f(a_1,\dots,a_n)\le f(b_1,\dots,b_n)</tex> Функция является монотонной тогда, и только тогда, когда для любых параметров функции, изменение некоторых из них с <tex>0</tex> на <tex>1</tex> не приводит к уменьшению ее значения. Примером монотонной функции от двух переменных является <tex>and</tex>. Примером немонотонной булевой функции от двух переменных является <tex>xor</tex>, т. к. для значений <tex>(0, 1)</tex> функция принимает значение <tex>1</tex>, а при изменении первого параметра на <tex>1</tex> функция уменьшает свое значение. * Класс линейных функций <tex>L</tex>: <tex>f(x_1,\dots,x_n)=a_0\oplus a_1x_1\oplus\dots\oplus a_nx_n,a_i\in\{0,1\}</tex> Очевидно, что количество линейных функций от <tex>n</tex> переменных всего <tex>~2^{n+1}</tex>. Функция является линейной тогда, и только тогда, когда в ее полиноме [[Полином_Жегалкина|Жегалкина]] присутствуют слагаемые, каждое из которых зависит не более чем от одной переменной. Построить полином Жегалкина можно с помощью [[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина|преобразования Мебиуса]].

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

* [http://ru.wikipedia.org/wiki/Заглавная_страница %D0%9A%D1%80%D0%B8%D1%82%D0%B5%D1%80%D0%B8%D0%B9_%D0%9F%D0%BE%D1%81%D1%82%D0%B0 Википедия — свободная энциклопедияКритерий Поста]* [http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%BC%D0%BA%D0%BD%D1%83%D1%82%D1%8B%D0%B5_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D1%8B_%D0%B1%D1%83%D0%BB%D0%B5%D0%B2%D1%8B%D1%85_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B9 Википедия — Замкнутые классы булевых функций]