Лекции . Технология построения интеллектуальных систем. Методы представления знаний Формальные языки и формальные системы (стр. 2 )

a - переменная

- объекты реального мира 

-  n-местный функциональный символ.

- отношение

- предикат

Тогда – модель (или интерпретация).

Понятие истинности модели

Атомарная формула , где , - константы, истинна в модели (записывается ), если пара .

Далее по индукции.

Полнота и корректность модели

Модель корректна, если всякая формула, выводимая в исчислении, оказывается истинна в модели.

Модель полна, если всякая формула, истинная в модели, выводима в исчислении.

Утверждение. Модель корректна и полна в исчислении предикатов первого порядка.

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

Напомним, что модель – это некоторая пара , где М – множество, F – отображение, которое каждой формуле исчисления предикатов ставит в соответствие некоторое отношение на множестве М (некоторое его подмножество).

Пусть – n-местная атомарная формула.

Предикат: функция отображает формулу в . Иногда атомарную формулу будем называть предикатом.

Пусть - константа.

Формула , где , - константы, истинна в модели ( ), если пара .

- предикатные символы.

- атомарная формула (или, если нестрого, предикат).

Определение. Предикат – функция, которая формулу отображает в множество {0,1}

Пример.

Пусть в качестве модели взяли таблицу (например, из БД):

Мать	Отец	Ребенок
Аня	Петя	Вася
Галя	Петя	Коля

Пусть задано исчисление, в котором определен предикат Родственные_отношения - трехместная атомарная формула. Чтобы определить истинность этой формулы, необходима модель . Эта таблица ее и задает. Хотим узнать что-нибудь об истинности формулы в модели.

– Родственные отношения в Москве

- родственные отношения могут быть в разных городах

Таким образом, , .

Если переменные означены2 чем-то, чего нет в таблице, то ложна.

Формула истинна в , если истинна в и истинна в .

Формула истинна в , если истинна в или истинна в .

Формула истинна в , если ложна в .

Формула ложна в , если истинна в и ложна в ; во всех остальных случаях она истинна в .

Таким образом, мы построили отношение истинности для любых формул исчисления предикатов 1-го порядка. Если формула истинна во всех моделях, то говорят, что она истинна. Иногда называют интерпретацией формул исчисления предикатов 1-го порядка.

Системы правил для представления знаний
(продукционные системы)

Определение. Правило3 – это некоторая упорядоченная тройка множеств , где

С – условие

А – множество добавляемых фактов

D - множество удаляемых фактов.

Пример.

Прозвенел звонок - войти в класс - ;

Как описать эти факты?

С – список формул исчисления предикатов 1-го порядка.

А - список формул исчисления предикатов 1-го порядка.

D – список формул исчисления предикатов 1-го порядка.

(списокконъюнкция).

Пример.

Мир кубиков

Задача: построить робота, который строит башни из кубиков4. Введем следующие предикатные символы:

= "Кубик находится на кубике " - двуместный предикатный символ (атомарная формула языка исчисления предикатов 1-го порядка); ="Кубик   пуст сверху" - одноместный предикатный символ = " Кубик стоит не земле "- одноместный предикатный символ.

Определим правила для робота: