- •Вопросы по математической логике и теории алгоритмов (автф, III семестр)
- •Вопрос 1. Формальные исчисления. Выводы в исчислении. Теорема исчисления. Разрешимые и непротиворечивые исчисления.
- •Вопрос 2 Исчисление высказываний ив. Теорема о замене
- •Вопрос 3. Основные эквивалентности (ив) формулы ,аксиомы и правила вывода. Понятия док-ва ,дерево док.. Теор. О дедукции.
- •4.Cимантика исчисление высказываний.Непротиворичивость ив.Таблицы истиности.Общезначимые и выполнимые формулы.Теорема о полноте.РазрешимостьИв.
- •5.Семантическое дерево. Алгоритм Квайна и алгоритм редукции проверки общезначимости формул.
- •Вопрос 6. Метод резолюций в ив. Правило согласия. Метод резолюций для
- •Вопрос 7. Алгебраические системы. Формулы сигнатуры Подформулы. Свободные и связанные переменные. Предложения. Истинность формулы на элементах алгебраической системы.
- •Вопрос 8. Общезначимые и выполнимые формулы. Теорема об общезначимости формул сигнатуры σ, соответствующих общезначимым формулам ив. Выполнимое множество формул. Теорема компактности.
- •Вопрос 9.
- •Теорема о существовании модели. Для любого непротиворечивого мн-ва формул г сигнатуры
- •Вопрос 10. Основные эквивалентности .
- •Вопрос 11. Элементарные теории. Сис-ма аксиом теории ….
- •Вопрос 12. Сис-ма аксиом арифметики Пеано…..
- •#13. Подстановка сигнатуры σ. Композиция подстановок. Унификатор и наиболее общий унификатор. Алгоритм унификации. Теорема об алгоритме унификации.
- •Метод резолюции в исчислении предикатов
- •Алгоритм унификации
- •Вопрос 14.
- •16.Понятие алгоритма, основные признаки алгоритма. Вычислимые функции и тезис Чёрча.
- •Вопрос 17. Определение машины Тьюринга
- •Вопрос 18. Основные машины Тьюринга.
- •Вопрос 19. Вычисление функций на машинах Тьюринга.
- •Вопрос 20. Понятие примитивно рекурсивной функции. Основные примеры. Простейшие прф:
- •Вопрос 21.Примитивно рекурсивные отношения, основные преобразования над ними…
- •Вопрос 22. Нумерация n-ок натуральных чисел примитивно рекурсивными ф-ями.
- •Вопрос 23. Частично рекурсивные и рекурсивные функции. Теорема об элиминации.
- •Вопрос 24. Вычислимость чрф на машинах Тьюринга.
- •Вопрос 25. Частичная рекурсивность функций , вычислимых на машинах Тьюринга.
- •Вопрос 26. Универсальное чрф. Теорема роб универсальности. Теорема Райса.
- •Вопрос 27. Геделевская нумерация формул, аксиом и правил вывода исчисления предикатов. Рекурсивно перечислимые множество…
- •Вопрос 28. Временная и ленточная сложности мт, вычисляющей заданную функцию. Теоремы о верхней границе сложности вычислений. Теорема об ускорении
- •Вопрос 29. Эффективности вычислений:
- •Метод сводимости:
- •Вопрос 30.Понятие переборной задачи. Универсальные переборные задачи. Примеры.
- •Вопрос 31. Основные алгоритмы сортировки и их сложность.
- •Вопрос 32. Детерминированные и недетерминированные конечные автоматы, связь м/у ними.
- •Вопрос 33. Неклассические логики
- •Предикатные логики
Вопрос 1. Формальные исчисления. Выводы в исчислении. Теорема исчисления. Разрешимые и непротиворечивые исчисления.
I=<A, F, Ax, R> - форм. исчисление. A-алфавит (мн-во символов), FS – мн-во формул, АхF-мн-во аксиом; R={R1…Rn}-конечное мн-во отношений на мн-ве F.
(1…m,)Ri непосредственное следствие формул (1…m) по правилу i.
i , R1Rn – правила вывода
Вывод в исчислении I – последовательность формул 1…m, где каждая i является аксиомой или получается из предыдущих ф-л по нек. правилу вывода.
наз. теоремой исчисления I (выводимой или доказуемой I), если вывод 1…m,
Примеры:
1. F - мн-во повествовательных предложений русского языка. Ax – мн-во истинных в данный момент предложений вида «подл + сказ»
Правила вывода:
2. F – нек. мн-во программ. Ах – мн-во «простых» простых программ, которые оканчивают работу за конечное время с любыми данными
Правила вывода:
Расширенное исчисление – сущ. алгоритм, который для любой ф-лымн-ва F (F) позволяет за конечное число шагов проверить выводимость ф-лы в данном исчислении.
Непротиворечивое исчисление – если все ф-лы доказуемые.
Вопрос 2 Исчисление высказываний ив. Теорема о замене
Используя понятие формального исчисления,определим ИВ.Алфавит ИВ состоит из букв A,B,Q,R,P и др,возможно с индексами (пропозициональные переменные) ,лог.символов(связок),,,, (симв.следования),а также вспомогат.сиволов (),.Мн-во формул ИВ определяется индуктивно: а)все пропозиц.переменные явл.атомарными формулами ИВ; б)если , -формулы ИВ,то,, ,-формулы ИВ;в)выражение явл.формулой ИВэто м!б!установлено с пом.пунктов а)и б).Схема аксиом:. Правила вывода:1)Г;Г/Г. 2)Г/Г.3) Г/Г.4)Г/Г.5) Г/Г.6)Г, ;Г,;Г/Г.7)Г,/Г(). 8)Г;Г/Г.9)Г,/Г.10)Г;Г/Г.11)Г1,,,Г2/Г1,,,Г2. 12)Г/Г,.
1…,n -формула выводима из формул 1,…,n (секвенция ИВ).1,…,m -лин.док-во. Дерево секвенций:1)если S-секвенция,то S-дерево секвенций.2)если Do,…,Dn-деревья,S-секвенция,то (Dо,…,Dn)/S-дерево секвенций. Дерево D наз.док-вом секв.S,если D явл.док-вом,а S-заключительная секв.дерева D. Теорема:Секв.S имеет док-во в виде дереваS-теорема ИВ.Формула наз.доказуемой,если доказуема секв..Теорема о дедукции:Если Г,,то Г,где Г-набор нек.формул 1,…, n.Следствие:секв. 1,…, n док-мадок-ма формула 1(2…(n)…).
Вопрос 3. Основные эквивалентности (ив) формулы ,аксиомы и правила вывода. Понятия док-ва ,дерево док.. Теор. О дедукции.
Алфавит.
-проиозициональные переменные Q0,Q1,…,Qn,… ; A,B,C,…
-логические символы или связки Λ,v,→, ┐,├- символ следования
-вспомогательные символы:( ),
Фор-лы ив – слово алфавита ив ,кот. Опр-ся по инд.:
1)любая проп. перем. явл. ф-лой(анотамарная или элементарная ф-ла) An,Q7
2)если φ,ψ –формулы ,то (φ Λ ψ),( φVψ), ( φ→ψ), ┐φ – ф-лы
Секвенции ИВ
φ 1 ,…,φn├ ψ,Г├ ψ
-Г├(из Г можно вывести противор.инф)
-├ общее противоречие ; φ 1 ,…,φn –посылки,ψ- заключение;схема аксиом: φ├ φ
Правила вывода:
1) (Г├ φ;Г├ ψ)/ (Г├(φ Λ ψ)) ; 2) (Г├(φ Λ ψ))/ (Г├φ) ; 3) (Г├(φ Λ ψ))/ (Г├ ψ) ;
4) (Г├ φ)/( Г├( φVψ)) ; 5) (Г├ ψ )/( Г├( φVψ)) ; 6) Г,φ├ ψ;Г,x├ ψ;Г├ φVψ/Г├ ψ;
7) Г,φ├ ψ/ Г├( φ→ψ) ; 8) Г├φ, Г├( φ→ψ)/ Г├ ψ ; 9)Г, ┐φ├/ Г├φ ; 10) Г├φ; Г├ ┐φ/ Г├;
11) Г1, φ, ψ,Г2├x/ Г1, ψ,φ, Г2├x ; 12) Г├φ/ ψ ├ φ;
Дерево секвенций
1)если S – секв. ,то S – дерево секвенций
2)если D0,…,Dn-деревья ,S –секв., то D0,…,Dn/S-дерево секвенций
Дерево D раз. Докозат. Если все начальные секвенции явл. аксиомами,а переходы осуществ. По правилам вывода.
Теорема о дедукции. Если Г,φ├ ψ,то Г├( φ→ψ) (правило 7) следствие секв. φ 1 ,…,φn├φ доказуема дказуема ф-ла (φ1→( φ2→…( φn→ ψ)…))