Главная | Обратная связь | Поможем написать вашу работу!

Интерпретация формул с логическими связками.

Пусть А(х) и В(х) - атомные формулы, заданные своими функциями интерпретации I_Аi(x) и I_B_j(x), тогда логическое значение формулы А(х)&В(х) определяется как конъюнкция функций интерпретации сомножителей. I_Ai(x)&I_Bj(x).

Если D_Aи D_B- области истинности формул A(x) и B(x), то область истинности конъюнкции определяется пересечением областей истинности D_Aи D_B: D_A_&_B==D_AÇD_B.Т.е. логическое значение формулы, образованной с использованием логических связок на каждом наборе значений переменных определяется как логическое значение соответствующей связки, примененной к значениям функций интерпретации атомных подформул на тех же наборах значений переменных.

Примеры

6. Найти логическое значение формулы (P®(Q&R)), если логические значения постоянных формул (P, Q,R) заданы тройкой (1,0,0).

Формула содержит 0-местные предикаты P, Q,R, поэтому ее значение в заданной интерпретации в любой предметной области определяется в соответствии с правилами логики высказываний как I[1® 0&0]=0.

7. Найти значения формулы (Q®Р(х)), если предметная область D={1,2,...,6}, и заданы функции интерпретации предикатов: I[ Q ]=1, I[ P(x) ]=I₁₃(x).

Таблица 7

x
P(x)
Q®P(x)

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

Интерпретация формул, содержащих кванторы

Логическое значение формул, содержащих кванторную приставку по переменной х, определяется для квантора существования $ как максимум из логических значений формулы, когда переменная кванторной приставки «пробегает» всю предметную область, и как минимум для квантора общности ", т.е.

Здесь d - объект из предметной области, являющийся интерпретацией I(x) параметрического терма х, когда переменная x ²пробегает² предметную область.

При определении логического значения формул логики предикатов необходимо учитывать следующие правила:

вначале выполняются действия в скобках;

кванторы связывают сильнее, чем отрицание, отрицание - сильнее, чем конъюнкция, конъюнкция - сильнее, чем дизъюнкция и импликация, последние - сильнее, чем эквивалентность.

Примеры

8. Найти логическое значение формулы $у Р(х,у) в модели:

M = ({1,2,3}; Р; I₁₃₁ [Р])

Формула является условием, так как переменная x входит в нее свободно. Следовательно, необходимо определить логическое значение формулы для каждого значения переменной x. Атом P 2-местный. Таблица истинности для него содержит строк (число размещений с повторениями из 3 по 2), а число различных функций интерпретации равно В заданной интерпретации I[Р(х,у)]=(010000011). Операции по построению таблицы истинности формулы даны в табл. 8.

Переменная х свободна в данной формуле, поэтому значение формулы с кванторной приставкой по переменной у определяется для каждого значения переменной x как максимум значений подформулы Р(х,у), когда переменная y пробегает всю предметную область.

Таблица 8

x	1 1 1	2 2 2	3 3 3
y	1 2 3	1 2 3	1 2 3
I[ Р(х,у) ]	0 1 0	0 0 0	0 1 1
I[$ yР(х,у) ]

9. Найти логическое значение формулы " х $ у Р(х,у) в модели D=({1,2,3}; P⁽²⁾; I₁₃₁[ Р(x,у) ]).

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

Таблица 9

х	1 1 1	2 2 2	3 3 3
у	1 2 3	1 2 3	1 2 3
I₁₃₁ Р(х,у)	0 1 0	0 0 0	0 1 1
$ у I₁₃₁ Р(х,у)
" x $ y I₁₃₁ Р(x,y)

10. Составить таблицу истинности формулы

$х(Р Ú Q(х)) ® Q(у) в предметной области D={1,2).

Истинностная таблица формулы языка логики предикатов в заданной предметной области содержит:

все возможные наборы значений переменных, имеющих свободное вхождение в формулу,

все возможные значения истинности атомных постоянных формул,

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

Переменная х входит в эту формулу связанно, а переменная y свободно. Следовательно, значение истинности всей формулы определяется значением переменной у в каждой возможной интерпретации атомной формулы Q(у).

Определим число строк таблицы истинности данной формулы. Переменные х и у пробегают предметную область. Каждому вхождению переменных необходимо сопоставить две строки таблицы истинности.

Так как функция интерпретации предикатных символов не указана, следует рассмотреть все возможные интерпретации формул Q(x,у) и Р. Из приведенных выше примеров очевидно, что в рассматриваемой модели атомная формула Q(х) может иметь четыре различных функции интерпретации.

Таблица 10

$ х	(Р	Ú	Q	(х))	®	Q	(у)

Постоянная атомная формула Р может иметь два истинностных значения: 0 и 1.

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

Значениям истинности подформулы, находящейся в области действия квантора существования по переменной x, соответствует столбец под знаком Ú. Последовательность действий при определении логического значения формулы очевидна из табл. 10.

11. Составить таблицу истинности формулы

" y ($ х (Р Ú Q (х))® Q(у)) в модели M=({1,2}, P⁽¹⁾, Q⁽²⁾).

Построение таблицы истинности подформулы, находящейся в области действия квантора общности, приведено в табл. 10, а таблицы истинности для всей формулы - в табл. 11.

Таблица 11

" у	($ х	(Р	Ú	Q	(х))	®	Q	(у))

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

12. Пусть предикат Р(х,у,z) означает х+у=z, х.у,z Î NÈ{0}.. Тогда I[P(3,5,3)] =0, I[ Р(3,5,8)] =1, I[Р(0,4,2)] =0. Выясним, как влияет квантор на смысл формулы.

Атом P(x,y,z) 3-местный, а формула $ у Р(х,у,z) задает 2-местный предикат, в списке свободных переменных которого отсутствует переменная у. Сигнатура в данном случае содержит один функциональный символ + и один символ отношения Р. При подстановке конкретных значений объектов из предметной области вместо свободных вхождений переменных получаем истинную или ложную формулу. Например, I[$ у Р(2,у,3) ]=1, I[ $у Р(0,у,0) ]=1, I[$ у Р(5,у,2) ]=0.

Понятно, что формула $ у Р(х, у, z) означает предикат x£ z.

На этом примере легко понять, почему свободные и связанные переменные играют разную роль в формуле:

вместо связанной переменной нельзя подставить конкретное значение, так как при этом получится бессмысленное выражение; так, запись $3(Р(2,3,3)) не имеет разумного смысла;

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

Пусть х₁, х₂,...,х_n -полный список свободных переменных формулы А.

Через обозначим формулу, в которой все свободные вхождения переменных связаны квантором общности. Такая формула называется замыканием А. Если формула А не содержит свободных переменных, то будем считать, что замыкание А совпадает с А. Заметим, что замыкание формулы является постоянной формулой. Аналогично через обозначим формулу $ x₁ … $ x_nA(x₁,…,x_n).

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

Формула А называется выполнимой, если она истинна в какой-либо интерпретации и в какой-нибудь модели. Таким образом, формула общезначима, если , и выполнима, если . Очевидно, что всякая общезначимая формула выполнима. Обратное не справедливо.

Действительно, рассмотрим постоянную формулу F =$ х " у r(х, у), r - двуместный предикат из множества R и две модели M₁ = (D₁, r⁽²⁾, I₁) и M₂ = (D₂, r⁽²⁾, I₂), которым соответствуют предметные области D₁=N и D₂=R (множества натуральных и действительных чисел соответственно). Сигнатура содержит единственный предикатный символ r⁽²⁾, означающий £. в модели M₁ формула F означает: существует наименьшее натуральное число, и она истинна. В модели M₂ формула F означает: существует наименьшее действительное число, и она ложна. Следовательно, указанная формула выполнима, но не общезначима.

Общезначимая формула А обозначается: ╞ А. Например, ╞ Если формула А не выполнима ни в какой модели, т.е. ни в какой предметной области и ни в какой интерпретации, она называется противоречием. Например, .

В бескванторных формулах вопрос о логическом значении формулы решается непосредственным использованием правил определения логического значения связок &, Ú, Ø, ®, «. Для формул с кванторами процедура определения логического значения формулы осложняется тем, что предметные переменные имеют в общем случае бесконечные области определения. Поэтому прямой перебор всех значений невозможен и приходится использовать косвенные приемы, основанные на использовании правил интерпретации формул с кванторами.

Рассмотрим примеры.

Доказать общезначимость формулы ╞

Пусть для некоторого предиката Р и предметной области D левая часть эквивалентности истинна. Тогда в предметной области не существует ни одного элемента а ÎD, для которого I[ P(a) ]=1. Следовательно, для всех а ÎD формула Р(а) ложна, а ее отрицание тождественно истинно. Согласно правилу интерпретации формул, образованных квантором общности, I[ "xØP(x) ]=1.Таким образом, левая и правая части эквивалентности истинны, следовательно, формула истинна.

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

Опять имеем: I[1«1]=1.

Это доказывает, что рассматриваемая формула общезначима.

Доказать общезначимость формулы

╞ ($х (Р(х)&Q(х))® ($хР(х)& $хQ(х))).

Если I[$ x(P (x) & Q(x)) ]=0, то импликация истинна при любом логическом значении заключения импликации.

Если I[ $x(P(x)&Q(x)) ] =1, то импликация истинна только при истинном значении заключения импликации. Истинность посылки импликации в данном случае означает, что в предметной области найдется хотя бы один элемент а ÎD, на котором обе формулы Р(а) и Q(а) истинны одновременно. Но в этом случае каждая из подформул, входящих в конъюнкцию в заключении импликации окажется истинной, и заключение импликации также будет истинно. В этом случае импликация также истинна.

Следовательно, данная формула общезначима.

⇐ Предыдущая 4 5 6 7 8910 11 12 13 Следующая ⇒