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

Логические константы, переменные и функции

Для описания логики функционирования аппаратных и программных средств ЭВМ используется алгебра логики, или булева алгебра [1] (по имени создателя — английского математика XIX в. Дж. Буля — G. Вооlе). Два элемента алгебры логики — ee константы — будем обозначать: 0 и 1 (ложь и истина — false и true), т. е. логический 0 и логическая 1. Алгебра логики оперирует с логическими переменными, которые могут принимать только два значения; истина или ложь — логический 0 и логическая 1 (не путать с двоичными!).

X=0, если X 1

Х=1, если X 0— это булева (логическая) переменная

Во всех схемах ЭВМ используются сигналы двух видов. Таким образом, сигналы можно интерпретировать как двоичные числа, или логические переменные.

Логической функцией F от набора логических переменных xi,-..Xn называется функция, которая может принимать только два значения: логический 0 и логическая 1

Область определения логической функции конечна и зависит от количества возможных наборов аргументов. Если п — число аргументов, то количество возможных наборов аргументов равно 2 ⁿ. Множество значений функции F(xi,...,Xn) — это множество {0,1}, т. е. F=0 либо 1.

Элементарные логические операции. Таблицы истинности

1. Логическое умножение - конъюнкция - операция И -AND. Обозначается: &,  , • или совсем опускается:

х • у, или х & у, или х  у или ху.

Постулаты операции И представлены в виде таблицы истинности функции F(x,y)=x • у:

X	Y	X • Y
0	0	0
0	1	0
1	0	0
1	1	1

Функция F(x,y) принимает значение 1 только в том случае, когда оба аргумента - и первый, и второй - равны 1.

2. Логическое сложение - дизъюнкция - операция ИЛИ - OR.

Обозначается: v или +:

X v Y или х+у

X	Y	X v Y
0	0	0
0	1	1
1	0	1
1	1	1

 

Функция F принимает единичное значение, когда хотя бы один из аргументов, или первый, или второй, или п-й, равен 1.

 

3. Отрицание - инверсия - операция НЕ - NOT. Обозначение: not X :

Постулаты операции НЕ представлены в виде таблицы истинности функции F(x)=x:

X	not X
0	1
1	0

Логические схемы. Булевы выражения

Булева алгебра — математическая система с элементами логический 0 и логическая 1 и операциями И, ИЛИ и НЕ с их заданными постулатами. Цель булевой алгебры — описание поведения и структуры логических схем.

Булево выражение— это булевы константы и переменные, связанные логическими операциями И, ИЛИ и НЕ в единую формулу.

При вычислении логического выражения учитывается следующее старшинство логических операций:

1) инверсия ( ), not

2) конъюнкция (•) , &, and

3) дизъюнкция ( v ), +, or

Для изменения порядка используются скобки.

Примеры.

1. F(X1 ,Х2,Хз) = (XI v X2) • (X1 v Хз) v X2 • Хз

2. F(X1 ,Х2,Хз) = (XI • X2 V Х2 • not ХЗ) • Xi V ХЗ

Логическая схема, которая полностью описывается булевыми выражениями или таблицами истинности, называется комбинационной схемой.

Таким образом, комбинационная схема— схема, в которой значения входных переменных в текущий момент времени полностью определяют значения выходных переменных.

Другой класс схем — последовательностные схемы. Это схемы с внутренней памятью. В них значения выходных переменных определяются не только значениями входных переменных в текущий момент времени, но и их значениями в предыдущие моменты времени

Будем рассматривать только комбинационные схемы.