- •Глава 1. Алгебра логики
- •1.1. Функции алгебры логики
- •1.2. Элементарные булевы функции
- •1.3. Формульное представление булевой функции
- •1.4. Существенные и фиктивные переменные
- •1.5. Эквивалентные соотношения (тождества) алгебры логики
- •1.6. Разложение булевой функции по подмножеству переменных и совершенные нормальные формы
- •1.7. Двойственная функция
- •1.8. Полнота систем булевых функций
- •1.9. Функции k-значной логики
- •1.10. Контрольные вопросы к главе 1
КАДР
Глава 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.
= ( + ) – дизъюнкция (логическое сложение) (читается “ или ”).
= ( & , , ) – конъюнкция (логическое умножение) (читается “ и ”).
= – сумма по модулю два (читается “ плюс ”).
= ( , ) – импликация (логическое следование) (читается “ имплицирует ”).
= ~ ( , ) – эквивалентность (читается “ эквивалентно ”).
= ( / ) – штрих Шеффера (инверсия конъюнкции) (читается “ штрих ”).
= – стрелка Пирса (инверсия дизъюнкции) (читается “ стрелка ”).
КАДР