- •Введение
- •Занятие 1. Основные понятия математической логики. Исчисление высказываний
- •1.1. Введение
- •1.2. Исчисление высказываний
- •1.2.1. Основные логические функции исчисления высказываний
- •1.2.2. Дизъюнктивно-нормальная и конъюнктивно- нормальная формы
- •Контрольные вопросы и упражнения
- •Занятие 2. Перевод высказываний естественного языка на язык исчисления высказываний
- •Контрольные вопросы и упражнения
- •Занятие 3. Логический вывод в исчислении высказываний
- •3.1. Силлогизмы
- •3.2. Метод прямого преобразования
- •3.3. Метод семантических таблиц
- •3.4. Метод резолюций
- •Метод насыщения уровня
- •3.4.2. Стратегия вычеркивания
- •Контрольные вопросы и упражнения
- •Занятие 4. Исчисление предикатов
- •4.1. Основные понятия
- •4.2. Кванторные операции
- •4.3. Равносильности логики предикатов
- •4.4. Предваренная, сколемовская нормальная и сколемовская стандартная формы
- •Контрольные вопросы и упражнения
- •Занятие 5. Перевод высказываний естественного языка на язык логики предикатов
- •Контрольные вопросы и упражнения
- •Занятие 6. Логическое следствие в исчислении предикатов
- •6.1. Метод семантических таблиц
- •6.2. Процедура вывода Эрбрана
- •6.3. Принцип резолюции
- •6.3.1. Алгоритм унификации
- •6.3.2. Метод резолюций в исчислении предикатов
- •Контрольные вопросы и упражнения
- •Занятие 7. Теория алгоритмов
- •7.1. Вычислимые функции, частично-рекурсивные и общерекурсивные функции. Тезис Черча
- •7.2. Машинная математика. Машина Тьюринга.
- •7.3. Тезис Тьюринга (основная гипотеза теории алгоритмов)
- •7.4. Нормальные алгоритмы Маркова
- •Занятие 8. Обзор неклассических логик
- •8.1. Нечеткая логика
- •8.2. Модальные логики
- •8.3. Временные (темпоральные) логики
- •Заключение
- •Библиографический список
- •Оглавление
- •394026 Воронеж, Московский просп., 14
Контрольные вопросы и упражнения
Задание 1
Какие из следующих выражений являются предикатами. Выделите среди предикатов высказывания.
1. Число - простое;
2. ;
3. ;
4. ;
5 Все подобные треугольники равны;
6 ;
7. Все четные числа делятся на число ;
8. Все четные числа делятся на 2;
9. 8 – нечетное число;
10. Имеется бесчисленное множество различных простых чисел;
11. Число не является простым.
Задание 2
Пусть переменные в нижеследующих выражениях выбираются из множества действительных чисел, а алгебраические знаки имеют свои обычные значения. Определить, истинны ли эти выражения:
1. ;
2. ;
3. ;
4. ;
5. ;
6. ;
7. ;
8. ;
78
9. ;
10. ;
11. ;
12. .
Задание 3
Для действительных чисел записать на языке предикатов предложения, выражающие:
1. коммутативность сложения;
2. коммутативность умножения;
3. ассоциативность сложения;
4. ассоциативность умножения;
5. дистрибутивность умножения относительно сложения.
Задание 4
Выразить области истинности предиката через области истинности предикатов и , если:
1. ;
2. ;
3. ;
4. ;
5. .
Задание 5
Указать свободные и связанные переменные:
1. ;
2. ;
3. ;
4. ;
5. .
79
Задание 6
Пусть все приведенные предикаты определены на множестве действительных чисел. Изобразить графически области изменения свободных переменных, при которых следующие предикаты принимают значение “истина”:
1. ; 2. ;
3. ; 4. ;
5. ; 6. .
Задание 7
Найти отрицание следующих формул.
1. ;
2. ;
3. ;
4. ;
5. ;
6. ;
7..
Задание 8
Привести следующие формулы логики предикатов сначала к предваренной нормальной форме (ПНФ), затем к сколемовской нормальной форме (СНФ) и стандартной сколемовской форме (ССФ).
1. ;
2.;
3. ;
4.;
5. ;
6.;
7. ;
80
8.;
9.;
10.;
11.;
12.;
13.
;
14.;
15.;
16. ;
17. ;
18. ;
19. ;
20. ;
21. ;
22. ;
23. ;
24. ;
25. ;
26. .
Задание 9
Пусть и два одноместных предиката, определенных на множестве таким образом, что высказывание - всегда истинно. Доказать, что высказывание - всегда ложно.
81
Задание 10
Пусть обозначает “ – простое число”, – “ – четное число”, – “ – нечетное число”, – “ делится на ”. Дать словесную формулировку следующим формулам:
1.;
2. ;
3.;
4.;
5. ;
6. ;
7. ;
8. ;
9. ;
.
Задание 11
Даны утверждения – “число делится на 3”, – “число делится на 2”, – “число делится на 4”, – “число делится на 6”, – “число делится на 12”. Укажите, какие из следующих утверждений истины, а какие ложные.
1.;
2.;
3.;
4. ;
5.;
6.;
7..
82
Задание 12
Доказать следующие равносильности.
1. ;
2. ;
3. ;
4. ;
5. ;
6. ;
7. ;
8. ;
9. ;
10. ;
11. .
Задание 13
Какие из заданных формул являются общезначимыми?
1.;
2.;
3.;
4.;
5.;
6.;
7.;
8.;
9.;
10.;
11.;
12.;
13.;
83
14.;
15.;
16.;
17.;
18.;
19.).
Задание 14
Доказать тождественную ложность формул.
1.;
2./