Лекция 9. Теорема построения

При определении терма и формулы мы не использовали скобок. По-

скольку нет скобок, то встает задача об однозначности чтения терма или

формулы: нельзя ли терм или формулу собрать двумя различными спосо-

бами? Для того, чтобы избежать повторений, введем термин «указатель».

Указателем будем называть терм или формулу. Каждый указатель

имеет вид uv1 . . . vn, где u - первый символ указателя. По правилу постро-

ения термов и формул он является или переменной или n -арным функци-

ональным или предикатным символом или одним из знаков ￢, ∨, ∃. При-

пишем этому первому символу индекс следующим образом.

• индекс переменной равен 0,

• индекс n -арного функционального или n -арного предикатного сим-

вола равен n,

• индекс ￢ равен 1, индекс ∨ и индекс ∃ равен 2.

Таким образом индекс первого символа указателя показывает «сколько

строительных блоков» для построения указателя стоит за ним.

В качестве примера запишем терм u = x + y в строгом виде и найдем

индекс первого символа. Получим u = +xy с первым символом +. Это

бинарный предикатный символ, и, поэтому, имеет индекс 2.

Введем отношение сравнимости ∼ на множестве всех выражений язы-

ка первого порядка. Пусть даны два выражения u и v. Тогда u сравнимо

с v, если одно из них имеет начальное вхождение в другое (т.е. получает-

ся из другого приписыванием справа некоторого выражения t, возможно

пустого). Очевидно, что отношение ∼ рефлексивно и симметрично.

ТЕОРЕМА 10 Пусть u1, u2, . . .un , u_

1, u_

2, . . .u_

n - произвольные ука-

затели, причем u1u2 . . .un ∼ u_

1u_

2 . . .u_

n

Тогда u1 = u_

1, u2 = u_

2, . . . , un = u_

n.

Доказательство индукцией по числу символов в выражении u1, . . .un.

Пусть u1 . . .un — контрпример с наименьшим числом символов. Рас-

смотрим строение указателя u1. Имеем u1 = uv1 . . .vl, где u - символ u

индекса l (так как за ним стоит l блоков). Тогда u – первый символ в u_

1.

Поэтому u_

1 имеет вид u_

1 = uv_

1 . . .v_

l (l символов, так первый символ u

42

индекса l). Из сравнимости u1u2 . . .un ∼ u_

1u_

2 . . .u_

n следует сравнимость

выражений v1 . . .vl и v_

1 . . .v_

l: По индукции v1 = v_

1 , . . . , vl = v_

l.

Из u1u2 . . .un ∼ u_

1u_

2 . . .u_

n имеем u1u2 . . .un = u_

1u_

2 . . .u_

nt или

u1u2 . . .unt = u_

1u_

2 . . .u_

n для некоторого выражения t. Сократим на u1 =

u_

1 и применим индукцию к оставшимся сравнимым выражениям. Полу-

чим u2 = u_

2, . . . , un = u_

n. Теорема доказана.

ТЕОРЕМА 11 (об однозначности построениятерма и формулы).

Произвольный указатель v однозначно представим в виде

uu1 . . .un, где u – символ индекса n, а u1, . . . , un – указатели.

Доказательство. Существование записи v = uu1 . . .un следует из опреде-

ления указателя (терма или формулы).

Докажем единственность. Пусть наряду с записью v = uu1 . . .un то

же самое выражение v построено в другом виде v = uv_

1 . . . v_

n. Ясно, что

первые символы в обоих выражениях равны и во втором выражении за

символом u стоит ровно n указателей v_

1 . . . v_

n. При этом u—символ ин-

декса n.

Приравняем выражения: uu1 . . .un = uv_

1 . . .v_

n и сократим на u. Полу-

чим равенство u1 . . .un = v_

1 . . . v_

n и, тем более, сравнимость u1 . . .un ∼

v_

1 . . .v_

n. По предыдущей лемме v1 = v_

1, . . . , vn = v_

n. Получили однознач-

ность записи. Теорема доказана.

Эта теорема необходима для корректности многих последующих опре-

делений. Она показывает также, что скобки не обязательны для языка

первого порядка.

Аксиомы теории первого порядка.

Аксиомы теории первого порядка делятся на два вида логические и

нелогические. Логические аксиомы — законы логики, которые мы ис-

пользуем в математике. В теории первого порядка правила логического

выводы строго зафиксированы.

В нелогических аксиомах отражают свойства объектов, рассматрива-

емых в теории. Например, в аксиомах N1 – N9 отражены свойства сло-

жения, умножения и отношения > для натуральных чисел.

Операция подстановки. Для их формулировки аксиом нам необхо-

димо понятие подстановки вместо переменной произвольного терма. Эта

подстановка может осуществляться в терме или в формуле.

Рассмотрим сначала пример.Пусть дан терм u = x+y. Заменимбукву

x в терме u на на терм z · t. Получим выражение z · t+y, которое является

термом.

Возможна замена буквы x не в в терме, а в формуле. Результат под-

становки в формулу A вместо переменной x терма u обозначается Ax[u].

Если формула A что-то утверждала про объект x, то, естественно, мы

полагаем, что формула Ax[u] то же самое утверждает про объект u. Одна-

ко на этом пути возникает затруднение. Пусть, например, мы рассуждаем

о целых числах и записали формулу ∃x 2x = y. Она выражает мысль,

что y – четное число. Заменим в этой формуле y на u, где u = x + 1. Мы

надеемся получить «x+1 – четное число», однако результат подстановки

∃x 2x = x + 1 – не выражает эту мысль.

Выясним природу этого явления. В формуле ∃x 2x = y квантор ∃x не

относится к y, значит и в формуле ∃x 2x = x + 1 квантор ∃x не должен

относится к x + 1, что не так при прочтении формулы. Данную ситуацию

назовем запрещенной подстановкой .

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

связанной и свободной переменной в формуле.

Пусть дана произвольная формула A. Тогда A - или атомная форму-

ла, т.е. A = pu1 . . .un, или A образована из других формул посредством

применения несколько раз следующих действий при сборке формулы:

￢B, ∨BC, ∃xB

Формулы, из которых строится формула A, называются ее частями,

Сама формула также часть A.

Пример. Найти части формулы C = ∃x∃y x + y = 1. Имеем три части:

A,B,C, что видно из следующего рисунка

∃x

_ _B_ _

∃y x + y = 1 _ __ _

_ __ A _

C

Действительно: u1 = x + y — терм, u2 = 1 — терм (конкретный пред-

мет, то есть нульарный функциональный символ). Далее = — бинарный

предикатный символ, x + y = 1 - атомная формула, ∃y x + y = 1 и

∃x∃y x + y = 1—формулы.

Рассмотрим произвольную формулу A и некоторое конкретное

вхождение переменной x в формулу A (может быть несколько вхождений

переменной x в формулу A).

ОПРЕДЕЛЕНИЕ 9 Вхождение переменной x в формулу A называ-

ется связанным, если оно содержится в некоторой части форму-

лы A следующего вида ∃xB. В противном случае данное вхождение

называется свободным.

В предыдущем примере x - связанное вхождение, y - также связанное

вхождение. Нет свободного вхождения переменной.

ОПРЕДЕЛЕНИЕ 10 Переменная x называется свободной в A, если

в A есть свободное вхождение x; переменная x называется связан-

ной в A, если в A есть связанное вхождение x;

Рассмотрим формулу A, равную x + 1 = 2∨ ∃xx + y = 2. Первое вхо-

ждение x в A является свободным, а второе—связанным. Поэтому x од-

новременно свободная и связанная переменная в формуле A. Очевидно,

что в атомной формуле каждая переменная является свободной.

Введем два вида подстановки. Пусть a, b —термы. Обозначим через

bx[a] результат замены каждого вхождение переменной x в терме b на

терм a.

ТЕОРЕМА 12 Результат замены bx[a] является термом.

Доказательство самостоятельно индукцией по длине терма b.

Рассмотрим произвольную формулу A и некоторое конкретное сво-

бодное вхождение переменной x в формулу A. Будем говорить, что до-

пустима подстановка Ax[u], заменяющая данное вхождение переменной