Т. А. Сливина математическая логика и теория алгоритмов

1. Основные равносильности
– законы идемпотентности.
– закон снятия двойного отрицания.
– законы поглощения.
Докажем формулу 4.
Пусть А ≡ при x = 1, значение А = 1, при х = 0, значение А = 0. Итак во всех случаях значения формулы А совпадают со значениями х, следовательно, А ≡ х.
2. Равносильности, выражающие одни логические операции через другие
1.
2.
3.
4.
5.
6.
Замечание. Формулы 5 и 6 получаются из 3 и 4, если от обеих частей последних взять отрицания и воспользоваться законом снятия двойного отрицания.
Докажем формулы 1–4.
Докажем формулу 1.
1) при одинаковых логических значениях x и y формулы
и – истинны, следовательно, истинной будет и коньюнкция т. е. обе части равносильности имеют одинаковые истинные значения.
2) пусть теперь x и y имеют разные логические значения, тогда будут ложными и одна из или При этом будет ложной и коньюнкция т. е. обе части равносильности имеют одинаковые ложные значения. Что и требовалось доказать.
Докажем формулу 3.
1) пусть x и y одновременно принимают истинные значения, тогда будет истинной и коньюнкция и ложным ее отрицание В то же время будут ложными и , следовательно, будет ложной и дизьюнкция
2) пусть хотя бы одна из переменных x или y принимает значение ложь, тогда тоже ложь, а – истина. В то же время отрицание хотя бы одной из переменных будет истинным, следовательно, будет истиной и дизьюнкция
Следовательно, во всех случаях обе части равносильности 3 принимают одинаковые логические значения.
Аналогично доказываются равносильности 2 и 4.
Из равносильностей группы 2 следует, что всякую формулу алгебры логики можно заменить равносильной ей формулой, содержащей только две логические операции: коньюнкцию и отрицание или дизьюнкцию и отрицание.