Логическая корректность рассуждения 3 страница

Свойство подформульности, определенное, может быть, излишне педантично, тем не менее, играет важ­ную роль в построениях КЛП.

Определение 5.4. Символы: л, v, <->соответ­ственно для двуместных пропозициональных связок «и», «или», «взаимно влечет»; эх — для квантора существования «для некоторого х такого, что» опре­деляются следующими дефинициями.

Дф 1.1 А л В =Дф -п(А -> -В);

Дф 1.2 A v В =Дф -А -> В;

Дф 1.3 А <-> В =дф (А -> b) л (в -» а);

ДФ1.4 эха(х)=дф -,vx-a(x).

Таким образом, язык классической логики пре­дикатов может быть сформулирован без ущерба для его выразительных возможностей, используя лишь отрицание, одну любую пропозициональную связку и один любой квантор. Остальные пропозициональ­ные связки и квантор могут быть введены в теорию КЛП соответствующими дефинициями.

Определение 5.5. Формула А языка КЛП имеет негативно-нормальную форму, если в любой ее под­формуле вида —! В формула В является атомарной, а сама формула А построена без использования дву­местных пропозициональных связок —» и <-».

Иначе говоря, формула языка КЛП находится в негативно-нормальной форме, если она содержит лишь связки конъюнкцию л и дизъюнкцию v, кван­торы всеобщности у и существования з, а все отри­цания -1 в ней находятся лишь перед атомарными подформулами. Скажем, формула

Зх^х-ДС-пАСх^зОл B(y))v Vx3-.C(x2,x3))

имеет негативно-нормальную форму, если ее подфор­мулы А и С являются атомарными формулами и подформула В не содержит отрицаний перед неато­марными подформулами.

Теорема 5.1. Пусть А — произвольная формула КЛП-языка. Тогда А<->А°, где А° есть формула А в негативно-нормальной форме (н.н.ф.).

Доказательство. Индукцией по длине подфор­мульности формулы А, используя тезисы КЛП и оп­ределение 5.4.

А = -iP^,...,^): A — формула в негативно-нормальной форме по определению 5.5. А = (В <-> С): А <» (В -> С)л (С ->- b) по Дф 1.3 А = (В -> С): ао (-.В v С) по КЛВ А = -,(В л С): А <» (-.В v -,С) по КЛВ А = -,(В v С): А <» (-,В л -iC) по КЛВ А - -iVxB(x): A <» Эх-Л(х) по Дф 1.4 и КЛВ А = -1ЗхВ(х): А о Vx-,B(x) по Дф 1.4 и КЛВ

Теорема доказана. Действительно, отрицание ато­марной формулы есть формула в н.н.ф. Эквиваленция

может быть представлена как конъюнкция импли­каций по законам КЛВ. Отрицание конъюнкции (дизъюнкции) эквивалентно по КЛВ дизъюнкции (конъюнкции) отрицаний. Отрицание перед кванто­рами легко «проносится» в формулу по Дф 1.4.

Пример. Привести следующую формулу КЛП-язы-ка к н.н.ф.

-п(ух(А(х)-> (B(x)v С(х)))л ЗхЬА(х)л b(x))).

Решение. Методом эквивалентных преобразова­ний, используя КЛВ и дефиниции определения 1.4.

1. -,vx(a(x) -> (В(х) v С(х))) v -,Зх(-,А(х) л В(х)) 1^/1. 2- зх-,(а(х) -> (в(х) v С(х))) v Vx-,(-,A(x) л b(x)) 1 V/ 1,

3. Зх-,(-,А(х) v b(x)v C(x)) v Vx-i(-nA(x)A b(x))

4. 3x(A(X)A-1B(x)A-,C(x))vVx(A(x)v-^B(x))

Язык классической логики предикатов очень удо­бен для логического анализа силлогистических суж­дений и рассуждений. В действительности аристоте­левская силлогистика является фрагментом КЛП, представляющим кванторную логику одноместных предикатов. Все категорические атрибутивные суж­дения силлогистики легко переводимы на КЛП-язык в следующей форме.

1. Все S есть Р: Vx(s(x) -> р(х)); -пЗх(8(х)л->Р(х)).

2. Все S не есть Р: Vx(s(x) -» -пР(х)); -^Зх(з(х)л р(х)).

3. Некоторые S есть Р: Зх(з(х)л р(х)).

4. Некоторые S не есть Р: 3x(s(x) л -iP(x)).

5. Только S есть Р: Vx(p(x) -» S(x)); -Зх(р(х) л -iS(x)).

6. Не все S есть Р: -,Vx(s(x) -> р(х)); 3x(s(x) л -iP(x)).

7. Не все S не есть Р: -,Vx(s(x) -> -^(x)); 3x(s(x) л р(х)).

Легко увидеть, что 3 <=> 7 и 4 <=» 6.

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

1.-VxA(x) О -тЗх-1А(х);

2.-Vx-,A(x)<i>-I3xA(x);

3.-nVxA(x) <» 3x-iA(x);

4.-,Vx-iA(x) О ЗхА(х).

В заключение раздела следует сказать несколько слов о смысле и ценности формализации научного знания, в том числе и гуманитарного. Формальные языки, подобные КЛП-языку, не ставят перед собой задачу заменить естественный язык. Естественный язык и формальный язык различны по своим целям и функциям. Естественный язык возникает и функ­ционирует в процессе коммуникативной практики

общения людей, их интеллектуального взаимодей­ствия в гуманитарной и социокультурной деятель­ности, связанной с получением, обменом и хранени­ем социально значимой информации. Естественный язык выразителен, метафоричен, гибок и многозна­чен. Для него эти характеристики подчеркивают важность роли, которую язык играет в развитии куль­туры и духовной жизни общества.

Формальный язык — это искусственный язык, построенный на основе точно сформулированных (синтаксических и семантических) правил. Синтак­сис формального языка регулирует в нем правила осмысленных логических структур — терминов, фор­мул, выводов и доказательств с точки зрения их эф­фективности, регулярности и универсальности для целей логического исследования оснований естествен­нонаучного или гуманитарного знания. Для гумани­тарного познания эта задача оказывается тем более нетривиальной, что в основаниях, скажем, этики или юриспруденции заложены нормативные понятия, требующие для своего анализа особого нормативно­го искусственного языка с его специальной дедук­тивной логикой суждений и рассуждений. Для со­циологии, политологии или эстетики требуется эф­фективный формальный аппарат, оценочные фрагменты естественного языка.

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

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

Ошибочно полагать, что формализация естествен­ного языка преследует цели краткости и сжатости его изложения, в чем-то похожего на стенографиро­вание. В действительности, направленность формаль­ного языка на поиск строгих, логически коррект­ных, содержательно адекватных и конструктивных моделей для отображаемых объектов естественного языка заставляет часто поступаться в формализме принципами краткости и сжатости. Г. Фреге как-то заметил, что тенденция к краткости не всегда оправдана даже в языках математики, так как при­водит к неточным выражениям и открывает доро­гу ошибочным определениям. Логическую коррект­ность нельзя приносить в жертву краткости выра­жения. Формальный язык, прежде всего, является инструментом эффективного представления логи­ческих и вне-логических связей и отношений фор­мализуемого фрагмента языка. Во-вторых, формаль­ный язык в строгой форме воспроизводит принци­пы логической дедукции, принятые в исследуемой области научного познания.

Упражнения

5.1. Следующие силлогизмы переведите на фор­мальный язык классической логики преди­катов. Поясните с точки зрения собственного логического опыта и логической интуиции, какие силлогистические рассуждения не яв­ляются логически корректными, надежными.

Пример.

Только философы эгоисты.

Нет циника, который не был бы эгоистом.

Следовательно, все циники — философы.

Силлогистическое рассуждение логически корректно, но не надежно, так как, по-види­мому, ложна первая посылка.

1. Только демократическое государство может быть правовым.

Тоталитарное, значит антидемократическое государство.

Нет правового государства с тоталитарным режимом.

2. Лишь глупые люди верят в конец света.

Тот, кто верит в гармонию мира, не верит в конец света.

Всегда найдется глупец, который не верит в гармонию мира.

3. Каждого, кто верит в себя, можно считать человеком. Никто, ни один человек не верит политикам.

Все, кто верит политикам, не верят в себя.

4. Лишь идеалистом может быть юрист.

Все мошенники придерживаются материалистических взглядов.

Юрист не может быть мошенником.

5. Нет таких членов парламента, которые не участвовали бы в законотворчестве. Только 12% членов парламента составляют юристы.

Не все, кто создают законы, являются юристами.

6. Этот политик — лжец.

Только болтуны могут быть лжецами.

Этот политик, помимо всего прочего, еще и болтун.

7. Среди юристов имеются профессиональные бизнесмены. Настоящий бизнесмен не боится инфляции.

Некоторые юристы не опасаются инфляции.

8. Только политики верят в пользу насилия.

Не всякий любитель насилия любит собственных детей.

Некоторые политики не любят своих детей.

9. Только в споре рождается истина.

Никто не станет спорить, кроме глупца или мошенника.

Лишь глупец или мошенник может достичь истины.

10. Ведь никто не будет отрицать, что Аполлон прекрасен. Лишь обладающие женской логикой относятся к прекрасной половине человечества.

Выходит, что Аполлону была свойственна женская логика.

11. Все люди смертны.

Некоторые писатели бессмертны.

Значит, некоторые писатели не люди.

12. Боязливый к прекрасному полу — боязлив и в жизни. Тот, кто знает логику, не боится женщин.

Трус не разбирается в логике.

13. Среди болтунов нет логиков.

Только болтун может стать политиком.

Этот логик, как и все его коллеги, никогда не станет политиком.

14. Иногда проходимец может оказаться ясновидцем. Если ты ясновидец, то не имеешь права лгать.

Существуют проходимцы, которые обязаны говорить лишь правду.

15. Лишь двоечник по убеждению — лентяй. Ни один студент не любит получать двойки.

Значит, среди студентов нет лентяев.

16. Лишь в правовом государстве реализуются права граждан.

Только демократическое государство может быть правовым.

Права граждан могут быть реализованы лишь в демократическом государстве.

17. Любой честный человек не любит лжецов. Каждый принципиальный человек честен.

Принципиальные люди не любят лжецов.

5.2. Пусть задан некоторый перевод силлогиз­ма из упражнения 5.1 на язык классичес­кой логики предикатов в форме: А, В=ФС. Объединим посылки силлогистического рас­суждения конъюнкцией, а полученный конъ-юнктор свяжем с заключением импликаци­ей: (Ал В)—» С. Представим результирующую формулу в негативно-нормальной форме. Пример. (См. пример к упр. 5.1)

(Vx(3(x) -> ф(х))а -^Эх(ц(х)л -,э(х))) -> Ух(ц(х) -> ф(х)).

1. -,(ух(-,э(х) v ф(х)) л -ах(ц(х) л -.Э(х))) v Ух(-,ц(х) v ф(х)).

2. -,Vx(-,a(x) v ф(х)) v Зх(ц(х) л -.э(х)) v \'х(-,ц(х) v ф(х)).

3. Зх-,(-,э(х) v ф(х)) v Эх(ц(х) л -.э(х)) v Ух(-,ц(х) v ф(х)).

4. Зх(э(х) л -.ф(х)) v Эх(ц(х) л -1э(х)) v Ух(-,ц(х) v ф(х)).

Обоснуйте шаги эквивалентных преобразований самостоятельно.

5.3. Пусть А — формула КЛП-языка в негатив­но-нормальной форме, определенная по усло­виям упражнения 5.2. Покажите, что -iA<=>B, где В — формула, полученная из А заменой всех кванторов vx на Зх и Зх на Vх; всех пропозициональных связок л на v и v на л; всех отрицаний атомарных формул на сами эти формулы и всех атомарных формул на их отрицания.

Пример. (См. пример к упр. 5.2.)

А = Зх(э(х) л ~.ф(х)) v Зх(ц(х) л ~.э(х)) v Vx(-Jj(x) v ф(х)).

-А = -,(эх(э(х) л -пф(х)) v Эх(ц(х) л -,э(х)) v Vx(-fl(x) v ф(х))).

-А = -Зх(э(х) л -.ф(х)) л -пЗх(тДх) л -.э(х)) л -,Vx(-,H,(x) v ф(х)).

-А = Ух-,(э(х) л -Л>(х)) л Ух-,(ц(х) л ->э(х)) л Эх-ЈтЦ(х) v ф(х)).

-Л = Ух(-а(х) v ф(х)) л Ух(-,ц(х) л э(х)) л Зх(ц(х) v -,ф(х)).

Определение 5.6. Пусть А — формула КЛР-языка в негативно-нормальной форме, формула В получе­на из формулы А заменой всех встречающихся в ней

кванторов Vx на Зх, кванторов Эх на Vx; всех встречающихся в ней пропозициональных связок а на v и v на л; всех встречающихся в ней отрица­ний атомарных подформул на сами эти подформулы м всех встречающихся в ней атомарных подформул на их отрицания. Тогда формула В называется контр-дуалом для формулы А в КПП-языке.

5.4. Докажите следующую теорему.

Теорема 5.2. Пусть А — произвольная фор­мула КЛП-языка в негативно-нормальной форме, формула В является контрдуалом фор­мулы А. Тогда и- -iA <=> В.

5.5. Следующие выводы КЛП переведите на язык силлогистики, подобрав подходящие примеры, сформулированные в естественном языке.

1. vx(m(x) -» -iP(x)), dx(s(x)A m(x)) => Зх-ф(х) -*• р(х)).

2. -ах(м(х) л р(х)), Ух-т(м(х) л ^S(x)) => 3x(s(x) л -iP(x)).

5.2. Теория моделей классической логики предикатов

Теоретико-модельное исследование классической логики предикатов обращено к изучению логичес­ких отношений, связывающих выражения формаль­ного КЛП-языка е описанной в них структурой ре­альности. Иными словами, теория моделей представ­ляет собой раздел теоретической логики, изучающий соотношения между формальным языком и его ин­терпретациями, или моделями. Теорию моделей ло­гики предикатов обычно называют классической те­орией моделей.

Итак, теория моделей является областью теорети­ческой логики» изучающей методы и средства, соот­носящие выражения языка со структурами реально­сти. Это означает, что каждой паре, состоящей из высказываний языка и модели, ставится в соответ­ствие одно из истинностных значений — истинно или ложно. Вводимое таким образом понятие ис­тинности играет роль моста, связывающего формаль­ный язык с его интерпретацией в реальности посред­ством моделей. Если высказыванию А и модели М сопоставлено истинностное значение «истинно», бу­дем говорить, что высказывание А истинно в модели М, а также, что М является моделью высказывания А. В противном случае мы говорим, что высказыва­ние А ложно в модели М и что М не является моде­лью для высказывания А.

М является моделью для множества высказыва­ний. ecли M является моделью для каждого из этих высказываний, то есть каждое такое высказывание истинно в модели М. Множество высказываний

формального языка, истинных в модели М, называ­ется описанием ситуации, состояния дел, сложив­шихся в реальности. Такое описание реальной ситу­ации представлено языковыми средствами в «про­екции» интерпретирующей модели М.

Аналитическим фактором, придающим теории моделей характеристику единства, является прово­димое в этой теории различение синтаксиса и семан­тики. Синтаксис имеет дело с чисто формальной структурой языка. Например, понятия подформуль-ности или совокупности входящих в формулу сим­волов являются синтаксическими категориями фор­мализованного языка. Синтаксические характерис­тики КЛП-языка были подробно рассмотрены в разделе 5.1.

Семантика изучает интерпретацию или область значений элементов формального языка. Скажем, ис­тинность или ложность высказываний в модели — вопрос семантический. Таким образом, в теории мо­делей исследуется взаимодействие синтаксического и семантического уровней логического анализа.

Объясненная таким образом теория моделей от­ражает классическую идеологию общей философской концепции истины, восходящей в своих теоретичес­ких источниках к логике и философии Аристотеля. В соответствии с классической концепцией, быть ис­тинным означает соответствовать действительно­му положению дел в реальном мире. Поэтому эту философскую концепцию называют также коррес­пондентской теорией истины.

Применительно к изучаемой здесь теории моде­лей классическая философская концепция исти­ны может быть переформулирована следующим об­разом: «быть истинным высказыванием» означает

быть адекватным описанием соответствующей си­туации, сложившейся в реальности и отображенной в ее модели. Содержательно классическое понима­ние истинности является достаточно ясным, однако для использования в теоретической логике оно дол­жно получить более точную формулировку. Такое уточнение классической концепции истины в терми­нах формальных языков типа КЛП-языка как раз и является областью исследования в теории моделей.

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

Предположим, что анализируемый формальный язык является фрагментом КЛП-языка и его син­таксис включает следующие символы: индивидные константы — а1, а2, а3, которые читаются: «Джон», «Джейн» и «Майкл» соответственно; одноместные предикатные символы — Р*, Р*, читаются соответствен­но: «быть юношей» и «быть девушкой»; двуместные предикатные символы Р2, Р: «любить» и «дружить». Таким образом, формальный язык L, анализируемый как фрагмент КЛП-языка, задается упорядоченной последовательностью:

L = <a1,a2,a3,P1SP21,P12,P22>.

Понятие модели М для языка L можно задать упорядоченной парой М = (U, Р), где U — предмет­ный универсум индивидов, а Р — множество преди­катов, то есть свойств или отношений, определенных на предметном универсуме U.

Ясно, что относительно интерпретируемого языка L предметный универсум ограничен тремя индивидами,

соответствующими индивидным константам ах, а2, а3, то есть U = \а1> а2> а^ jt где а^ — Джон-индивид, а^ — Джейн-индивид и»з — Майкл-индивид. Записи а и а различаются как термин языка L, выражающий единичное имя, и индивид, принадлежащий предмет­ному универсуму U модели М.

Одноместные предикаты Р*, РЈ интерпретируются на модели М предикатами р и р. По содержател ным интуициям совершенно ясно, что pi = Неформально говоря, это означает, что свойство «быть юношей» приписывается индивидам Джону и Май­клу, а свойство «быть девушкой» — естественно, Джейн.

С логической точки зрения для каждого двумест­ного предикатного символа языка L, Р2 или Р2, имеют место ровно U2 = З2 =9 логически возможных интер­претаций, определенных на модели М. Это означает в нашем случае, что предикат Р^ может быть задан некоторыми упорядоченными парами индивидов из полной последовательности таких пар, определенных на U2. То есть

P2 и U2 =

\а2> а2/> \*_2» *_3 /' \аЗ> %/» \аЗ» а2/> \аЗ> a

Относительно множества логически возможных ситуаций, предназначенных для интерпретации сим­волов языка L, можно мыслить множество альтер­нативных моделей, определенных на структуре М = (U, p) и представляющих альтернативные состо­яния дел в реальности.

Примеры. Ml = <U,P), U = Ka^aJ. Р/ = {а^,^}, ^ = (аД

Неформальная интерпретация. Состояние дел, фиксируемое Mi-моделью, представляет собой орди­нарный треугольник неразделенной любви. Джон любит Джейн, но Джейн любит Майкла, который, в свою очередь, никого не любит, кроме себя. Несмотря на эгоизм Майкла и соперничество юношей в «пред­мете вожделения», все же Джон и Майкл дружат друг с другом.

Сказанное вытекает из Mi-истинности следующих высказываний:

1. Джон — юноша.

2. Джейн — девушка.

3. Майкл — юноша.

4. Джон любит Джейн.

5. Джейн любит Майкла.

6. Майкл любит себя.

7. Джон дружит с Майклом.

8. Майкл дружит с Джоном.

9. VxjVx2 (p| (xj, х2) -» Pg (x2, Xj)). Для любой пары индивидов: если первый дружит со вторым, значит второй дружит с первым.

10. Vx—iP|(x,x). Никто не может дружить сам с собой.

Ml-истинность формул 9 и 10 не обозначена яв­ным образом в условиях Mi-модели, но имплицит­но содержится в контексте ее содержательной интер­претации. Действительно, если по условиям Ml-моде­ли Джон дружит с Майклом, то с необходимостью

следует, что Майкл дружит с Джоном. Точно так же интуитивно ясно, что невозможно дружить с самим собой. Для pi эти интуиции могут не выполняться.

М2 = (U,P), U = КаД р = {ааД р = {aj,

Неформальная интерпретация. Реальная ситуация, фиксируемая в М2-модели, представляет собой такое состояние дел, когда юноши, Джон и Майкл, исклю­чительно эгоистичны и любят лишь самих себя. Джейн, наоборот, любвеобильная альтруистка и гото­ва любить всех, кроме себя. Кроме того, никто ни с кем не желает дружить, поэтому интерпретация пре­диката Р| пуста.

Сказанное следует из М2-истинности следующих высказываний:

1. Джон — юноша.

2. Джейн — девушка.

3. Майкл — юноша.

4. Джон любит себя.

5. Джейн любит Джона.

6. Джейн любит Майкла.

7. Майкл любит себя.

8. VXi-axjjPl^x^Xa). Никто ни с кем не дружит.

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

Определение 5.7. М-моделью, предназначенной для интерпретации формального КПП-языка классической логики предикатов, называется упорядоченная пара M = (U,f), где U — непустое множество; f — функция такая, что f (pn)e {l,0} при n = О, f (pn)s Un при n > 0; если f(y)= a, то as U.

Необходимые неформальные объяснения, касаю­щиеся определения 5.7 М-модели, кратко могут быть изложены в следующих ситуациях.

Непустое множество U представляет собой предмет­ный универсум интерпретации: U = {«ц,«ц,...,«ц,...J. Предметный универсум индивидов может быть сколь угодно большим и ограничен лишь требованием непустоты. Каждой индивидной константе a., i > 1, КЛП-языка ставится в соответствие индивид «Ц из универсума U, определенного на М-модели.

Для интерпретации предикатных символов КЛП-язы­ка в структуру М-модели вводится функция припи­сывания f, которая каждому n-местному предикат­ному символу Р" ставит в соответствие предикат Р в качестве приписанного значения для f(Pn). Если Р" — пропозициональный символ, то есть n = 0, то Р^ е {l>0}, где 1 и О соответственно предикаты «истин­но» и «ложно». Если Рп — предикатный символ, то есть n > О, то Р" с U" • Функция f каждой свободной предметной переменной у приписывает в качестве ее значения индивид из универсума U, то есть f (y)e U.

Определение 5.8. Пусть А — произвольная форму­ла КЛП-языка со свободными переменными у,,..., уп. Тогда ее истинностное значение при заданном при­писывании f(yi)=^i» •••» НУп)= |4i определяется в М-модели рекурсивно следующими условиями.

1. А = Р°. Значение f(A) определено М-моделью.

2. А = Р(у,,..., У„)- А = 1, если и только если

^aj_,...,a,,Je f(Pnj. в противном случае А = 0.

3. А = — iB. А = 1, если и только если В = 0.

4. А = В л С. А = 1, если и только если В = 1 и С = 1.

5. A=BvC. A = 1, если и только если В = 1%*б = 1.

ЧПЧ

6. А = В — > С. А = 1, если и только если В = 0-и С = 1.

7. А = VxB(x, yj,...,-уп). А = 1, если и только если В(у, у,, —, Уп) = 1 при каждом приписываемом f та-

ком, что f*(y)e U, fl(yi)=ai,..., f16'n)=^n •

8. A = 3xB(x,y1,...,yn). А = 1, если и только если В(У> У,, •••, Уп) = 1 при некотором приписании f, таком, что f'(y)eU, f1(yi)=ai,...,f1(yn)=?n.

Определение 5.9. Формула А (у,,..., уп) называет­ся М-истинной, если и только если А = 1 при любом

приписывании f. Обозначается: Mh=A(y1,...,yn).

Определение 5.10. Формула А (у,,..., уп) называ­ется логически истинной в классической логике пре-

дикатов, если и только если Mb=&yi,...,yn для каж­дой М-модели, определенной на структуре М = (U, f }.

В определениях 5.7-5.10 достаточно прозрачно уточняются основные семантические понятия клас­сической логики предикатов — понятия модели, ис­тинности в модели и логической истинности. Важно, что эти определения существенно опираются в своей идеологии на философскую классическую концепции истины, а поэтому сами приобретают образ класси­ческой теории моделей. Однако развитые таким об­разом теоретико-модельные понятия при всех их

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

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

Одним из таких косвенных методов установле­ния логической истинности формул КЛП-языка яв­ляется метод «безуспешного» поиска М-контрмоде-ли, опровергающей М-истинность искомой формулы. Суть дела сводится к следующей схеме косвенного доказательства. Вместо прямого доказательства ло­гической истинности формулы делается допущение, что формула может быть М-ложной и, поэтому, иметь опровергающую ее М-контрмодель. Если попытка построить такую М-контрмодель оказывается безус­пешной и приводит к противоречию в рассуждении, то это дает основания для утверждения логической истинности искомой формулы. Ясно, что здесь исполь­зуется известный уже метод рассуждения от против­ного или сведения доказательства к противоречию.

Пример 1. Доказать методом поиска М-контр-мо-дели: 1= 3x(A(x)v b(x))-> (3xA(x)v ЗхВ(х)). Символ н= означает: «логически истинно».

Доказательство. Допустим, что данная форму­ла не является логически истинной. Тогда для нее имеется М-контрмодель, в которой по КЛВ (1) |3x(A(x)v В(х))]= 1 и (2) (3xA(x)v ЗхВ(х)] = О. Из (1) по

условию 8 определения 5.8 следует (3) [А.(у) v В(у)] = 1 для некоторого, по крайней мере одного, приписыва­ния f такого, что f(y)e U. Случай (3) по условию 5 распадается на два подслучая: (4.1) [А(у)] = 1 или (4.2) [В(у)] = 1 при некотором заданном приписы­вании f.

С другой стороны, (2) по КЛВ влечет (5.1) [ЭхА(х)]=0, (6.1) [ЗхВ(х)]=0, (5.2) [ЗхА(х)]=Ои (6.2) [ЗхВ(х)] = 0, то есть ложность дизъюнкторов из (2) в обоих подслучаях. Но из (5.1) следует (7.1) [А(у)] = 0 при любом приписывании, в том числе и f, что противоречит (4.1). Из (6.2), в свою очередь, следует (7.2) [В(у)] = 0 при любом приписывании, в том числе и f, что противоречит (4.2).

Таким образом, доказано, что анализируемая в примере формула зх(а(х) v b(x)) -> (ЗхА(х) v ЭхВ(х)) не имеет М-контрмоделей и, поэтому, является логи­чески истинной. Доказательство завершено.

Пример 2. Доказать методом поиска М-контрмо-дели: -н (VxA(x) -> VxB(x)) -» Vx(A(x) -» b(x)). Сим­вол =н означает: «опровержимо».

Доказательство. Для доказательства опровер-жимости данной формулы следует найти для нее М-контрмодель, в которой: (1) [VxA(x) —> VxB(x)] = 1 и (2) [Vx(A(x)-*B(x))]=0.

Из (2) по условию 7 определения 5.8 следует, что имеет место (3) [А^) -» В(ух)]= 0 для некоторого приписывания f1 такого, что f1(y1)e U. (3), в свою очередь, по КЛВ влечет (4) [А(ух)] = 1 и (5) [Щу^] = О при заданном приписывании f1.

Случай (1) по условию 5 распадается на два под-случая: (6.1) [VxA(x)]=0 или (6.2) [VxB(x)] = l. Подслучай (6.2) закрывается, так как из него следу-

ет по условию 7 (7.2) [В(у1)] = 1 для любого припи­сывания, в том числе и приписывания f1. Тогда (7.2) противоречит (5).

Подслучай (6.1) требует по условию 7 введения новой свободной переменной у2, не встречающейся ранее в рассуждении, то есть (7.1) [А(у2)] = О при новом приписывании f2, отличающимся от f1 только тем, что f1^)^ f2(y2). Противоречия между (7.1) и (4) не возникает. Следовательно, данный подслу-чай и является М-контрмоделью, опровергающей ло­гическую истинность анализируемой формулы (VxA(x) -> VxB(x)) -» Vx(A(x) -> b(x)). Доказатель­ство завершено.

Упражнения

5.6. Докажите логическую истинность в класси­ческой логике предикатов следующих фор­мул методом поиска М-контрмоделей.

1. h= -iVx-iACx) <-> ЗхА(х);

2. i= -,VxA(x) <-> Зх-.А(х);

3. h= Vx-,A(x) <-> -i3xA(x);

4. h= VxA(x) <-» -.3x-.A(x);

5. h= Ух(А(х)л В(х)) о (УхА(х)л VxB(x)); 6.1= (VxA(x) v VxB(x)) -> Vx(A(x) v B(x)); 7. И=Зх(А(х)л В(х)) -^ (ЗхА(х)л ЗхВ(х)); 165

8. l= 3x(A(x)v b(x))<-> (3xA(x)v ЭхВ(х)).

5.7. Опровергните логическую истинность в клас­сической логике предикатов следующих фор­мул методом поиска М-контрмоделей.

1. -н Vx(A(x) v b(x)) -> (VxA(x) v VxB(x));

2. =н (ЗхА(х) л ЭхВ(х)) -» Зх(А(х) л b(x)).

Изложенный выше метод поиска М-контрмоде-лей для установления логической истинности фор­мул КЛП-языка достаточно тяжел в изложении, так как многие его фрагменты выражены в форме рас­суждений на естественном языке. Это затрудняет ре­гулярную эффективность поиска нужной контрмо­дели и, практически, делает невозможным конструк­тивное ведение доказательства. Далее в данном разделе описывается метод модельных конструкций, который, как представляется, свободен от указанных недостатков.

Определение 5.11. Пусть А — произвольная фор­мула КЛП-языка в негативно-нормальной форме, В — подформула формулы А. Тогда последовательность формул < А, В^..., Вп> образует список Сп[А] фор­мул, если она построена по следующим правилам:

1. Если В = А, то ВеСп[А].

2. Если В = (С л D) и Be сп[а], то Се сп[а] иям-DeCn[A).