2.2.1.1.2. Синтаксис и семантика языка предикатов

Определим множество знаков, которыми можно пользоваться в языке предикатов. Знак – условное обозначение какого-либо понятия предметной области . Знаки моргут состоять как из одного символа ({,Y,F,B), так и из группы символов (ГРУППА). Это множество знаков называется алфавитом. В нем есть:

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

2. Знаки, обозначающие функциональные зависимости между объектами (функциональные знаки)

3. Знаки, обозначающие атрибуты, свойства объектов, отношения истинности между объектами (предикаты или предикатные знаки)

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

Различия между 2 и 3 групп состоит в том, что знаки 2ой группы (функциональные) соответствуют таким отношениям, результатом которых является константа, а знаки 3ей группы таким отношениям, которые могут быть либо истинными, либо ложными. Функции обозначаются строчными буквами и описываются с указанием синтаксиса и семантики.

Знак: синтаксис и семантика

G^g(x)=1/x

Плюс: плюс (х,у) = х,у

Профессия: профессия(х)=профессия человека, обозначенного знаком

Функция обладает следующими свойствами: она каждому картежу констант, являющимся ее аргументами ставит в соответствие константу, т.е. это полное отображение множества всех картежей констант в множество констант. Пусть D-множество всех констант, а D^n – декартово произведение множества всех констант самого на себя столько раз, сколько аргументов у функции, т.е. D^n = DxDx…xD ( n раз). Тогда функция – это отображение декартова произведения D^n с множеством констант D. Если Dn- функция от n аргументов, то

Fn: D^nD

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

БОЛЬШЕ: БОЛЬШЕ (х,у) = если х>у.

Для предиката свойственно следующее: отображение множества всех кортежей констант в множество I={ИСТИНА, ЛОЖЬ}. Следовательно, если Pn – предикатный знак от n аргументов, то:

Pn: D^n  I

Как функции, так и предикаты могут иметь разное количество аргументов. Если у функции или предиката 1 аргумент, то они называются одноместными, 2 аргумента – 2-местные, если n аргументов, то n – местные.

В качестве аргументов предикат может иметь константы, переменные, функции и предикаты. От того, что допускается указывать в качестве аргументов предиката существенно зависит язык. Если в качестве аргумента в предикатах, кроме const, переменных и функций допускается предикаты, то имеем язык предикатов 2-го порядка. В языке предикатов 3-го порядка, кроме этого в предикатах - аргументов в качестве аргумента допускается предикаты не выше 2-го порядка и т.д. Обычно для представления знаний используется логика предикатов 1-го порядка. В ней в качестве аргумента в предикаты не допускаются предикаты. В связи с особой важностью аргументы предикатов имеют специальные названия “термы”.

Другими базовыми понятием языков предикатного типа является понятие “атома” (атомарной формулы). Атом в разговорном языке соответствует предложения наиболее простого типа (нераспространенное предложение).

Такая формула записывается с помощью одного предиката. Таким образом, если P_n- n-местный предикатный знак, а t₁, t₂, t₃,…t_n – его термы, то атомарная формула имеет следующий вид: P_n(t₁, t₂, t₃,…t_n)

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

Логические связи используются для отражения в языке составных утверждений и задается с помощью правил следующих знаков:

1. ­­­­­¬ или ( ¯ ) – отрицание ( ¬А или А^¯) (неверно, что А)

2. ˄ (&) – конъюнкция (А˄B) (А и B)

3. ˅ - дизъюнкция (А˅B) (А или В)

4. → импликация (А→В) (если А, то В)

5. ↔ эквивалентность (А↔В) (А эквивалентно В)

Здесь А и В функции.

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

А и В	¬А	А˄B	А˅B	А→В	А↔В
ИИ	Л	И	И	И	И
ИЛ	Л	Л	И	Л	Л
ЛИ	И	Л	И	И	Л
ЛЛ	И	Л	Л	И	И

Где Л – ложь, И - истина.

Импликация А→В в языке предикатов не полностью соответствует выражению в естественном языке “Если А, то В”. Выражению “если А, то В” в обычном языке привносится упорядоченность, при которой А является посылкой, а В – заключением.

В импликации А→В языке предикатов, такая упорядоченность отсутствует. Использование этих логических связей избыточно, поскольку знаки импликации и эквивалентности можно выразить через знаки “˅”, “˄”, “¬”. Действительно, по таблице истинности можно убедиться, что при всех возможных значениях А и В, т.е. А→В=¬А˅В. Тем не менее эти знаки используются для удобства описания знаний. Кроме приведенных выше по таблице истинности можно убедиться, что:

1. А˅(А˄В) = А

2. ¬(А˄В) = ¬А˅¬В

3. ¬(А˅В) = ¬А˄¬В

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

Кванторы позволяют формулировать какие-либо общие утверждения, т.е. обо всех объектах или о каких-то из них (когда не важно о каких именно объектах идет речь). Они задаются с помощью следующего знака ¥ - квантор общности. Синтаксически он используется следующим образом: (¥x) P(x) – (для всех формула P(x) истина). Это означает, что формула P(x) является истинным при ¥ интерпретации. Другими словами, при подстановке в формулу P(x) вместо переменной X ¥ константы соответствующей конкретному объекту предметной области. Эта формула равно значению – истина.

Ǝ – квантор существования. Синтаксически он используется следующим образом:

(Ǝx) P(x). Читается “Существует такое “x” для которого формула P(x) – истина. ” Это означает, что существует по крайней мере одна такая интерпретация, при которой P(x) – истина. Другими словами, в предметной области существует один такой объект, что при подстановке в формулу P(x) соответствует const, эта формула равна значению - истина.

Переменные, к которым в формуле следует применить кванторы называются связанными соответствующими кванторами. Не связанные переменные называются свободными.(¥x)(Ǝy)P(x,y,z). В этой формуле x – связанная переменная квантилем общности, y – связанная переменная квантилем существования, z – свободной переменной.

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