ЛОГИЧЕСКАЯ МОДЕЛЬ ПРЕДСТАВЛЕНИЯ ЗНАНИЙ

Рассмотрим логические модели, основанные на классической теории исчисления предикатов 1-го порядка, когда предметная область описывается в виде набора аксиом.

Изучение логики предикатов начнем с исчисления высказываний. Высказыванием называется некоторое предложение, смысл которого можно выразить значениями ИСТИНА (TRUE) или ЛОЖЬ (FALSE). Например, предложения «кошка серая» и «кошка черная» будут высказываниями. Из простых высказываний можно составить более сложные [2, 3]:

«кошка серая или кошка черная»,

«кошка серая и кошка черная»,

«если кошка не серая, то кошка черная».

При этом элементарными высказываниями считаем те, которые нельзя разделить на части. Элементарные высказывания рассматриваются как переменные логического типа.

Исчисление высказываний. Символами языка логики высказываний, составляющими ее алфавит, являются:

• логические переменные Р, Q, R, S,...,

• логические константы TRUE (ИСТИНА) и FALSE (ЛОЖЬ),

• логические операции Ù («и», конъюнкция), Ú («или», дизъюнкция), («не», отрицание), ≡ («тогда и только тогда, когда», эквиваленция), → («следует», импликация) и круглые скобки.

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

• каждая логическая переменная и константа истинности являются формулами. Например: TRUE, Р, Q и R — формулы;

• если Р и Q — формулы, то Р, P Ù Q, P Ú Q, P«Q, P → Q — тоже формулы (запись Р будем заменять на );

• других формул не бывает.

Формула, давая некоторое описание мира, может быть как истинной, так и ложной. Интерпретация — это утверждение относительно правдивости высказывания в некотором возможном мире.

Интерпретация определяет семантику формулы путем сопоставления сим­волов формул со свойствами объектов среды. Значение формулы ИСТИНА говорит о наличии некоторого свойства и ЛОЖЬ — об отсутствии. Каждое возможное отображение значения истинности высказывания соответствует возможной интерпретации мира. Например, если Р обозначает высказывание «идет дождь», a Q — «я на работе», то набор высказываний { Р, Q }имеет четыре различных отображения в таблице истинности {ИСТИНА, ЛОЖЬ}. Эти отображения соответствуют четырем различным интерпретациям.

Рассмотрим теперь основы исчисления предикатов.

Логика предикатов первого порядка является более выразительным средством, чем логика высказываний, и позволяет представлять знания о среде более компактно.

Приведем понятие предикат, данное Д. А. Поспеловым: «Под предикатом будем понимать некоторую связь, которая задана на набо­ре констант или переменных». Пример предиката: «А больше В». При задании семантики (т. е. определении переменных А и В) можно будет судить об истинности предиката.

Предикат принимает только два значения ИСТИНА или ЛОЖЬ.

Исчисление предикатов. Основными синтаксическими единицами ло­гики предикатов являются константы, переменные, функции, предикаты, кванторы и логические операторы. Формальный синтаксис логики предикатов первого порядка можно представить с помощью языка Бэкуса—Наура, который обычно применяется для записи грамматик языков программирования [2, 3]:

‹константа› →‹идентификатор1›

‹переменная› → ‹идентификатор2›

‹функция› → ‹идентификатор3›

‹предикат› →‹идентификатор4›

‹терм› → ‹константа› | ‹переменная› | ‹функция›(‹список термов›)

‹список термов› → ‹терм› | ‹терм›{, ‹терм›}

‹атом› → ‹предикат› | ‹предикат›(‹список термов›)

‹литера› →‹атом› | ‹атом›

‹оператор› →Ù | Ú | → | ≡

‹список переменных› → ‹переменная› | ‹переменная›{, ‹переменная›}

‹квантор› → ($ ‹список переменных›) | (" ‹список переменных›)

‹формула› → ‹литера› | (‹формула› | ‹квантор› ‹‹формула›) |

(‹формула›) ‹оператор› (‹формула›)

В данной записи слева в угловых скобках приводятся типы синтаксиче­ских объектов, в правой части записи приводятся возможные способы организации синтаксически корректных объектов определяемого типа. При этом знак «|» интерпретируется как знак «или»; заключение конструкции в скобки {} означает, что эта конструкция может повторяться нуль или более раз. Номера идентификаторов следует понимать в том смысле, что идентификаторы, используемые для обозначения объектов разных типов, должны быть различны. Например, ‹идентификатор1› обозначает константу, которая формируется из строчных букв. Имена переменных ‹идентификатор2› должны начинаться с заглавных букв. Имена предикатов ‹идентификатор4› должны состоять из прописных букв. Имена функций ‹идентификатор3› состоят из строчных букв, при этом первой буквой является f, g, h, р, q. Функции, как и предикаты, задают связь между переменными и константами, но эта связь не характеризуется логическим значением. С помощью функции можно представить сложный объект, представляющий набор информации о мире. Предикат и функция отличаются также и на синтаксическом уровне, так как функция может являться аргументом предикатов, а предикат — нет.

Математически строго формулы логики предикатов определяются рекурсивно:

1) предикат есть формула;

2) если А и В — формулы, то А, А Ù В, A Ú В, А → В, A «B — тоже формулы;

3) других формул не бывает.

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

 

Таблица 1

 

Истинность связок предикатов (И — ИСТИНА, Л — ЛОЖЬ)

 

А	B	А Ù В	A Ú B	A	А → В	А «В
И	И	И	И	Л	И	И
И	Л	Л	И	Л	Л	Л
Л	И	Л	И	И	И	Л
Л	Л	Л	Л	И	И	И

 

 

Заметим, что выражение А → В аналогично «ЕСЛИ А, ТО В» в естественном языке.

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

Условимся, что выражение «все течет, все изменяется» является правильным. Если определить, что предикат ТЕЧИЗМ(х) описывает «х течет, изменяется», то этот предикат является истиной при подстановке любой сущности реального мира в х. Выделенная фраза обозначается через " x (перевернутое А от английского Аll — все), она обычно читается как «для всех» и записывается перед предикатом в виде " xF (x).

В логике предикатов имеется еще одна конструкция для суждения о значении предикатов по их переменным. Этот квантор эквивалентен суждению «существует, по крайней мере, одно х такое, что F(x) — истина». Выделеная фраза записывается в виде $х (перевернутое Е от английского Exists — существует), а все суждение представляется как $х$х F (x).

Символы, которые означают «для всех» и «существует» называются соответственно квантором общности и квантором существования. В логике предикатов первого порядка не разрешается применение кванторов к предикатам.

Переменная, которая проквантифицирована, называется связанной переменной, а переменная, которая не связана кванторами, называется свободной переменной.

Формула, в которой все переменные связаны, называется предложением. Каждому предложению ставится в соответствие определенное значение — «истина» или «ложь».

Сложные формулы в логике предикатов получаются путем комбинирования атомарных формул с помощью логических операций. Такие формулы называются правильно построенными логическими формулами (ППФ). Интерпретация ППФ возможна только с учетом конкретной области интерпретации, которая представляет собой множество всех возможных значений термов, входящих в ППФ. Для представления знания в данной предметной области необходимо установить область интерпретации, т. е. выбрать константы, которые определяют объекты в данной области, а также функции и предикаты, которые определяют зависимости и отношения между объектами. После этого уже можно построить логические формулы, описывающие закономерности данной предметной области. Все это возможно, когда знания являются полными, четкими и надежными, в противном случае записать знания с помощью логической модели не удается [2, 3].

 

Пример. Введем обозначения:

А(х) = «студент х учится отлично»;

В(х) = «студент х получает повышенную стипендию».

 

Теперь формула A (Иванов) → B (Иванов) означает: «студент Иванов учится отлично, следовательно, студент Иванов получает повышенную стипендию», а формула с квантором общности " х (А (х) → В (х))означает: «каждый студент, который учится отлично, получает повышенную стипендию».

Наиболее известным языком логического программирования является PROLOG (Пролог) — это (logic programming language). Логическая программа — это набор спецификаций в рамках формальной логики. Язык PROLOG основан на теории предикатов первого порядка. Само имя этого язы­ка расшифровывается как Programming in Logic (Программирование в логике).

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

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