Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
Обращение теоремы Хорна неверно. А именно, Ч а н г и M о р е л [75] показали, что существуют мультипликативно устойчивые VJ-формулы, не эквивалентные никакой формуле хорновского вида (см. п. 8.4). Что касается V-формул и Э-формул, то для них обращение теоремы Хорна справедливо. Мы ограничимся здесь только рассмотрением V-формул, более важных для приложений.
Теорема 2. Пусть класс S алгебраических систем обладает тем свойством, что декартово произведение любых двух систем класса S принадлежит Я. Тогда каждая V-формула % (уі, . . ., Уп)і мультипликативно устойчивая на классе Й, эквивалентна на A универсальной хорновской формуле.
Формулу S представим в виде
(Чхи...хт){и,&...&ит), (5)
где Ux—формула
"14xtV... VH^xp V^. (6)
и A%j—простейшие формулы типа (1) или (4). Допустим, что в члене (6) число q — р больше 1. Обозначим через 2? формулу, получающуюся из % вычеркиванием в ее члене (6) k-то выражения вида Ait p+ft. Ясно, что формула
тождественно истинная. Покажем, что для подходящего к на классе ft истинна и формула
(7)
Пусть, напротив, для каждого к формула (7) не истинна на классе й. Это значит, что в й найдется система SJlft л в. этой системе найдутся такие элементы у*[ \ ..., 188
ЯЗЫКИ ПЕРВОЙ II ВТОРОЙ СТУПЕНИ [Гл. III
что в точке у\\ ..уп' на SJlft формула g будет истинна, а формула ^ft ложна. Из истинности формулы gf следует, что истинны все ее подформулы (Vs1 ... Xm) Ui. Так как все эти подформулы, кроме Я-й, входят и в состав формулы то ложность формулы влечет ложность подформулы (6) с вычеркнутым членом. Значит, в SJlft найдутся такие элементы ..., хт\ что в точке
yf\ - • •, Уп\ 4ft\ ---,^rn выражения Ax і, ...,Axp будут истинны, а выражения A%t р+а (а фк) ложны.
Рассмотрим декартово произведение SJl систем SJlfe (к = 1, ..., q — р). Обозначим через у і последовательность , .. ., y\q~p^) (і — 1, ..., п) и через Xj—последовательность (x<jl\ ..., Xjq~p)) (] = і, .. ., т). Последовательности Уи • • •, Упj хи • • ч хт—это элементы системы 3)1. В точках у(і \ ..., уп \ х*і \ • • •, х(т (к = 1, ..., q—p) выражения Axl, . . ., Axv были истины, поэтому они истины и в точке а=(уи OJ1, ..., хт). G другой стороны, каждое
из выражений Axl p+i, . .., AXq ложно в подходящей проекции anh = (y<{\ ..., уп \ \ • • хт}) точки а. Поэтому все выражения Ах, P+i, . .., A%q ложны в точке а. Мы видим, что в точке а формула U% ложна. Следовательно, в точке (уі, ..., уп) формула % ложна. Но это противоречит мультипликативной устойчивости формулы так как для каждого k = i, ...,q—p формула ^iylTtk, ynnk) истинна.
Итак, если мультипликативно устойчивая V-формула 5 не имеет хорновского вида, то она эквивалентна на классе Я более короткой мультипликативно устойчивой на Я V-формуле ^?. Если не имеет хорновского вида, то, производя в ^ft указанное вычеркивание, получим еще более короткую формулу ^kr И т. д. Через конечное число шагов процесс оборвется, и в результате получится формула, удовлетворяющая требованиям теоремы 2.
В этом и предыдущих пунктах был определен ряд устойчивостей: устойчивость относительно перехода к подсистемам, гомоморфная устойчивость, мультипликативная устойчивость. Среди формул, обладающих несколькими из этих устойчивостей, особенно большое значение имеют так называемые тождественные соотношения или, КЛАССИФИКАЦИЯ ФОРМУЛ
189
короче, тождества и условные тождества (квазитождества) .
По определению тождествами называются формулы вида
(Vx1 . ..хп) (f = g), (Vx1 ... хп) P (сц, .. ., ат), (8)
где /, g, O11 . . ат— термы от хи . . ., хп, P — сигнатурный предикатный символ.
Условными тождествами (квазитождествами) называются формулы вида
(Vx1 ... хп) (Ai& . .. &АР-+А),
где через A1, ..., Ap, А обозначены простейшие формулы вида
/ = g, P (ві, .... om).
Из приведенных выше результатов этого параграфа видно, что тождественные соотношения устойчивы относительно перехода к подсистемам, гомоморфно устойчивы и мультипликативно устойчивы. Условные тождества устойчивы относительно перехода к подсистемам и мультипликативно устойчивы, но в общем случае не обладают гомоморфной устойчивостью.
Заметим еще, что каждое тождество (8) эквивалентно условному тождеству
(Vx1 ... Xn) (Xi = Xl-^f = g) или соответственно условному тождеству
(Vx1 . . . Xn) (x1 = x1 p (q1, . . . , om)).
Поэтому тождества можно рассматривать как частный вид условных тождеств.
Известен ряд задач о существовании алгоритмов, естественно связанных с понятиями хорновской формулы и мультипликативной устойчивости. Например:
а) Существует ли алгоритм, позволяющий по записи произвольной замкнутой формулы сказать, обладает или нет эта формула свойствами мультипликативной устойчивости?
б) Существует ли алгоритм, позволяющий по записи произвольной замкнутой формулы сказать, эквивалентна 190
ЯЗЫКИ ПЕРВОЙ II ВТОРОЙ СТУПЕНИ [Гл. III
или нет эта формула подходящей формуле хорновского вида?
Вопросы а), б) можно специализировать, рассматривая в них не произвольные замкнутые формулы, а лишь формулы какой-то фиксированной сигнатуры. Можно и по-другому видоизменять вопросы а), б). Например, условимся замкнутую формулу S называть квадратоустойчи-вой, если из истинности % на произвольной системе ЯК вытекает истинность S на декартовом квадрате ЯЗІ X ЯЛ. Естественно к вопросам а), б) добавить и вопрос
