Аксиомы и теоремы алгебры логики

Основы алгебры логики были заложены еще в середине XIX века трудами английского математика Дж. Буля, по имени которого она называется также булевой алгеброй. Ясное понимание принципов, лежащих в ее основе, исключительно важно для овладения формальными методами проектирования цифровых систем.

В алгебре логики рассматриваются переменные, которые могут принимать только два значения – 0 и 1. В дальнейшем эти переменные мы будем обозначать либо латинскими буквами x, y, z, …, либо наборами х₁, х₂, х₃, ….

В алгебре логики определены отношение эквивалентности (=) и три операции:

– дизъюнкция (операция ИЛИ), обозначаемая в различной литературе знаками Ú или +;

– конъюнкция (операция И), обозначаемая знаком & или точкой, которую можно опускать (например, х×у=ху);

– отрицание (инверсия, операция НЕ), обозначаемое чертой над переменными или над элементами 0 и 1 (например, ).

Отношение эквивалентности удовлетворяет следующим очевидным свойствам:

х=х – рефлексивность;

если х=у, то у=х – симметричность;

если х=у и у=z, то х=z – транзитивность.

Из отношения эквивалентности также очевидно следует принцип подстановки: если х=у, то в любой формуле, содержащей х, вместо х можно подставить у, и в результате будет получена эквивалентная формула.

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

(1.1)

(1.2)

(1.3)

(1.4)

(1.5)

Аксиома (1.1) является утверждением того, что в алгебре логики рассматриваются только двоичные переменные, аксиомы (1.2)–(1.4) определяют операции дизъюнкции и конъюнкции, а аксиома (1.5) – операцию отрицания.

С помощью аксиом алгебры логики можно доказать целый ряд теорем и тождеств. Одним из эффективных методов доказательства данных теорем является метод перебора всех значений переменных: если теорема истинна, то с учетом (1.2)–(1.5) уравнение, формулирующее утверждение теоремы, должно быть истинно при подстановке любых значений в обе его части. Так, методом перебора легко убедиться в справедливости следующих теорем:

х+х=х; х×х=х (1.6)

х+у=у+х; х×у=у×х (1.7)

(х+у)+z=x+(у+z); (х×у)×z=x×(y×z) (1.8)

х×(у+z)=x×y+x×z; х+у×z=(x+y)×(x+z) (1.9)

(1.10)

0+x=1×x=x (1.11)

1+x=1; 0×x=0 (1.12)

теоремы де Моргана, или законы двойственности:

(1.13)

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

(1.14)

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

х+ х×у=x; х×(х+у)=x (1.15)

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

(1.16)

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

(1.17)

Все теоремы могут быть доказаны методом перебора. Докажем, например, тождество (1.13), сведя все возможные пары значений в таблицу 1.1:

Таблица 1.1

х у
0 0
0 1
1 0
1 1

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

,

однако скобки нельзя опустить в выражении , поскольку

.