61
правка
Изменения
Нет описания правки
|}
А проверка таблиц, построенных для некоторых суперпозиций, даст следующие результаты:
{| style="width:15cm9cm"
|-
| <tex>x \land \overline{x}=0</tex> || <tex>x \lor \overline{x}=1</tex>
|}
{| style="width:15cm"
|-
| <tex>\overline{x \land y}=\overline{x}\lor\overline{y}</tex>
|| <tex>\overline{x}\land\overline{y}=\overline{x\lor y}</tex> || (законы де Моргана)
|}
<tex>x \land (y\lor z)=(x \land y)\lor (x \land z)</tex><br />
{{main|Теорема Поста о полной системе функций}}
{{Определение
|definition=
Множество булевых функций называется '''полной системой''' (англ. ''complete set''), если замыкание этого множества совпадает с множеством всех функций.
}}
Американский математик Эмиль Пост <ref> [https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D1%81%D1%82,_%D0%AD%D0%BC%D0%B8%D0%BB%D1%8C_%D0%9B%D0%B5%D0%BE%D0%BD Эмиль Пост]</ref> сформулировал необходимое и достаточное условие полноты системы булевых функций. Для этого он ввел в рассмотрение следующие замкнутые классы булевых функций:
* функции, сохраняющие константу <Tex>T_0</Tex> и <Tex>T_1</Tex>,
Полином Жегалкина имеет следующий вид:
<tex>P = a_{000\ldots000} \oplus a_{100\ldots0} x_1 \oplus a_{010\ldots0} x_2 \oplus \ldots \oplus a_{00\ldots01} x_n \oplus a_{110\ldots0} x_1 x_2 \oplus \ldots \oplus a_{00\ldots011} x_{n-1} x_n \oplus \ldots \oplus a_{11..1\ldots1} x_1 x_2 \ldots x_n </tex>
С помощью полинома Жегалкина можно выразить любую булеву функцию, так как он строится из следующего набора функций: <tex>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</tex>, который, в свою очередь, по [[Теорема Поста о полной системе функций|теореме Поста]] является полным.
