- •1. Элементы теории множеств
- •1.1 Множества. Основные понятия
- •1.2. Способы задания множеств
- •1.3. Операции над множествами. Диаграммы Венна
- •1.4. Свойства операций над множествами
- •1.5. Прямое (декартово) произведение множеств
- •1.6 Разбиения и покрытия
- •1.7. Замечание о мощности некоторых множеств
- •1.8 Представление множеств в эвм
- •1.9. Отношения
- •1.9.1.Определения
- •1.9.2 Бинарные отношения
- •1.9.3. Способы задания бинарных отношений
- •1.9.4 Свойства бинарных отношений
- •1.9.5. Отношение эквивалентности
- •1.9.5. Отношение порядка
- •1.9.6.1. Минимальные и максимальные элементы множества
- •1.9.6.2. Диаграммы Хассе
- •1.9.6.3. Принцип двойственности
- •1.9.7. Представление отношений в эвм
- •1.10. Соответствия. Функции. Операции. Отображения
- •1.10.1. Соответствия и их свойства
- •1.10.2 Функции и отображения
- •1.10.3. Инъекция, сюръекция и биекция
- •1.10.4. Композиция и суперпозиция функций. Способы задания функций
- •1.10.5. Представление функций в эвм
- •1.10.6. Операции
- •1.10.6.1. Способы задания операций
- •1.11. Алгебраические структуры
- •1.11.2. Замыкание и подалгебры
- •1.11.3. Гомоморфизм и изоморфизм
- •1.11.4. Алгебры с одной бинарной операцией
- •1.11.5. Алгебры с двумя бинарными операциями
- •1.11.6.Решетки
- •1.11.7. Булевы алгебры
- •2. Элементы математической логики и булевы функции
- •2.1. Операции над высказываниями
- •2.2. Логические операции (логические связки)
- •2.3. Элементарные булевы функции
- •2.3.1. Функции алгебры логики
- •2.3.2. Равносильность функций. Существенные и несущественные переменные
- •2.3.3. Реализация функций формулами. Суперпозиция функций
- •2.3.4. Подстановки и замены
- •2.3.5. Принцип двойственности
- •2.3.6. Нормальные формы в логике высказываний
- •2.3.6.1. Разложение булевых функций по переменным. Дизъюнктивно-нормалльная форма (днф)
- •2.3.6.2. Совершенная дизъюнктивная нормальная форма
- •2.3.7. Арифметические операции в алгебре логики. Полиномы Жегалкина
- •2.3.8. Монотонные функции алгебры логики
- •2.3.9. Функционально замкнутые классы
- •2.4. Полнота системы булевых функций. Теорема
- •2.5. Элементы логике предикатов
- •2.5.1. Определение предиката
- •2.5.2. Кванторы. Формулы логики предикатов
- •2.5.3. Равносильность формул
- •2.5.4. Предикаты на конечных областях. Логика одноместных предикатов
- •2.6. Операции над предикатами и кванторами
- •2.7. Построение доказательств в логике предикатов
- •1.6.2. Разбор решений задач по логике предикатов
- •1. Элементы теории множеств 3
- •1.1 Множества. Основные понятия 3
- •2.6. Операции над предикатами и кванторами 137
- •394026 Воронеж, Московский просп., 14
1.6.2. Разбор решений задач по логике предикатов
1. Установим истинность следующих логических выражений путем конкретизации. Для варианта 10 имеем следующее тождество:
Доказательство:
Для варианта 19 имеем следующую клаузу:
Для доказательства ее истинности избавимся от кванторов в обеих частях клаузы:
Последняя клауза верна в силу аксиомы порядка
2. Решения для второго задания приведем для всех вариантов. Ответы не трудно будет отыскать, если знать, каким образом были составлены логические выражения. Замена в соответствии с принципом двойственности предполагает одновременную перестановку местами всех заключений и всех посылок, а также замену обозначений.
Для варианта 1 из принципа двойственности по варианту 9
Для варианта 2
Для варианта 3. из принципа двойственности по варианту2. Для варианта 4 из принципа двойственности по варианту 10. Для варианта 5
Для варианта 6 из принципа двойственности по варианту 13. Для варианта 7 из принципа двойственности по варианту 12. Для варианта 8:
Для варианта 9 по клаузе 8 со следующими обозначениями
Для варианта 10.
Для варианта 11 из принципа двойственности
по варианту 5.
Для варианта 12 по клаузе 10 со следующими обозначениями:
Для варианта 13:
Для варианта 14: из принципа двойственности по варианту 16.
Для варианта 15: из принципа двойственности по варианту 8.
Для варианта 16: по клаузе 13 со следующими обозначениями:
Для варианта 17:
Для варианта 18:
Для варианта 19.
Для варианта 20
Для варианта 21:
Для варианта 22:
Для варианта 23:
Для варианта 24 из принципа двойственности по варианту 21.
Для варианта 25:
3. Для легенды варианта 2 практического задания п. 1.7 (3) введем следующие предикаты:
Области определения переменных:
Посылки.
Если некоторый х уважает некоторого у по причине некоторого z, то первый всегда окажет второму конкретную материальную помощь, если имеется определенная вероятность того, что у как-то компенсирует затраты х.
Из приведенной легенды следует, что бизнесмен уважает художника за его мастерство:
Понятно также, что бизнесмен будет иметь добрую репутацию мецената за то, что он помог художнику в организации выставки его картин:
Заключение: бизнесмен поможет художнику организовать выставку его картин:
Доказать истинность составленной из этих предикатов клаузы не составит большого труда.
Для легенды варианта 5 практического задания п. 1.7 (3) можно ввести следующие предикаты:
Области:
Посылки:
Все х извергают какие-то
Если некоторые х извергают какие-то у, то будет высокая урожайность.
Высокая урожайность всегда несет благо людям:
Заключение: то, что источником блага является господь бог, не противоречит исходным посылкам:
Доказательство очевидно.
4. Произведем трассировку работы ПРОЛОГ-программы «Родственные отношения» для первой цели варианта 12. Для этого имеющуюся программу дополним клаузой
Цель: 85)свекор (Петр, у).
Трассировка программы.
Из соответствующих фактов и правил составим противоречие.
Целевой дизъюнкт нейтрализуется предикатами под номерами 47, 44 и 65, когда переменные принимают конкретные значения
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики. М.: Наука,2002.
2. Нефедов В.Н., Осипова В.А. Курс дискретной математики. Мю: Изд-во МАИ, 1992.
3. Новиков Ф.А. Дискретная математика для программистов. СПб. Питер, 2001.
4. Москинова Г.И. Дискретная математика дляменеджера. М.: Логос, 2002.
5. Стол Р. Множества. Логика. Аксиоматическая теория. М.: Просвкщение, 1968.
6. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: Энергоатомиздат, 1989.
7. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Физматлит, 2001.
8. Акимов О.Е. Дискретная математика. Логика, группы, графы. М.: лаборатория базовых знаний, 2001.
СОДЕРЖАНИЕ
Введение 3