1-й сем-ДМ-слайды-ДГТУ / Прилолжения,л.2-3
.docЛогические операции над высказываниями
-
Отрицание
Отрицание х – новое высказывание, которое истинно, если х ложно и наоборот.
-
х
х
1
0
0
1
-
Конъюнкция (логическое умножение)
Конъюнкция двух высказываний х и у – новое высказывание, которое истинно, если х и у истинно и ложно, если хотя бы одно из них ложно.
Конъюнкции х и у: х&у или xу («х и у»).
-
х
у
ху
1
1
1
1
0
0
0
1
0
0
0
0
-
Дизъюнкция (логическое сложение)
Дизъюнкция х и у – новое высказывание, которое истинно, если хотя бы 1 из высказываний истинно и ложно, если оба ложны.
-
х
у
ху
0
0
0
0
1
1
1
0
1
1
1
1
-
Импликация – новое высказывание, логично, если х истинно, а у – ложно и истинно во всех остальных случаях.
х→у («если х, то у» или «из х следуют у»)
х – условие или посылка, у – следствие или замещение.
х |
у |
х→у |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
-
Эквиволенция (или эквиваленционность) двух высказываний х и у – новое высказывание, которое истинно, если оба высказывания х и у, либо одновременно истины, либо одновременно ложны и ложно во всех остальных случаях.
х→у («для того, чтобы х, необходимо и достаточно, что бы у или х тогда и только тогда, когда у»).
х |
у |
ху |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
Формулы алгебры логики:
→
х |
у |
|||||
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
Основные равносильности
-
закон идентичности
-
закон идентичности
-
-
-
-
-
закон противоречия
-
закон истинного противоречия
-
закон двойного отрицания
-
-
Равносильности, выражающие одни логические операции через другие
Равносильности, выражающие основные законы алгебры логики
-
коммутативность конъюнкции
-
коммутативность дизъюнкции
-
ассоциативность конъюнкции
-
ассоциативность дизъюнкции
-
дистрибутивность конъюнкции относительно дизъюнкции
-
дистрибутивность дизъюнкции относительно конъюнкции
Булевы функции
x |
у |
f1 |
f2 |
f3 |
f4 |
f5 |
f6 |
f7 |
f8 |
f9 |
f10 |
f11 |
f12 |
f13 |
f14 |
f15 |
f16 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
f1 f5 f9 f13
f2 f6 f10 f14
f3 f7 f11 f15
f4 f8 f12 f16
Приложение:
1)
А В
2
А
Формула:
3) Применение алгебры логики к решению логических задач
-
Антон был вторым, а Борис – пятым
-
Виктор был вторым, а Денис – третьим
-
Григорий был первым, а Борис третьим
-
Антон был третьим, а Евгений – пятым
-
Виктор был третьим, а Евгений – четвертый
Одно из двух высказываний ошибочно. Что было на самом деле?
Обозначим высказывания ху, где х – первые буквы имени, у – номер места в структуре.
Получим:
А2Б5; В2Д3; Г1Б31;
А3Е6; В3Е4;
Тогда истинна формула:
Б5)В2Д3)Г1Б3)(А3Е6)(В3Е4)В2Д3Б5Д3Б5В2)Г1А3Г1Е6Б3В3Е4)А2Д3Г1А2Д3Г1Е6А2Д3Б3Е6Б5Д3Г1А3Б5Д1Г1Е6Б5Д3Б3Е6Б5В2Г1А3Б5В2Г1Е6Б5В2Б3Е6)(В3Е4)(А2Д3Г1Е6В3А2Д3Г1Е6Е4Б5Д3Г1Е6В3Б5Д3Г1Е6Е4Б5В2Г1А3В3Б5В2Г1А3Е4Б5В2Г1Е6В3Б5В2Г1Е6Е4Б5В2Г1А3Е4.