Введение в схемы, автоматы и алгоритмы

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

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

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

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

$Булевы функции от 1-ой и 2-х переменных$
- константа 0;
$Булевы функции от 1-ой и 2-х переменных$
- константа 1;
$Булевы функции от 1-ой и 2-х переменных$
- тождественная функция;
$Булевы функции от 1-ой и 2-х переменных$
Эта функция называется отрицанием
$Булевы функции от 1-ой и 2-х переменных$

и обозначается
$Булевы функции от 1-ой и 2-х переменных$
(используется также обозначение
$Булевы функции от 1-ой и 2-х переменных$
, а в языках программирования эта функция часто обозначается как
$Булевы функции от 1-ой и 2-х переменных$
).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

0 0

0 1

1 0

1 1

0

0

0

0

1

1

1

1

0

0

1

1

1

1

0

0

0

1

0

1

1

0

1

0

0

0

0

1

0

1

1

1

1

1

0

1

0

1

1

0

1

0

0

1

1

1

1

0

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

$Булевы функции от 1-ой и 2-х переменных$
- константа 0;
$Булевы функции от 1-ой и 2-х переменных$
- константа 1;
$Булевы функции от 1-ой и 2-х переменных$
- функция, равная 1-му аргументу;
$Булевы функции от 1-ой и 2-х переменных$
- отрицание
$Булевы функции от 1-ой и 2-х переменных$
;
$Булевы функции от 1-ой и 2-х переменных$
- функция, равная 2-му аргументу;
$Булевы функции от 1-ой и 2-х переменных$
- отрицание
$Булевы функции от 1-ой и 2-х переменных$
;
$Булевы функции от 1-ой и 2-х переменных$
- конъюнкция, читается "
$Булевы функции от 1-ой и 2-х переменных$
и
$Булевы функции от 1-ой и 2-х переменных$
" (используются также обозначения
$Булевы функции от 1-ой и 2-х переменных$
,
$Булевы функции от 1-ой и 2-х переменных$
,
$Булевы функции от 1-ой и 2-х переменных$
и
$Булевы функции от 1-ой и 2-х переменных$
AND
$Булевы функции от 1-ой и 2-х переменных$
));
$Булевы функции от 1-ой и 2-х переменных$
- дизъюнкция, читается "
$Булевы функции от 1-ой и 2-х переменных$
или
$Булевы функции от 1-ой и 2-х переменных$
" (используются также обозначения
$Булевы функции от 1-ой и 2-х переменных$
,
$Булевы функции от 1-ой и 2-х переменных$
и
$Булевы функции от 1-ой и 2-х переменных$
OR
$Булевы функции от 1-ой и 2-х переменных$
));
$Булевы функции от 1-ой и 2-х переменных$
- импликация, читается "
$Булевы функции от 1-ой и 2-х переменных$
влечет
$Булевы функции от 1-ой и 2-х переменных$
" или "из
$Булевы функции от 1-ой и 2-х переменных$
следует
$Булевы функции от 1-ой и 2-х переменных$
" (используются также обозначения
$Булевы функции от 1-ой и 2-х переменных$
, и ( IF
$Булевы функции от 1-ой и 2-х переменных$
THEN
$Булевы функции от 1-ой и 2-х переменных$
));
$Булевы функции от 1-ой и 2-х переменных$
- сложение по модулю 2, читается "
$Булевы функции от 1-ой и 2-х переменных$
плюс
$Булевы функции от 1-ой и 2-х переменных$
" (используется также обозначение
$Булевы функции от 1-ой и 2-х переменных$
);
$Булевы функции от 1-ой и 2-х переменных$
- эквивалентность, читается "
$Булевы функции от 1-ой и 2-х переменных$
эквивалентно (равносильно)
$Булевы функции от 1-ой и 2-х переменных$
" (используется также обозначение
$Булевы функции от 1-ой и 2-х переменных$
);
$Булевы функции от 1-ой и 2-х переменных$
- штрих Шеффера (антиконъюнкция), иногда читается как "не
$Булевы функции от 1-ой и 2-х переменных$
и
$Булевы функции от 1-ой и 2-х переменных$
".

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

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

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

и

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

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

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

и

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

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

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

, а функции

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

и

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

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

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

Функции

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

и

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание раздела