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

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

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

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

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

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

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

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

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

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

L = lt; at, а2, а3, Р*, Р2, Р2, Р| gt;.

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

Ясно, что относительно интерпретируемого языка L предметный универсум ограничен тремя индивидами, соответствующими индивидным константам а{, а2, а3, то есть U = {а, , а2, а3 Где at — Джон-индивид, а2 — Джейн-индивид и ад — Майкл-индивид. Записи а и а различаются как термин языка L, выражающий единичное имя, и индивид, принадлежащий предметному универсуму U модели М.

Одноместные предикаты Р|, Р2 интерпретируются на модели М предикатами Р[ и Р2 . По содержательным интуициям совершенно ясно, что Pj = \а,,а3}. Неформально говоря, это означает, что свойство «быть юношей» приписывается индивидам Джону и Майклу, а свойство «быть девушкой» — естественно, Джейн.

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

P^cU2 и U2 = {(aJ» а1 )gt; («I gt;              а3 )’ (а2 ’ )»

(а2gt; аг)gt; (а2gt; аз )’ (аз* ai)’ (азgt; аг)gt; (азgt; аз)}Относительно множества логически возможных ситуаций, предназначенных для интерпретации символов языка L, можно мыслить множество альтернативных моделей, определенных на структуре М = (и, Р) и представляющих альтернативные состояния дел в реальности.

Примеры.

Ml = (и,Р), и = К,02,аз), Р? = К,аз}, Р,1 = {а2}, +1 = {(а1,а2)’(а2gt; аз)gt; (азgt;аз) }» ^2 = {(а1»аз)gt; (аз»а1) }•

Неформальная интерпретация. Состояние дел, фиксируемое Ml-моделью, представляет собой ординарный треугольник неразделенной любви.

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

1. Джон — юноша.
2. Джейн — девушка.
3. Майкл — юноша.
4. Джон любит Джейн.
5. Джейн любит Майкла.
6. Майкл любит себя.
7. Джон дружит с Майклом.
8. Майкл дружит с Джоном.
9. Vx, Vx2 (Р2 (хх, х2 ) -gt; Р2 (х2, Xj ))- Для любой пары индивидов: если первый дружит со вторым, значит второй дружит с первым.
10. Vx-iP2(x,x). Никто не может дружить сам с србой.

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

М2 = (U,P), U — {а1,а2,а3 }, Pt = {а1,а3 }, Р2 — {а2}, ^1 = 1{а1 ’ Щ}’ (а_2gt;              )» (а2¦gt; ^3)’ (а3’ аз)}’ ^*2 = {0 }•

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

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

1. Джон — юноша.
2. Джейн — девушка.
3. Майкл — юноша.
4. Джон любит себя.
5. Джейн любит Джона.
6. Джейн любит Майкла.
7. Майкл любит себя.
8. Vxj-iBXgP^x^x^. Никто ни с кем не дружит.

Таким образом, для одной и той же модельной

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

Определение 5.7. М-моделью, предназначенной для интерпретации формального КЛП-языка классической логики предикатов, называется упорядоченная пара M = (U,f), где U — непустое множество; f —

функция такая, что f(pn)e {l,o} при п = 0, f(pn)c Un при п gt; 0; если f(y)= а, то а є U.

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

Непустое множество U представляет собой предметный универсум интерпретации: U =

Предметный универсум индивидов может быть сколь угодно большим и ограничен лишь требованием непустоты. Каждой индивидной константе а., і gt; 1, КЛП-языка ставится в соответствие индивид а; из универсума U, определенного на М-модели.

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

Определение 5.8. Пусть А — произвольная формула КЛП-языка со свободными переменными уп.

Тогда ее истинностное значение при заданном приписывании Г(Ух) = ai,              f(yn)=a попределяется в

М-модели рекурсивно следующими условиями.

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

^ах,...,ап^ є f(p"). в противном случае А = 0.

3. А = —iB. А = 1, если и только если В = 0.
4. А=ВлС. А= 1, если и только если В = 1 и С = 1.
5. А = В v С. А= 1, если и только если В = 1 и С = 1.
6. А = В —gt; С. А = 1, если и только если В = 0 и С = 1.
7. А = VxP»(x,у1,...,уп).
   А = 1, если и только если В(у, у^ ..., уп) = 1 при каждом приписываемом f таком, что f^JeU, ft(yi)=ax, .              f1(yn)=
8. А = ЗхВ(х,у1,...,уп). А = 1, если и только если В(у, у1,..., уп) = 1 при некотором приписаним іл таком,

что f‘(y)eU, f%i)=ai, .. .f^nb^nОпределение 5.9. Формула А (у,,уп) называется М-истинной, если и только если А = 1 при любом

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

Определение 5.10. Формула А (у,, ..., уп) называется логически истинной в классической логике предикатов, если и только если Mt==A(y1,...,yn) для каждой М-модели, определенной на структуре М = (U, f).

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

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

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

Пример 1. Доказать методом поиска М-контр-мо- дели:              3x(a(x)v              в(х))-gt;              (3xA(x)v              ЗхВ(х)).              Символ

h= означает: «логически истинно».

Доказательство. Допустим, что данная формула не является логически истинной. Тогда для нее имеется М-контрмодель, в которой по КЛВ (1) [3x(A(x)v В(х))] = 1 и (2) |3xA(x)v ЗхВ(х)]= О . Из (1) по условию 8 определения 5.8 следует (3) [а(у) v В(у)]=1 для некоторого, по крайней мере одного, приписывания f такого, что f(y)e и. Случай (3) по условию 5 распадается на два подслучая: (4.1) [А(у)] = 1 или

2. [ В(у)] - 1 при некотором заданном приписывании f.

С другой стороны, (2) по КЛВ влечет (5.1) [ЗхА(х)]=0, (6.1) [ЗхВ(х)]=0, (5.2) [ЗхА(х)] = Ои

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

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

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

Доказательство. Для доказательства опровер- жимости данной формулы следует найти для нее М-контрмодель, в которой: (1) [VxA(x) -gt; VxB(x)j= 1 и (2) [\/х(а(х) -» В(х))] = 0.

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

Случай (1) по условию 5 распадается на два подслучая: (6.1) [\/хА(х)]=0 или (6.2) [VxB(x)]=l. Подслучай (6.2) закрывается, так как из него следует по условию 7 (7.2) [В(ух)] = 1 для любого приписывания, в том числе и приписывания f1. Тогда (7.2) противоречит (5).

Подслучай (6.1) требует по условию 7 введения новой свободной переменной у2, не встречающейся ранее в рассуждении, то есть (7.1) [А(у2)] = О при новом приписывании f2, отличающимся от f1 только тем, что f1(y1)5t f2(y2) • Противоречия между (7.1) и (4) не возникает. Следовательно, данный подслучай и является М-контрмоделью, опровергающей логическую истинность анализируемой формулы (VxA(x) —gt; VxB(x)) —gt; Vx(a(x) —gt; В(х)). Доказательство завершено.

Упражнения

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

1. h= —iVx—iA(x) lt;-gt; ЗхА(х);
2. h= -iVxA(x)              Зх-іА(х);
3. t= Vx-iA(x)              —i3xA(x);
4. VxA(x) lt;-gt; -i3x-iA(x);
5. h= Vx(a(x)a B(x)) lt;-gt; (VxA(x) a VxB(x));
6. (VxA(x)v VxB(x)) —gt; Vx(a(x) v B(x));
7. i==3x(a(x)a B(x)) —gt; (ЗхА(х) a 3xB(x));
8. Н= Зх(а(х) v В(х)) lt;г» (ЗхА(х) v ЗхВ(х)) .

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

1. HVx(A(x)v В(х)) -gt; (VxA(x)v VxB(x));
2. =н (ЗхА(х) л ЗхВ(х)) —gt; Зх(а(х) л В(х)) .

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

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

1. Если В = А, то Be Сп[А].
2. Если В = (С л D) и Be Сп[а], то Се Сп[а] или D є Сп[а) .
3. Если В = (С v D) и Be Сп[а) , то Се Сп[а) или De Сп[а).

4. Если В = ЭхС(х,у1,...,уп) и Вє Сп[а], то

С(у,у1,...,уп)є Сп[а]для новой свободной предметной переменной у, yt встречающейся в списке Сп[А].

5. Если В = VxC(x,y11...,yn) и Вє Сп[а], то

С(у,у1,...,Уп)є Сп[а)для каждой свободной предметной переменной у, встречающейся в списке Сп[А[.

Определение 5.12. Модельной МК[А]-конструкци- ей для формулы А называется множество альтернативных списков формул {Сп[а]1,...,Сп[а]п}1 построенных по правилам определения 5.11.

Определение 5.13. Список Сп[А] называется замкнутым, если он содержит формулу В такую, что

В є Сп[а]и -.Вє Сп[а] . Модельная конструкция называется замкнутой, если замкнут каждый принадлежащий ей список формул из {Сп[а]1,...,Сп[а]п}.

Определение 5.14. МК-моделью для формулы А

называется любой незамкнутый список формул Сп[А].

Определение 5.15. Формула А называется МК-ис- тинной, если и только если она имеет МК-модель, определенную на №К[А]-конструкции.

Определение 5.16. Формула А называется логически истинной в классической логике предикатов, если и только если ее контрдуал, то есть негативно-нормальная форма формула —і А, не является МК-истинным ни на одной из МК-моделей. Обозначается. h=A.

Теорема 5.3. А на модельной структуре М = (U, f) если и только если t=A на модельной конструкции МК [А].

Теорема приводится без доказательства.

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

В МК[А]-конструкции реализуется концепция когерентности истины. В соответствии с когерентной концепцией истины высказывание является истинным, если оно совместимо с множеством других высказываний и может быть включено в данное множество без противоречия. Безусловно, в модельные структуры и модельные конструкции вкладывается различный философский смысл относительно понятия истинности. Модельные структуры определяют семантическую категорию истинности как отношения между языком и реальностью. В модельных конструкциях категория истинности устанавливает отношения между лингвистическими объектами: формулой и списком формул. В модельных структурах основными семантическими понятиями являются понятия предметного универсума и определенного на нем множества предикатов, то есть, в целом, — понятие состояния объекта. В модельных конструкциях

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

Пример 1. Доказать методом модельных конструкций логическую истинность формулы

Зх(а(х) л В(х)) —gt; (ЗхА(х) л ЗхВ(х)) .

Доказательство. Приведем данную формулу в негативно-нормальную форму методом эквивалентных преобразований.

1 • А = Зх(а(х) л В(х)) -» (ЗхА(х) л ЭхВ(х)) .

2.              —,Зх(а(х)л B(x))v (ЗхА(х)л ЗхВ(х)).              KJIB

А0 = Vx(—iA(x) v -іВ(х)) v (ЗхА(х) л ЭхВ(х)) ,              ,              л/

где А0 — негативно-нормальная формула для А.

4. Контр. A[a]=3x(a(x)aB(x))a(Vx-,A{x)vVx-gt;B(x)),гдеКонтр. А[А] — контрдуал для формулы А0.

Модельная конструкция контрдуала для формулы А0 строится в соответствии с правилами 1-5 определения 5.11.

Следовательно, по определениям 5.12-5.16: (=А.

Пример 2. Проверить логическую корректность следующего силлогизма методом модельных конструкций.

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

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

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

Решение. Данный силлогизм имеет следующий перевод на формальный язык (см. пример к упр. 5.1) \/х(э(х) -gt; ф(х)), -іЗх(ц(х) л |Э(х)) =gt; \/х(ц(х) -» Ф(х)).

Данный перевод силлогизма на формальный язык имеет следующую негативно-нормальную форму (см. пример к упр. 5.2.)

Vx(—|Э(х) V ф(х)) A Vx(—1І((х) А э(х)) А Зх(ц(х) v іф(х)).

Построим модельную конструкцию для контрду- ала формулы А в негативно-нормальной форме, используя условия 1-5 определения 5.11.

Модельная конструкция для контрдуала замкнулась. Следовательно, силлогизм логически корректен.

Упражнения

8. Проверьте логическую корректность силлогизмов, приведенных в упр. 5.1, методом модельных конструкций.
9. Докажите логическую истинность формул упр. 5.6 методом модельных конструкций.
10. Опровергните логическую истинность формул упр. 5.7 методом модельных конструкций.