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

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

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

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

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

Ясно, что отношение равносильности рефлексивно, симметрично и транзитивно.

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

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

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

1. х&х х – закон идемпотентности;
2. х х х – закон идемпотентности.
3. х&1 х
4. х 1 1
5. х&0 0
6. х 0 х
7. х& 0– закон противоречия.
8. х 1 закон исключённого третьего.
9. х – закон снятия двойного отрицания.

10. Х&(у х) х – закон поглощения;

11. х (у&х) х – закон поглощения.

12. Х (Х&Y) (X& )- первая формула расщепления.

13. Х (Х Y) & (X )- вторая формула расщепления.

Докажем один из законов поглощения. Рассмотрим формулу

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

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

1. х у (х у)&(у х)

2. х у у

3.

4. &

5. х&у

6.х у &

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

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

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

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

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

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

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

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

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

х	у	х у

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

1) х у.

2) х&у (х у) (х у).

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

Отметим, что х у .

Аналогично может быть введена операция (х, у)

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

1. х&у у&х – коммутативность конъюнкции.
2. х у у х – коммутативность дизъюнкции.
3. х&(у&z) (х&у)&z –ассоциативность конъюнкции.
4. х (у z) (х у) z –ассоциативность дизъюнкции.
5. х&(у z) (х&у) (х&z) – дистрибутивность конъюнкции относительно дизъюнкции.
6. х (у&z) (х у)&(х z) – дистрибутивность дизъюнкции относительно конъюнкции.

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

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: