Лупанов О.Б. Лекции по математической логике

Подождите немного. Документ загружается.

Определение. Полная система предикатов на конечном множестве M — такая система, что любой преди-

кат над M выражается через предикаты этой системы.

Очевидно, одноместных предикатов на конечном множестве M имеется 2

|M|

, поскольку одноместный пре-

дикат задаёт некоторое подмножество множества M. Именно поэтому одноместные предикаты называют свой-

ствами.

Теорема 5.3. Система предикатов P = {P

(x), . . . , P

(x)} — полная ⇔ ∀ a, b ∈ M, a 6= b, найдётся преди-

кат P

∈ P, такой, что P

(a) 6= P

(b).

 ⇒ Докажем от противного. Предположим, все предикаты из P принимают равные значения на a и

b. Тогда люба я формула над этой с истемой обладает тем же свойством, значит, нельзя получить, например,

предикат, который равен 1 на a и 0 в остальных точках (в том числе b). Противоречие.

⇐ Построим формулу для любого предиката над P. Пусть a ∈ M. Возьмём предикат P

(x) ∈ P. Сделаем

предикат P

(a)

(x) :=

(

(x), P

(a) = 1;

(x), P

(a) = 0.

Имеем P

(a)

(a) = 1. Построим предикат P

(a)

(x) := P

(a)

(x)& . . . &P

(a)

(x).

Он обладает двумя свойствами: P

(a)

(a) = 1 и P

(a)

(b) = 0, если b 6= a, поскольку по условию ∃ P

∈ P : P

(a) 6=

6= P

(b), и он присутствует в выражении для P

(a)

(x). Таким образом, построен аналог функции x

. Теперь для

любого предиката построим аналог СД НФ.

Пусть P (x) — любо й предикат. Пусть T = {a ∈ M : P (a) = 1}. Тогда на ш предикат выражается формулой

P (x) =

a∈T

(a)

(x). Здесь очень существенно то, что |M| < ∞, иначе подобная формула не имела бы смысла. 

5.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.

Определим понятие формулы, а также связанных и свободных переменных в ней. Грубо говоря, свободные

переменные в формуле — э то такие переменные, вместо которых имеет смысл подставлять некоторые значения.

Связанные переменные возникают в формуле при на вешивании кванторо в или других так называемых связыва-

ющих операторов, например,

. . . dx. Они обладают тем свойством, что вместо этих переменных бессмысленно

подставлять конкретные значения: ∃ xP (x) ∃ 1P (1) — эта «формула» смысла не имеет. Теперь дадим строгое

определение формулы.

Определение.

◦

Любой предикат P (x

, . . . , x

) является формулой. При этом X = {x

, . . . , x

} — множество своб одных

переменных, а множество связ анных переменных Y пусто.

◦

Если F

и F

— формулы, а для их свободных и связанных переменных верно X

∩ Y

= ∅ и X

∩ Y

= ∅,

то F

, F

∨ F

— тоже формулы, и их множес тва свободных и связанных переменных равны соотв е тственно

X = X

∪X

, Y = Y

∪Y

. Вычисление происходит по правилу F

= F

, для дизъюнкции — аналогично.

также является формулой с множе с твами свободных и с вязанных переменных X

и Y

соотв е тственно.

◦

Если F — формула, X и Y — её свободные и связанные переменные, x ∈ X (для определённости пусть

x — по с ледняя переменная функции F ), то навешиванием квантора общности получаем формулу F

′

= ∀ xF , и

при этом X

′

= X r {x}, Y

′

= Y ∪ {x}. Вычисление происходит так: F

′

(α

, . . . , α

) = 1 ⇔ F (α

, . . . , α

, x) = 1 при

любом значении x. Аналогично строится формула F

′′

= ∃ xF , где X

′′

= X r {x}, а Y

′′

= Y ∪ {x}.

Определение. Интерпретация — задание значения (смысла ) математических в ы ражений (символов, фор-

мул и т.д.) В математике такими значениями служат математические объекты (математические операции, вы-

ражения и т.п). Моделью называется интерпретация, в которой выполнен заданный набор аксиом.

Определение. Формула называ ется ист инной в модели, если для всех наборо в значений свободных пере-

менных она принимает значение 1.

Пример 3.1. Пусть в нашей модели P

(x), P

(x) — предикаты делимости соответс твенно на 2, на 3 и

на 6. Тогда формула P

(x)&P

(x) → P

(x) истинна в этой модели. Если бы мы придали символам P

(x) другой

смысл (выбрали бы другую модель), то эта формула могла бы быть и не истинной в этой новой модели.

Определение. Формула истинна на множестве, если она истинна в любой модели на данном множестве.

Пример 3.2. ∃ xA(x) → ∀ xA(x) — не всегда верна, но верна на любом множестве из одного элемента.

Определение. Тождественно истинная формула — формула, истинная для любого множества.

5.4. Эквивалентные формулы и нор мальный вид формулы

Формулы могут быть эквивале нтными (в модели/на множестве/тождественно).

Пример 4.1. P

(x)&P

(x) и P

(x) эквивалентны в модели, в которой P

обозначает делимость на 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 эквивалентны.

 Рассмотрим набор eα = (α

, . . . , α

). Если B

eα

= 1, то



A(x) ∨ B



eα

= 1, и это верно для люб ого x, значит

имеем ∀ x



A(x) ∨ B



eα

= 1. Но в то же время истинна и вторая ф ормула. Если же B

eα

= 0, то это со отношение

никак не зависит от x, откуда при любом x имеем



A(x) ∨ B



eα

= A(x)

eα

. Тогда первая формула преобразуется

к виду ∀ xA(x). Но точно к такому же виду приводится и вторая формула, поскольку B

eα

= 0. 

При тех же условиях имеются следующие ра венства:

∀ xA(x)&B = ∀ x



A(x)&B



, ∃ xA(x) ∨ B = ∃ x



A(x) ∨ B



, ∃ 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 = {q

, q

, . . . , q

}. Вся эта конструкция

называет ся машиной Тьюринга.

Программа для машины Тьюринга представляет собой конечный список команд вида aq → a

′

D, где a, a

′

∈

A, q, q

′

∈ Q, D ∈ {L S R}. Команда расшифровывается так: если машина была в состоянии q и считанный с ленты

в данный момент символ равен a, то машина переходит в состояние q

′

, печатает на текущей клетке символ a

′

затем выполняет одно из трёх действий: если D = L, то машина смещает ся на одну клетку влево, если D = R, то

на одну клетку вправо, если D = S, то машина никуда не смещается. Необходимо, чтобы в программе не было

разных команд с одинаковыми входами вида aq → a

′

и aq → a

′

– это противоречит однозначности

алгоритма. Заметим также, что порядок распо ложения команд программы, в отличие от привычных языков

программирования, может быть произво льным.

Изначально машина находится в сос тоянии q

. Если машина пришла в состояние q

, то она останавлив ается.

Введём понятие применимости ма шины к входным данным, записа нным на ленте до начала её ра боты.

Определение. Машина называется применимой к некоторой записи на ленте, если при работе над этой

записью после конечного числа шагов она остановится. Если она никогда не остановится, то машина называется

неприменимой к этой записи.

Пример 1.1. Рассмотрим машины

M : a

→ a

S и M : a

→ a

S. Как нет рудно видеть,

M над

любой записью будет работать в е чно, а M сразу остановится при любых входных данных. Таким образом,

неприменима ни к одному входу, а M применима к любому входу.

Машину Т ьюринга удобно применять при вычислении функций вида f : N

→ N

. Введём правила записи

чисел на ленте. Пусть наш алфавит состоит из символов 0 и 1. Тогда число n будем з аписывать с помощью

последовательности из n + 1 единицы, а набор (n

, n

, . . . , n

) в виде 0 11 . . . 1

| {z }

0 11 . . . 1

| {z }

0 . . . 0 11 . . . 1

| {z }

Пример 1.2. Составим машину, прибавляющую к числу на ленте 1. Она дойдёт до конца массива из единиц,

поставит туда 1 и вернется назад. Вот её код:

1 q

→ 1 q

0 q

→ 1 q

1 q

→ 1 q

0 q

→ 0 q

Определение. Го ворят, что машина M вычисляет функцию f (x

, . . . , x

) : N

→ N

, если на любом наборе

(α

, . . . , α

) ∈ D(f ) машина останавливается и на ленте остаётся результат (β

, . . . , β

) = f (α

, . . . , α

), а в

случае (α

, . . . , α

) /∈ D(f) она работает вечно, т. е. неприменима к таким входным записям.

Пример 1.3. Машина, которая топчется на месте, вычисляет нигде не опред е ленную функцию.

Рассмотрим алфавит A = {a

, . . . , a

} и символ-разделитель △ /∈ A. Построим машину M

, удваивающую

слова, помещая между ними разделите ль: a

, . . . , a

7→ a

, . . . , a

△ a

, . . . , a

. Для этого добавим к алфавиту

символы {b

, . . . , b

}, не входящие в алфавит A ∪ {△}. Код машины M

→ q

0 → q

△ R

△ → q

△ R

0 → q

→ q

△ → q

△ L

→ q

△ → q

△ L

→ q

0 → q

0 R

Построим универсальную кодировку программы машины Тьюринга. Занумеруем алфа вит {a

, . . . , a

}, со-

стояния q

, . . . , q

и сдвиги натуральными числами:

R L S a

. . . a

. . . q

1 3 5 7 9 . . . 2k + 7 0 2 . . . 2m

Тогда любую команду можно закодировать набором из 5 чисел, а этот набор представить на ленте в помощь ю

алфавита {1, ∗} стандартным образом, помещая вместо разделяющих нулей символ ∗. При это м мы получим

код команды (обозначим его через K). Теперь можно составить код всей программы K(M ) = K

∗ K

∗ · · · ∗ K

где K

— коды всех команд программы. Заметим, чт о по слову K(M) всегда можно восстановить программу.

Пусть в алфавите наших маш ин содержатся символы 1 и ∗. Тогда можно подсунуть машине в качестве

исходных данных её собственный код.

Определение. Машина , которая работает над собств е нным кодом и останавливается, называет ся самопри-

менимой. Если машина при этом не останавлив ается, она называется н есамоприменимой.

6.2. Алгоритмически неразреши мые проблемы

Зададимся вопросом: сущес твует ли машина M

, которая по коду любой маш ины M определяет, само-

применима ли она? Если она существует, о на должна быть применима к коду любой машины M и должна

останавливаться на клетке с 1 в случае с амоприменимости M, и на клетке с 0 в противном случае.

Теорема 6.1. M

не существует, т о ест ь проблем а самопримени мости алгоритмически неразрешима.

 Пусть M

существует. Тогда постро им машину

M, неприменимую к коду с амоприменимых машин и

применимую к коду несамоприменимых машин, добавлением к M

двух команд: q

0 → q

′

0S и q

1 → q

1S.

При этом q

сделаем «обычным» состоянием

M, а некоторое новое состояние q

′

сделаем для неё стоповым.

Применим

M саму к себе. Она не может быть самоприменимой, поскольку в этом случае M

выдаст 1, и

M зациклится. Но она не может быть и несамоприменимой, поскольку в этом случае M

выдаст 0, и она

остановится. Противоречие, значит M

не существует. 

Поставим вопрос: существует ли машина M

, определяющая, применима ли некоторая машина M к входным

данным B. Входные данные M

— код вида K(M )△B.

Теорема 6.2. Машина M

не существует, т . е. проблема приме нимости алгоритмически неразреши ма.

 Пусть существует M

. Присоединим к ней спереди машину удвоения с лова M

. Подсунем ей в качес тве

входных данных код K(M). Она удвоит его, и зат е м решит, применима ли M к K(M), то есть решит проблему

самоприменимости, что невозможно. Прот иворечие. 

В з аключение приведём без доказательства б олее общую теорему.

Теорема 6.3 (Райса). Задача определения т ого, обладает ли некоторый объект нетривиальным с в ой-

ством, алгоритмически неразрешима. Свойство называется нетривиальным, если существуют объекты, об-

ладающие им, и объекты, не обладающие им.