Тема 3: От языковых структур к выражениям естественного языка и/или нелогических теорий: модели и контрмодели для множеств формул (продолжение)

Основные понятия, которые необходимо усвоить:

• интерпретация = возможная реализация

• истинность формулы в интерпретации

• модель для множества предложений ЯКЛП

• контрмодель для множества предложений ЯКЛП

Пояснения и определения

Строгое определение условий истинности и ложности связок – см. лекцию.

Примеры на построение моделей и контрмоделей

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

Пример 1 ∀х(Р(х)⊃Q(x))&∃x(P(x)&¬Q(x)

Ответ: у этой формулы вообще нет моделей, т.к. она как логически противоречива (вдумайтесь в то, что она утверждает).

Пример 2 ∃х(Р(х)&R(х,а)).

Смысл этого выражения: имеется объект, обладающий свойством Р и находящийся в отношении R с фиксированным объектом а.

Допустим, вы выбрали в качестве носителя интерпретации множество натуральных чисел (U={0,1,2,…}). Тогда вы обязаны:

• символу «а» сопоставить конкретный объект из области интерпретации, т.е. конкретное натуральное число;

• символу «Р» – одноместный предикат на множестве натуральных чисел (т.е. какое-то свойство натуральных чисел);

• символу «R» – двухместное отношение на множестве натуральных чисел.

Допустим, вы выбрали такую интерпретацию I:

• |a|_I = 0,

• |P|_I =свойство «быть четным»,

• |R|_I = отношение «<».

Тогда в выбранной вами интерпретации предложенная формула означает «Существует четное число, которое строго меньше 0», что неверно (принимают по определению, что 0 – четное число)». Стало быть, интерпретацию вы построили, но не ту, которую требовалось, не модель. Дело, конечно, легко поправимо. Достаточно изменить значение «а». Например, рассмотрим I*:

|a|_I* = 1

|P|_I* =свойство «быть четным»

|R|_I* = отношение «<»

В новой интерпретации смысл формулы таков: «Существует четное число, которое строго меньше 1», что истинно. (Это 0).

Пример 3 ∃x∃y∃z(P(x)&P(y)&P(z)&¬R(x,y)&¬R(z,x))v∀z(P(z)⊃(Q(z)vR(a,z))vR(a,а)

В силу ассоциативности конъюнкции и дизъюнкции несколько скобок опущены.

Все не так страшно, как может показаться. Формула представляет собой дизъюнкцию трех формул. Некоторые студенты стараются подобрать модель, где истинными будут все три дизъюнкта. Между тем это совсем необязательно. Чтобы нестрогая дизъюнкция оказалась истинной, достаточно, чтобы истинным был хотя бы один дизъюнкт (в нашем случае – одна из трех формул: ∃x∃y∃z(P(x)&P(y)&P(z)&¬R(x,y)&¬R(z,x)), или ∀z(P(z)⊃(Q(z)vR(a,z)), или R(a,а)) – вспомните табличное определение дизъюнкции. Значит, если мы найдем интерпретацию, в которой формула R(a,a) будет истинна, то в этой же интерпретации будет истинна и вся формула 3. Пойдем по этому пути.

Выберем в качестве носителя интерпретации множество людей (когда-либо живших).

Тогда (предметной) константе «а» надо сопоставить (логическое имя) конкретного человека, (предикатной) константе R – двухместное отношение между людьми, (предикатной) константе Р – свойство, определенное на людях.; причем в результате должно получиться истинное предложение (по требованию задачи)

Предикат R проинтерпретируем как «быть современником». Поскольку каждый человек сам себе современник, то в качестве значения константе «а» можно сопоставить (логическое имя) любого человека и формула R(a,а) превратится в истинное высказывание в нашей интерпретации (чтобы в ней не означал предикат Р). Таким образом, моделью для формулы R(a,а), а значит и для всей формулы 3 будет, например, такая интерпретация I:

U= множество людей (когда-либо живших).

|a|_I = Гай Юлий Цезарь

|P|_I =свойство «быть сангвиником»

|R|_I = отношение «быть современником».

*

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

Пример 4 ∀x∀y(x≠y⊃P(x,y)).

Смысл формулы – для любых объектов х и у верно: если эти объекты различны, то они находятся в отношении Р.

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

U= множество людей (когда-либо живших).

|R| = отношение «быть современником».

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

Пример 5 ∀х∃уР(х,у)⊃∃у∀хР(х,у)

Контрмоделью для формулы 2 будет такая интерпретация, в которой антецедент импликации (∀х∃уР(х,у)) истинен, а консеквент (∃у∀хР(х,у)) ложен (вспомните табличное определение импликации).

Следующие интерпретации не являются контрмоделью для формулы 2.

1. U = множество натуральных чисел (U={0,1,2,…}).

|Р| = «быть четным числом».

Ошибка: в нашей формуле Р – двухместный предикат, а «четное число» – одноместный.

2. U = множество натуральных чисел (U=N={0,1,2,…}).

|Р| = отношение «>».

Ошибка. Прочтем антецедент нашей формулы в данной интерпретации: «Для всякого натурального числа х найдется натуральное число у, такое что х>у», т.е. всякое (натуральное) число (строго) больше какого-нибудь, что неверно: для нуля в N не существует числа, которого он больше. Значит, антецедент импликации ложен. В таком случае вся импликация истинна (см. таблицу истинности для импликации). Значит, интерпретация (2) показывает, что формула 2 – не является логически непротиворечивой, а нам нужно по заданию другое: показать, что она логически необщезначима (= не является логическим законом).

Подойдет интерпретация из предыдущего примера:

U= множество людей (когда-либо живших).

|R| = отношение «быть современником».

В этой интерпретации:

• антецедент импликации (∀х∃уР(х,у)) означает «У всякого человека есть современник», что истинно;

• консеквент импликации (∃у∀хР(х,у)) означает: «Существует человек, которому всякий человек - современник», что ложно.

Значит вся импликация ложна в данной интерпретации, и, значит, она (интерпретация) является контрмоделью для формулы 2, что и требовалось.

*

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

Пример 6 Q(a)  Q(b) Q(c)

Формула читается: по меньшей мере один из объектов – а, b или с – обладает свойством Q.

Модель

U= множество римских первосвященников до Бенедикта XVI включительно.

|a|_I = Иоанн Павел II

|b|_I = Бенедикт XVI

|c|_I = Иоанн Павел I

|Q|_I = поляк

Q(a) в этой интерпретации истинно (Иоанн Павел II был поляком), значит, по определению условий истинности дизъюнктивной структуры, истинна и вся формула.

Конрмодель

U = множество римских первосвященников до Бенедикта XVI включительно.

|a|_I = Иоанн Павел II

|b|_I = Бенедикт XVI

|с|_I = Иоанн Павел I

| Q |_I = уроженец Австралии

Все дизъюнкты в этой интерпретации ложны (среди римских пап не было уроженцев Австралии). Значит, и вся дизъюнкция ложна.

Пример 7 ∃у(Р(у)  Q(у))

Формула читается: есть такой объект, для которого обладание свойством Р равносильно обладанию свойством Q.

Модель 1

U = {0, 1, 2, 3}

|Р|_I = делиться нацело на 3

|Q|_I = делиться нацело на 0

При (у)= 1, имеем: 1 делится нацело на 3  1 делится нацело на 0. Обе части эквиваленции ложны, значит вся эквиваленция истинна по крайней мере при одной оценке переменных. Значит, в этой интерпретации истинно ∃у(Р(у)  Q(у)).

Модель 2

Для построения модели надо на некотором носителе U найти такой объект u, что для него истинна будет эквиваленция Р(у)  Q(у) ( и при некоторой оценке : (у) = u). Эквиваленция истинна только в случае, если обе ее части оценены одинаково: либо как истинные, либо как ложные. Пойдем по второму пути.

U = гражданин РФ

|Р|_I = английский лорд

|Q|_I = конгрессмен США

Поскольку мы найдем такого гражданина РФ (пока что все граждане РФ такие), для которого ложно, что он английский лорд, и ложно, что конгрессмен США, эквиваленция истинна, и утверждение о существовании истинно.

Контрмодель

U = {0, 2, 4}

|Р|_I = делиться нацело на 2

|Q|_I = делиться нацело на 0

Какую бы оценку для у мы не взяли для формулы Р(у)  Q(у), в любом случае левая часть эквиваленции истинна, правая – ложна, т.е. не существует понимания у (функции оценки у), при котором наша формула в этой интерпретации истинна. Значит, построили контрмодель.

Пример 8 ∀у(Р(у)  (Q(у,а)  Q(у,b)))

Формула читается: Для любого объекта (из некоторой области) верно, что если он обладает свойством Р, тогда он находится в отношении Q с объектом а или b.

Модель

U= множество людей (когда-либо живших).

|а|_I = Аристотель

|b|_I = Аристофан

|Р|_I = классик русской литературы

|Q|_I = родиться раньше

(В данной интерпретации эта структура прочитывается: Для любого человека верно, что если он классик русской литературы, то родился раньше Аристотеля или Аристофана (или и того, и другого), или просто: Все русские классики родились раньше Аристотеля или Аристофана (или и того, и другого))

Контрмодель

U = множество людей (когда-либо живших).

|а|_I = Аристотель

|b|_I = Аристофан

|Р|_I = классик русской литературы

|Q|_I = родиться позже

Пример 9 ∀у∀x(ху  (Q(у,х)  Q(х,у)))

Формула читается: Для любых двух объектов х и у верно, что если они не совпадают, то у находится в отношении Q с х или х находится в отношении Q с у.

Модель

U = {Цезарь, Брут}.

|Q|_I = современник

Рассмотрим формулу ху  (Q(у,х)  Q(х,у)). При любом понимании х и у (а в этой интерпретации есть только два варианта: или Брут, или Цезарь), каждая из формул Q(у,х) и Q(х,у) истинна. Значит, при любой оценке х и у дизъюнкция истинна. В импликативной структуре А  В, если консеквент истинен, вся импликация истинна, независимо от значения антецедента. Значит формула ху(Q(у,х)Q(х,у)) истинна при любой подстановке вместо х и у. Значит, в этой интерпретации истинна формула

∀у∀x(ху  (Q(у,х)  Q(х,у))).

Контрмодель

U = множество людей (когда-либо живших).

|Q|_I = современник

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