Равносильные формулы алгебры логики

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

Равносильность формул будем обозначать знаком , а запись A В означает, что формулы А и В равносильны.

Например, равносильны формулы:

Формула А называется тождественно истинной (или тавтологией), если она принимает значение 1 при всех значениях входящих в нее переменных.

Например, тожественно истинны формулы , .

Формула А называется тождественно ложной, если она принимает значение 0 при всех значениях входящих в нее переменных. Например, тождественно ложна формула х& .

Между понятиями равносильности и эквивалентности существует следующая связь: если формулы А и В равносильны, то формула А В - тавтология, и обратно, если формула А В - тавтология, то формулы А и В равносильны.

Важнейшие равносильности алгебры логики можно разбить на три группы.

I. Основные равносильности:

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

1.

2.

3.

4.

5.

6.

7. - закон противоречия.

8. - закон исключенного третьего.

9. -закон снятия двойного отрицания.

10.

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

11.

Докажем один из законов поглощения. Рассмотрим формулу . Если в этой формуле х = 1, то, очевидно, и тогда как конъюнкция двух истинных высказываний. Пусть теперь в формуле А х = 0. Но тогда по определению операции конъюнкции будет ложной и конъюнкция . Итак, во всех случаях значения формулы А совпадают со значениями х, а поэтому А х.

II. Равносильности, выражающие одни логические операции через другие:

1. ;

2. ;

3. ;

4. ;

5. ;

6. .

Ясно, что равносильности 5 и 6 получаются из равносильностей 3 и 4 соответственно, если от обеих частей последних взять отрицания и воспользоваться законом снятия двойного отрицания. Таким образом, в доказательстве нуждаются первые четыре равносильности. Докажем две из них: первую и третью.

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

Пусть теперь х и у имеют различные логические значения. Тогда будут ложными эквивалентность х↔у и одна из двух импликаций х ® у или у х. Но при этом будет ложной и конъюнкция . Таким образом, в этом случае обе части равносильности имеют одинаковые логические значения.

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

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

Следовательно, во всех случаях обе части равносильности 3 принимают одинаковые логические значения.

Аналогично доказываются равносильности 2 и 4.

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

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

Однако существуют операции, с помощью которых может быть выражена любая из пяти логических операций, которыми мы пользуемся. Такой операцией является, например, операция «Штрих Шеффера». Эта операция обозначается символом и определяется следующей таблицей истинности:

Очевидно, имеют место равносильности:

1) .

2) .

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

Аналогично может быть введена операция .

III. Равносильности, выражающие основные законы алгебры логики:

1. х&у≡у&х - коммутативность конъюнкции.

2. - коммутативность дизъюнкции.

3. - ассоциативность конъюнкции.

4. - ассоциативность дизъюнкции.

5. -дистрибутивность конъюнкции относительно дизъюнкции.

6. -дистрибутивность дизъюнкции относительно конъюнкции.

Докажем последний из перечисленных законов. Если х = 1, то будут истинными формулы .

Но тогда будет истинной и конъюнкция . Таким образом, при х = 1обе части равносильности 6 принимают одинаковые логические значения (истинные).

Пусть теперь х=0. Тогда и , а поэтому и конъюнкция . Следовательно, здесь обе части равносильности 6 равносильны одной и той же формуле у& z и поэтому принимают одинаковые логические значения.