Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
SJii = ({о, і,..., 0; о (f = i, 2,...)
образуют возрастающую цепочку, объединение подмоделей которой совпадает с SJi. Формула (Зж) (Уу) у <х истинна на каждой подмодели SJi; и ложна на модели SJi. Поэтому формула (3х) (Уу) у^x не эквивалентна никакой V3-формуле. Отрицание указанной формулы (Vx) (3?/) 1 у < х не эквивалентно по той же причине никакой ЗУ-формуле.
В предыдущем пункте было показано, что если некоторая формула S одновременно эквивалентна У-формуле и 3-формуле, то S эквивалентна формуле низшего, бескванторного вида. Для УЗ- и ЗУ-формул аналогичное утверждение неверно. Существует формула, эквивалентная одновременно некоторой УЗ-формуле и некоторой ЗУ-формуле и в то же время не эквивалентная никакой У-фор-муле и никакой 3-формуле.
В качестве примера может быть взята формула
(Ч х) P (X) & (Iy)Q (у).
(3) КЛАССИФИКАЦИЯ ФОРМУЛ
179
Эта формула эквивалентна каждой из следующих двух формул:
(V*) (Эу) (P (X) & Q (у)), (Зу) (Vx) (Р (X) & Q (у)).
В то же время легко проверить, что формула (3) неустойчива ни относительно перехода к подмоделям, ни относительно перехода к надмоделям, и потому не эквивалентна ни V-формуле, ни 3-формуле.
Структурные свойства УЗУ-формул, ЗУЗ-формул и формул с более сложными префиксами известны, но формулируются они довольно сложно. При помощи их, а также и из других соображений, нетрудно вывести, что, например, формула
Уі, ..., хп, уп)
не эквивалентна никакой формуле, содержащей меньшее число кванторов.
Теорема 2 из п. 7.1 переносится на УЭ-формулы и формулы с иными префиксами следующим образом.
Положим HV = 3, "1 3 = V и префикс H Q1H Q2 ... ...~]Qi, где Qt = V, 3, назовем двойственным префиксу
QlQz • •. Qi-
Теорема 2. Если формула % эквивалентна как формуле с префиксом Q1 .. . Qi, так и формуле с двойственным префиксом П Qi . . . H Qi, то % эквивалентна конъюнкции дизъюнкций подходящих формул с более коротким префиксом
Доказательство мы здесь опустим.
Те о-рема 3. Каков бы ни был фиксированный префикс Qi . . . Qi, не существует алгоритма, распознающего по записи произвольной замкнутой формулы, эквивалентна или нет эта формула какой-нибудь Qi . . . Qi-формуле.
Для I = 1 эта теорема была доказана в п. 7.1. Справедливость ее в общем виде в этой книге не будет установлена, мы докажем эту теорему лишь для префикса V3. Как и в п. 7.1, покажем, что если бы мы при помощи некоторого алгоритма Л могли распознать, эквивалентна или нет произвольная замкнутая формула gr какой-нибудь V3- формуле, то мы могли бы при помощи Л узнать, тождественно истинна или нет произвольно заданная замкнутая формула fj, не содержащая функциональных
12» 180
ЯЗЫКИ ПЕРВОЙ II ВТОРОЙ СТУПЕНИ [Гл. III
символов, в противоречие с теоремой Чёрча. Действительно, если бы формула % оказалась не эквивалентной никакой VB-формуле, то % не была бы тождественно истинной, так как любая тождественно истинная формула эквивалентна V3-формуле
(Vx) (Iy) х=у.
Пусть формула % эквивалентна какой-то УЗ-формуле. При помощи алгоритма Гильберта находим конкретную УЗ-формулу
(Vxi...Xm) (Iy1...уп)^, (4)
эквивалентную формуле Как и в п. 7.1, мы можем предполагать, что формула (4) имеет ту же сигнатуру, что и формула и> в частности, что формула (4) не содержит функциональных символов. Нам надо узнать, является ли формула (4) тождественно истинной, т. е. является ли выполнимой формула
(Ix1. . .Xm) (Vy1. . -Уп) H 21 (Si, ...,хт,Уи Уп). (5)
Если формула (5) истинна на какой-нибудь модели Sft, то в Sft существуют элементы аь . . ., ат такие, что выражение
И 21(0!, ..., ат, ylt ..., уп) (6)
истинно для всех г/ь . . ., уп из 9Л, и, значит, выражение (6) истинно для всех значений , . . ., уп в подмодели Sft1, образованной в SOi элементами а1у . . ., ат.
Итак, если формула (5) выполнима, то она выполнима на некоторой модели, содержащей не более т элементов. Все эти модели можно эффективно построить и для каждой узнать, истинна или ложна на ней формула (5).
7.4. Позитивные формулы. Формула ПИП называется позитивной, если в ее записи нет знаков отрицания и импликации. Вынося вперед в позитивной формуле кванторы, получим предваренную позитивную формулу, эквивалентную первоначальной.
Пусть ^ (х1г . . ., хт) — позитивная формула сигнатуры G и X1, ..., хт— все ее свободные предметные переменные. На каждой алгебраической системе SJl сигнатуры а указанная формула определяет ш-арный предикат КЛАССИФИКАЦИЯ ФОРМУЛ
181
i?sgj, который называется позитивно формульным предикатом.
Теорема 1. Пусть R (хх, . . хт) — позитивно формульный предикат, определяемый позитивной предваренной формулой
(QlXyn + l) • • • {Qn%m+n) Я (xit . . ., Xm, Xm^i, . . ., Хт+п) (1)
сигнатуры о, и пусть ср — гомоморфизм некоторой алгебраической системы SJl сигнатуры о на алгебраическую систему 9Ї. Тогда из истинности Ryji (xi, . . ., хт) для каких-либо Xi, хт из SJl вытекает истинность
Rs? (яіф, . . ., хтср). Иными словами, позитивно формульные предикаты устойчивы относительно гомоморфизмов системы на систему.
