- •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. !!! Задачи, не решаемые компьютерами. Тест Тьюринга для систем искусственного интеллекта.
23. Формальная арифметика. Непротиворечивость формальной арифметики. Теорема Генцена.
Формальная арифметика – это теория, в которой имеются следующие объекты:
1)Предметы констант: 0
2)Три функтора:
Двухместные + •
Одноместные ‗
3)Двухместная предиката =
4)термы t1, t2…….
5)предикаты Р( ), Q( ) …
В формальной арифметики определены следующие аксиомы:
(P(o)& x(P(x) → P(x‘))) → x P(x)
t1‘=t2‘ → t1=t2
┐(t1‘=0)
t1=t2→ (t1=t3→t2=t3)
t1=t2→t1‘=t2‘
t1+0=t1
t1+t2‘= (t1+t2)‘ |
t1=5 t2‘=7 |
5+7=(5+6)‘ |
t•0=0
t1•t2‘=t1•t2+t1
Непротиворечивость формальной арифметики.
Метод математической индукции входящей в качестве аксиомы в формальную арифметику может быть расширен за счет применения его к множеству трансфинитных чисел.
Финитные числа – это натуральные, трансфинитные идут за натуральными.
Теорема Генцена 1936
Непротиворечивость формальной арифметики доказывается в более широкой формальной теории, содержащей арифметику и принцип трансфинитной индукции.
24. Неклассические логики: модальная, темпоральная, нечеткая.
Нечеткая логика допускает континуальное число истинностных значений для высказываний. В простейшем случае эти значения принадлежат отрезку [0,1] действительных чисел. Иначе говоря между значением 0, соответствующим классическому ┴ (ложь) и 1, или ┬ (истина), имеем несчетное число промежуточных истинностных значений α є (0,1).
Нечеткая логика широко используется в современной прикладной математике и технических науках.
Пусть Е некоторое фиксированное множество и М=[0,1] – отрезок действительных чисел.
Нечеткое подмножество А множества Е – это множество пар вида
{(x, μА(x)): x €E}, где μА : Е→М – функция.
Множество нечетких множеств не является булевой алгеброй, следовательно логика построенная на нечетких множествах будет неклассической.
Модальная логика
Модальная логика строится на основе логики высказываний за счет добавления новых законов, позволяющих выражать отношение тех или иных высказываний к окружающей действительности. Как правило, это суждение о возможности или необходимости чего-либо.
Различают три типа модальностей, каждый из которых подразделяется на виды:
Алетические модальности. Это высказывания, содержащие такие виды модальности, как «необходимо», «возможно», «невозможно», «случайно».
Деонтические модальности. Это модальности с характеристиками действий и поступками людей в обществе. Например, «обязательно», «разрешено», «запрещено», «безразлично».
Эпистемические модальности. Характеристики наших знаний. Можно назвать такие виды модальности этого типа, как «доказано», «опровергнуто», «не доказано», «не опровергнуто», «знает», «верит», «убежден», «сомневается».
Темпоральная (временная) логика – это модальные логики. Они строятся добавлением к логике высказываний новых знаков, отражающих свойства времени. Например процесс выпадения дождя. Это процесс продолжается некоторое время, а затем
прекращается. Но предположим, что это происходит не внезапно, а постепенно. Пусть А……….┐А, иллюстрирует что на определенном отрезке времени вначале определенно идет дождь(А), потом определенно не идет дождь (┐А), а между этими временными точками находится переходная область, когда, капает небольшое количество капель. В этой области А ни истинно, ни ложно. Т. о., появляется еще третье значение высказывания: «ни истинно, ни ложно»; или «и истинно, и ложно»; или «неопределенность».