Материал: Дискретная математика. учебное пособие. Горбунов В.В., Лапшина М.Л
Пусть
.
Таблица 14.
X |
Y |
Z |
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Поскольку
таблицы истинности для
и
совпадают, то эквивалентность
доказана.
Задача 3.
Для высказывания «Если Иван умен, а
Василий глуп, то Иван будет победителем»
найдите логическую формулу и постройте
таблицу истинности. Воспользуйтесь
буквенными обозначениями:
для «Иван умен»,
для «Василий глуп»,
для
«Иван будет победителем».
Решение.
Логическая формула имеет вид:
.
Таблица истинности имеет вид:
Таблица 15.
|
|
|
|
|
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
Задача 4. Для высказывания «Если Василий глуп, а Иван не будет победителем, то Иван не умен» найдите логическую формулу и постройте таблицу истинности. Воспользуйтесь буквенными обозначениями: для «Иван умен», для «Василий глуп», для «Иван будет победителем».
Решение.
Логическая формула имеет вид:
.
Таблица истинности имеет вид:
Таблица 16.
-
X
Y
Z
0
0
0
1
1
0
1
0
0
1
1
0
0
1
0
1
0
1
1
1
1
0
1
1
1
0
0
1
1
0
0
0
1
0
1
1
0
1
0
0
0
1
1
1
0
0
1
1
0
1
1
1
0
0
0
1
Задача 5. Доказать равносильность, используя основные законы логических операций:
.
Решение.
1.Используя законы де Моргана и , получим:
.
2.Используя
закон двойного отрицания
,
получаем:
.
3. Применяя
распределительный закон
,
получаем
=
=
.
4. Ассоциативность дизъюнкции позволяет упростить последнее выражение:
.
5. Учитывая законы, включающие тождественно ложные высказывания, окончательно получаем:
.
Задача 6. С
помощью таблиц истинности проверить,
являются ли эквивалентными высказывания:
и
.
Решение.
Таблица 17.
X |
Y |
Z |
|
|
|
|
|
|
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
Так как значения для высказываний и в таблице истинности не совпали, то они не эквивалентны.
Задача 7. Определите для высказывания, будет ли оно логически истинным, противоречивым; ни тем, ни другим.
.
Решение.
По прежнему, составляем таблицу истинности для высказывания
Таблица 18.
-
X
Y
0
0
1
1
1
1
0
1
0
1
1
1
1
0
1
1
1
1
1
1
0
0
0
1
(т)
– логически истинное высказывание.
Задача 8.
Постройте таблицы истинности следующих
составных высказываний: (а)
;
(б)
;
(в)
;
(г)
;
(д)
.
Для каких пар имеет место отношение
следствия или эквивалентности?
Ответ: (б) эквивалентно (в), из (а) следует (г), из (д) следует (б), (в).
Задача 9.
Постройте составные высказывания,
эквивалентные а)
;
б)
,
используя только связки отрицания и
конъюнкции.