Основы искусственного интеллекта презентация

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

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

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

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

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

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

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

(том, боб)
родитель (том, лиз)
родитель (боб, энн)
родитель (боб, пат)
родитель (пат, джим)

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

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

Программа на Турбо Прологе может состоять из следующих разделов:

domains % определение типов данных
predicates % определение предикатов
clauses % определение фактов и правил

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

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

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

 

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

 

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

% секция констант
const1 = definition
const2 = definition
[GLOBAL] DOMAINS
dom [,dom] = [reference] declaration1; declaration2
% reference -ссылочный домен
listdom = dom* % список
dom =
[GLOBAL] DATABASE [ - ]
[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" % включение файла в программу

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

Михайлович","Софья").
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).