Ш.И._Галиев_МЛ_и_ТА_2004
.pdfимеетсял, для которого 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