Научная литература
booksshare.net -> Добавить материал -> Математика -> Мальцев А.И. -> "Алгебраические системы" -> 61

Алгебраические системы - Мальцев А.И.

Мальцев А.И. Алгебраические системы — Наука, 1970. — 392 c.
Скачать (прямая ссылка): algebraicheskiesistemi1970.djvu
Предыдущая << 1 .. 55 56 57 58 59 60 < 61 > 62 63 64 65 66 67 .. 133 >> Следующая


ЯЗЫКИ ПЕРВОЙ и ВТОРОЙ СТУПЕНИ [Гл. III

отрицаний простейших формул, или дизъюнкция отрицаний простейших формул. Например, формула

(Vx) (Зу) (Vz) (/о = g0&h=gi&h = g2\jh^ g3\jh ф **).

где ft, gi— термы, есть формула хорновского вида.

Если X1, . . ., хп— свободные предметные переменные какой-то хорновской формулы ^ . . ., хт) сигнатуры о, то указанная формула определяет на каждой алгебраической системе SJl сигнатуры о m-арный предикат, который будет называться хорновским.

Пусть теперь на каждой системе SJl сигнатуры а каким-то способом задан предикат P^ (хи . . ., жт). Этот предикат мы будем называть мультипликативно устойчивым; если он удовлетворяет следующему требованию.

Обозначим через SJl декартово произведение системы моделей SJlce (a ^ А) сигнатуры а, и пусть аи . . ., ат— произвольные элементы SJl. Если для каждого а (Ц А

PtSfla • • • > ?mJta) = И

(ла — проектирование ЭД1 на SJla), то

Рш(аі. • • •> ат)^И.

Основное свойство хорновских предикатов выражает

Теорема 1 (А. X о р н [71]). Каждый хорнов-ский предикат мультипликативно устойчив. В частности, если какая-нибудь хорновская замкнутая формула % истинна на каждом сомножителе SOla декартова произведения SJl = IjSJla (а ? А), то % истинна и на самом декартовом произведении.

Для доказательства введем вспомогательное понятие. Предикат {уи . . уп), определенный на каждой системе SJl сигнатуры о, назовем строго мультипликативно устойчивым, если он мультипликативно устойчив и из истинности его в некоторой точке уі, . . ., уп декартова произведения П^а вытекает истинность его в каждом сомножителе 9)la В соответственной точке УіЛа, . . . • - *» Уп^а- КЛАССИФИКАЦИЯ ФОРМУЛ

185

Строгая мультипликативная устойчивость простейших формул вида

Piiy1, уп), Vl = Fiyl, ..уп), (1)

где Pi, Fi— сигнатурные символы, непосредственно следует из определения декартова произведения. Столь же очевидно, что конъюнкция (строго) мультипликативно устойчивых предикатов есть (строго) мультипликативно устойчивый предикат.

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

В самом деле, пусть S? (j/i, . . ., уп) — строго мультипликативно устойчивый предикат, и выражение (З уi) Sfiiy1, у%, . . уп) истинно на декартовом произведении

SJl = II^co (а є Л) для некоторых у2, ..., Уп 6 30?- Это значит, что для подходящего у 6 gyi 5? ІУ, г/2, • • •, Уп) = И. Ввиду строгой устойчивости предиката S? отсюда следует

$ (упC6, у2па, • • ., УпПа) = И (2)

для каждого а 6 А, т. е. для каждого а ? А

(ІУ) (У. Уг3т«> • • •. УпЯа) = Я. (3)

Обратно, пусть для фиксированных у2, ..., уп 6 ЗЯ и для каждого a ^A имеет место (3), т. е. для подходящего i/a€9fta

$ (у%» Уг^ал • • • > УпЯи) = И.

Берем в SER элемент у такой, что ула = уа для каждого a 6 А. Из (2) получаем 5JS (у, г/г, • • •» Уп) = И, и потому <3t/)m г/2, Уп) = и.

Мы показали, что навешивание квантора существования на (строго) устойчивый предикат дает снова (строго) устойчивый предикат. Аналогичные рассуждения показывают, что навешивание квантора всеобщности также сохраняет (строгую) устойчивость.

Докажем теперь, что из строгой мультипликативной устойчивости предиката SJS (yu . . уп) и мультиплика- 186

ЯЗЫКИ ПЕРВОЙ II ВТОРОЙ СТУПЕНИ [Гл. III

тивной устойчивости Q (уи . . ., уп) вытекает мультипликативная устойчивость импликации

%(Уи • • Уп)->&(Уи ..Уп).

Пусть для некоторых уи ..., уп из декартова произведения 30? .. уп)=И [и для каждого а импликация

(УіПа, . . ., Уп ла) —> Q (г/jJta, ..., упяа)

истинна. Так как предикат $$ строго устойчив, то ^ G/lrta, ¦ • - , УпЛа) = И, и потому Q ІУіЛа, • • • , Уп^а) = И. Из устойчивости предиката Q1 теперь заключаем, что

Ул)=И.

Наконец, заметим, что отрицание строго мультипликативно устойчивого предиката есть мультипликативно устойчивый предикат.

Действительно, H эквивалентно импликации -у X Ф х, мультипликативно устойчивой в силу предыдущего замечания.

Из доказанных замечаний теорема 1 вытекает непосредственно. В самом деле, согласно п. 7.1 формула вида

/ (Уи Уп) = 8 (Уи ¦ • Уп), (4)

где f,g— некоторые термы от уи . . ., уп, эквивалентна Э-формуле, у которой бескванторная часть есть конъюнкция простейших выражений вида (1). Эти простейшие выражения строго мультипликативно устойчивы. Вместе с ними строго устойчивыми будут их конъюнкция и кван-торизованная формула (4). Таким образом, формулы вида (4) строго мультипликативно устойчивы. Хорнов-ская формула есть кванторизация конъюнкции членов, каждый из которых есть либо формула одного из видов (1), (4), либо отрицание формулы этого вида или их конъюнкции, либо формула вида

AlSzA2Sz.. .&Ар-> Лр+1,

где Ai- формулы видов (1), (4). Так как формулы видов (1), (4) строго мультипликативно устойчивы, то каждый КЛАССИФИКАЦИЯ ФОРМУЛ

187

член хорновской формулы мультипликативно устойчив. Поэтому мультипликативно устойчивы конъюнкция указанных членов и ее кванторизация, что и требовалось.
Предыдущая << 1 .. 55 56 57 58 59 60 < 61 > 62 63 64 65 66 67 .. 133 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed