Geum.ru

Логико-лингвистические модели предикации и предикативности

Вид материалаРеферат

Содержание


Интерпретация в логике предикатов первого порядка
Подобный материал:
1   2   3   4   5   6

Интерпретация в логике предикатов первого порядка


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

Каждой переменной xi задается область ее значений Xi. Объединение этих областей X=Xi называется универсумом. Каждая константа интерпретируется некоторым символом из X. Другими словами, интерпретация функциональных символов определяется по интерпретации термов, входящих в качестве аргументов в эту функцию. Каждому предикатному символу приписывается интерпретация, совпадающая с отображением Xn в Q,, где Q={И, Л}. Формула xiP, где P- некоторый предикат, интерпретируется как истинная, если предикат P истинен при всех интерпретациях xi. Другими словами, P остается истинным, когда xi принимает любое значение из области Xi. Формула  xi P) где P- некоторый предикат, интерпретируется как истинная, если предикат P истинен хотя бы при одной интерпретации xi. Другими словами, среди значений xi из области Xi, найдется хотя бы одно значение, для которого P является истинным.

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

Интерпретация кванторов общности и существования позволяет найти зависимость, связывающую эти кванторы. Рассмотрим формулу x(P(x))). Высказывание, стоящее в скобках, будет интерпретироваться как ложное, если среди значений x найдется хотя бы одно x* такое, что P(x*) является ложным. Тогда относительно P можно сформулировать следующее: “Найдется хотя бы одно значение x такое, что P(x) является истинным”. Но это утверждение эквивалентно истинности формулы x(P(x)). Отсюда следует, что x(P(x)))= x(P(x)), где знак равенства понимается как знак равносильности (т. е. совпадения интерпретации данных формул при любых интерпретациях термов и функциональных символов, входящих в них). Аналогично можно показать, что имеет место соотношение xP(x))= x(P(x)).

Рассмотрим описанное выше на примере. Пусть имеется формула исчисления предикатов:

x y P(x, y).

Зададим общую область для значений переменных x, y:D={1,2}.

Допустим, что предикат P принимает значения истинности для x и y в области D (табл. 1).

Таблица 1

P(1, 1)
P(1, 2)
P(2,1)
P(2, 2)

И
Л
И
Л


Из этой таблицы видно, что если x=1, то найдется такое значение y (а именно, y=1), при котором P(1, y) истинно. Если же x=2, то при y=1 предикат P(2, y) принимает значение И. Следовательно, для всех значений переменной x в заданной области D имеется хотя бы одно значение переменной y в этой же области, при котором P(x, y) истинно. Таким образом, формула xyP(x, y) в заданной интерпретации истинна.

В качестве еще одного примера возьмем рассмотренную выше запись афоризма Козьмы Пруткова. Проанализируем ее возможную интерпретацию. Зададим область значений для переменных x, y и z как двухэлементное множество D={1,2}.

Далее для предиката МЕНЬШЕ(x, y) зададим отображение Dn в D с помощью таблицы 2.

Таблица 2

МЕНЬШЕ(1, 1)
МЕНЬШЕ(1, 2)
МЕНЬШЕ(2,1)
МЕНЬШЕ(2, 2)

Л
И
Л
И



А для предиката БОЛЬШЕ(x, z) – с помощью таблицы 3

Таблица 3

БОЛЬШЕ(1, 1)
БОЛЬШЕ(1, 2)
БОЛЬШЕ(2,1)
БОЛЬШЕ(2, 2)

Л
Л
И
Л



Из таблиц 2 и 3 видно, что не для всех значений x в области D найдется такой y, когда оба предиката истинны. Для первого из них таблица 2 только при одном значении x (когда x=1) находится значение y (когда y=2) такое, что значение выражения МЕНЬШЕ(1,2) есть И. Следовательно, формула xy МЕНЬШЕ(x, y) в данной интерпретации ложна. Аналогично из таблицы 3 можно определить, что формула xz БОЛЬШЕ(x, z) в этой интерпретации ложна. Следовательно, и значение истинности всей формулы есть Л.

Рассмотрим формулу, содержащую кроме предикатов, функциональный смысл и константу:

(x)(P(x)R(g(x), a)).

Зададим следующую интерпретацию:

D={1,2}, a=2;

g(1)=2, g(2)=1;

P(1) есть И; P(2) есть Л.

Тогда R (g(x), a) можно задать в виде таблицы 4.

Таблица 4

R(1, 1)
R(1, 2)
R(2,1)
R(2, 2)

И
И
И
Л

Такую интерпретацию обозначим буквой I. Когда значение переменной x равно 1, имеет место равенство

P(x)R(g(x), a)= P(1)R(g(1), 2)= P(1)R(2, 2).

В принятой интерпретации P(1) принимает значение И, а R(2, 2) – Л; таким образом, они не равносильны. При данном значении переменной x рассматриваемая формула является ложной.

Проверим истинность формулы при x=2. В этом случае P(2) интерпретируется как Л, а R(1, 2) как И. Таким образом, в этом случае эквивалентность интерпретируется как Л. Поскольку при любых значениях x имеется ложное утверждение под квантором существования, то и вся формула, включающая этот квантор, интерпретируется как ложная.