17
правок
Изменения
→Основные сведения
|3-ИЛИ, максимум
|}
== Полные системы булевых функций ==
=== Тождественность и двойственность ===
Две булевы функции тождественны друг другу, если на любых одинаковых наборах аргументов они принимают равные значения. Тождественность функций f и g можно записать, например, так:<br />
<math>f(x_1, x_2, \dots, x_n)=g(x_1, x_2, \dots, x_n)</math>
Просмотрев таблицы истинности булевых функций, легко получить такие тождества:
{| style="width:15cm"
|-
| <math>\overline{0}=1</math> || <math>\overline{1}=0</math> || <math>\overline{\overline{x}}=x</math>
|| <math>xy=yx\!</math> || <math>x\lor y=y \lor x</math>
|-
|| <math>0x=0\!</math> || <math>1x=x\!</math> || <math>0\lor x=x</math> || <math>1\lor x=1</math> || <math>xx=x\lor x=x</math>
|}
А проверка таблиц, построенных для некоторых суперпозиций, даст следующие результаты:
{| style="width:15cm"
|-
| <math>x\overline{x}=0</math> || <math>x\lor\overline{x}=1</math>
|}
{| style="width:15cm"
|-
| <math>\overline{x\cdot y}=\overline{x}\lor\overline{y}</math>
|| <math>\overline{x}\cdot\overline{y}=\overline{x\lor y}</math> || (законы де Моргана)
|}
<math>x(y\lor z)=xy\lor xz</math><br />
<math>x\lor yz=(x\lor y)(x\lor z)</math> (дистрибутивность конъюнкции и дизъюнкции)
Функция <math>g(x_1,x_2,\dots,x_n)</math> называется двойственной функции <math>f(x_1,x_2,\dots,x_n)</math>, если <math>f(\overline{x_1},\overline{x_2},\dots,\overline{x_n})=\overline{g(x_1,x_2,\dots,x_n)}</math>. Легко показать, что в этом равенстве f и g можно поменять местами, то есть функции f и g двойственны друг другу. Из простейших функций двойственны друг другу константы 0 и 1, а из законов де Моргана следует двойственность конъюнкции и дизъюнкции. Тождественная функция, как и функция отрицания, двойственна сама себе.
Если в булевом тождестве заменить каждую функцию на двойственную ей, снова получится верное тождество. В приведённых выше формулах легко найти двойственные друг другу пары.
=== Полнота системы, критерий Поста ===
Система булевых функций называется ''полной'', если можно построить их суперпозицию, тождественную любой другой заранее заданной функции. Говорят ещё, что замыкание данной системы совпадает с множеством <math>P_2</math>.
Американский математик Эмиль Пост ввёл в рассмотрение следующие замкнутые классы булевых функций:
* Функции, сохраняющие константу <math>T_0</math> и <math>T_1</math>;
* Самодвойственные функции <math>S</math>;
* Монотонные функции <math>M</math>;
* Линейные функции <math>L</math>.
Им было доказано, что любой замкнутый класс булевых функций, не совпадающий с <math>P_2</math>, целиком содержится в одном из этих пяти так называемых ''предполных классов'', но при этом ни один из пяти не содержится целиком в объединении четырёх других. Таким образом критерий Поста для полноты системы сводится к выяснению, не содержится ли вся эта система целиком в одном из предполных классов. Если для каждого класса в системе найдётся функция, не входящая в него, то такая система будет полной, и с помощью входящих в неё функций можно будет получить любую другую булеву функцию.
Заметим, что существуют функции, не входящие ни в один из классов Поста. Любая такая функция сама по себе образует полную систему. В качестве примеров можно назвать штрих Шеффера или стрелку Пирса.
