Конспект лекций по дисциплине «Системы искусственного интеллекта»

Скачать 1.15 Mb.

Название	Конспект лекций по дисциплине «Системы искусственного интеллекта»
страница	2/11
Дата	05.09.2012
Размер	1.15 Mb.
Тип	Конспект

1 2 3 4 5 6 7 8 9 10 11

2.1. Язык исчисления предикатов первого порядка.

Основные конструкции языка L – языка исчисления предикатов первого порядка [1,2] называются формулами. Введем вначале алфавит языка L. Алфавит включает:

Счетное множество букв: ,…; которое будем называть множеством символов для обозначения переменных языка;
Счетное множество букв _; которое будем называть множеством символов для обозначения констант языка;

Счетное множество прописных букв _{; для обозначения} предикатных символов языка;

Счетное множество строчных букв ; для обозначения функциональных символов;
Символы для логических связок (влечет),(не);
_{Символ для квантора}__{(для любого);}

7. ( , ) - скобки.

Предикатные буквы P, Q, … и функциональные буквы f, g,…могут быть n – местными или, как еще говорят, n – арными. Иначе говоря, с каждым предикатным или функциональным символом будем связывать некоторое натуральное число, равное числу его аргументов.

Определим понятие формулы или правильно построенного выражения языка исчисления предикатов первого порядка.

Формулы языка определяются индуктивным образом. Начнем с определения терма языка:

Переменная есть терм.
Константа есть терм.
Если t₁ ,t₂ , …,t_m ,…, t_n - термы, а f и g – функциональные символы арности m и n, соответственно, то f (t₁ ,t₂ , …,t_m ) и g(t₁ ,t₂ ,…,t_n ) также термы.
Если t₁ ,t₂ , …,t_m ,…, t_n - термы, а P и Q – предикатные символы арности m и n, соотвественно, то P(t₁ ,t₂ , …,t_m ) и Q(t₁ ,t₂ ,…,t_n ) - атомарные формулы.
Атомарная формула есть формула.
Если - формулы, то₍_A_B₎,, - формулы.
Если A – формула, то xA– формула.
Всякое слово в алфавите языка является формулой тогда и только тогда, когда это можно показать с помощью конечного числа применений п.п. 1-7.

Например, если бы мы пожелали таким образом описать язык теории групп, то следовало бы задать один двуместный функциональный символ × (умножение) и одну константу l (единицу). Предикатные символы в этом случае не понадобятся. Термами тогда были бы выражения вида × (х, у) и ×(1× (×1)).

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

Можно, например, определить логические связки

_{(читается}_и_и_или_{), выразив их через связки}__и__:

_1._A__B₌_₍_A__B₎

2. A B =AB

Квантор существования -  (существует) также выражается через квантор всеобщности и отрицание:

xA(x) = x A(x)

Разумеется,

и  с тем же успехом можно было бы включить в язык в качестве трех дополнительных символов. Есть, однако, некоторые преимущества в том, чтобы сохранить список символов как можно более коротким. Например, индуктивные определения и доказательства по индукции оказываются в этом случае короче.

В дальнейшем нам придется использовать понятия свободного и связанного вхождения переменной в формулу. Вхождение переменной x в формулу A называется связанным, если эта переменная следует за квантором существования или всеобщности, предшествующими формуле A. В противном случае, вхождение переменной называется свободным. Если в формуле A отсутствуют свободно входящие в нее переменные (т.е. либо все переменные связаны, либо просто отсутствуют), то формула называется замкнутой формулой или предложением. Атомарную замкнутую формулу будем называть фактом. В том случае, если язык состоит только лишь из предложений, то он называется пропозициональным языком, а буквы A, B, …, входящие в формулы этого языка – пропозициональными переменными.

1.2.5. Пример.

Рассмотрим иллюстративный пример, который назовем Мир кубиков.

Пусть перед нами стоит задача написать программу, которая бы обеспечила разумное поведение робота - строителя башни из кубиков.

Введем вначале следующие предикатные символы:

On - двуместный предикатный символ “находиться на”;

Em - одноместный предикатный символ “ не находиться под кубиком”;

Er - находиться на земле.

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

означает, что"Кубик

находится на кубике

"; атомарная формула

означает, что"Кубик

не находится под другим кубиком"; а атомарная формула

означает, что " Кубик

стоит на земле ".

Мы полагаем, что эти формулы будут использованы в качестве элементов условий, множеств добавляемых и удаляемых фактов в правилах. Но прежде чем говорить о правилах, опишем устройство рабочей памяти. Если действовать таким же образом, как было описано выше, следует задать интерпретирующее отображение I, которое каждому предикатному символу поставит в соответствие некоторое отношение на множестве кубиков. Основное множество M будет состоять из элементов, соответствующих кубикам.

Итак, отображение I ставит в соответствие предикатному символу On бинарное отношение на M, предикатным символам Em и Er – одноместные отношения на M. Обозначим эти отношения так же, как соответствующие предикатные символы, только иным шрифтом. Иначе говоря, I (On) = On,

I (Em) = Em, I(Er) = Er.

Поскольку все отношения конечны, то их можно представить в виде таблиц (Рис. 1.2.) Элементы множества М обозначим через m₁ , m₂ , …, m_n.

On

m₁

m₂

………..

m_n

m₁

m₂

………..

m_n

Рис.1.2.1.

В начальном состоянии первая из таблиц не заполнена, а две другие заполнены полностью. Таким образом, на рис 1.2.1. изображено начальное состояние «Мира кубиков». Целевое состояние должно иметь такой вид (заметим здесь, что мы считаем все кубики идентичными и, поэтому, нумерации элементов из М не будем придавыать значения) :

On

m₂	m₁
m₃	m₂
….	…
m_n	m_n-1

m_n

m₁

Рис. 1.2.2.

Если мы принимаем решение использовать описания состояний, приведенные на рис. 1.2.1.и 1.2.2. в качестве рабочей памяти системы, основанной на правилах, то сами правила должны применяться к описаниям этих состояний для порождения новых состояний и такая система называется прямой системой правил. Однако, в рабочей памяти можно хранить описания целей, подцелей и т.д. Такая система правил будет называться обратной. Впрочем, различие между этими двумя системами правил можно провести лишь на интуитивном уровне.

Вернемся в мир кубиков и опишем прямую систему правил для робота – строителя башен; вначале неформально.

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

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

Для решения этой задачи можно было бы построить систему и из одного правила. Однако это привело бы к серьёзному усложнению этого правила и увеличению вычислительных трудностей на этапе исполнения. Кроме того, трудно было бы продемонстрировать возможности стратегии управления.

Перейдем к уточнению вида правил для решения этой задачи. Обозначим правила через П1 и П2, т.е.

П1 = <С₁ , A₁, D₁ > , где

. С₁= {

},

A₁= {On (x, y)},

D₁= {

}.

П2 = <С₂ , A₂, D₂ >, где

С₂= {

_, On (y, z) },

A₂= {On (x, y)},

D₂= {

}.

Стратегия управления, которая потребуется для решения этой задачи, описана в п 1.2.3 . Напомним её:

Шаг 1. Выбрать очередное правило из множества правил;

Шаг 2. Проверить выполнимость условия правила в текущем состоянии рабочей памяти;

Шаг 3. Если условие правила выполнено, поместить правило в конфликтное множество;

Шаг 4. Если множество применимых правил исчерпано, выбрать какое- либо правило из конфликтного множества правил и применить его.

Шаг 5. Перейти к шагу 1.

В нашем примере к начальному состоянию применимо лишь первое правило (т.к. в начальном состоянии таблица On пуста и, следовательно, формула On(x,y) невыполнима), поэтому в начальном состоянии конфликтное множество состоит из одного лишь правила и проблемы выбора не возникает._{При установлении выполнимости формул}

_{в условия первого правила вместо свободных переменных в формулы условия будут подставлены значения (например,}_m₁_вместо_y_и_m₂_вместо_x_{). Соответствующие подстановки будут выполнены также в формулы из множеств}_А_и_D_{. Атомарные формулы из множеств}_А_и_D_{превратятся в формулы без свободных переменных, т.е. в добавляемые и удаляемые факты, а именно, формулы}_On₍_x_,_y₎_{из множества добавляемых фактов и}_Em₍_y₎_и_Er₍_x₎_{из множества удаляемых фактов примут вид}_On₍_m₂_,_m₁₎_,_Em₍_m₁_),_Er₍_m₂_),_{соответственно. Применение правила состоит в том, что первая пара, т.е.}₍_m₂_,_m₁₎_{будет помещена в таблицу}_On_,азначения переменных из второй и третьей формул, т.е. m₁иm₂, соответственно,– удалены из таблиц Em и Er. Таким образом, мир кубиков будет модифицирован и в рабочей памяти появится описание второго состояния.

К этому, второму состоянию оказываются применимы оба правила. Т.к. множество применимых правил будет теперь состоять из двух правил, то необходимо уточнить шаг 4 стратегии управления, т.е. значение слов «какое – либо правило».

Если попытаться промоделировать стратегию управления «вручную», то нетрудно убедиться, что на втором шаге следует применить второе правило. Чтобы обеспечить строительство одной башни (а не нескольких), второе же правило следует применять и на всех последующих шагах. Второе правил отличается от первого большим количеством атомарных формул в условии. Таким образом, возникает следующий эмпирический принцип выбора: всякий раз, когда к некоторому состоянию применимо более одного правила, должно выбираться правило, более точно учитывающее особенности текущего состояния; таким правилом, очевидно, является то правило, условие которого более детально описывает состояние.

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

“Выбрать из множества применимых правил то правило, условие которого содержит наибольшее число различных атомарных формул».

Именно так следует в данном случае модифицировать шаг 4 стратегии управления.

Применение сформулированной эвристики приведет к выбору второго правила и на всех последующих шагах.

Процесс завершится либо по исчерпании применимых правил, либо по достижении целевого состояния.

К системам правил мы бдем возвращаться и в дальнейшем; им будет уделено достаточно много места в четвертой главе; пока же рассмотрим иной способ представления знаний, называемый семантическими сетями.

1 2 3 4 5 6 7 8 9 10 11

	Конспект лекций по дисциплине "Программное обеспечение интеллектуальных систем". Для магистров специальности 5А521902 Целью данного курса является приобретение знаний по разработки и реализации основных элементов систем искусственного интеллекта		Лабораторная работа №1 по дисциплине “Системы искусственного интелекта Исчисление предикатов первого порядка является теоретической основной множества формализмов методов искусственного интеллекта. Задачи...
	«шаг за шагом» создание искусственного интеллекта гашева Светлана Интеллект рассматривают как прикладную область исследований, связанных с имитацией отдельных функций интеллекта человека [6]. Распознавание...		Учебно-методический комплекс по дисциплине “основы искусственного интеллекта” ...
	«Основы искусственного интеллекта» Рабочая учебная программа по дисциплине «Основы искусственного интеллекта» для ооп «050100 Физика и информатика по циклу б в. 13...		Рабочая программа дисциплины «Системы искусственного интеллекта» Рабочая программа основана на требованиях Федерального государственного стандарта высшего профессионального образования по направлению...
	Учебно-методический комплекс по дисциплине “основы искусственного интеллекта” для специальности ...		Учебно-методический комплекс по дисциплине “основы искусственного интеллекта” для специальности ...
	В. К. Финн к структурной когнитологии: феноменология сознания с точки зрения искусственного интеллекта Ки и искусственного интеллекта – полигона экспериментальной проверки научных средств имитации рациональности и продуктивного мышления....		1. интеллектуальные системы Системы искусственного интеллекта, решающие задачи по обработке знаний и при этом проявляющие черты, сходные с чертами естественного...

Конспект лекций по дисциплине «Системы искусственного интеллекта»

2.1. Язык исчисления предикатов первого порядка.

Похожие: