Аксиомы, основные теоремы и тождества алгебры логики

В алгебре логики рассматриваются переменные, которые могут принимать только два значения: 0 и 1. В дальнейшем переменные будем обозначать латинскими буквами х, у, z,... . В алгебре логики определено отношение эквивалентности (=) и три операции: дизъюнкция (операция ИЛИ), обозначаемая знаком V (+); конъюнкция (операция И), обозначаемая точкой, которую можно опускать (например, х·у=ху); отрицание (инверсия, операция НЕ), обозначаемое чертой над переменными или элементами 0 и 1 (например, , ). Отношение эквивалентности удовлетворяет следующим свойствам: х = х—рефлексивность; если х=у, то у=х - симметричность; если х = у и у = z, то x = z — транзитивность. Из отношения эквивалентности следует принцип подстановки: если х=у, то в любой формуле, содержащей х, вместо х можно подставить у, и будет получена эквивалентная формула.

Алгебра логики определяется следующей системой аксиом:

	(1.30)
	(1.31)
	(1.32)
	(1.33)
	(1.34)

Аксиома (1.30) утверждает, что в алгебре логики рассматриваются только двоичные переменные, аксиомы (1.31) — (1.33) определяют операции дизъюнкции и конъюнкции, а аксиома (1.34)—операцию отрицания. Если в аксиомах (1.31) —(1.34), заданных парами, произвести взаимную замену операций дизъюнкции и конъюнкции, и также элементов 0 и 1, то из одной аксиомы пары получится другая. Это свойство называется принципом двойственности.

С помощью аксиом алгебры логики можно доказать целый ряд теорем и тождеств. Одним из эффективных методов доказательства теорем является метод перебора всех значений переменных. Если теорема истинна, то с учетом (1.31)—(1.34) при подстановке любых значений переменных в обе части выражения, формулирующего утверждение теоремы, должно получиться тождество. Метод перебора не слишком трудоемок, так как переменные могут иметь только два значения: 0 и 1. Так, методом перебора легко убедиться в справедливости следующих теорем:

идемпотентные законы

(1.35)

коммутативные законы

(1.36)

ассоциативные законы

(1.37)

дистрибутивные законы

(1.38)

законы отрицания

	(1.39)
	(4.40)
	(1.41)

законы двойственности (теоремы де Моргана)

(4.42)

закон двойного отрицания

(1.43)

законы поглощения

(1.44)

операции склеивания

(1.45)

операции обобщенного склеивания

	(1.46)
	(1.47)

Теоремы (1.35) —(1.42) и (1.44) —(1.47) записаны парами, причем каждая из теорем пары является двойственной другой, так как из одной теоремы пары можно получить другую на основании принципа двойственности, т. е. путем взаимной замены операций дизъюнкции и конъюнкции, а также элементов 0 и 1, если они имеются. Теорема (1.43) самодвойственна, так как она не изменяется по принципу двойственности (отсутствуют элементы 0 и 1 и операции дизъюнкции и конъюнкции).

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

Некоторые теоремы и тождества алгебры логики имеют особое значение, так как позволяют упрощать логические выражения. Например, в соотношениях (1.35), (1.39)—(1.41), (1.44) —(1.47) правая часть проще левой. Поэтому, произведя в логических выражениях соответствующие преобразования, можно добиться существенного их упрощения. Особенно часто для преобразования логических выражений, с целью их упрощения, используются тождества (1.44) — (1.47).

Операция сумма по модулю два (исключающее ИЛИ, логическая неравнозначность) обозначается символом Å и определяется соотношением

.

(1.48)

Используя аксиомы алгебры логики, легко убедиться, что:

(1.49)

Из соотношений следует, что значение хÅу совпадает со значением младшего разряда суммы двух двоичных чисел, где х и у — значения младших разрядов этих чисел. Соответственно этому значение i-ro разряда суммы двух двоичных чисел будет определяться значением x_iÅy_iÅz_i; где x_i и y_i — значения i-x разрядов двоичных чисел, a z_i—перенос в i-й разряд из предыдущего (i—1)-го разряда.

Операция сумма по модулю два коммутативна, ассоциативна и дистрибутивна относительно операции конъюнкции, т. е.

(1.50)

Для операции сумма по модулю двасправедливы также следующие тождества:

(1.51)