- •Вопросы по математической логике и теории алгоритмов (автф, 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. Неклассические логики
- •Предикатные логики
Вопрос 11. Элементарные теории. Сис-ма аксиом теории ….
Элементарные теории. Т-мн-во предл.сигн. ∑ 1 для кот. из Т├φ ,
Следует φ Т. Т-элементарная сигн. Теоремы Σ z c Т , z ├ Т
Z – система аксиом для теории Т. Примеры:
1) Σ={.} z={Vx Vy Vz((xy)z≈x(yz))} z├ Т – теория всех полугрупп
2) Σ={≤} Z- рефл. транз. z├Т Г^Г –теория плотного линейного прядка
3) =<A,Σ>, |A|< ω |Σ|<ω – Все взаимо-я записываются одной
аксиомой φ. φ├ Т –теория алг.системы ,
Т=Тh ()={φ|φ- предл. |φ} Непрот. Теория Т наз. полной если для люб. предл. φ сигн. Σ, φ Т или ¬φ Т, ,Th()-полная теория. Vx Vy (xy≈yx) Tо ¬Vx Vy (xy≈yx) ↑ неполная теория
Полная теория Т=Th() Теорией Т наз.λ- категоричной(где λ-нек. кардинал), если все модели ╞Th имеющие мощность λ изоморфны
≈, если сущ. φ :A↔B, для кот. 1)P Σ : ╞ P(a1……an)<=> ╞P(φ(a1)… φ(an)) 2) f Σ: ╞f (a1……an)≈a<=>╞f (φ(a1)……φ(an))≈φ(a). Теорема: Т λ- категорична (≥ω),
и Т∞=Т U { x1,… xn (^ ¬xi≈xj)| n ω} непрот.=> T∞-полная теорема Т∞={φ| T∞├ φ} φ-прел. Тnun, Σ={≤}-рефл. антисим. транзит. сравнимость, полность x y z ≤
¬ xVy (x≤ y)
¬ Vy (y≤ x) Следствие: (Тmn)’∞-полная теория
Док: (Tmn)’∞ , ω –категорична (=> полнота)
╞ (Tmn)’∞ ╞ (Tmn)’∞ |a2 |a0 | a’1 | a1 | a’2 ≤
A={an , | nω}
A={an , | nω}
b’2 b0 b1 b’1 b2
φ:A↔B a; ≤ aj <=> φ(ai)≤ φ(aj) , φ(a0)=b0 , φ(a1)=b’1 , φ(a’1)=b1
φ(a2)=b’2 , φ(a’2)=b2 . φ: .
Вопрос 12. Сис-ма аксиом арифметики Пеано…..
Системы Дедекинда – Пеано.
Множество натуральных чисел можно определить двояко:
-
Исходя из Ø последовательно выражать натуральные числа, как множества, состоящие из предыдущих натуральных чисел;
-
Задавать алгебраическую систему N = <N,0, ´>, удовлетворяющую системе аксиом Дедекинда – Пеано.
Теорема Дедекинда – Пеано: Любые две системы Дедекинда – Пиано изоморфны.
По индукции в системе N однозначно определимы двухместные операции сложения и умножения. <N,0,´,+,·>
#13. Подстановка сигнатуры σ. Композиция подстановок. Унификатор и наиболее общий унификатор. Алгоритм унификации. Теорема об алгоритме унификации.
-
Метод резолюции в исчислении предикатов
Подстановка сигнатуры ∑ называется множество вида {t1/x1, ..., tn/xn} при этом xi ≠ xj, xi ≠ ti. ∑ - - пустая подстановка.
Пример.
{ F1(z)/x, y/z} - подстановка сигнатуры ∑ = { F11(1) }.
{ C1/x, F2(9)/y, F1 ( F2 (C1))/z} – подстановка сигнатуры ∑ = {C1(0), F2(1), F1(1), C1(0)}.
Пусть Ө = {t1/x1, ..., tn/xn} подстановка сигнатуры ∑. W Ө - множество получаемое из W с помощью одновременной подстановки вместо x1, ..., xn термов t1, ..., tn.
Пример.
Ө = { C1/x, F(C2)/y, y/z }
t = F1 (x, y, z), тогда t Ө = F1(C1, F(C2), y)
Q = F (x, C1, z)
Q Ө = F1 (C1) ≈ F1(C1, C1, y)
Ө = {t1/x1, tn/xn}
λ = { g1/y1, ... , gn/yn}
Ө λ = { t1, λ/x1,..., tnλ/xn, g1/gn,..., gn/yn}
Если yi принадлежит { x1 ... xn}, то gi/yi - вычёркиваем
Если tiλ = xi , то ti λ/xi – вычёркиваем
Пример.
Ө = { F1(y)/x, z/y}; λ = {C1/x, C2/y, y/z}
Ө λ = {F1(y)λ/x, zλ/y, C1/x, C2/x, y/z} = {F1(C2)/x, y/y, y/z} = {F1(C2)/x,y/z}
Өz = Ө любая Ө
Ө ( λ μ ) = (Ө λ ) μ для любых μ, λ, Ө
Определение: пусть Ф = {φ1, .... ,φn} – множество формул сигнатуры ∑; Ө - подстановка сигнатуры ∑. Ө называется унификатором множества Ф, если φ1 Ө = … = φn Ө.
Пример.
Ф = {P (C1,y), P(x1) = C2} можно заменять только переменные
Ө = {C1/x, F(C2)/y} – унификатор множества Ф
Определение: множество формул называется унифицируемым, если для него есть унификатор.
Определение: унификатор σ для множества {φ1, .... ,φn} называется наиболее общим унификатором (НОУ), если для любого другого унификатора Ө существует λ такая что Ө = σλ.
Определение: пусть W = {φ1, .... ,φn} – непустое множество атомарных формул. Множеством рассогласований множества W называется множество термов t1, ..., tn, где ti входит в φi и начинается с символа стоящего на первой слева позиции в φi; на которой не для всех формул φ1, .... ,φn находится одинаковый символ.
Пример.
W = { P(x), F(y, z), P(x, c), P(x |= (y, F1(z)))}
Найдём множество рассогласований Дl = {F(y, z), C |= (y, F1(z))}