Основы искусственного интеллекта

1. Основы искусственного интеллекта

2. ОБЩАЯ ХАРАКТЕРИСТИКА ЯЗЫКА ПРОЛОГ. ПРЕДСТАВЛЕНИЕ ЗНАНИЙ С ПОМОЩЬЮ ФАКТОВ И ПРАВИЛ.

Логическое программирование представляет собой
нетрадиционную технологию программирования,
основывается на описании логической структуры
задачи при отсутствии описания способов её решения.
Логическая программа - это набор утверждений
(“деклараций”), определяющих базу данных (знаний),
в которых хранятся соответствующие объекты и
заданные на них отношения.
Логическое программирование возникло главным
образом благодаря успехам в автоматическом
доказательстве теорем, в частности, благодаря
разработке правила резолюции.

3. ОБЩАЯ ХАРАКТЕРИСТИКА ЯЗЫКА ПРОЛОГ. ПРЕДСТАВЛЕНИЕ ЗНАНИЙ С ПОМОЩЬЮ ФАКТОВ И ПРАВИЛ.

Правило резолюции является полным множеством правил вывода
для фразовой формы логики предикатов. В своей наиболее общей форме
резолюция применяется к произвольным дизъюнктам вида L1 L2 L3
… Ln, где Li – это либо положительная литера (атом, предикат), либо
отрицательная литера (атом, стоящий с отрицанием). На каждом шаге
берутся два дизъюнкта (родительские дизъюнкты), такие, что некоторая
положительная литера в одном из них и некоторая отрицательная литера в
другом содержит предикаты, унифицируемые некоторой подстановкой Θ и
данные литеры “отрезаются”. В результате этого шага получается третий
дизъюнкт (резольвента) CΘ, где С – дизъюнкция всех литер (если,
конечно, они имеются) из родительских дизъюнктов, отличных от тех,
которые отрезаются. Выбор родительских дизъюнктов и отрезаемых литер
осуществляется произвольным образом.
Как показал автор правила резолюции Робинсон, метод резолюций
является корректным и полным в том смысле, что пустой дизъюнкт
выводим из входного множества дизъюнктов S посредством некоторой
конечной последовательности шагов резолюции тогда и только тогда,
когда множество S невыполнимо.

4. ОБЩАЯ ХАРАКТЕРИСТИКА ЯЗЫКА ПРОЛОГ. ПРЕДСТАВЛЕНИЕ ЗНАНИЙ С ПОМОЩЬЮ ФАКТОВ И ПРАВИЛ.

Наиболее полное и строгое выражение идеи
логического программирования
нашли в языке
программирования Пролог
(PROLOG – PROgramming in LOGic).
Идея использования логики в качестве языка
программирования
возникла в начале 70-х гг.
Теоретические аспекты были разработаны Робертом
Ковальским,
экспериментальная демонстрационная
система - Маартеном ван Эмденом (оба - Эдинбург),
реализация выполнена Аленом Колмероэ (Марсель),
Девидом Уорреном (Эдинбург).

5. ОБЩАЯ ХАРАКТЕРИСТИКА ЯЗЫКА ПРОЛОГ. ПРЕДСТАВЛЕНИЕ ЗНАНИЙ С ПОМОЩЬЮ ФАКТОВ И ПРАВИЛ.

Под представлением знаний будем понимать множество синтаксических
и семантических соглашений, которое делает возможным описание состояния
некоторой предметной области.
Синтаксис
представления
специфирует
набор
правил,
регламентирующих объедение символов для формирования выражений на
языке представления. При этом смысл имеют только хорошо сформированные
выражения. Общепринятым в области искусственного интеллекта является
синтаксис в виде конструкции предикат-аргумент, которая имеет вид:
<фраза>::=<предикат>(<аргумент>, …, <аргумент>)
В этой конструкции за k-местным предикатом должны следовать k аргументов.
Семантика представления специфирует, как должно интерпретироваться
выражение, построенное в соответствии с синтаксическими правилами, т.е.
как из его формы можно извлечь какой-то смысл. Спецификация обычно
выполняется присвоением смысла отдельным символам, а затем
индуцированием присвоения в более сложных выражениях. Так, присваивая
смысл символам at, робот, комната1, можно сказать, что выражение at(робот,
комната1) означает: робот находится в комнате1 (но не наоборот – комната1
находится в роботе).

6. ОБЩАЯ ХАРАКТЕРИСТИКА ЯЗЫКА ПРОЛОГ. ПРЕДСТАВЛЕНИЕ ЗНАНИЙ С ПОМОЩЬЮ ФАКТОВ И ПРАВИЛ.

Программа на языке Пролог состоит из трех основных
конструкций: фактов, правил и запросов.
Простейшим видом утверждения является факт.
Факты используются для констатации того, что выполнено
некоторое отношение между объектами. Другое название
отношения – предикат.
Факт, состоящий из структуры с одним элементом,
обычно описывает некоторое свойство. Например, факт
"студент ("Иванов")" определяет, что объект "Иванов"
имеет свойство "быть студентом". Этот факт можно
интерпретировать на естественном языке так: "Иванов есть
студент" или более строго так: "Высказывание "Иванов
есть студент" истинно".

7. ОБЩАЯ ХАРАКТЕРИСТИКА ЯЗЫКА ПРОЛОГ. ПРЕДСТАВЛЕНИЕ ЗНАНИЙ С ПОМОЩЬЮ ФАКТОВ И ПРАВИЛ.

Объекты данных в Прологе называются термами. Терм
может быть константой, переменной или составным термом. К
константам относятся целые и действительные числа, а также
атомы. Атом есть любая последовательность символов,
заключенная в одинарные кавычки. Кавычки опускаются, если и
без них атом можно отличить от символов, используемых для
обозначения
переменных.
Предикат
может
обладать
произвольным количеством аргументов.
Факты с более чем одним элементом описывают
взаимосвязи объектов (отношения между ними), например, факт
"имеет (саша, машина)" определяет, что объекты "саша" и
"машина" находятся между собой в таком отношении, что
второй является собственностью первого. Этот факт
интерпретируется на русском языке так: «Саша имеет машину".

8. ОБЩАЯ ХАРАКТЕРИСТИКА ЯЗЫКА ПРОЛОГ. ПРЕДСТАВЛЕНИЕ ЗНАНИЙ С ПОМОЩЬЮ ФАКТОВ И ПРАВИЛ.

Простейшая Пролог-программа – это множество
фактов. Совокупность фактов называется базой данных.
Фактографическая база данных Пролога является, по сути,
реляционной базой. Отдельный факт соответствует
кортежу, имена объектов — атрибутам, а совокупность
фактов с одинаковым именем и количеством объектов —
отношению реляционной базы.

9. Пример. Родственные отношения.

родитель (пам, боб)
родитель (том, боб)
родитель (том, лиз)
родитель (боб, энн)
родитель (боб, пат)
родитель (пат, джим)
????-
родитель (боб, пат).
yes
родитель (лиз, пат).
no
родитель (том, бен).
no
родитель (Х, лиз).
Х=том
(Кто родитель лиз?)
?- родитель (Х, У). (Кто чей родитель?)
Х=пам У=боб
Х=том У=боб
Х=том У=лиз …….
?- родитель (У, джим), родитель (Х, У).
(Кто родитель родителя джима)
Х=боб У=пат
?- родитель (боб, Х). Х=энн Х=пат
(Кто дети боба?)

10. ОБЩАЯ ХАРАКТЕРИСТИКА ЯЗЫКА ПРОЛОГ. ПРЕДСТАВЛЕНИЕ ЗНАНИЙ С ПОМОЩЬЮ ФАКТОВ И ПРАВИЛ.

Программа на Турбо Прологе может состоять из
следующих разделов:
domains
predicates
clauses
% определение типов данных
% определение предикатов
% определение фактов и правил
Перед разделом domains может быть раздел constants, в
котором определяются необходимые константы.
Перед разделом clauses может располагаться раздел goal, в
котором определяется цель. Цель может состоять из
нескольких подцелей.

11. ОБЩАЯ ХАРАКТЕРИСТИКА ЯЗЫКА ПРОЛОГ. ПРЕДСТАВЛЕНИЕ ЗНАНИЙ С ПОМОЩЬЮ ФАКТОВ И ПРАВИЛ.

Раздел domains
В разделе определяются глобальные и локальные типы данных.
Возможно определение ссылочного типа (reference).
В Турбо Прологе изначально определены простые типы данных:
char
Отдельный символ, заключенный в апострофы
Integer Целое число в диапазоне от -32768 до 32767
real
Число, может быть представлено в экспоненциальной форме
ref
Ссылочный тип, используемый во внешней базе данных
symbol Последовательность букв, цифр и знаков подчеркивания,
которая начинается со строчной буквы или заключена в кавычки
string
Любая последовательность символов, которая заключена в
кавычки
db_selector Назначенный пользователем селектор для внешней
базы данных
file
Внутреннее имя файла (файловый домен)

12. ОБЩАЯ ХАРАКТЕРИСТИКА ЯЗЫКА ПРОЛОГ. ПРЕДСТАВЛЕНИЕ ЗНАНИЙ С ПОМОЩЬЮ ФАКТОВ И ПРАВИЛ.

Раздел predicates
В разделе определяются предикаты (отношения). Каждый
предикат определяется со своим именем и своими аргументами
(параметрами). Использование параметров по назначению можно
задавать. Передоказуемый предикат описывается как nondeterm.
Добавив отсечение и объявив determ, можно предикат превратить в
детерминированный. Турбо Пролог позволяет присоединить к
программе процедуры, написанные на языках C, Pascal, Fortran или
Assembler. Процедуры, написанные на этих языках, следует объявлять
в Пролог-программе как глобальные. Для трансляции программы
необходимо указывать нужный объектный файл.

13. ОБЩАЯ ХАРАКТЕРИСТИКА ЯЗЫКА ПРОЛОГ. ПРЕДСТАВЛЕНИЕ ЗНАНИЙ С ПОМОЩЬЮ ФАКТОВ И ПРАВИЛ.

Раздел clauses
В этом разделе определяются факты и правила. Факт
представляется именем предиката, за которым следуют аргументы,
заключенные в круглые скобки. Заканчивается запись факта точкой.
Правило состоит из заголовка правила и тела. Заголовок
представляет собой предикат, тело состоит из термов, которые могут
быть связаны между собой словами or или and. Между телом и
заголовком стоит слово if. Каждое правило заканчивается точкой.
Имена переменных должны начинаться с прописной буквы и могут
содержать только буквы, цифры или знак подчеркивания - "_".
Максимальная длина имени - 250 знаков.
Особую
роль
играют
анонимные
переменные.
Они
представляются собой одиночным знаком подчеркивания.

14. ОБЩАЯ ХАРАКТЕРИСТИКА ЯЗЫКА ПРОЛОГ. ПРЕДСТАВЛЕНИЕ ЗНАНИЙ С ПОМОЩЬЮ ФАКТОВ И ПРАВИЛ.

Правило – это утверждение вида: А: - В1, В2, …, Вn.
Заголовок: - тело.
Правило – это факт, значение истинности которого зависит от
истинностных значений условий, образующих тело правила.
Заголовок правила имеет точно такую же форму, как и факт. Каждое
условие, входящее в тело, называется подцелью. Для того, чтобы
заголовок правила оказался истинным, необходимо, чтобы каждая
подцель, входящая в тело, была истинной. Таким образом, правило
определяет некоторое отношение при условии, что выполняются
определенные отношения между объектами.
Например, внук (X, Z):- родитель (Y, X), родитель (Z,Y)
Правило, в состав которого входят переменные, можно рассматривать
как неявное определение множества фактов.

15.

project "project_name"
CONSTANTS
% секция констант
const1 = definition
const2 = definition
[GLOBAL] DOMAINS
dom [,dom] = [reference] declaration1; declaration2
% reference -ссылочный домен
% список
listdom = dom*
dom = <basisdom>
[GLOBAL] DATABASE [ - <databasename> ]
[determ] pred1(....)
pred2(.....)
% имя проекта
GLOBAL PREDICATES
[determ|nondeterm] pred1(.........)
-(i,i,o,..)(i,o,i,..) [ language c|pascal|fortran ] [ as "name" ]
pred2(........)
PREDICATES
[determ|nondeterm] pred1(.........)
pred2(........)
CLAUSES
p(....):-p1(...), p2(.....), ... .
p(....):-p1(...), p2(.....), ... .
Include "filename"
% включение файла в программу

16.

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

17.

Запрос
Простой запрос
без
аргументов
константами
Составной запрос
с аргументами
конъюктивный
запрос
именованными
переменными
анонимными
переменными
дизъюктивный
запрос

18. Пример. Pодственные отношения семьи Романовых  

Пример. Pодственные отношения семьи Романовых
domains
name=symbol
predicates
parent(name,name)
man(name)
women(name)
king(name,integer,integer)
clauses
parent("Михаил","Алексей Михайлович").
parent("Алексей Михайлович","Федор").
parent("Алексей Михайлович","Иван").
parent("Алексей Михайлович","Софья").
parent("Алексей Михайлович","Петр I").
parent("Петр I","Алексей").
parent("Екатерина II","Павел I").
parent("Петр III","Павел I").
man("Михаил").
man("Алексей Михайлович").
man("Федор").
man("Иван").
man("Петр I").
man("Алексей").
man("Павел I").
man("Петр III").
women("Софья").
women("Екатерина II").
king("Михаил",1613,1645).
king("Алексей Михайлович",1645 ,1676).
king("Федор",1676 ,1682).
king("Иван",1682 ,1696).
king("Софья",1682 ,1689).
king("Петр I",1682 , 1725).
king("Екатерина II", 1762, 1796).
king("Петр III", 1761,1762).
king("Павел I",1796 ,1801).