Санкт-Петербургский Национальный Исследовательский Университет
Информационных Технологий, Механики и Оптики
ФКТиУ, кафедра Информатики и прикладной математики
Домашняя работа №1
по дисциплине
«Дискретная математика»
(Вариант 9)
Выполнил: Студент группы P3119
Преподаватель: ассистент кафедры ИПМ
Санкт-Петербург
2017 г.
Задание 1
Для формулы в исходном виде подписать порядок действий, построить двоичную диаграмму. Затем заменить все вторичные связки первичными. Упростить, используя тождественные преобразования, изученные ранее, и построить двоичную диаграмму для упрощенной формулы
? ((a v b & d -> c) ? a & c) -> (d ? c)
b=0 | b=1 | ||||||||||||||
?((a v 1 & d -> c) ? a & c) -> ( d ? c ) | ?((a v 0 & d -> c) ? a & c) -> ( d ? c ) | ||||||||||||||
d=0 | d=1 | d=0 | d=1 | ||||||||||||
?((a v 1 & 0 -> c) ? a & c) -> (c) | ?((a v 1 & 1 -> c) ? a & c) -> (c) | ?((a v 0 & 0 -> c) ? a & c) -> (c) | ?((a v 0 & 1 -> c) ? a & c) -> (c) | ||||||||||||
|| | || | || | || | ||||||||||||
((a->c)?a&c)->(c) | ?((1->c)?a&c) -> (c) | ?((a->c)?a&c)->(c) | ?((a->c)?a&c) -> (c) | ||||||||||||
a=0…. | …a=1 | a=0…. | …a=1 | a=0…. | …a=1 | a=0…. | …a=1 | ||||||||
((0 -> c) ? 0&c) -> (c) | ((1 -> c) ? 1&c) -> (c) | ?((1->c) ? 0 &c) -> (c) | ?((1->c) ? 1&c) -> (c) | ?((0->c) ? 0 &c) ->(c) | ?((1->c) ?1&c) ->(c) | ?((0->c) ? 0 &c) -> (c) | ?((1->c) ? 1 &c) -> (c) | ||||||||
|| | || | || | || | || | || | || | || | ||||||||
0 -> (c) | (с ? c) -> (c) | ?( с ? 0) -> (c) | ?(с ? c) -> (c) | 0 -> (c) | ?(с ? c) -> (c) | 0 -> (c) | ?(с ? c) -> (c) | ||||||||
c=0 | .c=1 | c=0 | .c=1 | c=0 | c=1 | c=0 | c=1 | c=0 | c=1 | c=0 | c=1 | c=0 | c=1 | c=0 | c=1 |
0->1 | 0->0 | 0->1 | 0->0 | 1->0 | 0->1 | 0->0 | 0->1 | 0->1 | 0->0 | 0->1 | 0->0 | 0->0 | 0->1 | 0->0 | 0->1 |
|| | || | || | || | || | || | || | || | || | || | || | || | || | || | || | || |
1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
?
Заменим вторичные связки первичными и упростим:
d v c v b v a
b=0 | b=1 | |
d v c v 0 v a | d v c v 1 v a | |
d=0 | d=1 | || |
1 v c v 0 v a | 0 v c v 0 v a | 1 |
|| | || | |
1 | c v a | |
a=0…. | …a=1 | |
c v 0 | c v 1 | |
|| | || | |
c | 1 | |
c=0 | c=1 | |
0 | 1 |
Задание 2
Для формулы в упрощенном виде из п.1 добавить в выражение не более, чем одну переменную (с использованием логической связки) так, чтобы получилась формула со следующим количеством фиктивных переменных:
d v c v b v a
а) 2 фиктивные переменные
d v с & (c v b v a)
б) 3 фиктивные переменные
с & ( d v c v b v a)
Задание 3
Указать посылки и заключение рассуждения. Затем, составить формулу, привести её к КНФ. К КНФ применить метод Д-П.
а) ? ? Проверить на выполнимость по методу Дэвиса-Патнема
? Уровень содержания в крови элементов высокий (a), что свидетельствует об обезвоживании организма (b) или печеночной недостаточности (c).
Уровень содержания элементов в крови низкий (? ? a), что указывает на нарушение функций печени (c) или сильное утомление (d).
Высокий уровень содержания элементов в крови (a) обозначает заболевание печени (c) или почек (e), если пациент не спортсмен (?? f). Пациент спортом не занимается (? ? f). Страдает ли пациент печеночной недостаточностью? (c)
Посылки -
| Заключение рассуждения -
|
Заменим все на первичные связки:
Приведем формулу к КНФ:
=
Так как в обоих дизъюнктах присутствует С (и отсутствует его отрицание), значит по правилу чистых литер формула является выполнимой.
б) ? ? Придумать формулу-?тавтологию ?из 3 переменных (в ней должны присутствовать вторичные связки) и проверить ее на общезначимость по методу Дэвиса-Патнема. Должны быть использованы все правила проверки по Д-П.
Инверсия формулы:
Заменим вторичные связки первичными (исключаем импликации):
Применим правило Де-Моргана:
Применим правило чистых литер:
Применим правило однолитерных дизъюнктов:
Сократим по идемпотентности:
Получили противоречие 
, значит инверсия формулы - противоречие, значит сама формула - общезначима.
Задание 4
Придумать формулу из 5 переменных (в ней должны присутствовать следующие операции: отрицание, импликация, дизъюнкция, конъюнкция, остальные операции по желанию) и применить к ней метод резолюций Робинсона.
Заменим вторичные связки на первичные:
Приведем к КНФ:
Начинаем исключать контрарные литеры.
Исключим a из первого и четвертого дизъюнкта:
Исключим b из первого и третьего дизъюнкта:
Исключим тавтологию:
Исключим d:
Задание 5
Из трех данных высказываний А, В, С постройте такое составное высказывание, которое ложно тогда и только тогда, когда все данные высказывания либо истинны, либо ложны.
| Составное высказывание - КНФ -
ДНФ -
|
