Булевы функции от 1-ой и 2-х переменных

Перечислим вначале все булевы функции от 1-ой переменной

$x_1$

. Как мы знаем, их всего четыре.

$f_1(x_1)= 0$
- константа 0;
$f_2(x_1)= 1$
- константа 1;
$f_3(x_1)= x_1$
- тождественная функция;
$f_4(0)=1, f_4(1)=0.$
Эта функция называется отрицанием
$x_1$

и обозначается
$\neg x_1$
(используется также обозначение
$\overline{x}_1$
, а в языках программирования эта функция часто обозначается как
$NOT x_1$
).

В следующей таблице представлены наиболее используемые 12 (из 16) функций от 2-х переменных.

Таблица 1.2. Булевы функции от 2-х переменных

$x_1$

$x_2$

$f_1$

$f_2$

$f_3$

$f_4$

$f_5$

$f_6$

$f_7$

$f_8$

$f_9$

$f_{10}$

$f_{11}$

$f_{12}$

0 0

0 1

1 0

1 1

Многие из этих функций часто считаются "элементарными" и имеют собственные обозначения.

$f_1(x_1,x_2)= 0$
- константа 0;
$f_2(x_1, x_2)= 1$
- константа 1;
$f_3(x_1,x_2)= x_1$
- функция, равная 1-му аргументу;
$f_4(x_1,x_2)= \neg x_1$
- отрицание
$x_1$
;
$f_5(x_1,x_2)= x_2$
- функция, равная 2-му аргументу;
$f_6(x_1,x_2)= \neg x_2$
- отрицание
$x_2$
;
$f_7(x_1,x_2)= (x_1 \wedge x_2)$
- конъюнкция, читается "
$x_1$
и
$x_2$
" (используются также обозначения
$(x_1 & x_2)$
,
$(x_1x_2)$
,
$\min(x_1,x_2)$
и
$(x_1$
AND
$x_2$
));
$f_8(x_1,x_2)= (x_1 \vee x_2)$
- дизъюнкция, читается "
$x_1$
или
$x_2$
" (используются также обозначения
$(x_1 + x_2)$
,
$\max(x_1x_2)$
и
$(x_1$
OR
$x_2$
));
$f_9(x_1,x_2)= (x_1 \rightarrow x_2)$
- импликация, читается "
$x_1$
влечет
$x_2$
" или "из
$x_1$
следует
$x_2$
" (используются также обозначения
$(x_1 \supset x_2)$
, и ( IF
$x_1$
THEN
$x_2$
));
$f_{10}(x_1,x_2)= (x_1 + x_2)$
- сложение по модулю 2, читается "
$x_1$
плюс
$x_2$
" (используется также обозначение
$(x_1 \oplus x_2)$
);
$f_{11}(x_1,x_2)= (x_1 \sim x_2)$
- эквивалентность, читается "
$x_1$
эквивалентно (равносильно)
$x_2$
" (используется также обозначение
$(x_1 \equiv x_2)$
);
$f_{12}(x_1,x_2)= (x_1 | x_2)$
- штрих Шеффера (антиконъюнкция), иногда читается как "не
$x_1$
и
$x_2$
".

В качестве элементарных функций будем также рассматривать 0-местные функции-константы 0 и 1.

Отметим, что функции

$f_1(x_1,x_2)$

$f_2(x_1,x_2)$

фактически не зависят от значений обоих аргументов, функции

$f_3(x_1,x_2)$

$f_4(x_1,x_2)$

не зависят от значений аргумента

$x_2$

, а функции

$f_5(x_1,x_2)$

$f_6(x_1,x_2)$

не зависят от значений аргумента

$x_1$

Определение 1.1. Функция

$f(x_1,\ldots, x_i,\ldots, x_n)$

не зависит от аргумента

$x_i$

, если для любого набора значений

$\sigma_1,\ldots,\sigma_{i-1},\sigma_{i+1},\ldots, \sigma_n$

остальных аргументов

$f$

имеет место равенство

$f(\sigma_1,\ldots,\sigma_{i-1},0,\sigma_{i+1},\ldots, \sigma_n)= f(\sigma_1,\ldots,\sigma_{i-1},1,\sigma_{i+1},\ldots, \sigma_n)$

. Такой аргумент

$x_i$

называется фиктивным. Аргументы, не являющиеся фиктивными, называются существенными.

Функции

$f_1(x_1,\ldots, x_n)$

$f_2(x_1,\ldots, x_m)$

называются равными, если функцию

$f_2$

можно получить из функции

$f_1$

путем добавления и удаления фиктивных аргументов.

Например, равными являются одноместная функция

$f_3(x_1)$

и двухместная функция

$f_3(x_1,x_2)$

, так как вторая получается из первой добавлением фиктивного аргумента

$x_2$

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

Содержание Назад Вперед