» » »

Семантика логики предикатов.

 Семантика логики предикатов

Стратегия определения семантических значений компонент и формул логики предикатов базируется на понятии интерпретации логической формулы. Напомним это понятие.

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

Уже отмечалось, что высказывание либо истинно, либо ложно. Поэтому введем семантическую область {И, Л}. Интерпретировать формулу - значит приписать ей одно из двух значений истинности И или Л.

Семантика (то есть набор правил интерпретации формул) должна быть композиционной: значение формулы должно быть функцией значений ее составляющих. Точнее, значение истинности формулы зависит только от структуры этой формулы и от значений истинности составляющих ее высказываний. Таким образом, связки исчисления высказываний представляют функции истинности: например значение истинности формулы будет известно, если известны значения истинности Х и Y. Следующие две таблицы описывают семантику отрицания и бинарных связок.

Х

Х

И

Л

Л

И

Х

Y

XY

XY

XY

XY

И

И

И

И

И

И

И

Л

Л

И

Л

Л

Л

И

Л

И

И

Л

Л

Л

Л

Л

И

И

Интерпретация - это отображение i, сопоставляющее каждому элементарному высказыванию р некоторое значение истинности. Интерпретацию i, заданную на множестве элементарных высказываний, можно распространить (продолжить) на множество формул (высказываний) посредством таблиц истинности. Соответствующее продолжение (расширение) I тоже называется интерпретацией. Интерпретация, при которой истинностное значение формулы есть И, называется моделью этой формулы.

Литера - это элементарное высказывание или его отрицание. Литеры р и противоположны. Интерпретация определяет разбиение множества L литер на два подмножества Lи и Lл, каждое из которых содержит по одному элементу из каждой пары противоположных литер.

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

Точнее, интерпретация I - это тройка (D, Ic, Iv) со следующими свойствами:

· D - непустое множество, область интерпретации.

· Ic - функция, которая сопоставляет каждой функциональной n-местной константе f некоторую функцию Ic(f) из Dn в D и которая сопоставляет каждой предикатной m-местной константе Р некоторую функцию Ic(Р) из Dm в {И, Л}.

· Iv - функция, сопоставляющая каждой переменной некоторый элемент из D.

Теперь можно задать для интерпретации I = (D, Ic, Iv) такие правила, которые каждой формуле А ставят в соответствие некоторое значение истинности I(A), а каждому терму t сопоставляется элемент I(t) из D.

· Если х - свободная переменная, то I(x)=def Iv(x).

· Если f - функциональная n-местная константа, t1, ... ,tn - термы, то I(f(t1, ... ,tn)) =def= =(Ic(f))(I(t1), ... ,I(tn))

· Если Р - предикатная m-местная константа, t1, ... ,tm - термы, то I(P(t1, ... ,tm)) =def= =(Ic(P))(I(t1), ... ,I(tm))

· Если s и t термы, то I(s=t) есть И при I(s)=I(t), а иначе Л.

· Если А и В - формулы, то А, (АВ), (АВ), (АВ) и (АВ) интерпретируются как в исчислении высказываний.

Осталось задать интерпретацию для двух типов квантифицированных формул. Введем сначала одно понятие. Если I - интерпретация c областью DI, x - переменная, d - элемент из DI, то Ix/d означает такую интерпретацию J, что DJ = DI, Jc = Ic, Jv(x) = d и Jv(y) = Iv(y) для всех свободных переменных у отличных от х.

Правила интерпретации будут такими:

· Если А - формула и х - переменная, то I(хА) есть И при условии, что Ix/d (А) есть И для всех элементов d из D.

· Если А - формула и х - переменная, то I(хА) есть И при условии, что Ix/d (А) есть И хотя бы для одного элемента d из D

Формула А исчисления предикатов называется истинной при интерпретации I, если I(A)=И.

Теперь видно, что запрещение перекрытия кванторов, действующих на одну и ту же переменную, не является существенным ограничением. В частности, интерпретируется как и интерпретируется как . Ясно также, почему требуется условие Dш; без него естественные импликации

не всегда были бы истинны.

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

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

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

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

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

Имена индивидуумов

Семантические значения

Жак_2

Жак Дюпон

Мари_4

Мари Дюран

Джордж_5

Джордж Буль

Книга_22

Законы мышления

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

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

Фундаментальным понятием семантики является понятие истины реального мира. Более общее понятие - истина в модели. Здесь моделью является реальный мир. Состояние реального мира позволяет приписывать семантические значения «истинно» или «ложно» предикатам и функциям. Например:

Предикат

Семантическое значение

Посылка(Жак_2, Мари_4, Книга_22)

истинно

Посылка (Мари_4, Жак_2, Книга_22)

ложно

Написанное (Джордж_5, Книга_22)

истинно

Написанное (Жак_2, Книга_22)

ложно

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

Формула

Семантическое значение

Посылка(Жак_2, Мари_4, Книга_22) Написанное (Жак_2, Книга_22)

истинно

Посылка(Жак_2, Мари_4, Книга_22) Написанное (Джордж_5, Книга_22)

истинно

Основной задачей представления знаний является перевод неформальных выражений или описаний метаязыка в фразы объектного языка.


Друзья! Приглашаем вас к обсуждению. Если у вас есть своё мнение, напишите нам в комментарии.

Поделиться

Оплаченная реклама

Дисциплины