- •1. Предмет и задачи науки логики. Логика и мышление. Логические парадоксы. Силлогизмы.
- •2. Основные этапы развития логики. Классическая и современная логики.
- •3. Понятие математической логики. Ее место и роль среди других наук.
- •4. Понятие формализации. Алфавиты, слова, языки.
- •5. Формальные теории: определение, построение.
- •6. Вывод в формальной теории. Интерпретация, полнота и непротиворечивость формальной теории.
- •7. Алгебра высказываний. Пропозициональные формулы.
- •8. Интерпретация, тавтология, противоречие. Логическое следование и логическая эквивалентность.
- •9. Удаление и восстановление скобок в ПФ
- •10. Законы логики.
- •11. Понятие теоремы. Основная теорема логического вывода и ее доказательство.
- •12. Основная теорема логического вывода
- •13. !!! Ошибочные доказательства и парадоксы.
- •14. Дедуктивные и индуктивные доказательства. Примеры индуктивных доказательств.
- •15. Силлогизмы с точки зрения формальной теории.
- •16. Формальная теория для исчисления высказываний.
- •17. Метод резолюций в логике высказываний.
- •18. Синтаксис и семантика языка логики предикатов. Формулы логики предикатов.
- •19. Ограниченные предикаты
- •20. Метод резолюций в логике предикатов
- •21. Формальная теория для исчисления предикатов
- •22. !!! Диаграммы Венна (Эйлера) и их использованиие.
- •23. Формальная арифметика. Непротиворечивость формальной арифметики. Теорема Генцена.
- •24. Неклассические логики: модальная, темпоральная, нечеткая.
- •25. Логическое программирование.
- •26. Теорема Геделя о неполноте и суть ее доказательства.
- •27. Понятие алгоритма. Свойства алгоритмов. Способы записи алгоритмов.
- •28. Сложность алгоритма. Оценки сложности: двусторонняя, односторонняя. Классификация алгоритмов по сложности.
- •29. Классы сложности P, NP. Трудно решаемые задачи и способы их решения
- •30. Понятие алгоритмической системы. Понятие вычислимости.
- •31. Частично-рекурсивные функции. Тезис Черча.
- •33. Машина Тьюринга: определение, построение, использование. Тезис Тьюринга.
- •34. !!! Примеры использования машины Тьюринга.
- •35. !!! Задачи, не решаемые компьютерами. Тест Тьюринга для систем искусственного интеллекта.
20. Метод резолюций в логике предикатов
Если формула A не содержит предикатов и знаков операции, то метод резолюции не требует существенных изменений.
Если формула А содержит кванторы, то ее надо привести к предварительной формуле (т.е. кванторы , не перемениваются, а встречаются группами и все «вынесена влево»), а затем устранить кванторы, вводя скалемовские функции. При этом появляются знаки операции. Затем полученную формулу приводят к конъюнктивной нормальной форме и ищут резольвенты для дизъюнктов.
Правила замены термов и понятие унификации.
Замена – это пара вида <x\t> где х-переменная, t- терм
Применение замены:
X<x\t>=t если х переменная
A<x\t>=А если а константа
F(t1…t2)<x\t>=f(t1<x\t>…tn<x\t>)
Унификация двух последовательностей термов t1…tn и тау1…тауН это замена tj<x\t>=тауj<x\t> при (j=1…n)
Резольвента для дизъюнктов
Di=Di v P(t1) Di=Di v !P(t2) ищутся помощью унификации термов T1 и t2 :
21. Формальная теория для исчисления предикатов
Исчисление предикатов - это формальная теория, получаемая за счет добавления к исчислению высказываний новых знаков, понятия терма, новых типов формул и новых правил вывода.
1.Дополнения в алфавит
Знаки индивидуальных переменных
Знаки индивидуальных констант
Знаки предикатов
( |
)( |
) |
( |
)( |
) |
Знаки операций |
|
|
|
|
|
( |
)( |
) |
( |
)( |
) |
Логические знаки (кванторы) |
. |
||||
2. Термы
Переменные x1,…xn… — это термы;
Константы с1,с2….сn,… – это термы;
Если ( )( |
) — n-местный знак операции и t1,…tn термы, то ( )( |
) терм. |
3. Формулы |
|
|
- |
|
|
- |
|
|
- |
|
|
- |
|
|
4.Дополнительные аксиомы
-
-
5.Дополнительные правила ввода
-
-
-
Приведенный язык исчисления предикатов образует теорию, которую называют узким исчислением предикатов, или чистым исчислением предикатов
Появление в теории аксиом, разрешаюших «навешивание квантов» по знакам операции или предикатов, приводит к исчислениям высших порядков. Исчисление предикатов – это теория первого порядка
Расширение узкого исчисления предикатов за счет добавления новых знаков индивидуальных констант, операций (знаков функций, знаков операций) , знаков предикатов, новых аксиом, связывающих новые знаки, и новые правила вывода называется часто прикладным исчислением предикатов.
Полнота и непротиворечивость исчисления предикатов.
Теорема2.6 Исчисление предикатов –полная теория
Теорема2.7 Исчисление предикатов – непротиворечивая теория