Основные понятия алгебры логики

Для математического описания работы компьютера и его программного проектирования широко используется алгебра логики (булевская алгебра). В булевской алгебре рассмотрим константы и функции.

Константы алгебры логики – логический 0 (ложь) и логическая 1 (истина). Логические переменные принимают только два значения–логический 0 или логическая 1.

Логической функцией F от набора логических переменных x₁, x₂, …, x_n называется функция, которая может принимать только два значения: логический 0 или логическую 1. Для того, чтобы определить логическую функцию, надо перечислить либо все наборы ее аргументов, при которых она принимает значение 1, либо все наборы при которых она принимает значение 0. Набор аргументов – это конкретное сочетание значений аргументов. Полный набор - это переменные всех возможных сочетаний значений аргументов. Любая логическая функция может быть задана с помощью таблицы истинности, в левой части которой записываются наборы аргументов, а в правой соответствующее значение функции.

Элементарные логические функции – логические функции, которые зависит от одной или двух логических переменных, называются элементарными.

a) логическое умножение (конъюнкция) – операция «И» (and). Обозначается &, ^, , или совсем опускается: x&y, x^y, x y или xy.

Таблица истинности функции F(x,y)=xy:                 Логическая схема.

Полный набор всех значений аргументов x	y	xy
1	1	and 1
1	0	0
0	1	0
0	0	0

б) логическое сложение (дизъюнкция) – операция «ИЛИ» (or). Обозначается или +: x y или x+y.

or

Таблица истинности функции F(x,y)=x y:                Логическая схема.

x	y	x y
1	1	1
1	0	1
0	1	1
0	0	0

в) отрицание (инверсия) – операция «НЕ» (not). Обозначается  или ‘: или x’.

Таблица истинности функции F(x)=                      Логическая схема.

x	not x x y
истина	ложь
ложь	истина

Булевы (логические) выражения – это булевы константы и переменные, связанные логическими операциями «И», «ИЛИ» и «НЕ» в единую формулу. При вычислении логического выражения учитывается приоритет логических операций: 1 – инверсия («НЕ»), 2 – конъюнкция («И»), 3 – дизъюнкция(«ИЛИ»). Для изменения порядка действий используются скобки. Например, F(X1, X2, X3)=(X1 X2)(X1 X2) X2X3.