Ш.И._Галиев_МЛ_и_ТА_2004

имеетсял, для которого Plxj.

Рассмотрим следующее часто встречающиеся предложения 1рава от нихприведемих символическую шш»:

(A)все iJсугеР-У^ЭД ~;Р(х»,

(Е)ни одно Sне сеть Р- 4x(S(x) =>1Р(х»,

(/) некоторые Sсуть Р - Эл(ЗД&/'(х));

(О) некоторые 6'ие естьР-Н*№)&1РС*)).

Символизация приведенных предложений позволяет записывать

швопичеекпм виде довольна сложные выводы, использующие все МОжныакомбинации првдлохсеиий(/1)-(0).

До емх пор мы рассматривали приписывание кваьггирос « одто ■тиым предикатам Далее рассмотрим приписывание кванторов

м гтредшатам. Пусть РСад...х^ - к-местный (иг2) пре

множестве ж. Выражение
Vx/(xl,x1....x ^ iil< n ,		(2.1
1)-ме?гным предикатом, зависящим от		(свободны
... -On............ «,)
истинно Т0ГЛ8 и только тогда, когда лля ЛК>5ого 3
P(<ill0jl...,a1.ll«Ba,l,1 „о,,).
Выражение
=*Л*ь«.
является (я-!)-ыессным up	зависящим от (свободных) m
менныхл|,д-;,...,дг„1. x | ....л
3x^(ohah...,a	,Ая)

истинно тогда а только тогда, когда существует такое зна1 (о(€Я!) переменной ,с„ длв шжчюго вымсачъимвие (2.2) истин* Также гюложим, что велн Р - иульместиый Предикат (i

ванне), ю записи ¥л/ и ЗхР означаютто же, чтои Р.

51

Приписывание (навешивание) квантора по переменной х святымет переменную х. Приписывая к {п-1|-иэстиым предикатам (2.1) и (2.3| любой квантор по любой из свободных переменных, получим (л-2)-меитчыс предикаты (зола п=2, то проста выскаишапие). Ясно, что-к полученным предикатам можно снова приписать произвольные кванторы и т.д. Очевидно, что, приписав кванторы по поен перемен­ ным, получим высказывание. Например, пусть на множестве дейст­ вительны* чисел гадая трешестый предикат х! + У г г2, который можно превратить в двуместный предикат, записав квантор: I tfj1 + / 2 г или в одноместный предикат ¥yVr(i‘ + у1 2 г),

VxVyV.-^-y^z2).	(2.4)
Можно шлучип идругие высказывания, например:
> Д	(2.5)
VxV;'3r(x! + / > ; ’)	(2.6)

и т.д, Ясно, что высказывание (2.6) истинно, а (2.4) и (2.5) - яожные.

Удражнеине. Пусть на множестве Мгадан трехместныЯ пре­ дикат Р(ху,г). Определить, какое число одноместных предикатов можно Получить ИзР(у.,у/;, приписывая к нему различные кванторы.

Пусть множество Ж состоит из конечного числа элементов. Для определенности положим М- {д^.-.а,} и пусть;’(*)- заданный на ftfодноместный лрецИеат Тогда, очевицно. имеем:

VxP(x) равносильно />(а:)&Р(аз)&...&Р(<г,),	(2.7)
ЭхР(х) равносильно P(a,)wP[aiy^...‘jP(a^.	(2.8)
Следовательно, квантор всеобщности является обобшевисм
(аналогом) конъюнкции, а кяантов существования -	о€общ;якем

(аналогом) дизъюнкции на произвольное, не обязательно конечное, множество.

52

§3. Формулы логики прецикнтов

В ото?.! параграфе рассмотрим правила образования из определенных символик различных оыра&ений (термов, формул) без вдкш-пибо ссылок на их содержательный смысл. Толыпз о дальнейшем {§ 4) будем придавать содержательный смисл гтим наборам символов, те. рассматривать, какие предложеяия содержательного языка они могут обспиачатъ,

Буквы начала латинского алфавита		и они *с с число­
выми индексами (а^ ь		‘шывнотс* предметными
нсстаянн&ми.
Буквы тонна латинского алфавита (вда,...) и они же с числовы­
ми индексами	называются гредмвтяыми пере-

Буквы А," с числовыми индексами i £ 1, п к 0 называются лре-

дикатюлми бутами, a f “, / >. 1, л £ 1- функциональными буквами.

Верхний индекс предикатной или функциональной буквы указывает число аргументов, а нижний индекс служитдля различения букве ид-

1>удем по чогможности опуекптъ числовыа индексы у предикат­ ных н функциональных букв, считая, что их легко можно впсстано-

вить. Например, вместо Л,1^ ) будем писать /4)(:¾1 и, если нет дру­ гих двухаргумектных (двуместных) предикатных букв А, вместо А у) будем писать прост:А{ху); крометого иногда будем исполно­ веть буквыP,Q,R,S для обозначения предикатных букв А?.

Определение/яерма:

в) всякая предаетеая постоянная или предметная переменная

б) если /" - функциональна* буква н ад... - термы,

1« /"((!,t2,...,Q ten тори;

в) выражение является термом только в том случае, если это следует из правила) и6).

Примерытермов: о, I,, / tz(x,a), /3 (я, /2 О)).

Предикатные буквы, примененные а термам, порождают

элементарные формулы или точнее: если Л," - предикатная бухла,

a 11,6....,4, - термы,то А‘(f,,t3	г^-иементарная формуле.
Будем считан,, что нульыклиая предикатная буква гоже
является элементарнойформулой.
Примеры элементарных	формул: Л,с, ^ { * ,01),	( /j1(л)),

A b fr fi W l ) .

Ф(^^лы«^илрл)«етт[>з определяются следующимобразом: а) всякая элементарна»формула еегьформула;

б) вели А и Б - формулы и * -	предметная		переменная,
то каждое из выражений("Й) (ЛэЗ), (Уь4) и(3x4)		естьформула;
в) выражение является формулой	только	в	том случае,

если это следует изправил а) и б).

В выражениях (VM) к (Эь4) формула А называется областью действия кванторовVx кЭксоответственно.

54

Примеры формул: (Af (Vx.i' (/. f l i f ' (-»)1)),

Если А и В - формулы, то договоримся, т о А&В япяяется сокращенной записью формулы (1 (А э(1 Л))), A-JS - сокращенной записью формулы (("U)=sff), АйВ ■ обкрашенной записью формулы (1(и=?«)=>(1:в=>.4))».

Будем придерживаться тех же правил опускания скобок, которые приняты в § 3 гя 1, ввела дополнительно, что кванторы 'ix. Зх располагаются по силе между связками п, &, v и связками э ,? .

Например, вместо (fVx4)»B) пишем Vx4=5B.
Договоримся также	опускать скобки,	в которые заключа­
ется формула А в формулах виса (£>i(£M))),		где Q, и Q -	любые
кванторы. Например,	вместо	(Arjv)))))	пишем

Вхоясдение переменной х в данную формулу называется связан­ ным, если х «вдается переменной входящих в эту формулу кванторов Vx, :х или находится в области действия входящих в яту формулу кванторов У*, Зх; в нротивноы случае вхождение переменной х в дан- н)ю формулу называется свободным. Мапркчер, вхождение перемен­

ной х в формулу УуЛ"!<х,у)--л1(уу! является свободным, перке

и второе вхождение переменнойу - связанным, а третье и четвертое вхождениеу в эту формулу' свободным.

Таким образом, одна и та же переменная в одной и той же фор­ муле может иметь как связанные, так и свободные вхождения.

Переменная называется свободной (связанной) переменной в данной формуле, если существуют свободные (связан)сые) ее вхож­ дения вэту формулу.

Формула называется замкнутей, если она не содержит никаких свобэднчх переменных, т е. либо все ее переменные связанные, либо переменных нет совсем. Например, формула %с(VyW,2 (ху)-^> (jyr)) -

здикиутм, а формула Vx A? (xjj) - иеммкнутая, ибо содержит свобод­ ную переменнуюу,

55

Замыканием формулы А называется формула, полученная из А приписыванием перед нею кванторов всеобщности по всем ее свободным переменным, при з'юм кванторы приписываются следующим образом: сначала записываем кванторы общности по всем свобидныч переменным х (если они слъ) ь порядке ягарастаниа т индексов, затем по свободным переменным у (если они есть) в порядке возрастания их индексов и т.д. Так, замыканием формулы

А‘(Jj ,уг) будетформула:
а замыканием для формулы V>.3*. ^3,3(х(	Д1 (¾.¾} будет фор­
мула:
VtiVj'jWyVyia;; A*(xt.ybxd=,A*{x3.X2))-
апотоминтерпретируйте ихш		хотите.
		М TKJI
		Ф.Ницше
Когда л беру слово, оно означает		то, что я хочу,

нг бояыке и намеиыиз, - сказах Шлтай презрительно.

II. Кэррэлл

§4. Иитерпрьлтшиа, Модель

Интерпретациюбудем счит&тъзаданной, если:

1.Задано непустое множество М, называемое областью итерлретаинн.

2.Заданы следующие соответствие

а) предикатным буквам Л," поставлены в соответствие некото­

рые п - честные предикаты (отношения) в 04,

бифункциональным буквам /" поставлены в соответствие некоторые н-аргумс>ггныс функции, отображающие JW“ в ОН,

в) каждой предметной постоянной поставлен я соответствие вскоюрый (фиксированный) элемгнтвз Я£

г) символам 1, V.x, Вх поставлен в соответствие их обычный

3. Считается, что предметные переменные пробегают вес мно жество 5И.

Нанрииср, чтобы задать :штерпрстацик1 дли формулы УхД’^.уД), нужно задать множество М - область интерпретации (область изменении переменных х,у). Из этой области М‘ будем брать некоторый элемент, соответствующий предметной постоянной h\. Да­ лее нужно задать трехчестный предикат нл Ж, соответствующей пре­ дикатной букве А‘ . Так, можно положить, что Я*=[0, ео); предметной постоянной bi поставить в соответствие I, а (х,_уд) поставить в соеггвегсгаие предикат х + у Ъ.г. Тогда формула V*Л{ (вдА,) в заданной интерпретации запишется: ~ix{x * у 2 1) я будетозиачаи, что для лю-

ошошение истинно при некоторых у ly > 1) и ложно при других тачениях у ((Ку<1). Если предметной постоянной bt посгаоить а соот­ ветствие 0, а не 1, то утеержденне Ух(х +у > 0) будет истинно при лю­ бом значениисвоболной переменнойу.

Легко видеть, что дли той же формулы можно построить бесчисленное множество других интерпретаций, выбирал различные множества Ж, фиксируя из X каким-то образом элемент, соответствующий Ы я задавая разлечньтм образом на 5К трехместныв предикат.

S7

■а Ь\ - студент»	Ивлнсва, а.	поставить в соответствие
предикат: *.г и у	учатся в той	же группе, что и г». Тогда исходная

формул» УхЛ,1 {х,у,Ь') в этой интерпретации означает утверждение.

Vi(r иу учатся с той же группе, что иИванов). Это утверждение явля­ ется ложным при каждом у, нбене может быть, чтобы любой х и некоторый>>учились впой же группе, что иИванов.

При данной ингерпрепадии всякая формула без свободных пе­ ременных (замкнутая формула) представляет собой высказывание, которое истинно либо ложно, а всякая формула се свободными пере­ менными выражает некоторое отношение на М, которое молот быть истинно для одних значений из Ии ложнодля друга*.

Формула называется оыяалхиледЗ в данной интерпретации, если ом ириннмао-г значение И хеггя бы для одной совокупности возмож­ ных значений ее свободных переменных (вели они есть). Если форму­ ла не содержит свободных перемечиых, го она называется выполни­ мей втом случае, ecim принимает значениев этойинтерпретации.

QK8 принимает значение И для всех возможных значений ее свобод­ ных переменных (если ониесть). .Нели же свободных неременных нет, то формула называете* нетшшой, когда она принимает значение И в этой интерпретации.

Формула называется ножной г данной иптцмрешции, если она принимает значение Л для все* возможных значении ее свободных переменных (еьли они есть). Е ст же свободны?: переменных нет, тп формула называется ложной, когда она принимает значение Л в этой интерпретации.

Очевидно, что формула ложна в данной интерпретации тогда и только тогда, когда она не выполнима в этой интерпретации. Так же ясно, что формула А выполнима в данной интерпретации тогда и только тогда, когда она не является ложной вэтой интерпретации.

мул G, если каждая формула из Gистинна взтой интерпретации.

58

§ 5. Свойства формул вданной интерпретации

Можно доказал, следующие свойства формуя о данной интер­ претации (некоторые из них очс-вианы, другие читательлегко докажет

1.Формула А ложна в донной иктсрпретацт тогда и -только югда, когда "U истинно в этой же интерпретации. Формула Л истинна в данной интерпретации тогда и только тогда, когда ~Й ложна вэтой же интерпретации.

2.Никакая формула не может 5ьпь одновременно истинной и

ложной в одной и той же интерпретации.

Ъ. Если в данной интерпретации истинны А и А=>В, то истинно и В. Это утверждение легко локоза'И методом от противного (сравни с теоремой 1.1).

4. Формула А ^ В ложна в да>1Ной интерпретации тогда, и тольmi тогда, когда А истинно в этой ннгерпрегации, а В лож*). Доназа-

13 определения импликации.

5. Формула AfiB выполнима в данной интерпретации тогда и только тогда, когдаА и В лрииимак>! ишчснис И одновременно ха гя бы Д’я одной совокупности значений своих свободных переменных. Если же свободных переменных нет. то формула А&В выполнима

вданной интврпрегации тогда и тс|Лько тогда, когда обе формулы

й.Формула А-/В выполнима в данной интерпретации, ссли хотя бы одна из Ш(х выполнима в лой интерпретации.

7, Формула А*В выполнима в данной интерпретации тогда

итолько тигда, когда А и Я приникают значение И пдночременно

или значение Л (тоже одновременно) хотя бы для одной совокупности значений своих свободных переменных. Роди же ейободньк перечвчных нет, то формул* А=В выполнима в данной интерпретации тогда

значение в этой интерпретации.

8. Формула ЗхА сыпапнима в данной интерпретации тогда и только Toi,ia, когда А принимает значение И хотя бы для одной сово-

59

купнсютизначений ее свободных переменных н хотя бы одного значе­ ния переменкой х.

9. Формула VxA истинна в данной интерпретации тог и только тогда, когда в этой интерпретации истинной.

Как следствие из ггого утверждения получаем, что формула А истинна r данной интерпретации тогда и только тогда, когда в этой интерпретации истиннозамыкание формулыА.

Бели формула А замкнута, то в данной интерпретации А

доватйш.но, А истинно либо ложно. Иначе, ес.ои А замкнуто, го в любой данной интерпретациилибо нетинно/1, либо истинно А.

1(1.Рассмотрим некоторую пропозициональную форму. Если D пропошциональную фирму место пропознциоиальпы* букв подставить формулы логики предишое (вместо все* вхождений од­ ной и той же пропозициональной буквы подставлять одну н ту же формулу), получим некоторую формулу, которая называется

частный о;>чяги пргтозиципнпльной фпцчы. Тогда легки доказать следующееутверждение.

Всякий частный случайлюбойтавтологии истиненв каждой ин­ терпретации.

§ 6. Логически обшиначимые формулы. Выполнимые и равносильные формулы

Логическая общезначимость формулы означает, что какую бы выбирали область интерпретации н какие бы соответствия, ука-

60