Законы алгебры логики

Для упрощения логических выражений используют законы алгебры логики. Они формулируются для базовых логических операций — «НЕ», «И» и «ИЛИ».

 

Закон	Для операции «И*	Для операции «ИЛИ»
двойного отрицания	А	-А
исключённого третьего	АА=0	А + А=1
операции	А1 = А,    А 0=0	А + 1 = 1,    А+0=А
повторен»»	А-А =А	А + А=А
переместительный	АВ=В А	А+В=В+А
сочетательный	А-(ВС)=(АВ)-С	A + (S + C)=(A+S) + C
распределительный	А+В-С=(А+В)-{А+С)	А(В+С)=А В + А С
поглощения	А + А-В = А	А(А + В)=А
де Моргана	АВ=А^ + В	А+В-А-Б

Закон двойного отрицания означает, что операция «НЕ» обра­тима: если применить ее два раза, логическое значение не изме­нится. Закон исключённого третьего основан на том, что в клас­сической (двузначной) логике любое логическое выражение либо истинно, либо ложно («третьего не дано»). Поэтому если А = 1, то А =0 (и наоборот), так что произведение этих величин всегда рав­но нулю, а сумма — единице.

Операции с константами и закон повторения легко проверя­ются по таблицам истинности операций «И» и «ИЛИ». Перемес-тительный и сочетательный законы выглядят вполне привычно, так же, как и в арифметике. Почти везде «работает» аналогия с алгеброй чисел, нужно только помнить, что в логике 1 + 1 = 1, а не 2.

Распределительный закон для операции «ИЛИ» — это обыч­ное раскрытие скобок. А вот для операции «И» мы видим незна­комое выражение, в алгебре чисел это равенство неверно. Доказа­тельство можно начать с правой части, раскрыв скобки:

{А + В){А+С)=АА + АС + ВА + ВС.

Дальше используем закон повторения (А ■ А = А) и заметим,

Анало

образом,

О. де Морган (1806-1871)

азываем,   что   А + В-А = А (1 + В) = А,   таким

(А+В)(А+С) = А + ВС.

Равенство доказано. Попутно мы дока­зали также и закон поглощения для опе­рации «И» (для операции «ИЛИ» вы мо­жете сделать это самостоятельно). Отме­тим, что из распределительного закона следует полезное тождество:

Правила, позволяющие раскрывать отрицание сложных выражений, названы в честь шотландского математика и логи­ка Огастеса (Августа) де Моргана. Обрати­те внимание, что при этом не просто «об­щее» отрицание переходит на отдельные выражения, но и операция «И» заменяет-ся на «ИЛИ» (и наоборот). Доказать законы де Моргана можно с помощью таблиц истинности.

Теперь с помощью приведённых законов алгебры логики упростим полученное ранее логическое выражение для объедине­ния областей 3 и 4 на диаграмме с тремя переменными (§ 20, рис. 3.15):

ABC + A~BC = (A + A~)BC = BC.

Здесь мы сначала вынесли общий множитель двух слагаемых за скобки, а затем применили закон исключённого третьего.

В общем случае можно рекомендовать такую последователь­ность действий.

1. Заменить все «небазовые» операции (исключающее ИЛИ, им­
   пликацию, эквивалентность и др.) на их выражения через ба­
   зовые операции «НЕ», «И» и «ИЛИ».
2. Раскрыть отрицания сложных выражений по законам де Мор­
   гана так, чтобы операции отрицания остались только у от­
   дельных переменных.
3. Используя вынесение общих множителей за скобки, раскры­
   тие скобок и другие законы алгебры логики, упростить выра­
   жение.

Пример

= {А  А + ВА)В(А+С) = ВА  Ъ(А+С) = = А~В В (А+С) = ВА~(А+С) = В А.

Здесь последовательно использованы закон де Моргана, рас­пределительный закон, закон исключённого третьего, перемести­тельныи закон, закон повторения, снова переместительныи закон

Логические уравнения

Если приравнять два логических выражения, мы получим уравнение. Его решением будут значения переменных, при кото­рых уравнение превращается в истинное равенство, т. е. когда значения левой и правой частей совпадают. Например, уравнение А ■ В = 1 имеет  единственное   решение:   А = В = 1,   для  остальныхкомбинаций значений переменных левая часть равна нулю. В то же время уравнение А + В=1 имеет три решения: (А=0, В=1), (А=1, Б=0) иА = В=1.

Пример 1. Требуется найти все решения уравнения

Вспоминаем, что импликация равна нулю только тогда, когда первое выражение равно 1, а второе — 0. Поэтому исходное урав­нение сразу разбивается на два:

(B+C)-A=l,     AC+D = 0.

Первое уравнение с помощью закона де Моргана можно преоб­разовать к виду ВС А=1, откуда сразу следует, что все три со­множителя должны быть равны 1. Это значит, что А=1, В=0 и С=0. Кроме того, из второго уравнения следует, что D = 0. A =1 и С =0 удовлетворяют и второму уравнению тоже. Решение найдено, причём оно единственное.

Возможен второй вариант — упростить выражение. Заменяя импликацию по формуле А —> В = А + В, получаем:

(В+С)А + АС+£> = 0. Используем закон де Моргана:

B+C + A~+~AC+D = Q и закон поглощения:

B + C + A+D-0.

Для того чтобы логическая сумма была равна нулю, каждое слагаемое должно быть равно нулю, поэтому A=l, B=C =D=Q.

Есть и третий вариант — построить таблицу истинности вы­ражения в левой части и найти все варианты, при которых оно равно 0. Однако таблица истинности выражения с четырьмя пере­менными содержит 2⁴ = 16 строк, поэтому такой подход достаточ­но трудоёмок.

Пример 2. Требуется найти все решения уравнения (А + В)->(В CD) = 1.

Преобразуем выражение, раскрыв импликацию через опера­ции «НЕ» и «ИЛИ» и применив закон де Моргана: если логическая сумма равна 1, то хотя бы одно слагаемое равно 1 (или o6ji одновременно).

Равенство А В = 1 верно при А = 0, В-1 и любых С и D. По­скольку есть всего 4 комбинации значений С и D, уравнение А  В=1 имеет 4 решения:

 

А	в	с	D
0	1	0	0
0	1	0	1
0	1	1	0
0	1	1	1

Второе уравнение, B-C-D = \, даёт B=C=D=\ при любом А, т. е. оно имеет два решения:

 

А	В	С	D
			-А--
1	1	1	1

Видим, что первое из этих решений уже было получено рань­ше, поэтому уравнение имеет всего пять разных решений. Заме­тим, что_определить все повторяющиеся решения можно из урав­нения (А ■ В) ■ (В ■ С ■ D) = 1, которое имеет единственное решение А=0, B-C=D=1.

Пример 3, Требуется найти число решений урав: АВ С + В С D = 0.

Здесь, в отличие от предыдущих задач, не ну сами решения, интересует только их количест* распадается на два:

А ■ В С = 0 и В С D = 0.

го находить Уравнение . Можно по­ступить следующим образом: сначала найти количество решений «обратного* уравнения, с единицей в правой части: АВС + ВС D = l

Каждое из них имеет достаточно много решен

Логические основы компьютеров

и затем вычесть его из 16 (общего количества комбинаций че­тырёх переменных). Уравнение А ■ В ■ С = 1 имеет два решения: А = В = С = 1 и любое D (0 или 1). Второе уравнение, B-C-D=l, тоже имеет два решения: А — любое, В=С = О, D = l. Среди этих четырёх решений нет повторяющихся, поэтому исходное уравне­ние имеет 16 - 4 = 12 решений.

Пример 4. Требуется найти число решений уравнения

Так как каждая логи ко значения 0 и 1, мож цепочки. Например, цеп

 еская переменная может принимать толь­ о представить решение в виде 6-битной  чка 010110 означает, что Х₁ = Х₃ = Х₆ =0

₂₄₅

Заметим, что импликация А -»В ложна тогда и только тогда, когда А=1 и В = 0. Поэтому в решении заданного уравнения не может встречаться последовательность 10, иначе какая-то импли­кация оказывается ложной и всё выражение будет равно 0. Поэтому существует всего 7 решений:

000000      000001       000011      000111      001111      011111       111111

ния (0 и 1), и число ных конечно, оно равно 2", Поэтому уравнение с п пере

Обратите внимание, что число решений логических уравне­ний, в отличие от «обычных уравнений», всегда конечно. Это свя­зано с тем, что каждая переменная может принимать только два ния (0 и 1), и число разных комбинаций значений перемен­ — это количество переменных,  ми имеет не более 2" решений.