О.Б. Лупанов - Курс лекций по математической логике (1109964), страница 8
Текст из файла (страница 8)
Пусть T = {a ∈ M : P (a) = 1}. Тогда наш предикат выражается формулойP (x) =P (a) (x). Здесь очень существенно то, что |M| < ∞, иначе подобная формула не имела бы смысла. a∈T5.3. Кванторы и формулыРассмотрим предикат P (x, y). Навешиванием квантора общности на P называется получение из него предиката Q(y) = ∀ xP (x, y), такого, что Q(y) = 1 ⇔ для любого x ∈ M имеем P (x, y) = 1. Навешиванием кванторасуществования называется получение предиката R(y) = ∃ xP (x, y), такого, что R(y) = 1 ⇔ существует x ∈ M,для которого P (x, y) = 1.Определим понятие формулы, а также связанных и свободных переменных в ней. Грубо говоря, свободныепеременные в формуле — это такие переменные, вместо которых имеет смысл подставлять некоторые значения.Связанные переменные возникаютв формуле при навешивании кванторов или других так называемых связываRющих операторов, например, .
. . dx. Они обладают тем свойством, что вместо этих переменных бессмысленноподставлять конкретные значения: ∃ xP (x)∃ 1P (1) — эта «формула» смысла не имеет. Теперь дадим строгоеопределение формулы.Определение.1◦ Любой предикат P (x1 , . . . , xn ) является формулой. При этом X = {x1 , . .
. , xn } — множество свободныхпеременных, а множество связанных переменных Y пусто.2◦ Если F1 и F2 — формулы, а для их свободных и связанных переменных верно X1 ∩ Y2 = ∅ и X2 ∩ Y1 = ∅,то F1 &F2 , F1 ∨ F2 — тоже формулы, и их множества свободных и связанных переменных равны соответственноX = X1 ∪ X2 , Y = Y1 ∪ Y2 .
Вычисление происходит по правилу F = F1 &F2 , для дизъюнкции — аналогично.RRRF 1 также является формулой с множествами свободных и связанных переменных X1 и Y1 соответственно.3◦ Если F — формула, X и Y — её свободные и связанные переменные, x ∈ X (для определённости пустьx — последняя переменная функции F ), то навешиванием квантора общности получаем формулу F ′ = ∀ xF , ипри этом X ′ = X r {x}, Y ′ = Y ∪ {x}.
Вычисление происходит так: F ′ (α1 , . . . , αt ) = 1 ⇔ F (α1 , . . . , αt , x) = 1 прилюбом значении x. Аналогично строится формула F ′′ = ∃ xF , где X ′′ = X r {x}, а Y ′′ = Y ∪ {x}.Определение. Интерпретация — задание значения (смысла) математических выражений (символов, формул и т.д.) В математике такими значениями служат математические объекты (математические операции, выражения и т.п). Моделью называется интерпретация, в которой выполнен заданный набор аксиом.Определение. Формула называется истинной в модели, если для всех наборов значений свободных переменных она принимает значение 1.Пример 3.1. Пусть в нашей модели P2 (x), P3 (x), P6 (x) — предикаты делимости соответственно на 2, на 3 ина 6.
Тогда формула P2 (x)&P3 (x) → P6 (x) истинна в этой модели. Если бы мы придали символам Pi (x) другойсмысл (выбрали бы другую модель), то эта формула могла бы быть и не истинной в этой новой модели.Определение. Формула истинна на множестве, если она истинна в любой модели на данном множестве.Пример 3.2. ∃ xA(x) → ∀ xA(x) — не всегда верна, но верна на любом множестве из одного элемента.Определение.
Тождественно истинная формула — формула, истинная для любого множества.215.4. Эквивалентные формулы и нормальный вид формулыФормулы могут быть эквивалентными (в модели/на множестве/тождественно).Пример 4.1. P2 (x)&P3 (x) и P6 (x) эквивалентны в модели, в которой Pk обозначает делимость на k, формулы∃ xA(x) и ∀ xA(x) эквивалентны на одноэлементном множестве, а A(x) и A(x) тождественно эквивалентны.Сформулируем правила эквивалентного преобразования формул.В любой формуле можно переименовать связанную переменную, не нарушая связанности остальных.Утверждение 5.4. ∀ xA(x) = ∃ xA(x). Пусть первая формула (обозначим её F ) равна 1. Тогда существует x ∈ M, для которого A(x) = 0.(Если бы для всех x A(x) = 1, то ∀ xA(x) = 1 ⇒ F = 0, что невозможно).
Но это и означает, что ∃ xA(x), т. е.верна вторая формула. Аналогично разбирается второй случай, когда F = 0. Утверждение 5.5. ∃ xA(x) = ∀ xA(x). Доказательство аналогично предыдущему. Утверждение 5.6. Рассмотрим формулу A(x) ∨ B, причём x — свободная переменная для A и x не входитв B. Тогда формулы ∀ x A(x) ∨ B и ∀ xA(x) ∨ B эквивалентны.= 1, и это верно для любого x, значит Рассмотрим набор αe = (α1 , .
. . , αt ). Если B = 1, то A(x) ∨ Bαeαeимеем ∀ x A(x) ∨ B= 1. Но в то же время истинна и вторая формула. Если же B = 0, то это соотношениеαeαeникак не зависит от x, откуда при любом x имеем A(x) ∨ B= A(x) . Тогда первая формула преобразуетсяαeαeк виду ∀ xA(x). Но точно к такому же виду приводится и вторая формула, поскольку BПри тех же условиях имеются следующие равенства:∀ xA(x)&B = ∀ x A(x)&B , ∃ xA(x) ∨ B = ∃ x A(x) ∨ B ,= 0. αe∃ xA(x)&B = ∃ x A(x)&B .(1)Теорема 5.7.
Любую формулу можно эквивалентными преобразованиями привести к нормальной форме,в которой все кванторы вынесены в начало формулы. Сначала переносим отрицания под кванторы, затем переименовываем связанные кванторами переменные так, чтобы все они были различными. Далее, используя правила из предыдущего утверждения, выносимвсе кванторы наружу, после чего формула принимает нормальный вид. Пример 4.2. ∀ xA(x) ∨ ∃ xB(x) = ∀ xA(x) ∨ ∃ yB(y) = ∀ x ∃ y A(x) ∨ B(y) .6. Алгоритмы6.1. Машина ТьюрингаОпределение. Алгоритм — чётко описанная процедура преобразования информации, приводящая к результату.Представим себе бесконечную в обе стороны ленту, разбитую на ячейки.
Представим себе устройство, способное двигаться по ячейкам вправо и влево, а также способное считывать и записывать информацию в ячейке, надкоторой оно в данный момент находится. В ячейках могут быть записаны символы некоторого конечного алфавита A. Устройство обладает некоторым конечным набором состояний Q = {q0 , q1 , . . . , qn }. Вся эта конструкцияназывается машиной Тьюринга.Программа для машины Тьюринга представляет собой конечный список команд вида aq → a′ q ′ D, где a, a′ ∈A, q, q ′ ∈ Q, D ∈ {L S R}.
Команда расшифровывается так: если машина была в состоянии q и считанный с лентыв данный момент символ равен a, то машина переходит в состояние q ′ , печатает на текущей клетке символ a′ изатем выполняет одно из трёх действий: если D = L, то машина смещается на одну клетку влево, если D = R, тона одну клетку вправо, если D = S, то машина никуда не смещается. Необходимо, чтобы в программе не былоразных команд с одинаковыми входами вида aq → a′1 q1′ D1 и aq → a′2 q2′ D2 – это противоречит однозначностиалгоритма. Заметим также, что порядок расположения команд программы, в отличие от привычных языковпрограммирования, может быть произвольным.Изначально машина находится в состоянии q1 .
Если машина пришла в состояние q0 , то она останавливается.Введём понятие применимости машины к входным данным, записанным на ленте до начала её работы.Определение. Машина называется применимой к некоторой записи на ленте, если при работе над этойзаписью после конечного числа шагов она остановится. Если она никогда не остановится, то машина называетсянеприменимой к этой записи.22f : ai qi → ai qi S и M : ai qi → ai q0 S. Как нетрудно видеть, Mf надПример 1.1.
Рассмотрим машины Mfлюбой записью будет работать вечно, а M сразу остановится при любых входных данных. Таким образом, Mнеприменима ни к одному входу, а M применима к любому входу.Машину Тьюринга удобно применять при вычислении функций вида f : Nk → Nm . Введём правила записичисел на ленте. Пусть наш алфавит состоит из символов 0 и 1. Тогда число n будем записывать с помощью. . . 1} 0 . . . 0 11. . . 1} 0.последовательности из n + 1 единицы, а набор (n1 , n2 , .
. . , nk ) в виде 0 11. . . 1} 0 11| {z| {z| {zn1 +1n2 +1nk +1Пример 1.2. Составим машину, прибавляющую к числу на ленте 1. Она дойдёт до конца массива из единиц,поставит туда 1 и вернется назад. Вот её код:1 q10 q1→ 1 q1→ 1 q2RL10q2q2→ 1→ 0q2q0LRОпределение. Говорят, что машина M вычисляет функцию f (x1 , . . . , xk ) : Nk → Nm , если на любом наборе(α1 , . . . , αk ) ∈ D(f ) машина останавливается и на ленте остаётся результат (β1 , .
. . , βm ) = f (α1 , . . . , αk ), а вслучае (α1 , . . . , αk ) ∈/ D(f ) она работает вечно, т. е. неприменима к таким входным записям.Пример 1.3. Машина, которая топчется на месте, вычисляет нигде не определенную функцию.Рассмотрим алфавит A = {a1 , . . . , ak } и символ-разделитель △ ∈/ A. Построим машину MD , удваивающуюслова, помещая между ними разделитель: ai1 , . . .
, ain 7→ ai1 , . . . , ain △ ai1 , . . . , ain . Для этого добавим к алфавитусимволы {b1 , . . . , bk }, не входящие в алфавит A ∪ {△}. Код машины MD :q1q2iq2iq2iq3iaiaj0△0→→→→→q2iq2iq3iq3iq4bibj△△aiRRRRLq3iq4q4q5q5ajaj△aibi→ q3i→ q4→ q5→ q5→ q1ajaj△aibiRLLLRq1q6q6△bj0→ q6→ q6→ q0△aj0LLRПостроим универсальную кодировку программы машины Тьюринга. Занумеруем алфавит {a0 , . . . , ak }, состояния q0 , . . . , qm и сдвиги натуральными числами:R1L3S5a07a19......ak2k + 7q00q12......qm2mТогда любую команду можно закодировать набором из 5 чисел, а этот набор представить на ленте в помощьюалфавита {1, ∗} стандартным образом, помещая вместо разделяющих нулей символ ∗. При этом мы получимкод команды (обозначим его через K). Теперь можно составить код всей программы K(M ) = K1 ∗ K2 ∗ · · · ∗ Ks ,где Ki — коды всех команд программы.
Заметим, что по слову K(M ) всегда можно восстановить программу.Пусть в алфавите наших машин содержатся символы 1 и ∗. Тогда можно подсунуть машине в качествеисходных данных её собственный код.Определение. Машина, которая работает над собственным кодом и останавливается, называется самоприменимой. Если машина при этом не останавливается, она называется несамоприменимой.6.2. Алгоритмически неразрешимые проблемыЗададимся вопросом: существует ли машина MS , которая по коду любой машины M определяет, самоприменима ли она? Если она существует, она должна быть применима к коду любой машины M и должнаостанавливаться на клетке с 1 в случае самоприменимости M , и на клетке с 0 в противном случае.Теорема 6.1. MS не существует, то есть проблема самоприменимости алгоритмически неразрешима.f, неприменимую к коду самоприменимых машин и Пусть MS существует.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
