Глава 4. Алгебра логических функций
4.1. Основные определения
Двоичное
(бинарное) множество
,
где логический символ 0 означает –
«ложь», логический символ 1 означает –
«истина».
Логической
функцией
называется операция типа
.
–
множество всех логических функций от
n
переменных.
–
множество всех логических функций.
Утверждение:
.
Единичным
набором
значений аргументов называется набор,
на котором функция равна 1. Множество
единичных наборов
функции
f
называется единичным
множеством
–
.
Нулевым
набором
значений аргументов называется набор,
на котором функция равна 0. Множество
нулевых наборов
функции
f
называется нулевым
множеством
–
.
Таблица логических функций одной переменной
х |
|
|
|
|
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
=
0 – функция-константа
0;
– тождество
переменной
х;
– отрицание
переменной х;
=
1 – функция-константа
1.
Таблица логических функций двух переменных
x |
y |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
x |
y |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
Функции № 0 и № 15 – функции константы 0 и 1.
Константы принимают одно и то же значение при любых наборах значений аргументов.
Функция № 1 –
конъюнкция
x
и y.
Обозначение конъюнкции
.
Конъюнкция принимает значение
1 только в случае, когда и х и у равны 1.
Функция № 7 –
дизъюнкция
x
и y.
Обозначение дизъюнкции
.
Дизъюнкция принимает значение
1 тогда, когда х или у равны 1 (т.е. хотя
бы один аргумент).
Функция № 9 –
эквивалентность
x
и y.
Обозначение эквивалентности
.
Эквивалентность принимает значение
1 только в случае, когда х и у равны.
Функция № 6 –
сложение
по модулю 2 x
и y.
Обозначение сложения по модулю 2
.
Сложение по модулю 2 принимает значение
1 только в случае, когда сумма х и у
нечетна.
Функция № 13 –
импликация
x
и y.
Обозначение импликации
.
Импликация принимает значение
0 только в случае, когда из «истины»
следует «ложь».
Функция № 11 –
импликация
у и х.
Обозначение –
.
Функция № 14 –
штрих
Шеффера x
и y.
Обозначение штриха Шеффера
.
Штрих Шеффера является отрицанием
конъюнкции:
.
Функция № 8 –
стрелка
Пирса x
и y.
Обозначение стрелки Пирса
.
Стрелка Пирса является отрицанием
дизъюнкции:
Введем обозначения:
;
.
Теорема о разложении функции по переменным
Всякая логическая
функция
может быть разложена по переменным
,
где
,
то есть представлена в виде:
Дизъюнкция
в правой части равенства берется по
всем наборам параметров
.
Конъюнкций, соединенных знаком дизъюнкции
будет
штук.
Разложение функции по всем переменным носит название совершенной дизъюнктивной нормальной формы.
Элементарной конъюнкцией называется конъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза.
Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция элементарных конъюнкций.
Дизъюнктивная форма будет совершенной (СДНФ), если каждая элементарная конъюнкция содержит все наименования переменных.
Элементарной дизъюнкцией называется дизъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза.
Конъюнктивная нормальной формой (КНФ) называется конъюнкция элементарных дизъюнкций.
Конъюнктивная форма будет совершенной (СКНФ), если каждая элементарная дизъюнкция содержит все наименования переменных.