Изучение функций в курсе математики (стр. 1 из 4)
Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
Государственное образовательное учреждение
высшего профессионального образования
«Комсомольский-на-Амуре государственный
технический университет»
Факультет компьютерных технологий
Кафедра «Информационных систем»
РАСЧЕТНО-ГРАФИЧЕСКОЕ ЗАДАНИЕ
по дисциплине «Дискретная математика»
Студент группы 9-ПИ Шикер С.А.
2010
Задача 1. Представьте заштрихованные области диаграммы Эйлера-Венна (рис.1) максимально компактным аналитическим выражением, в котором используется минимальное количество операций и букв.
рис.1
Решение
На рис.2 изображена диаграмма Эйлера-Венна, заштрихованные области которой соответствуют выражению: C∩D. На рис.3 изображена диаграмма Эйлера-Венна, заштрихованные области которой соответствуют выражению: C/B. На рис.4 изображена диаграмма Эйлера-Венна, заштрихованные области которой соответствуют выражению: C∩А.
Рис. 2 Рис. 3 Рис.4Чтобы получить необходимое множество (рис. 1) необходимо между этими тремя выражениями поставить операцию объединение. В результате получаем:
(C∩D) È (C/B) È (C∩A)
Задание 2. Записать высказывание в виде формулы логики высказываний, используя пропозициональные (логические) переменные для обозначения элементарных высказываний, т.е. таких, которые уже не могут быть построены из каких – либо других высказываний:
Неверно, что если Сидоров - не кассир, то Сидоров убил кассира; следовательно, фамилия кассира – Сидоров.
Решение
Введем обозначения:
a – «Сидоров – кассир»
b – «Сидоров убил кассира»
Исходное высказывание содержит связку «если …, то …», которая соответствует импликации, а так же связку «Неверно, что…» и предлог «не», что соответствует отрицанию. Формула имеет вид:
→ aЗадание 3. Используя равносильности логики высказываний, упростить исходную формулу
Для исходной формулы и упрощенной построить таблицу истинности.
Решение.
Введем обозначения: F1 =
F2 =
Построим таблицу истинности для F1 и F2:
| № | a | b | c |  |  |  |  | F1 |  | F2 |
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
| 2 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
| 3 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
| 4 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 5 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 6 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 |
| 7 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Столбцы, соответствующие F1 и F2, совпадают. Это значит, что аналитические преобразования исходной формулы верны.
Задание 4. Ниже приведена клауза
Необходимо выяснить при помощи алгоритма Вонга и метода резолюции является ли клауза теоремой.
Решение
Метод Вонга.
Построим дерево доказательства.
 |
 |
 |
 |
 |
Все ветви дерева заканчиваются клаузами, в которых по обеим сторонам символа
присутствует одна и та же буква. Следовательно, логическая теорема верна.Метод резолюция.
Необходимо преобразовать клаузу таким образом, чтобы после знака
получился ноль, при этом избавимся от импликации. 
ǾВыпишем по порядку все посылки и далее начнем их «склеивать».
| 1 |  | 7 | (2;3)А |
| 2 |  | 8 | (1;5)  |
| 3 |  | 9 | (7;4)  |
| 4 |  | 10 | (9;6)B |
| 5 |  | 11 | (10;8)Ǿ |
| 6 |  |
Иначе, порядок «склеивания» можно представить в виде цепочки равносильных преобразований:
