- •Вопросы по математической логике и теории алгоритмов (автф, 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. Неклассические логики
- •Предикатные логики
-
Алгоритм унификации
Определяет, унифицируемость множества атомарных формул, или нет, и если унифицируемо, то находим наиболее общий унификатор.
Дано W –множество атомарных формул.
-
k = 0, w0 = w, σ0 = ∑.
-
Если | wk | = 1 следовательно, множество W унифицируемо в качестве НОК = σk. Иначе находим Дk – множества рассогласований множества Wk.
-
Если Дk содержит переменную xk и терм tk не содержащий xk, то переходим к 4. иначе – остановка, W не унифицируемо.
-
σk+1 = σk {tk/xk}, Wk+1 =Wkσk+1, k →k + 1 переходим к шагу 2.
Теорема: если W унифицируемо, то алгоритм унификации закончит работу на втором шаге и последняя подстановка σk является НОУ. |
Пример.
W = { P ( z, x, F2(F1(y))), P(z, F2(z), F2(n))}
1. W0 = W, σ0 = ∑.
2. | W0| ≠ 1, тогда Дk = {c, z}
3. 4. σ1 = σ0, {c/z} = {c/z}
W1 = {P (e, x, F2(F1(y))), P(e, F2(e), F2(n)}
Следовательно 2 | W1 | ≠ 1, тогда Дk = {x, F2(e)}.
Вопрос 14.
Литера сигнатуры : атомарная формула или ее отрицание.
Дизъюнкт сигнатуры : литера или дизъюнкт литера сигнатуры
А;… A- дизъюнкт в ИВ
А, A - атомарные формулы (дизъюнкт сигнатуры )
P(c1x1*h (y,z)) h(g,(x),y)z
Ф-дизъюнкт сигн-ы вида
1 …n X или 1 …n ,
где 1 – атомарные форм-ы сигн-ы
Пусть - НОУ для {1 ,…,n }
Тогда 1 наз-ся ??????? формулы Ф
Ф = P(x) P(F(y)) P2(x)
= {F(y) / x}
Ф= P(F(y)) P2(F(y))
Ф1,Ф2 – два дизъюнкта, не имеющих общих переменных.
L1- литера в Ф1
L2`=L2- литера в Ф2
Если L1 и L2 имеют НОУ , то дизъюнкт, получ-ый из Ф1 Ф2 вычерчиванием L1 и L2 наз. бинарной резольвентой дизъюнктов Ф1 и Ф2
L1 и L2 – отрезаемые литеры
Если Ф1= L1 , Ф2 = L2 , то бинар.рез. Ф1 и Ф2 = 0
Если Ф1 и Ф2 имеют общие переменные, то после замены общих переменных в Ф2 на новые обр. ???? Ф2
Бин. рез. Ф1 и Ф2 = бин. рез. Ф1 и Ф2`
Ф1 = P1(x) P2(y)
Ф2 = P1(c) P3(x)
Ф2` = P1(c) P3(y)
L1 = P1(x)
L2 = P1(c), L2 = ???(c) P1(c) = L2`
= {c/x}
Бин. рез. Ф1 и Ф2 = P1(с) P2(с) P1(c) P3(y) = P2(с) P3(y)
Резольвента дизъюнктов Ф1 и Ф2
(res (Ф1,Ф2)):
- бин. рез Ф1 и Ф2
- бин. рез. склейки Ф1 и Ф2
- бин. рез. Ф1 и склейке Ф2
- бин. рез. склейки Ф1 и склейки Ф2
Ф1 = P(x) P(F(y)) P1(F1(y))
Ф2 = P(F(F1(c1))) P2(c2)
res (Ф1,Ф2) = ?
склейка Ф1:Ф1` = P(F(y)) P1(F1(y))
L1 = P(F(y))
L2 = P(F(F1(c1)))
res (Ф1`,Ф2) = P1(F1(F1(c1))) P1(c2)
S – мн-во дизъюнктов.
Результативным выводом формулы Ф и S наз. полслед-ть дизъюнктов Ф1, … , Фк, где Фк = Ф
и каждый дизъюнкт Фi или принадл. S, или явл-ся резольвентой дизъюнктов, предшествующих Фi.
Ф(x1,…,xn)
x1…xn Ф(x1,…,xn) универсальное замыкание формулы Ф (x1,…,xn)
Теорема о полноте метода резолюций для ИП
Если S – мн-во дизъюнктов или , то мн-ва универсальных замыканий формулы из S противоречиво сущ. рез. вывод из S.
16.Понятие алгоритма, основные признаки алгоритма. Вычислимые функции и тезис Чёрча.
Определение: Алгоритм на интуитивном уровне - это последовательность шагов, применяемых для достижения цели.
Основные признаки алгоритма:
-
Последовательность элементарных шагов.
-
Детерминированность - после каждого шага ясно, что делать дальше.
-
Достижимость цели.
-
Массовость- применимость к широкому классу задач.
Определение: Под частичной функцией будем понимать отображение f: X→w, где для некоторого . О частичной функции f: X→w, где , будем говорить как о вичислимой, если существует алгоритм ß, действующий на , не применимый к n-кам X, для которого ß()=f(), X.
Определение: Частичная функция f: X→w, где называется нормально вычислимой, если существует такой нормальный алгорифм £=<A,S>, что 0, 1, A, для любой n-ки <m1,…,mn> w имеем <m1,…,mn> X ↔£ применим к записи <m1,…,mn> и £(α)=f(α) для αX. Такой алгорифм £ будем называть нормальным алгорифмом, вычсляющим функцию f.
Принцип нормализации для частичных функций будет теперь гласить: класс вычислимых частичных функций совпадает с классом нормально вычислимых функций.
Тезис Чёрча: Класс рекурсивных функций и класс функций, вычисленный с помощью машин Тьюринга совпадают.