Элементы алгебры логики

3.1. ЛОГИЧЕСКИЕ ОПЕРАЦИИ
Переменная x называется логической, если x ∈ {0, 1}.
Над логическими переменными определены логические операции или логические функции.
Функцией алгебры логики или булевой функции
n переменных f(x1, x2, ... , xn) называется функция,
областью значений которой служит {0,1} и
область определения также {0,1}.
(x1, x2, ... , xn) ∈ {0, 1} f ∈ {0, 1}

Базовые операции над логическими переменными:
1. Отрицание
Обозначается:
Таблица истинности логической операции «отрицание»:
Отрицание соответствует союзу «НЕ». Если логическая переменная а истинна, то есть а = 1, то ее отрицание (НЕ a) будет ложно, и наоборот.

2. Конъюнкция или логическое умножение
Обозначается:
Конъюнкция в русском языке соответствует союзу «И».
3. Дизъюнкция или логическое сложение
Обозначается:
Дизъюнкция в русском языке соответствует союзу «ИЛИ».

Таблица истинности логических операций конъюнкция» и «дизъюнкция»:
Логические элементы могут быть реализованы на различной
элементной базе. Сначала это были электромагнитные реле,
затем появились электронные лампы, еще позже - транзисторы
и, наконец, интегральные микросхемы.
В настоящее время один кремниевый кристалл может содержать
несколько миллионов логических элементов.

Рассмотрим реализацию логики на электромагнитных
релейно-контактных схемах. Если логическая переменная a = 1,
то реле замкнуто, а если a = 0, — то разомкнуто.
Конъюнкция соответствует последовательному соединению
реле. Лампочка будет гореть, если оба реле замкнуты,
a = 1 и b = 1.
Поэтому конъюнкция равна «1» только на наборе «1, 1»,
а на остальных наборах равна «0».
Дизъюнкция соответствует параллельному соединению реле.
Лампочка не будет гореть, если оба реле разомкнуты, т. е.
a = 0 и b = 0. Поэтому дизъюнкция равна «0» только на наборе
«0, 0», а на остальных наборах равна «1».
Все остальные логические операции могут быть выражены
через базовые.

f = a ∨ b
f = a ▪ b

4. Импликация или следование
Обозначается: «→»
Импликация соответствует выражению «Если а, то b».
Переменная a называется посылкой, b — следствием.

а → b = ā ∨ b.

а → b = ā ∨ b.

5. Эквиваленция или равнозначность
Обозначается: а ~ b
Эквиваленция соответствует выражению «a, если и только если b». Эквиваленция в русском языке соответствует выражению «a, если и только если b».

а ~ b = a ▪ b ∨ а ▪ в

а ~ b = a ▪ b ∨ а ▪ в

5. Неравнозначность
Обозначается: a ⊕ b
Неравнозначность противоположна эквиваленции и
соответствует выражению «либо a, либо b».

Другое название неравнозначности — «исключающее ИЛИ».
Оно говорит о том, что на наборах «1, 1» и «0, 0»
неравнозначность равна 0, то есть не допускается
одновременный выбор и того и другого.
Третье название неравнозначности — «сложение по модулю два».
Оно означает, что остаток от деления на два равен 0.
Обозначим его словом mod.
0 + 0 = 0 0 mod 2 = 0
0 + 1 = 1 1 + 0 = 1 1 mod 2 = 1
1 + 1 = 2 2 mod 2 = 0

a ⊕ b = a ▪ в ∨ a ▪b.