1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 20
Текст из файла (страница 20)
В. Скажем, что стандэртнэя схем«8 тотальна (пу«те) но мкож««т«« к«нг«нмэ ияэмряр«талип, еслк для любой конечной нктерпрет«цпн > программ«(Я,!) ост«невлнэ«ется (э«цнклвээется). Постройте првмер стандартной схемы, которая татэльв«не мнажестэе конечных пктерпре«ацпй, но не тат«льне нэ множестэе эсен внтерпретацкй. Г. Покежвте, что стандарте«я схема пуста тогда н только тогда, когда онэ пуста нэ множестве всех конечных внтерпрет«цвй. Д. В«едем атнашенне «ст«мм 8«и 8«к«и««ое-эк«ива.аентим«, ээменнэ в определеннн функцвон«лъной экэнээлевтноств слова «для любой внтерпрашцкп«не «для любой конечной ннтерпретацнн«.
Постройте пример парм станд«ртэых схем, которме конечно-экеввэлеатвм, во ве экэнээлевтвы фувкцнон«льна. Б. Отношепне слабак экэввэлентнаств определяют следуккцкм обре«ам: сэ«мм я> к 8 ««обо вк«иоь««яэи«м, если для любая нптерпретэцвв > реэультаты программ (8«, Х) н (8«, >) соэп«дают э том случае, когда абе программы остановлен«ются. Убедптесь, что атношенке сл«бой екэвэалентностн дейстэвтельво ел«бее аткошення функцнональнай ешппмлевтноств, более того, ово не яэляется отвшпевнем экэвээлевтностн э обжемэтемэтвческом смысле. Укежатв н«рнс.
4.3 трн схемы 8>, 3 п 8« текве„что 8«слабо »кена«лентяе Юе; 8« слабо экэвеэлевтк«8«, но 8«н Лэ не являлися сл«ба экэнээлевткымк. Ж. Стакдэртвме схемы Яз и Яз ваэывзются изоморфными, если соэяадзют зовэкестэа всех цеяэчек операторов этих схем. Пекзжатз, что взоморфкзм схем является атксжеквем экавзэлеятвеств а классе стандартных схем„ прячем более свхьвым, чем фувкциокальвэя зкакэалевткость. Укажите ва рве. 4.3 кары кзомерфвых схем, а также пары ве вэемерфвых, ке фувкцкевэлыю экэвэзлевтвых схем. 3.
Ставдэртяые схемы 8г в 8з з общем бэзвсе называют иээмрэрвжачизэнз эзолорфяыми, есля любая вятерирзчацяя базиса вераждает соэкздэкацае цекечка оверзтороэ схем 8 в Яз. Пекажвтз, что витерврэтацковкый взоморфвзм язлязтся атжэлеввем экэввзлэвткести а классе стэвдартяых схем, прячем более свльвмм, чзм фуккцвевзльвая эквяээлевткесть, ке более слабым, чэм вземорфизм схем (см.
врэдыдущее эздавве). 3.2. Свободные интерпретации. Отношение функциональной эквивалентности, а также свойства тотальности и пустоты стандартных схем определены с использованием понятия множества всех воаможных интерпретаций базиса. Таким образом, чтобы убедиться в том, что, например, схема з пуста, надо установить, аацикливаетси ли программа (Я, 1) для любой интерпретации Х.
Такой путь окааыэается неперспективным, так как класс всех возможных интерпретаций базиса крайне широк. Однако существует подкласс интерпретацвй, называемых свободными, или арбраловыми э), который образует ядро класса всех интерпретаций в том смысле, что справедлввость высказываний о семантических свойствах стандартных схем достаточно продемонстрировать для класса всех программ, получаемых с помощью только свободных интерпретаций.
Кроме того, свободные интерпретации дают воэможность установить наглядную связь между синтаксисом схемы и ее семантикой, в чем мы убедвмся в следующих рааделах этого параграфа. Читатель, знакомый с эрбрановымн интерпретациями в логике, легко обнаружит полезные аналогии между ними и свободнымн интерпретациями схем программ. Все свободные интерпретации бааиса л) имеют одну и ту же область интерпретации, которая совпадает со множеством Т всех термов бааиса %.
Все свободные интерпретации одинаково интерпретируют переменные и функциональные символы, а именно: а) для любой переменной х из базиса эт и для любой свободной интерпретации 1„атого базиса 1ь (х) = х; б) для любой константы а иа базиса 1„(а) = а; в) для любого функционального символа Х<э) из базиса Ю, где в ~э 1, Ха Д">) = гч">г Т" -~ Т, где Р<ю — словарная функция такая, что гчю (т, т,..., т„) = Х~э) (т, т,..., г„), т. е.
функция Р<*'> по термам тю г,..., т„иэ Т строит новый терм, используя функциональный символ д">. Что касается интерпретации предикатиых символов, то она, в отличие от интерпретации переменных и функциональных символов, полностью зсвободна»: в проиаэолъной конкретной свободной интерпретации предикатному символу сопоставлен проиа.волъный преднкат, отображающий Т в (О, х). Следовательно, разе) здесь в теории схем лрегрзмм была всвэльэезака идущая вз матзматкческев логккк идея Эрбрава е аезможвссти нестроевая сквтэкскчзсквх наделен для вевретцзоречвэых теорий первого порядка.
ные свободные о) интерпретации различаются лишь интерпретацией предикатных символов. Таким образом, после введения свободных интерпретаций термы испольауются в двух разных качествах, как функциональные выражения в схемах н как аначения переменных и выражении. Если нам потребуется различать ати два употребления термов, то мы будем термы-значения заключать в апострофы. Так, если т = '1 (л, а)' — терм-значение переменной л, а т« = 'у (у)' — термзначенне переменной у, то значение свободно интерпретированного терна-выражении т = 1 (л, Й (у)) равно терму-значению '1 Д (л, а), Ь (у (у)))'. П р и и е р. Пусть 1е — свободная интерпретации базиса„ в котором определена схема о«,т из раздела 2.2 этой главы, и в этой интерпретации предикат Р = 1„(р) задан таким обрааом: 1. если число функциональных символов в с больше Р (т) = двух; О, в противном случае. Тогда протокол выполнения программы (Я«т, 1,) можно представить в следующем виде: Зе«ч«еля к э ~- рацея м«тка Обратим внимание на следующую особенность термов.
Если иа терма удалить все скобки н аапятые, то получим слово (назовеж его бес«побочных«термен), по которому можно одноапачпо восстановить первоначальный вид терма (при условии, что отмечена илинавестна местность функциональных символов). Например, терму у~т> (Ип (л), бле> (л, у)) соответствует бесскобочный терм у)«хулу. е) «Свободные схемы«в «свободяые ввтерпретецвю — никак ие свят заввые между собой понятия. Спал«девис первых слов в я«их термввах иосвтслучавэый характер: в первом случае допустимая цепочка может быть построеиа «свободвым блуждакиемэ по схеме, во втором — оставлена свободе выбора влтерпретецви предвкатвых свмволов. Сба термина оби~епривяты в литературе. 87 Правила восстановления терма по бесскобочной записи аналогичны правилам восстановления арифметических выражений по их прямой полъской ааписн, поэтому мы предоставляем читателю возможность построить их самостоятельно.
Бесскобочная запись "гермов короче, и мы будем широко исполъэовать ее наряду с обычной записью. 3.3. Согласованные свободпъге интерпретации. Так как значениями переменных и выражений в свободно интерпретированных схемах служат термы, последние'можно проинтерпретировать следующим образом. Пусть М вЂ” бааис, 1 — пронэволъпая интерпретация этого базиса.
Интерпретация 1 определена для переменных, функциональных и предикатных символов базиса 83. Об.ласть определения интерпретации 1 можно естественным образом расширить, включан в нее множество всех функциональных и логических выражений базиса Я и полагая 1(х) , если ъ — переменная х, 1(а), если т — константа а, 1(1"~) (1(тъ),..., 1(т„)), если т — выражение вида ('ю (тд,..., с ), где 1~"» — функциональный или предикатяый символ и и,:э1. Более того, мы определим интерпретацию и на последовательностях тернов из Т, полагая 1 (ъ ... т„) = 1 (т,) 1 (тэ)...
... 1 (ъ„) для последовательности тернов т,... г„(п > 0). Пусть, например, т = 'у (й(й (х)), у(Ь(х), у(х, а)))', а вптерпретации 1э совпадает с интерпретацией 1» иэ п. 2.5 атой главы эа исключением лишь того, что 1э (х) =- 3. Так как 1э [а) = 1, 1э (у)— функция умноженив чжел, а 1э (Ь) — функция вычитания единицы, получаем 1э (ъ) = ((3 — 1) — 1) х ((3 — 1) х (3 х 1)) = = 1 х 2 х 3 = 6. Заметим, что если 1„— свободная ннтерпретацвя, то всякий терм из Т (а также всякая последовательность "герман иэ Т) является неподвижной точкой для 1ю т. е.
1„(т) = Будем говорить, что интерпретация 1 и свободная интерпретация 1ъ того же базиса э3 согласованы, если для любого логического выражения и справедлнво 1„(п) = 1 (я). Например, свободная интерпретация 1ю описанная в примере и. 3.2, согласована с только что рассмотренной интерпретацией 1э и с интерпретацией 1э иэ п. 2.5. Однако 1„ не согласована с интерпретацией 1» иэ п. 2.5.
Лемма 4.1. Дпп каждой ипп»ерпретпации 1 базиса й» сущвстпеуетп сомаеоеаниап с пей сеободпап иптерпрепищип этово баДо к а з а тел ьс тв о. Действителъно, для каждого предикатного свмзола р~ "» из 5» множество наборов терман-значений 1"' можно разбить па два непересекающихся иодмножества— Т„.ъъ и Тэ,ъэ — по следующему правилу: (т„..., г„) еБ Тэ.т»ы если 1(~Ф"») (1 (тъ),...> 1 (с„)) = 1, и (тм ..., тэ) Е:— Тр,ъе 88 в противном случае.
Полагая затем, что предикат 1ь (рОЧ) при- нимает авачение 1 на наборах вз Т" дл и значение 0 на наборах из Т„"„д,е, получаем свободную интерпретацию 1ю согласованную с 1. ~ До к а з атал ь ство ' легко проводится индукцией по глубине выражения и предоставляется чвтателю. Глубина выражения может быть определена следующим образом: О, если т — переменная или константа, 1+днах (глубина (тд),..., глубина (т„)), если ч=у(ч...„с„), где ч„..., т„ЕТ, а у— функциональный или предикатвый символ. [ ) глубина (т) = Лемма 4.3. Пусть Я вЂ” скииддартная схема в базисе Я, 1 — интерпретация, а Гь — согласованная с 1 свободная интерпретация зкимо базиса. Тогда для любой пари конфигураций ид = = (йд.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
