Лекция Какие семантики бывают. Исчисление предикатов как прототипический пример формального языка Владимир Борщев, винити ран



Скачать 411.65 Kb.
страница3/6
Дата07.11.2012
Размер411.65 Kb.
ТипЛекция
1   2   3   4   5   6

3. Синтаксис и семантика исчисления предикатов (ИП)


Как уже говорилось, мы в наших лекциях, будем обсуждать лексическую и формальную семантику и их интеграцию. Формальной основой всего этого является логика. Логика сама когда-то возникла из анализа естественного языка…

Поэтому нам естественно начать с краткого рассмотрения самого известного и, в некотором смысле, «прототипического» логического языка – Исчисления Предикатов. Мы используем его, чтобы проиллюстрировать наиболее важные для нас черты формального языка: понятие модели и теоретико- модельной семантики, и Принцип Композиционности (Principle of Compositionality).

3.1. Неформальное описание синтаксиса и семантики ИП


Мы ограничимся здесь несколькими примерами и замечаниями. Более точные определения даны в Приложении.

Предложения Джон любит Мери и Всякий, кого любит Мери, счастлив могут быть представлены как формулы ИП:

Джон любит Мери love (John, Mary)2

Всякий, кого любит Мери, счастлив x(love(Mary, x) happy(x))

Формула x(even(x) & (x 1)) говорит, что существуют четные числа, большие 1

Формулы и другие выражения ИП строятся из индивидуальных констант (или просто “констант”), (индивидуальных) переменных, предикатных констант (или предикатных символов), логических связок и кванторов. Каждое выражение принадлежит к определенному типу. Структура типов в ИП очень проста: объекты (individuals, entities), отношения разной арности (унарные, бинарные и т.д.), и истинностные значения.

В наших примерах мы используем следующие выражения

Выражения Types

===================================================

John, Mary, 1, 2, … константы объекты

x, y, z, x1, y1, z1, x2, ...
переменные объекты

happy, even унарные предикатные унарные отношения

символы

love, бинарные предикатные бинарные отношения

символы

love (John, Mary)

love(Mary, x)

happy(x)

even(x) формулы истинностные значения

(x 1)

x(love(Mary, x) happy(x))

x(even(x) & (x 1))

Первые пять формул выше – примеры атомарных формул.

Выражения логических языков интерпретируются в моделях. Структура моделей, в которых интерпретируются выражения данного языка, отражают базисные пресуппозиции о «структуре мира», имплицитно содержащиеся в языке. Для исчисления предикатов каждая модель состоит из множества {1,0} истинностных значений, универсума (или домена – domain) D – некоторого множества объектов, и некоторого набора n-арных отношений на множестве D.

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

Итак, мы будем представлять каждую модель в виде

M =

Интерпретация строится рекурсивно на основе интерпретирующей функции I. Каждому выражению сопоставляется его семантическое значение M M в данной модели М (точнее, M,g, где g – некоторая оценивающая функция, сопоставляющая значения переменным). Семантические значения должны соответствовать типам выражений. Так, в нашем примере индивидуальным константам John и Mary сопоставляются некоторые элементы множества D, переменные принимают свои значения на множестве D, бинарному предикатному символу love сопоставляется бинарное отношение loveM, а унарному предикатному символу happy сопоставляется унарное отношение happyM . Формулы получают истинностные значения. Формула love (John, Mary) истинна в модели М, если пара элементов, соответствующих константам John и Mary, принадлежит отношениюloveM.

Формула x(love(Mary, x) happy(x)) истинна в М если и только если:

для каждого элемента d D, d happyM, если MaryM, d loveM.

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

А здесь мы чуть точнее покажем, как вычисляется истинностное значение формулы x(love(Mary, x) happy(x)) в модели M по приведенным в этом Приложении семантическим правилам. Используемая ниже запись g[d/x] обозначает функцию оценки, которая совпадает с функцией g для всех переменных, кроме x. Для x значение g[d/x] равно d.

Итак, по правилу S7 мы имеем:

x(love(Mary, x) happy(x)) M,g = 1 тогда и только тогда, когда для каждого d D,

d happy M,g[d/x] , если MaryM,g[d/x], xM,g[d/x] loveM,g[d/x].

Заметим, что если в выражении нет переменных, то значение этого выражения не зависит от функций оценки. Так, в нашем примере, для каждой константы (индивидуальной или предикатной), M,g[d/x] = I().

Для переменной xM,g[d/x] = g[d/x]( x) = d.

Поэтому:

x(love(Mary, x) happy(x)) M,g = 1 тогда и только тогда, когда для каждого d D, d I(happy), если I(Mary), d> I(love).

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

Пример


Рассмотрим очень простой язык ИП, содержащий, как и формулы, рассмотренные выше, всего две константы, John и Mary, и два предикатных символа: love (бинарный) и happy (унарный).

Рассмотрим две модели, M1 и M2:

M1 = 1>, D = {j,m},

I1(John) = j, I1(Mary) = m,

I1(love) = {,,,}, I1 (happy) = {j,m},

M2 = 2>, D = {j,m},

I2(John) = j, I2(Mary) = m,

I2(love) = {,}, I2 (happy) = {m}.

Легко видеть, что формулы love (John, Mary) и love (Mary, John) истинны в модели M1, но только вторая из них истинна в M2. Формула x(love(Mary, x) happy(x)) истинна в M1 и ложна M2, так как для оценки g, такой, что g(x) = j имеет место love(Mary, x)M2,g = 1 и happy(x) M2,g = 0.

Формальная семантика тоже строится как теоретико-модельная. Каждое предложение рассматривается как формула некоторого логического языка и вычисляется его истинностное значение. Но это не истинность и ложность вообще, а истинность и ложность относительно той или иной модели. Т.е это тоже условие на вид модели. Грубо говоря, на тип ситуаций, для которых данное предложение истинно.
1   2   3   4   5   6

Похожие:

Лекция Какие семантики бывают. Исчисление предикатов как прототипический пример формального языка Владимир Борщев, винити ран iconЦентр научно-информационного обслуживания винити ран предоставляет копии первоисточников
Винити осуществляет обслуживание копиями первоисточников, хранящихся в фонде научно-технической литературы винити, в фондах других...
Лекция Какие семантики бывают. Исчисление предикатов как прототипический пример формального языка Владимир Борщев, винити ран iconРегистрационная форма пользователя on-line
Данная регистрационная форма является официальным документом для регистрации Вас, как пользователя базы данных (БД) винити ран в...
Лекция Какие семантики бывают. Исчисление предикатов как прототипический пример формального языка Владимир Борщев, винити ран iconЭлектронные ресурсы винити. Электронный Реферативный журнал итоги десятилетия Цветкова Валентина Алексеевна, д т. н., проф., зав отделением винити ран, Ген. Директор ООО «нти-компакт»
Цветкова Валентина Алексеевна, д т н., проф., зав отделением винити ран, Ген. Директор ООО «нти-компакт», Москва, Россия
Лекция Какие семантики бывают. Исчисление предикатов как прототипический пример формального языка Владимир Борщев, винити ран iconУчастник: Идашкина Анастасия
Цель моего исследования: узнать, как развивались города в течение времени, какие бывают города, какие они выполняют функции, а также...
Лекция Какие семантики бывают. Исчисление предикатов как прототипический пример формального языка Владимир Борщев, винити ран iconЛекция 3 Логика предикатов Понятие предиката
Такой логической системой является логика предикатов, содержащая всю логику высказываний в качестве своей части
Лекция Какие семантики бывают. Исчисление предикатов как прототипический пример формального языка Владимир Борщев, винити ран iconИсчисление предикатов. Пропозициональная функция
Р(Х­1,Х2,…,Хn) есть атомарная (элементарная) формула. Эта формула трактуется как высказывание, гласящее, что объекты Х1,Х2,,…,Хn...
Лекция Какие семантики бывают. Исчисление предикатов как прототипический пример формального языка Владимир Борщев, винити ран iconЛекция В. Б. Борщев и B. H. Partee. Казань, кгу, Апрель 2003 стр
Лекция Формальная семантика (продолжение). Интенсиональная логика. Типы. Лямбда и конструкции с лямбдой. Семантика Монтегю для именных...
Лекция Какие семантики бывают. Исчисление предикатов как прототипический пример формального языка Владимир Борщев, винити ран iconНормальные формы формул логики предикатов
При этом, используя равносильности алгебры высказываний и логики предикатов, каждую формулу логики предикатов можно привести к нормальной...
Лекция Какие семантики бывают. Исчисление предикатов как прототипический пример формального языка Владимир Борщев, винити ран iconИсчисление предикатов с равенством
Замечание. В формулах подформула называется областью действия квантора соответственно
Лекция Какие семантики бывают. Исчисление предикатов как прототипический пример формального языка Владимир Борщев, винити ран iconВинити ран

Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org