Колмогоров, Драгалин - Введение в математическую логику (947386), страница 14
Текст из файла (страница 14)
Такая подстановка называется константной. Константная подста. новка свободна для всякого выражения. Если подстановка О свободна для выражения Т, то нетрудно описать множество параметров выражения ТО. А именно, ~пусть 8' получается из 6 выбрасыванием из области определения О всех переменных, не входящих свободно в Т.
Пусть О' есть (хт, ..., хз) тогда Г» (ТО) = (Р»(Т),'~'(хь.„, х4) ()Р» ((~) Ц...ЦЕ» (1ь), т. е. из Р»(Т) следует выбросить параметры, вместо которых пбдставляют термы, и добавить параметры подставляемых термов. У п р а ж н е н и е. Приведите пример нарушения этого равенства в случае, когда О не допустима для Т. 7. Пусть А — формула и 0 — подстановка, необязательно допустимая для А.
Как мы уже говорили, в этом случае АО, вообще говоря, непригодна с точки зрения предполагаемого смысла подстановки. Правильный способ действий в этой ситуации таков. Следует найти вариант А', А'жА, такой; что 0 допустима для А', и рассмотреть формулу А'О. Мы назовем А'О результаяом правильной подстановки О в А и обозначим А'О через (АО]. И Формула ~АО) определена неоднозначно, она зависит от выбора варианта А'. Однако если А' А" и 8 — подстановка, свободная для Аг и для А", то А'О А"О. Таким образом, правильная подстановка определена однозначно с точаостью до конгрузнтности.
То обстоятельство, что нужный вариант А', для которого О допустима, найдется, вытекает, например, из следующей леммы. Будем говорить, что формула А обладает свойством чистоты переменных, если, во-первых, все ее связанные переменные отличны от свободных и, во-вторых, любые два различные вхождения кванторных приставок связывают различные переменные.- Л е м м а (о чистоте переменных). Пусть А — формула и 5 — конечное множество переменньи, Тогда может быть построена формула В со свойством чистоты переменных, такая, что АжВ и всякая связанная переменная В отлична от переменных из множества 5. > Доказательство проведем индувцией по ЦА). Если А атомарна, то в ~качестве В достаточно взять А.
Пусть А есть (СА0) и задано множество переменных Я. Пусть 51— множество всех переменных 0 (и свободных, и связарных). Найдем ~по индуктивному предположению формулу С' со свойством чистоты переменных, С'ж С, такую, что связан ные переменные С' отличны от всех переменных из ЯЦВь Пусть теперь Вз — множество всех переменных С'. Найдем вариант 0'ж0 со свойством чистоты переменных, так что связанные переменные 0' отличны от переменных из 50510 3ь Положим В= (С'б0').
Пусть А есть ЩгС. Выберем новую переменную и и определим формулу С', С'жС*,„так что С' обладает свойством чистоты переменных и связанные переменные С' отличны от элементов множества 50(и). Положим В=4иС'.С) Дадим теперь индуктивное определение правильной подстановки. Пусть А — формула, Π— формальная подстановка.
Определим формулу (А81 индукцией по ЦА), А. Если А атомарная формула, то (А81 = (АО), Б. Если А есть (ВАС), то ~А81 — ((ВО]Ь(СО) ). Если А есть ) В, то ~А81 — ЦВ81. В .Пусть А имеет вид ЯхВ. Тогда рассмотрим два'случая. ач 1) «Простой случай». Какую переменную у~доя О Рч(А) ни взять, все параметры соответствующего терм 0(у) отличны от х.
Тогда определим [А 01 — Ох[В (Π— (х)) 1. 2) «Сложный случай». Найдется переменная уендот О Рч(А), такая, что соответствующий терм 0(у) содержит свободно х. Выберем тогда новую переменную и, не входящую в ОхВ ни свободно, ни связанно и не фнгурирующу в подстановке О. Положим [АО1 = ()и [(В,") (Π— (х))[. Мы говорим, что [АО1 есть результат правильной под- становки 0 в А. 8.-Если О есть (хт ' х«1, то вместо [АО) мы часто А " Ть/' будем писать (А(хь ..., хь!!1ь ..., Ть)).
Если не возникает, разночтений, эту запись сокращаем до А(хи...,хь!!Ть...,(ь) или, даже до А(1ь ..., (ь), если упоминание о переменных хо ..., хь несущественно. Последнее обозначение, конечно, двусмысленно (неясно„ вместо каких переменных подставляют термы!), но компакт- но и практически часто употребляется. Например, если мы интересуемся параметрами х и у формулы А, то можно формулу А обозначить через А(х, у).. Если затем,в контексте имеется формула А(1, г), то сле- дует, конечно, иметь в виду именно правильную подстанов- ку А(х, у!!Т, г). У п р а ж н е н и е.
Произведите правильную подстановку: 1) ( ~ уР(х, у, х) (х, у, г!!х, я, у)); 2) ( Дху' у0(х, у)=зР(х)) (х!!1(х, х)), й 3. СЕМАНТИКА ЯЗЫКА. ИСТИННОСТЬ В МОДЕЛИ 1. Чтобы определить, что выражают формулы языка, следует, прежде всего, указать, какие множества пробегают переменные этого языка. Точно соответствующее понятие вводится следующим образом. Пусть дан язык первого порядка: й=(Ы, Спз1, Рп, Рг); Носителем для языка й, или объектпой областью для языка й, мы назовем функцию.й, сопоставляющую каждому сорту п~Бг! непустое множество.0, й:и х)„.
. Множество йя называется носителем,- сорта и, илн объектной областью сорта и. В наиболее популярном случае га:. олзосортного языка носитель Р полностью определяется за- данием множества Р,. Далее, мы желали бы нзучать формулы н термы, в кото- рые вместо параметров подставлены объекты носнтеля. По замыслу каждая-такая «оцененная» формула задает в модели конкретное высказывание. Так, В нестрогнх рассмот- реннях п. 11 $1' фнгурнровалн выражения Р(3, 5, 3), Р(3, 5, 8), йуР(2, у, 3) н т.
п. Весьма желательно, чтобы выражения такого тнпа сами били бы формулами некото- рого языка. С этой целью можно попытаться распзнрнть нс- ходный язык й объектамн носнтеля, нопользуя их в качест- ве новых констант языка. Но зто неудобно по ряду причнн. Во-первых, выражение языка есть строка нз снмволов, а не объектов «пронзвольной прнроды», н нельзя замешать пере- менные выраження любыми объектамн. Еще более серьез- ная причина состоит в том, что после,подстановкн объектов сложной природы может нарушаться однозначность чтения выраженнй. Так, элементы области Р„могут самн случайно оказаться выражениями языка й, н может оказаться, что после подстановкн по полученному выражению уже невоз- можно определять,.где именно находятся в нем объекты но- сителя.
Мы обойдем эту формальную трудность, сопоставнв вза- имно-однозначным образом каждому объекту а сорта и из носителя новый снмвол а н образовав язык, полученный до- бавлением нмевно этнх новых символов. 2. Итак; если задан носнтель Р для языка й, то можно определнть новый язык й(0): й(0)=(5г1, Спз1(0), Рп, Рг), отличаюшнйся от й только наличием новых констант Спз(«:— =-Спз((0). А нменно каждому элементу' аеяР„н сорту я- мы сопоставим новую константу а сорта и н добавим зту константу в множество Спз((Р). Каждая область Р„вза-. имно-однозначно сопоставлена' с .множеством констант (а~ае=Р„).
Кроме того, мы считаем, что константы разлнч- ных сортов раалнчны и, конечно, отличны от всех символов старого языка й. Замкнутое выражение языка й(0) мы назовем оценен- ным выражением языка й. Можно представлять, что, оце- ненное выражение получается яз некоторого выраження язы- ка й, еслй в последнем заместнть все параметры новыми константами языка й(0). В частностн, замкнутое выраже- ние самого языка й является оцененным выражением. Формальная подстановка языка й(Р) энда (а * ' 'а ) т. е. подстановка, прннямающая в качестве значепнй новые 71 константы, называется оценкой языка ь1 (в носителе 0) Заметим, что всякая оценка. является константной подста нонкой и потому свободна для всякого выражения. Будем говорить, что оценка О есть оценка для выражения Т, если Рч(Т)убогий. В этом случае ТО есть всегда оцененное выражение. Впрочем, на практике мы будем иногда смещивать а и а.
Необязательно следовать всем канонам строгости, достаточно понимать, как их достичь1 3. Введем фундаментальное в математической логике понятие — понятие интерпретации языка Й (в другой терминологии — понятие алгебраической структуры языка й, модели языка 11). Чтобы определить интерпретацию М для языка Й, необходимо задать несколько функций. А именно: 1) Следует задать носитель 0 для языка Я: Р;я Р. (пыБг1).
Мы говорим, что переменные сорта и пробегают область 0„. Таким образом, нужно задать область пробегания переменных каждого сорта. 2), Каждой константе сенСпз1 сорта и следует сопоставить объект сеиР„т. е. следует задать функцию Сйз(: с с. О) Каждому функциональному символу ~~рп вида (п~ ... и»- я) следует сопоставить функцию (,вида Р,, х ... х Рк»-э0„, т. е. й-местную функцию, перерабатывающую наборы аь ..., а» объектов соответствующих сортов в объекты сорта и.
.Все это соответствие задается, таким образом,' функцией Рп:Т 4) Каждому предикатному символу РенРг вида (яь я») следует сопоставить предикат Р вида 0«, х ... х 0„~-~-(0, 1), т. е. й-местную функцию, перерабатывающую на- ' боры аь ..., а» объектов из соответствующих областей Рл, 0к» ' в истинностцые значения О или 1 (О— «ложь», 1 — «истина») . В частном случае Й=О пропозиональной букве Р сопоставляется просто истинностное значение Р (т. е.
Р есть О или 1). Это соответствие задается функцией Рт:Р Р. Таким образом„модель М для языка Я определяется четверкой функций М = (Р, Сйз1, гй, Рг) указанного выше вида. Интуитивно говоря, модель языка есть предписание, сопоставляющее символам языка «настоящие» объекты: функциональным символам — функции,,предикатным символам — .предикаты и т.,п.
Если угодно, модель наполняет содержанием, смыслом символические 'выражения языка. Логики говорят, что модель определяет семантику языка (точнее, классическую семантику первого порядка). 4. Если дана модель М для языка Я, то носитель Р модели М определяет. согласно и.
1 оцененные формулы и термы языка й. Определим значение оцененного терма в модели М, Если 1 — терм сорта и,' то его значение 11~м есть объект области Р.. Значение определяется иидукцией по построению термов: 1) если сеиСпз1, то !с!м=с; 2) если 1 имеет вид а для а~Р„, то ~1~м=а; 3) У((ь -, 1») !м=й1111м, - 1Чм). Пусть теперь теиТт, — ' терм, быть может, содержащий параметры. Тогда для'всякой оценки 0 для 1 выражение 19 есть уже оцененный терм, и, следовательно, определено значение ~Ю~м. Таким образом, терм с параметрами определяет функцию от своей оценки. Значение терма зависит от значений его параметров. В частности, замкнутый терм тяТшдд» сам по себе является оцененным термом ~и определяет в М некоторый объект ~1)м. 5. Оцененные в модели М формулы языка И будем подразделять на истинньдв или ложные в М; Запись М).-=А будет означать: «оцененная формула А истинна в модели М».
Определим М)=А индукцией по логической сложности 1(А) формулы А: 1) М)=Р(Юд, ",1») =Р(1(д!м...,~(»1м) =1; 2) М)=АЛВ=М)=А и М)=В; 3) М ~ А у В = М )= А яли М )= В; 4) М)=А=иВ=если М~=А, то М)=В; 5) М)="1А= неверно, что М )=А; б) М)=)7' хА =для всякого ави Р„, М~= А,'; 7) М)=~кА=существует аеи Р„, М)=А,'„ в пунктах 6), 7) к — переменная сорта дд, тз Это определение является уточнением идеи нстинност формулы, если: ее связки и кванторы понимать «естествеиным образо как они читаются»„ считать, что переменные сорта н пробегают объекты об ласти Р„, функциональные символы и предвкатные символы «по, нвмаются» как функции и предикаты, указанные в моде ли М.
На первый взгляд определение истинности вообще мо жет показаться бессодержательным (слева и справа напи сана одно и то же!). Это обманчивое впечатление. Следует ясно понимать, что формула сама по себе ничего не означает, и нужно точно указать, как именно определять истинность формул в связи с моделью М. Чтение логических связок по-русски само,по себе,не придает значения формуле, необходимо точное определение истинности. Заметим, что приведенное выше определение М)==А явля ется законным математическим определением индукцией по величине логической сложности формулы А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
