Глава 1. Алгебра логики
1.1. Функции алгебры логики
Определение.
Функция
,
где
=
{0, 1}, называется функцией алгебры логики
или булевой функцией.
Булеву функцию от
n переменных можно
представить в виде таблицы, в которой
всевозможным наборам значений аргументов
сопоставляются значения функции, такую
таблицу называют таблицей истинности
булевой функции. Легко видеть, что n
переменных принимают
различных значений. Если набор
рассматривать как запись числа в двоичной
системе счисления, то расположение
наборов соответствует естественному
расположению чисел 0, 1, 2, …,
– 1. Таблица истинности функции n
переменных выглядит следующим образом
(табл. 1.1).
|
|
|
|
|
|
Таблица 1.1 |
|
|
|
… |
|
|
f ( ,…, ) |
0 |
0 |
0 |
… |
0 |
0 |
f (0,…, 0, 0) |
1 |
0 |
0 |
… |
0 |
1 |
f (0,…, 0, 1) |
2 |
0 |
0 |
… |
1 |
0 |
f (0,…, 1, 0) |
… |
… |
… |
… |
… |
… |
… |
– 2 |
1 |
1 |
… |
1 |
0 |
f (1,…, 1, 0) |
– 1 |
1 |
1 |
… |
1 |
1 |
f (1,…, 1, 1) |
Пример. Рассмотрим булеву функцию трех аргументов (табл. 1.2), функция принимает значение 1 только на наборах с одной единицей.
|
|
|
Таблица 1.2 |
|
|
|
f ( , , ) |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
Множество всех
булевых функций f
обозначается
(включая константы 0, 1).
В таблице истинности функции одного и того же числа аргументов отличаются лишь правыми столбцами. При увеличении числа аргументов таблица становится громоздкой.
Число
всех функций из
,
зависящих от n переменных
равно,
.
состоит из бесконечного множества
функций.
1.2. Элементарные булевы функции
Ряд функций булевой алгебры называются элементарными.
I. Элементарные булевы функции одной переменной (табл. 1.3).
Таблица 1.3 |
||||
|
|
|
|
|
x |
0 |
1 |
x |
|
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
Функции и не зависят от переменной x. = 0 – функция константа 0, = 1 – функция константа 1.
= x
– тождественная функция (читается
“икс”).
=
– функция отрицания (а также инверсия,
НЕ) (читается “не икс”).
II. Элементарные булевы функции двух переменных (табл. 1.4).
Таблица 1.4 |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
~ |
|
|
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
Всего таких функций 16.
= ( + ) – дизъюнкция (логическое сложение) (читается “ или ”).
=
(
&
,
,
)
– конъюнкция (логическое умножение)
(читается “
и
”).
= – сумма по модулю два (читается “ плюс ”).
= ( , ) – импликация (логическое следование) (читается “ имплицирует ”).
= ~ ( , ) – эквивалентность (читается “ эквивалентно ”).
= ( / ) – штрих Шеффера (инверсия конъюнкции) (читается “ штрих ”).
= – стрелка Пирса (инверсия дизъюнкции) (читается “ стрелка ”).