Упражнения. Пояснения и определения

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

Выше был построен ЯКЛП¹=. В этом языке очень много нелогических символов: индивидных констант, функциональных и предикатных, – бесконечно много, точнее – их столько же, сколько натуральных чисел. Но в любой содержательной теории, как правило, имеют дело с конечным набором объектов, функций, определенных на них, а также с конечным числом свойств объектов и отношений между ними, поэтому часто, прежде чем задавать какие-либо структуры в ЯКЛП¹=, фиксируют конечный список исходных нелогических символов, из которых будут строиться термы и формулы. Такой набор нелогических символов называется сигнатурой или словарем теории. Более строгое определение выглядит так.

Сигнатура – набор из трех множеств S=(Cnst, Fn, Pr), где

Cnst – (какое-то, возможно, пустое) множество индивидных констант,

Fn – (какое-то, возможно, пустое) множество функциональных констант,

Pr – (какое-то, возможно, пустое) множество предикатных констант.

При этом каждому функциональному и предикатному символу из Fn и Pr соответственно сопоставляется некоторое натуральное число – его местность (валентность, арность).

Примеры сигнатур

S₁=(a, f¹, P²)

S₂=(a)

S₃=(f²)

S₄=(P¹, Q², R²)

S₅=(c, h⁴, R¹, Q¹⁰)

S₆=(a, Q³)

S₇=(Q³)

Сигнатура языка формальной арифметики имеет вид S = (a, f¹, g², h²), или в обычных математических обозначениях S=(0,',+,·) (подразумеваемый смысл символа ' – взятие последующего элемента, или прибавление единицы: х'= x+1).

14. Запишите какие-нибудь термы и формулы в указанных сигнатурах.

S₁=(a, P¹)

S₂=(P²)

S₃=(P⁴)

S₄=(a, b, f¹, R²)

Выше подробно рассматривалась задача определения структурной информации в ЯЛП. Рассмотрим теперь обратную задачу: как языковой структуре сопоставить конкретное выражение естественного языка (или языка какой-либо теории), т.е. как задать интерпретации термов и формул.

Некоторые простые формулы не укажут на некоторые необходимые условия задания интерпретации. Рассмотрим формулу Р(а,с). Формулам соответствуют предложения. Чтобы превратить эту структуру в предложение надо символу Р сопоставить какой-то двухместный предикат, а символам а и с – выражения, задающие конкретные объекты.

Приведем несколько вариантов «превращения» формулы в предложение.

Р – современник, а – М.И.Кутузов, с – Александр I (при такой интерпретации получим истинное предложение: М.И.Кутузов современник Александр I);

Р – современник, а – М.И.Кутузов, с – Александр Македонский (при такой интерпретации структура Р(а,с), естественно, ложна);

Р – современник, а – А.С.Пушкин, с – Александр I;

Р – родственник, а – М.И.Кутузов, с – Александр I;

Р – родственник, а – Николай I, с – Александр I;

Р – родственник, а – Александр I, с –Николай I;

Р – родиться раньше, а – Николай I, с – Александр I;

Р – родиться раньше, а – Александр I, с – Николай I;

Р – >, а – 5, с – 4;

Р – <, а – 5, с – 4;

Р – >, а – 5, с – 6;

Р – >, а – 5, с – 5[10].

Вы понимаете, что вариантов таких «превращений» бесконечно много. Рассмотрим немного более сложную формулу: Р(а,с) & Р(а,b). Для того, чтобы сопоставить этой структуре конкретное предложение и вычислить его значение («истина» или «ложь»), надо 1) придать значения нелогическим символам Р, а, b, с и 2) сказать, как понимаем логическую связку &. Что касается пропозициональных связок Ø, &, Ú, É, º, ⊥, Т то в классической логике предикатов они понимаются так же, как в классической логике высказываний. Скажем, структура А&В в КЛП будет определена как истинная в том и только в том случае, если оба конъюнкта оценены как истинные.

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

значения нелогических символов	предложение, соответствующее формуле Р(а,с)&Р(а,b) при данном понимании нелогических символов	значение формулы Р(а,с)&Р(а,b)
Р – родиться раньше, а - Платон, b – Александр Македонский, с – Аристотель	Платон родился раньше Аристотеля и Александра Македонского.	истинно
Р – родиться раньше, а - Александр Македонский, b – Платон, с – Аристотель	Александр Македонский родился раньше Аристотеля и Платона.	ложно
Р - >, а - 5, b - 6, с -1	5 >1 и 5 >6	ложно

Пока никаких проблем с получением предложения по заданной структуре и с определением его истинностного значения не было.

Рассмотрим формулу "х$уР(х,у). Допустим, кто-то предложит Р понимать как отношение «<» и прочитает эту формулу так: Для каждого числа х существует число у такое, что х < у, т.е. для каждого числа найдется число, которое его (строго) больше. Спрашивается, это утверждение о числах истинно или ложно? Если вы скажете, что истинно, то поторопитесь. Так же, как если скажете, что ложно. Прежде, чем выяснять значение рассматриваемого предложения, нужно уточнить, к какому множеству чисел оно относится. В самом деле, если мы говорим (например) о натуральных числах, тогда это высказывание истинно: для любого натурального числа найдется (натуральное) число, которое его строго больше. Но если отнести это предложение к целым отрицательным числам, тогда оно будет ложным: для -1 среди рассматриваемых чисел не найдется большего. Ложным это предложение будет, если х и у брать из любого конечного множества действительных чисел, поскольку в конечном множестве действительных чисел, разумеется, существует наибольшее и для него-то мы не найдем число, которое его строго больше. Мораль такова: прежде чем интерпретировать языковую структуру, необходимо зафиксировать множество объектов, о которых мы рассуждаем, которые подразумеваются под х, у, z, а, b, с и т.д., между которыми задаем отношения, множество объектов, на котором определяем функции. Такое множество объектов называется носитель интерпретации, универсум (иногда говорят универс) или область рассуждения. Будем обозначать его U. В классической логике предикатов принимается следующее требование: носитель интерпретации должен быть непустым множеством: U¹Æ.

Если формула сигнатуры S не содержит переменных, тогда для превращения ее в предложение, надо зафиксировать некоторое множество объектов и относительно него проинтерпретировать все символы из S. Так выше мы «почти» поступили для формул Р(а,с) и Р(а,с)&Р(а,b), - там не было зафиксировано U (можно было в качестве U взять, скажем, множество всех людей, родившихся до 20 в., а в случае с числами – множество натуральных чисел). Для формул, содержащих переменные, этого недостаточно.

Рассмотрим, например, такую интерпретацию сигнатуры S=(P²): I = (U= Z, |P²|_I= “>”). Спрашивается, будет ли на этом носителе при таком понимании символа Р истинна формула Р(х,у)? На этот вопрос имеющейся информации недостаточно. Вместо х и у имеем право подставить любое целое число. Одни подстановки дадут нам истинные предложения, другие ложные. Значит, в рамках фиксированной интерпретации нелогических констант можно по-разному понимать нелогические переменные (х, у, z, x₁…). Каждое такое «понимание» назовем функцией оценки переменных или функцией интерпретации переменных. Каждая функция оценки сопоставляет каждой переменной какой-то объект из U.

Таким образом, объект, относительно которого определяем истинностное значение языковых структур (термов и формул) таков:

(1) некоторое множество,

(2) понимание нелогических символов,

(3) понимание переменных.

Интерпретацией (некоторой сигнатуры) или возможной реализацией назовем пару <(1), (2)>.

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

15. Рассмотрим интерпретацию сигнатуры S=(P¹,Q²,f¹,h²,a,b,с).

I: U=N, N={0,1,2,…}

|P¹|_I= множество четных чисел (= свойство «быть четным числом»)

|Q²|_I= множество таких пар чисел, первое из которых больше второго (>)

|f¹|_I= операция возведения в квадрат

|h²|_I= операция сложения

|a|_I1=0

|b|_I1=2

|c|_I1=3

Определите значения следующих термов и формул в интерпретации I:

а) h (a, b)

б) f (c)

в) f (f f((c)))

г) h (f(b), h(a,c))

д) P (h (a, b))

е) Q (f (b), h (a, a))

ж) P(c) Ú ØP(f(c))

з) $x (P(x) & Q(x,f(x)))

и) "x (P(f(x)) É P(x))

к) $x $y Q (c, h(x,y))

л) "x Q(h(x,a), a)

м) "x (P (x) É ØP (h (x, a)))

Терм	Значение в I

Формула	Соответствующее предложение русского языка в интерпретации	Значение формулы в I (И или Л)

16. Рассмотрим 3 интерпретации сигнатуры S=(P²)

I1: U=N, N={0,1,2,…} |P^2|I1= ≥

I2: U=N, N={0,1,2,…} |P^2|I2= >

I3: U= люди |P^2|I3= современник

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

Формула	Интерпретация I1	Интерпретация I2	Интерпретация I3	Интерпретация I3
Соответствующее предложение русского языка	Значение формулы (И или Л)	Соответствующее предложение русского языка	Значение формулы (И или Л)	Соответству ющее предложение русского языка	Значение формулы (И или Л)
∀xP(x,x)
∃xP(х,х)
∃x∃y(P(x,y)&P(y,x))
∃x∃y(P(x,y)&P(y,x))
∃x∃y(P(x,y)&P(y,x))
∃x∀y(x≠y⊃P(x,y))
∃x∀y(x≠y⊃P(y,x))

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

Основные понятия, которые необходимо усвоить: · интерпретация = возможная реализация · истинность формулы в интерпретации · модель для множества предложений ЯКЛП · контрмодель для множества предложений ЯКЛП

Дата добавления: 2014-12-27