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



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


Приложение. Синтаксис и семантика исчисления предикатов

СИНТАКСИС.

Синтаксические Категории:

термы (Term): множество Var (индивилуальных) переменных

множество Const (индивидуальных) констант

множество Term термов, Term = Var Const

предикаты (Pred): множество предикатных символов Pred, разбитое на подмножества одноместных предикатных символов Pred-1, двуместных предикатных символов Pred-2, ..., n-местных предикатных символов Pred-n, …

формулы (Form).

Основные выражения:

Term(s): (i) (индивидуальные) переменные: x, y, z, x1, y1, z1, x2, ...

(ii) (индивидуальные) константы: a,b,c,a1, ..., John, Mary, ..., 0,1,

Pred-1: run, walk, happy, calm, ..., even, odd,

Pred-2: love, kiss, like, see, ..., ,

Синтаксические правила задаются рекугсивно:

Базис рекурсии:

R1: Если P Pred-1 и T Term, то P(T) Form.

Если R Pred-2 и T1, T2 Term, то R(T1, T2) Form.

Более общее правило: Если R Pred-n и T1, ...,Tn Term, то R(T1, ...,Tn) Form

Формулы, определяемые этим правилом, называются атомарными

Рекурсивные синтаксические правила (операции на множестве формул):

R2 (): Если Form, то Form.

R3 (&): Если Form и Form, то ( & ) Form.

R4 (): Если Form и Form, то ( ) Form.

R5 (): Если Form и Form, то ( ) Form.

R6 (): Если Form и Form, то ( ) Form.

R7 (v): Если v Var и Form, то v Form.

R8 (v): Если v Var и Form, то v Form.

Заметим, что правила R7 и R8 задают множества операций, по одной операции для каждой переменной из Var.

Несколько дополнительных понятий и обозначений:

В формуле v ее подформула называется сферой действия квантора . Аналогично, в формуле v подформула называется сферой действия квантора .


Открытые и замкнутые формулы

Для формулы обозначим через Var() множество всех ее переменных. Для каждой формулы определим по индукции множество FreeVar() ее свободных переменных:

FreeVar() = Var() для каждой атомарной формулы ;

FreeVar() = FreeVar();

FreeVar( & ) = FreeVar( ) = FreeVar( ) = FreeVar( ) =

= FreeVar() FreeVar()

FreeVar(v) = FreeVar(v) = FreeVar() – {v}.

Формула называется замкнутой (или предложением), если множество ее свободных переменных пусто (FreeVar() = ). Незамкнутые формулы называются открытыми.

Примеры:

Атомарные формулы: love(Mary, x), calm(Peter)

Открытые формулы: love(Mary, x), x(calm(x) happy(y))

Замкнутые формулы: love(Mary, Mary), y(happy(y) &xlove(y, x))

СЕМАНТИКА.

Строение модели: Несущее множество D объектов (сущностей – entities, individuals)

Истинностные значения {Истина, Ложь} или {1,0}

I: Интерпретирующая функция, которая приписывает семантические значения всем константам из Const и предикатным символам из Pred (Pred-1, Pred-2, ... Pred-n)

Модель M =

Множество G функций оценки переменных g: Var D. Каждая такая функция придает каждой переменной значение из D.

Семантические типы, приписываемые Синтаксическим Категориям:

Term: объекты (индивиды, сущности – entities, individuals). Семантические значения этого типа являются элементами D (т.е. I(c) D для каждой константы c Const и g(v) D для каждой переменной v Var и каждой функции g)

Pred-1: множества (объектов). Семантические значения этого типа являются элементами (D)

(D) – множество всех подмножеств D (power set или булеан D).

Pred-2: отношения между объектами (множества пар объектов). Значения этого типа элементы (DD).

Pred-n: n-местные отношения; множества n-ок (n- местных кортежей) объектов. Значения: элементы (D ...D). (Т.е. I(R) Dn для каждого n-арного предикатного символа R)

Form: Истинностные значения. Значения: элементы {0,1}.

Семантическая интерпретация выражений относительно модели M и функции g:

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

Основные Выражения (“лексическая семантика”):

A. Если переменная, то M,g = g().

B. Если константа из Const или предикатный символ из Pred, то M,g = I().

(т.е. M,g D, если константа из Const или переменная и M,g Dn, если – n-арный предикатный символ).

Семантика формул ИП – это приписывание им истинностных значений. Мы делаем это рекурсивно с помощью правил S1-S8 (в соответствии с принципом композиционности).

Семантические Правила (“семантика синтаксиса”)

Базис рекурсии:

S1: Если P Pred-1 и T Term, то P(T)M,g = 1 если и только если TM,g PM,g .

Общее правило: Если R Pred-n и T1, ...,Tn Term, то R(T1, ...,Tn) M,g = 1 если и только если 1M,g , ..., TnM,g > RM,g .

Рекурсивные правила. Если , Form и v – переменная, то:

S2 (): M,g = 1, если и только если M,g = 0.

S3 (&): ( & ) M,g = 1, если и только если M,g = 1 и M,g = 1.

S4 (): ( ) M,g = 1, если и только если M,g = 1 или M,g = 1.

S5 (): ( ) M,g = 1, если и только если M,g = 0 или M,g = 1.

S6 (): ( ) M,g = 1, если и только если M,g = M,g.

S7 (v): v M,g =1 если для каждого d D, M,g[d/v] =1.

S8 (v): v M,g =1 если существует элемент d D такой, что M,g[d/v] =1.

Обозначение g[d/x]: g[d/x] – это функция оценки из G, идентичная функции g для всех переменных, кроме x. Для x значение g[d/x] равно d.

Замечание.

Правила S2 – S6 можно переписать в более элегантной форме:

S2 (): M,g = M,g.

S3 (&): ( & ) M,g = M,g & M,g.

S4 (): ( ) M,g = M,g M,g.

S5 (): ( ) M,g = M,g M,g.

S6 (): ( ) M,g = M,g M,g .

В такой записи в формулах левой части символы , & и т.п – это логические связки (синтаксические операции над формулами). В правой части те же символы обозначают булевы операции над истинностными значениями. Так t = 1 если и только если t = 0, t & s = 1 если и только если t = 1 и s = 1 и т.д.

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

Для каждой формулы Form:

M = 1, если и только если M,g = 1 для всех оценок g,

M = 0, если и только если M1,g = 0 для всех оценок g.

В других случаях M не определено.

ПРИМЕР. Синтаксический вывод и вычисление истинностного значения формулы x(love(Mary, x) happy(x))

Цель примера – проиллюстрировать «работу» синтаксических и семантических правил на данной формуле.

Начнем с синтаксиса. Ниже приведена синтаксическач структура данной формулы, ее «синтаксическое дерево». Каждой вершине (узлу) дерева сопоставлена формула или ее части, синтаксическая категория и синтаксическое правило, примененное в данном месте.

Дерево 1.

x(love(Mary, x) happy(x)), Form, R7

3

x (love(Mary, x) happy(x)), Form, R6

qp

love(Mary, x), Form, R2 happy(x), Form, R1

9 qp

love, Pred-2, Basic | x, T, Basic happy, Pred-1, Basic x, T, Basic

Mary, T, Basic

(Основные выражения помечены в дереве как Basic)

Вычисление истинностного значения

Ниже мы будем вычислять истинностное значение нашей формулы (в модели M, для функции оценки g), аннотируя каждый шаг применяемым семантическим правилом и указанием вершины в приведенном выше дереве (вместе с номером соответствующего синтаксического правила). Для краткости мы будем писать английское “iff” вместо русского «если и только если»

1.║x(love(Mary, x) happy(x))║M,g =1 iff для каждого d D,

love(Mary, x) happy(x)M,g[d/x] =1. Правило S7 в вершинеR7”

2. Это выполняется iff для каждого d D,

love(Mary, x) M,g[d/x] = 0 или ║happy(x) M,g[d/x] =1 . Правило S6 в вершинеR6”

3. Это выполняется iff для каждого d D,

если <║Mary M,g[d/x] ,║ x M,g[d/x]> ║love M,g[d/x], то

x M1,g[d/x]happyM1,g[d/x] .

Правило S2 в вершине R2 и правило S1 в вершине R1.

4. Это выполняется iff для каждого d D,

если <║Mary M,g[d/x], d> ║love M,g[d/x] , то d ║happy M,g[d/x].

Правило A (для переменных) для двух x вершин.

5. Т.е. если Mary), d> I(love), то d I(happy).

Правило B (для констант) для вершин Mary, love, happy.

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

Tree 2. x(love(Mary, x) happy(x)), Form, R7, S7

3

x (love(Mary, x) happy(x)) , Form, R6, S6

qp

love(Mary, x), Form, R2, S2 happy(x), Form, R1, S1

9 qp

love, Pred-2, Basic | x, T, Basic happy, Pred-1, Basic x, T, Basic

Mary, T, Basic

О лекторах



Barbara Hall Partee (Барбара Парти) закончила в 1965 г. аспирантуру (PhD) у Хомского, в MIT. С 1965 по 1972 г. – профессор Department of Linguistics in UCLA (University of California at Los Angeles). С 1972 по настоящее время профессор Department of Linguistics in UMass (University of Massachusetts), Amherst. С 1996 г. почти каждый год проводит один семестр в Москве, последнее время – в РГГУ (visiting professor), где читает курс лекций (иногда – два) по семантике.


В 1968 г. посещала семинар Р. Монтегю на котором тот впервые рассказывал о своем подходе к семантике естественного языка. С тех пор в основном занимается семантикой.

Владимир Борисович Борщев закончил в 1959 г. КАИ. В том же году поступил в аспирантуру ВИНИТИ, с тех пор в ВИНИТИ. К.т.н. (1968), диссертация, в основном, по математической лингвистике. Д.ф.-м.н. (1992)диссертация по семантике языков логического программирования и асинхронным параллельным вычислениям. В основном занимался Theoretical Computer Science. Но все время работал в отделе, в котором работало много лингвистов. Последние несколько лет вместе с Барбарой Парти занимается семантикой естественных языков.

1 По-видимому, имеется в виду, что вычисляются истинностные значения для выражений этого языка.

2 В формулах мы «переводим» с русского на английский (латинский алфавит, почему-то, кажется более подходящим для формул).
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