Понятие об искусственном интеллекте icon

Понятие об искусственном интеллекте


Смотрите также:
Iy-я Международная научно-практическая конференция «Интегрированные модели и мягкие вычисления в...
Vi-я Международная научно-практическая конференция «Интегрированные модели и мягкие вычисления в...
V-я Международная научно-практическая конференция «Интегрированные модели и мягкие вычисления в...
История развития науки о искусственном интеллекте...
Об алгебраических основаниях голографической парадигмы в искусственном интеллекте: алгебра...
I. Возникновение науки об искусственном интеллекте...
Решение задач и структурное программирование для разработка прикладных программ и создания...
Искусственный интеллект это одна из новейших областей науки...
Дети с нарушениями речи это дети...
Информационный бюллетень...
Вопросы для вступительного экзамена в аспирантуру по специальности...
Аннотация



Загрузка...
страницы:   1   2   3   4   5   6   7
скачать


Содержание


Введение

Глава 1. Основные понятия

    1. Понятие об искусственном интеллекте

      1. Точка зрения Петрунина

      2. Искусственный интеллект в обыденных представлениях и информатике

    2. Основные направления исследования в области искусственного интеллекта

    3. Данные и знания. Модели представления знаний и их классификация

^ Глава 2. Логические модели представления знаний

    1. Логика высказываний

      1. Булева алгебра

      2. Понятие о логическом следствии

      3. Метод резолюции в ЛВ

    2. Логика предикатов первого порядка

      1. Основные определения

      2. Метод резолюции в ЛППП

      3. Стратегии проведения резолюции

      4. Упорядоченный линейный вывод в ЛППП

      5. Применение поиска в пространстве состояний при реализации автоматизированного логического вывода

      6. Логический вывод на хорновских дизъюнктах

      7. Понятие экспертной системы и применение логического вывода при построении экспертных систем

      8. Запросы класса A

      9. Запросы класса B

      10. Запросы класса C

    3. Понятие о нечетком выводе

    4. Неклассические логики

      1. Логики высших порядков

      2. Модальные логики

      3. Многозначные логики

^ Глава 3. Продукционные модели представления знаний

    1. Основные понятия

    2. Стратегии управления

      1. Поиск с возвратом

      2. Поиск в пространстве состояний

    3. Понятие о коммутативных системах продукций

    4. Понятие о нечетком выводе на продукциях

    5. Сравнение продукционных и логических моделей

^ Глава 4. Реляционные модели представления знаний

    1. Основные элементы естественных языков

    2. Дескрипторные модели

      1. Понятие об ИПС

      2. Линейная модель работы ИПС

      3. Понятие о многоуровневом поиске

      4. Основные характеристики дескрипторной ИПС

    3. RX-коды

    4. Синтагматические цепи

      1. Понятие о синтагматических цепях

      2. Фреймы

    5. Сетевые модели представления знаний

      1. Понятие о семантических сетях

      2. Структура интеллектуальной системы доступа к данным на основе семантической сети

      3. Поиск по образцу в семантической сети

      4. Понятие о логическом выводе на семантических сетях

^ Глава 5. Нейронные сети

    1. Параллели из биологии

    2. Базовая искусственная модель

    3. Применение нейронных сетей

    4. Обучение сети

^ Глава 6. Организация диалога с ЭВМ на естественном языке

    1. Элементы теории формальных языков

    2. Обратная польская запись

    3. Недостатки применения аппарата формальных грамматик при анализе естественных языков

    4. Элементы семиотики

    5. Модель непосредственных составляющих

    6. Многозначность естественных языков

    7. Расширенные сети переходов

    8. Глубинные (семантические) падежи

^ Глава 7. Логическое программирование на языке Пролог.

    1. Основные понятия в языке Пролог

    2. Пакет Turbo Prolog

    3. Структура программы

    4. Поиск решений

    5. Механизм отката

    6. Операторы вывода информации

    7. Повторение и рекурсия

    8. Повторение и откат

      1. Метод отката после неудачи

      2. Метод отсечения и отката

      3. Метод повтора, определенный пользователем

    9. Методы организации рекурсии

    10. Отладка программ и обнаружение ошибок

    11. Графика в Turbo Prolog’е

      1. Создание меню

      2. Создание графического режима

      3. Черепашья графика

    12. Списки и их использование

      1. Использование списка

      2. Поиск элемента в списке

      3. Создание нового списка путем слияния двух списков

      4. Разделение на два списка

    13. Сортировки

      1. Наивная сортировка

      2. Сортировка включением

      3. Метод пузырька

      4. Быстрая сортировка

    14. Компоновка данных из базы в список

    15. Работа с символами и строками

    16. Специальные строки

    17. Работа с файлами

    18. Создание динамических баз данных

    19. Библиотеки Turbo Prolog’а

    20. Модульное программирование

    21. Решение задачи о волке, козе и капусте

^ Глава 8. Введение в язык Lisp

    1. Основные особенности языка Лисп

    2. Понятия языка Лисп

      1. Атомы и списки

      2. Внутреннее представление списка

      3. Написание программы на Лиспе

      4. Определение функций

      5. Рекурсия и итерация

      6. Функции интерпретации выражения

      7. Макросредаства

      8. Функции ввода-вывода

/Перечень используемых сокращений

Литература




Введение


Широкое внедрение информационных технологий привело к развитию и усложнению школьного курса информатики, и, как следствие, появлению новых дисциплин предметной подготовки в образовательном стандарте по специальности «030100-информатика (учитель информатики)». Одной из таких дисциплин являются «Основы искусственного интеллекта».

Анализ государственного образовательного стандарта [] по специальности 030100 показывает, что основная цель данной дисциплины – общее знакомство студента с основными понятиями теории интеллектуальных систем и моделирования знаний, а также обучение основам рекурсивно-логического и функционального программирования на примере языков Пролог и Лисп соответственно. В соответствии с этим, основную часть пособия составляет краткое изложение теоретических положений, на основе которых создаются современные интеллектуальные системы. Что касается практической части, то в ней приводится только краткий обзор языка Лисп, дающий фактически лишь представление о том, что такое функциональное программирование, а к изучению Пролога требования более высокие, что обусловлено содержанием стандарта [].

В первой главе дается введение в основные понятия, принятые при изложении методов искусственного интеллекта. Философская стороны проблемы рассматривается в понимании Ю.Ю. Петрунина[]. Также приводится классификации основных моделей представления знаний. Вторая глава посвящена логическим моделям представления знаний, и задачам, в процессе решения которых они находят применение. Особое внимание уделено автоматизированному логическому выводу и построению экспертных систем. В третьей главе рассмотрены продукционные модели. В четвертой главе рассматриваются реляционные языки представления знаний – языки, в которых естественным образом описываются понятия и отношения, характерные для естественных языков. Рассмотрены также задачи информационного поиска и ситуационного управления. На примере задач ситуационного управления иллюстрируется применение фреймовых моделей. Пятая глава фактически является введением в нейроинформатику – теорию о нейронных сетях, она разработана на основе материала, изложенного в []. Шестая глава посвящена моделям, используемых при организации диалога между ЭВМ и пользователем на естественном языке.

Седьмая и восьмая глава составляют практическую часть курса. В седьмой главе дано относительно подробное описание языка Пролог. При этом сделана попытка дать теорию вместе с практикой, т.е. все теоретические положения иллюстрируются работающими программами. При этом мы намеренно обходились искусственно-простыми примерами. Наиболее известные реализации языка Пролог – система Turbo Prolog версии 2.0 и система Visual Prolog (ViP). Все примеры, приведенные в пособии, разработаны под Turbo Prolog, что дало возможность не тратить время на описание различных расширений языка, а остановиться непосредственно на особенностях Пролога, как логического языка. В восьмой главе дано краткое введение в функциональное программирование и язык Лисп, при этом, в основном используется материал, изложенный в [].

При подготовке курса и пособия использовалась многочисленная зарубежная и отечественная литература, в которой излагается материал, имеющий отношение к данной дисциплине и которая приведена в списке в конце пособия. Значительная часть материала заимствована из источников [].


Глава 1.^ ОСНОВНЫЕ ПОНЯТИЯ


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


1.1. Понятие об искусственном интеллекте


Многие проблемы из области искусственного интеллекта и искусственного разума сами по себе выходит за пределы информатики. Прежде всего, возникает вопрос «a thinking machine?», то есть умеют ли (и могут ли уметь) компьютеры мыслить или нет? Данная проблема, на наш взгляд, довольно объективно проработана Петруниным Ю.Ю. во введении к монографии ««От тайного знания к нейрокомпьютеру: Очерки по истории искусственного интеллекта» []. В пункте 1.1.1 приведем ключевые мысли Петрунина.


^ 1.1.1. Точка зрения Петрунина.

Прежде чем обратимся к размышлениям Петрунина, еще раз заметим, что эти размышления относятся к философии, а не к технических наукам, и поэтому ни в коем случае не должны восприниматься, как неоспоримые истины. Итак, «слово» Петрунину.

«Можно ли научить машину думать? Наконец, просто верите ли Вы в возможность создания искусственного разума? Сама модальность верования, употребляемая в таких вопрошаниях, наводит на мысль о том, что вопрос об искусственном интеллекте выходит за рамки научного, или, тем более, технического. "Относительно разума вычислительных машин… – пишет один из крупнейших авторитетов в этой области П. Уинстон – имеется много ходячих мифов"[1] С этим высказыванием нельзя не согласиться. Но я бы добавил, что и сам термин "искусственный интеллект" обозначает некий миф, широко проникший в современное научное и обыденное сознание. Миф означает в данном случае не ложность некоего представления, а лишь то, что это представление не может быть рационально обосновано и эмпирически проверено.

Действительно, для эмпирической проверки необходимо ясное представление о том, что собственно проверять, иными словами четкое определение того, что есть искусственный интеллект. Однако в работах по искусственному интеллекту отсутствует общепризнанное определение центрального понятая этой науки – "интеллекта". "По существу, последний так и не получил достаточно удовлетворительного объективного определения, – замечает А. Эндрю. – Поэтому ... в конечном счете нам придется вернуться к нашему интуитивному представлению об интеллекте"[2].

Реферативный журнал «Abstracts in Artificial Intellegence» (The Turing Institute, ed. J. Ritchie) разделяет искусственный интеллект на следующие проблемы: экспертные системы, применения искусственного интеллекта, автоматическое программирование, автоматическое доказательство теорем и логическое программирование, обучение, естественный язык, поиск, управление и планирование, робототехника, зрение и обработка изображений, распознавание образов, когнитивное моделирование, взаимодействие человека и ЭВМ, технические средства для искусственного интеллекта. Но что объединяет эти столь разные задачи?

"Если бы физики или химики взялись дать абстрактные определения своих областей знания, – подчеркивает Э. Хант, – то скорее всего не нашли бы разногласий ни среди тех, ни среди других. Вряд ли бы обнаружилось такое единодушие, если бы пришлось собрать вместе разных ученых, занимающихся искусственным интеллектом"[3].

Предлагаемые определения интеллекта непохожи друг на друга настолько, словно речь идет о разных вещах. Одни считают, что интеллект – это умение решать сложные задачи; другие рассматривают его как способность к обучению, обобщениям к нахождению аналогий; третьи – как возможность взаимодействия с внешним миром путем общения, восприятия и осознания воспринятого. Некоторые ученые развивают даже теоретическую модель, в которой за осуществление интеллектуальной деятельности отвечает около 120 различных факторов, из которых только 50–60 сегодня известны [4].

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

В начале 1950-х годов известный английский математик и специалист в области вычислительной техники Алан Тьюринг предложил тест, позволяющий определить, является ли машина "думающей" или нет. Этот тест основан на "игре в переговоры", суть которой состоит в следующем. Играющие пытаются отгадать, кто находится в соседней комнате. По вопросам, передаваемым через посредника устно или письменно и ответам на них, необходимо выяснить, является ли этот человек мужчиной или женщиной. Идея Тьюринга заключалась в том, чтобы посредством подобных переговоров испытать машину на "интеллект". Если лицо, задающее вопросы, не в состоянии установить, общается ли он с человеком или машиной, то следует признать, что эта машина (если это на самом деле механическое устройство) обладает интеллектом.

Но при таком подходе вполне логично утверждать, что отдельные существующие программы для вычислительных машин вполне удовлетворяют тесту Тьюринга. Хорошо известна, например, программа "Элиза", созданная еще в 1964 г. крупным американским кибернетиком Дж. Вейценбаумом и имитирующая поведение психиатра. Пациенты, с которыми "беседовала" эта программа, в большинстве случаев не сомневались в том, что они общаются с врачом. Однако несомненный успех этой программы не может заставить никого считать ее искусственным интеллектом. Почему?

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

  • Все мужчины одинаковы.

  • В каком смысле?

  • Они всегда пристают к тебе с чем-нибудь.

  • Вы имеете в виду что-нибудь конкретное?

  • Ну да, это мой парень заставил меня прийти сюда.

  • Ваш парень заставил вас прийти сюда?

  • Он говорит, что я почти все время подавлена.

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

  • Это правда. Я несчастна.

  • Вы думаете, что ваш приход сюда поможет вам не быть несчастной?

  • Это точно; мне нужна чья-нибудь помощь.

  • Что значит для вас "получить помощь"?

  • Может быть, я научусь ладить с моей мамой.

  • Расскажите поподробнее о вашей семье.

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

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

Программа была задумана как своего рода пародия на поведение некоторых психотерапевтов. Однако вне зависимости от первоначальных намерений Вейценбаума, ответы "Элизы" выглядели столь завораживающе правдоподобными, что многих приводили в восторг. Программа сумела одурачить президента компьютерной исследовательской фирмы и заставить одного крупного советского специалиста по компьютерам сесть за терминал в Стэнфорде и изливать компьютеру свои беды [5].

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

Представим себе такую ситуацию.

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

Конечно, – соглашается критик.

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

А как же работает эта программа? – недоверчиво вопрошает критик.

Посидев недолго за дисплеем, он решает, что подозрения его не напрасны: "И всего-то? Это я не могу признать интеллектуальным". Создается впечатление, что если мы понимаем, как что-то делается, то это "что-то" нельзя считать требующим особого ума. "Быть интеллектуальным – значит быть загадочным, – утверждает П. Уинстон. – Как он мог до этого дойти? – спрашиваем мы. До тех пор пока происхождение идеи остается неясным, она выглядит как откровение, но как только на поверхность выходит ее объяснение, мы удивляемся: "Как это я об этом не подумал, ведь это так очевидно!" Когда процесс окажется разделенным на части, изученным и понятым, похоже, что интеллект исчезает"[6].

Известный французский исследователь Ж.Л. Лорьер пишет: "Всякая задача, для которой неизвестен алгоритм решения, априорно относится к искусственному интеллекту"[7]. Но не означает ли это, что как только такой алгоритм найден, задача перестает относиться к сфере искусственного интеллекта? Где же "прячется" интеллект: в методе решения задачи или в том, что привело к нахождению этого метода?

Понятие интеллекта, словно легендарный Протей, кажется неуловимым. "На самом деле дать определение, – резюмирует свои соображения П. Уинстон, – в обычном смысле этого слова, по-видимому, невозможно"[8]. Как остроумно замечают Мичи и Джонстон, "за неимением более точного определения машинного интеллекта его можно охарактеризовать словами: "Точного определения я дать не могу, но всегда могу узнать, когда вижу"[9]. Термин "искусственный интеллект" призван, по мнению некоторых специалистов, вызвать лишь некоторый "поток субъективных ассоциаций"[10]. Удивительное дело, ключевое понятие рационализма – интеллект, разум – само как бы находится за границами рациональности, представляя из себя загадочное (даже "таинственное", по мнению ведущих специалистов по искусственному интеллекту Р. Шенка и Л. Хантера[11]"), обнаруживаемое лишь интуицией свойство, исчезающее при приближении к нему!

Разумеется, такой характер ключевого понятия в исследованиях по искусственному интеллекту сказывается и на методах "аргументации" споров, ведущихся в этой области науки. Вот типичный пример. Анализируя интеллектуальные возможности ЭВМ, известный советский кибернетик К.Е. Морозов пишет: "Главное опровержение скептицизма в оценке способностей машин заключается не в критике отдельных "конкретных" аргументов порознь. У. Мак-Каллок и В. Питтс в своих работах по теории нейронных сетей доказали, что любая функция естественной нервной системы, которая может быть логически описана с помощью конечного числа слов, реализуема с помощью формальной нервной сети. А формальная нервная сеть во многом эквивалентна ЭВМ. Отсюда вывод: принципиально возможно моделировать любые функции человеческого мозга"[12].

Но можно ли строго логически описать работу мозга? Оказывается, что в основе "конкретного" доказательства лежит недоказуемое предположение, или эпистемологическое верование. "Иногда ставят вопрос, – продолжает тот же автор, – а можно ли дать достаточно полное описание мозга и его работы? Последовательный материалист (в отличие от агностика) не может сомневаться в принципиальной возможности создания информационной модели мозга"[13].

Знаменитый советский "пророк" кибернетической эры академик В.М. Глушков считал, что никаких априорных ограничений для автоматизации интеллектуальной деятельности не существует. Критики компьютерного оптимизма обычно приводили в качестве доказательства наличия таких ограничений знаменитую теорему Гёделя о неполноте арифметики. Суть последней состоит в том, что любая формальная теория, включающая в себя арифметику натуральных чисел, если она непротиворечива, неполна в том смысле, что в ней обязательно существуют недоказуемые предложения, т.е. предложения, не выводимые из аксиом данной теории. Отсюда можно сделать вывод, что формализовать достаточно сложные процессы, к которым, без сомнения, относится мышление невозможно (или, иначе, любая формализация будет неполной).

Для преодоления этого запрета, считал В.М. Глушков, в формальной теории необходимо ввести развитие. "Запрет Гёделя снимается лишь в том случае, – писал В.М.Глушков, – когда рассматриваемая формальная теория развивается не изолированно, а во взаимодействии с окружающим миром при непременном, однако условии, что этот мир, в свою очередь, не может быть описан в виде конечно-порожденной системы"[14].

Обратим внимание: "если мир не может быть описан в виде конечной системы правил". Но где основания для такой уверенности?

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

Более того, только частое употребление слов "искусственный разум" "механический мозг" и их синонимов скрывает всю парадоксальность этих словосочетаний. Действительно, в термине "искусственный", или "машинный", интеллект соединены два противоположных по значению понятия. С одной стороны, "машинный" – слово, означающее нечто механическое, бессознательное, непроизвольное, строго повторяющееся и т.п., с другой – "интеллект" ("разум") – нечто оригинальное, творческое, неформализуемое, непредвидимое, неподчиняющееся никаким правилам. Как же оказывается осмысленным использование термина, аналогичного таким как "круглый квадрат", "темный свет", "горячий лед", "сухая вода" и т.п., являющихся по сути contradicto in adjecto (противоречием в определении)? " [15].

Тем не менее, это не мешает идее искусственного разума стремительно перешагивать за пределы тесного круга логиков и программистов. В первой главе первого издания (1977 г.) своей классической книги по использованию искусственного интеллекта в гуманитарных науках Маргарет Боден писала, что упоминание об искусственном интеллекте в обычной беседе может повергнуть собеседника в растерянность[16]. Десять лет спустя во втором издании этой книги М. Боден пишет, что концепция искусственного интеллекта принята всеми [17].

Но идея, или, лучше сказать, мифологема искусственного интеллекта не замыкается узкими рамками научного сообщества. Ведь дело не в том, что какой-то гений (или сумасшедший) придумал (изобрел) искусственный интеллект, а в том, что его идея была сразу подхвачена средствами массовой информации, тиражирована в художественные произведения, закрепилась в обыденном сознании. Люди, понятия не имеющие ни о программировании, ни о модальной логике, ни о лямбда-исчислении Черча и тому подобных вещах, просто и быстро поверили в возможность искусственного интеллекта – без всяких доказательств, да они бы их и не поняли. Других же таких же рьяных не могут убедить никакие доказательства. Но и те, и другие сразу же включили искусственный интеллект в свое сознание; поняли, почувствовали, увидели. Он стал им родным, начиная с детей. Последние в развитых странах теперь, вероятно, больше воюют в играх с роботами, чем с индейцами. Даже в мультфильме о Библии – "Суперкниге" – действуют разумные роботы, видимо, чтобы было понятней детям.

Все это говорит о том, что искусственный интеллект сразу (или почти сразу) стал предметом массовой веры, интеллектуальным идеалом, надеждой и чаянием человечества. О последнем значении искусственного интеллекта уже упоминавшиеся Мичи и Джонстон пишут так:

"Высказываются опасения, что создать разумные машины – это значит впустить в наш дом полчища "завоевателей". На самом деле мы должны смотреть на себя как на осажденный гарнизон, который после десяти часов осады вдруг с облегчением замечает на горизонте пыль, поднятую спешащим нам на помощь отрядом"[18].

Не говорит ли это о том, что еще задолго до появления слов "искусственный интеллект" общество было готово принять это трудносоединимое словосочетание, а точнее стоящие за ним представления? Создатель программы "Элиза" Дж.Вейценбаум писал впоследствии в своей книге "Возможности вычислительных машин и человеческий разум": "Основная идея нашей книги как раз и заключается в том, что мы все вместе чересчур преуспели в превращении нашего мира в "компьютер" и что эта перестройка мира по образу и подобию вычислительной машины началась еще задолго до появления электронных вычислительных машин. Теперь, когда у нас есть вычислительные машины, стало легче замечать эту поразительную трансформацию, которой мы подвергли наш мир"[19].

Не относятся ли слова Вейценбаума еще в большей степени к искусственному интеллекту? Не есть ли исследования в области создания разумных машин лишь определенная фаза развития старинных традиций, ранее облаченных в другие словесные формулировки и оснащенные совсем другими техническими средствами; традиций, принадлежащих не сугубо научно-рациональной сфере, а уходящим в сокровенные глубины европейской культуры? Сами творцы искусственного интеллекта в конце XX века отмечают прямую связь своих исследований с оккультными науками древности, с практикой алхимиков в Средние века, с легендами и мифами о создании совершенного человекоподобного существа».


^ 1.1.2. Интеллектуальные алгоритмы.

Итак, на обыденном уровне под исследованиями в области искусственного интеллекта обычно понимается попытка создания некого искусственного разума, подобного человеческому. Такая цель действительно всерьез ставилась в середине 20 века, ставится она некоторыми исследователями и сегодня. В настоящее время появляется все больше причин считать построение искусственного разума задачей недостижимой. Помимо упоминаемой Петруниным теоремы Геделя о неполноте, в пользу этой точки зрения говорит наличие «в природе» алгоритмически неразрешимых проблем (это доказанный факт – см. []), доказанная эквивалентность любого компьютера и абстрактной машины Тьюринга, возможности которой сводятся к трем элементарным операциям, и многое другое.

Независимо от того достижима ли эта глобальная цель или нет, и имеет ли оно вообще смысл (см. 1.1.1), в ходе исследований были достигнуты значительные результаты в области построения формальных моделей человеческих знаний и человеческой логики. Эти модели в отличие от отвлеченных разговоров об искусственном разуме, являются реальными научными результатами. И хотя эти модели далеки от того, чтобы полностью формализовать процесс познания, они с успехом применяются для решения тех задач, для которых не существует классических алгоритмов решения вообще, или для которых эти алгоритмы неэффективны. Методы решения задач, основанные на формальных моделях знаний, будем называть интеллектуальными алгоритмами или методами искусственного интеллекта (ИИ).

Примечание. Как видим, в этой трактовке интеллектуальность – понятие очень условное, так как эти методы представляют собой обычные алгоритмы и на самом деле не подразумевают мыслительного процесса, как такового.


^ 1.2. Основные направления исследования в области ИИ


Перечислим основные направления исследования в области искусственного интеллекта или, иначе говоря, классы задач, для решения которых применяются методы искусственного интеллекта. Эта классификация, в сущности, уточняет классификацию реферативного журнала «Abstracts in Artificial Intellegence», упоминавшуюся в 1.1.1.

  1. Создание экспертных систем (ЭС). Под экспертные системами, как правило, понимают системы, которые выдаваемое решение сопровождают объяснением, почему выбрано именно это решение, а не другое. Чаще всего эти системы предназначены для установления какого-либо предмета или явления по его признакам. Подробнее об экспертных системах в 2.2.7.

  2. Автоматизированный логический вывод (автоматическое доказательство теорем). Подробнее в главе 2.

  3. Решение задач ситуационного управления, т.е. создание систем управления процессами, работу которых тяжело или невозможно описать формальными алгоритмами, например диспетчера в аэропорту. Подробнее в 4.4.2.

  4. Решение задач распознавания образов. К данной области относится на самом деле широкий класс задач, включающий в себя распознавание печатных знаков в отсканированном тексте, распознавание рукописного текста, «понимание человеческого голоса» (распознавание звуков), распознавание фрагментов растрового изображения (широко применяется при векторизации []) и т.д..

  5. Разработка эффективных поисковых систем в банке данных или в Internet’е; примерами таких систем являются www.yahoo.com, www.hotbot.com, www.rambler.ru, www.yandex.ru и т.д.

  6. Организация диалога между ЭВМ и пользователем на естественных языках (английском, русском и т.д.).

  7. Разработка качественных электронных переводчиков с одного естественного языка на другой.

  8. Приближенное решение любых задач, для которых доказано отсутствие или не найдено точного алгоритма решения задачи, или этот алгоритм экспоненциален (подробнее о полиномиальных и экспоненциальных алгоритмах см. []).

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


^ 1.3. Данные и знания. Основные модели представления знаний


Как известно из дисциплины «Информационные системы» [ ], под данными понимаются факты или идеи, представленные в формализованном виде. Сами по себе данные не имеют смысловой нагрузки, она появляется в результате интерпретации этих данных.

Пример.

//здесь пример таблицы из базы данных (1)










ФИО

студентов




Иванов И.И.

482




Иванов И.И.

482

Петров П.П.

482




Петров П.П.

482

Сидоров С.С.

482




Сидоров С.С.

482


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

Как мы помним, средство, позволяющее реализовывать интерпретацию данных и таким образом способствовать получению информации, называется моделью данных (МД), а совокупность данных, определенных с помощью модели данных, называется базой данных (БД). Отличительной особенностью баз данных является четкое разделение на интенсиональную часть (данные) и экстенсиональную (средства интерпретации данных). Особенностью моделей знаний (МЗ) является как бы совместное хранение интенсионала и экстенсионала базы данных, что открывает новые возможности. Модели знаний являются формальной основой для построения баз знаний. К сожалению, модели знаний в отличие от моделей данных не вписываются в какое-то одно общее формальное определение.

Примечание. Как мы помним модель данных можно формально определить, как тройку M={G, R, O}, где G – множество правил порождения структур данных (схемы), R – множество правил порождения ограничений целостности, О – множество допустимых операций над данными.

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

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

Заметим, что реляционные модели представления знаний, отличающиеся «близостью» к естественным языкам, ни в коем случае нельзя путать с реляционной моделью данных, которая изучается в курсе «Информационные системы».

Глава 2.^ ЛОГИЧЕСКИЕ МОДЕЛИ ПРЕДСТАВЛЕНИЯ ЗНАНИЙ


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

Основное внимание уделяется классическим логикам – логике высказываний (ЛВ) и логике предикатов первого порядка (ЛППП), но дается и краткий обзор неклассических логик, в частности логик высших порядков, модальных и многозначных логик.

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


^ 2.1. Логика высказываний


2.1.1. Булева алгебра.

Простейшей логической моделью представления знаний является логика высказываний (ЛВ).

Высказывание – это утверждение, значение которого может быть истинным или ложным. Данное значение называется истинностью высказывания.

В логике высказываний определено два истинностных значения:

1 – истина (true);

0 – ложь (false).

Атом – элементарное высказывание, обозначается строчной латинской буквой, например: p, q, f и т.д.

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

^ Дизъюнкцией (логическим «или», логическим сложением) называется логическая операция, которая любым двум высказываниям x, y сопоставляет единственное высказывание, истинностное значение которого определяется следующей таблицей истинности (рис ?):


x

y

xy

0

0

0

0

1

1

1

0

1

1

1

1


Рис. ? Таблица истинности для операции дизъюнкции

^ Конъюнкцией (логическим «и», логическим умножением) называется логическая операция, которая любым двум высказываниям x, y сопоставляет единственное высказывание, истинностное значение которого определяется следующей таблицей истинности:


x

y

xy

0

0

0

0

1

0

1

0

0

1

1

1


Отрицанием называется логическая операция, которая произвольному высказыванию x сопоставляет высказывание не x, истинностное значение которого определяется таблицей истинности:

x

x

0

1

1

0


Импликацией называется логическая операция, которая любым двум высказываниям x, y сопоставляет единственное высказывание, истинностное значение которого определяется следующей таблицей истинности:


x

y

xy

0

0

1

0

1

1

1

0

0

1

1

1


^ Эквивалентностью (эквиваленцией) называется логическая операция, которая любым двум высказываниям x, y сопоставляет единственное высказывание, истинностное значение которого определяется следующей таблицей истинности:


x

y

xy

0

0

1

0

1

0

1

0

0

1

1

1


Литералом или литерой называется атом или его отрицание.

Например: p, q, l

Рекуррентное определение формул:

  1. Атом – это формула

  2. Если F – формула, то F – формула

  3. Если F1, F2 - формулы, то F1F2, F1F2, F1F2, F1F2 – формулы.

Интерпретация формулы – это отображение, ставящее в соответствии истинностным значениям атомов истинностное значение формулы.

Например:

Пусть имеется формула:

(pq)l;

пусть p=0, q=0, l=0, следовательно, F=1

p=1, q=0, l=0, следовательно, F=0

Формула, истинная при всех интерпретациях, называется общезначимой. Формула, ложная при всех интерпретациях, называется противоречивой. Формулы f и q являются эквивалентными, если они истинны в одних и тех же интерпретациях.

Множество {0,1} (true, false) c определенными на нем операциями конъюнкции и дизъюнкции образует булеву алгебру:

({0,1}, , ) – Булева алгебра

Для любых формул F1, F2, F3 справедливы следующие свойства.

  1. Коммутативность

F1F2F2F1.

F1F2F2F1..

  1. Ассоциативность

(F1F2)F3F1(F2F3).

(F1F2)F3F1(F2F3).

  1. Дистрибутивность

F1(F2F3)(F1F2)(F1F3);

F1(F2F3)(F1F2)(F1F3).

  1. Законы единицы

F1F; F11;

  1. Законы нуля

F0F; F00;

  1. Закон исключённого третьего

FF1.

«закон» противоречия

FF0.

  1. Законы поглощения

F1(F1F2)F1;

F1(F1F2)F1.

  1. Законы де Моргана

(F1F2)F1F2;

(F1F2)F1F2.

  1. Правила замены

F1F2F1F2;

F1F2=(F1F2)(F2F1)(F1F2)(F2F1).

  1.  FF.

Все приведенные выше законы легко доказываются с помощью таблиц истинности.


^ 2.1.2. Понятие о логическом следствии.

Формула G называется логическим следствием формул F1,…,Fn (F1,…,FnG), если она истинна в тех же интерпретациях, где истинны формулы F1,…,Fn.

Имеют место две теоремы дедукции.

  1. Формула G является логическим следствием формул F1,…,Fn тогда и только тогда, когда формула (F1…Fn)G общезначима, т.е. F1,…,FnG  (F1…Fn)G1.

  2. Формула G является логическим следствием формул F1,…,Fn тогда и только тогда, когда формула (F1…Fn)G противоречива, т.е. F1,…,FnG  (F1 FnG0).

Говорят, что формула F представлена в конъюнктивной нормальной форме (КНФ), если она имеет вид: F=G1…Gn, где Gi является дизъюнктом (клозом), т.е. имеет вид l1…lm, где l1,…,lm – литеры.

Например, (pq)(qlf)c.

Говорят, что формула F представлена в дизъюнктивной нормальной форме (ДНФ), если она имеет вид: F=G1…Gn, где Gi является конъюнктом (кьюпом), т.е. имеет вид l1…lm, где l1,…,lm – литеры.

Доказано, что любая формула в логике высказываний может представляться как в КНФ, так и в ДНФ.

Множество клозов G1,…,Gn называется противоречивым, если противоречива их конъюнкция.

Пусть, поставлена задача доказать, что F1,…,Fn G. Если формулы F1,…,Fn и формула G представлены в КНФ, то доказательство с использованием второй теоремы дедукции (доказательство противоречивости формулы F1…FnG) сводится к задаче доказательства противоречивости множество клозов. Для этого удобно использовать метод резолюции. Остановимся на нём подробнее.


^ 2.1.3. Метод резолюции в ЛВ.

Пусть C1 и C2 – клозы. Клоз C1C2 называется бинарной резольвентой (или просто резольвентой) клозов C1 p, C1p.

Например, pql plf

qf

Литеры p, p при этом называются контрарными.

Доказано, что резольвента является логическим следствием.

Замечание. Клоз можно рассматривать как множество литер. Так клоз plf фактически есть множество литер {p,l, f}. Таким образом, мы приходим к понятию пустого клоза ( ).

Метод резолюции сводится к последовательному получению резольвент, каждая из которых является логическим следствием. Из данного множества клозов (так называемого входного множества) пытаются вывести пустой клоз. Этот процесс называется резолютивным выводом пустого клоза или опровержением множества клозов.

Например:

Дано: pq

q f

Доказать: pf

Доказательство: 1) Приводим все формулы к КНФ: pq, qf

( pf)= (pf)=pf

2) Производим резолюцию:




pq

pf

f











qf

p

f




p

f







f






Имеет место теорема о полноте резолютивного вывода. Множество клозов противоречиво тогда и только тогда, когда из него методом резолюции можно вывести пустой клоз.


Приведем формальный алгоритм, который проверяет, является ли формула G логическим следствием некоторых других формул.

ВХОД: S – входное множество клозов.

ВЫХОД: OK – удается получить пустой клоз, NO – не удается.

M:=S; // - M-текущее множество клозов.

while M do

if not Choose (M, C1, C2, p1, p2) then return(NO);

C:=R(M, C1, C2, p1, p2); // - вычисление резольвенты.

M:=M  {c}; // - пополнение текущего множества.

end

return (OK); //получен пустой клоз

Примечание.

1: Функция R вычисляет резольвенту двух клозов С1 и С2, содержащих контрарные литеры р1 и р2. Результатом работы функции является резольвента.

2. Процедура Choose выбирает в текущем множестве клозов М два резольвируемых клоза, то есть два клоза, которые содержат унифицируемые контрарные литеры. Если таковые есть, то процедура их возвращает, в противном случае возвращается пустое множество. Конкретные реализации процедуры Choose называются стратегиями метода резолюции.

Очевидно, что данный алгоритм может «зависнуть». Например, такое произойдет, если для резолюции постоянно выбирается одна и та же пара клозов. Поэтому стратегия резолюции должна гарантировать конечность алгоритма.

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


^ 2.2. Логика предикатов первого порядка


2.2.1. Основные определения.

Как показывает практика, возможностей логики высказываний явно недостаточно для представления знаний. Напомним основные понятия более сложной логики предикатов первого порядка (ЛППП).

Предикат – это логическая функция одного или нескольких переменных. Результатом этой функции является 1 – истина или 0 – ложь.

Примеры. СТУДЕНТ (Вася), ПРОЖИВАНИЕ (x, Томск).

Терм – это константа, переменная или некоторая n-местная функция (функтор f(x1,…,xn))

Примеры. а , x, f(x, y).

Если P – n-местный предикат и t1…tn – термы, то P(t1,…,tn) – атом.

Примеры. P(x), P(x,y), P(a, x), P(x, y, f(x, y)).

В формулах используются логические связки (операции):, , , ,  и кванторы:, .

Рекуррентное определение формулы:

  1. Атом – есть формула

  2. Если F – формула, то F – формула.

  3. Если F, G – формулы, то FG, FG, FG, FG – формулы.

  4. Если F – формула, в которой есть переменная x, то x F(x), x F(x) – формулы (при этом переменная x называется связанной квантором всеобщности или существования).

  5. Все переменные в формуле связаны кванторами.

Пример. Формализуем утверждение: «для любого натурального числа существует единственное натуральное число, непосредственно следующее за ним».

Введем предикаты E(x, y) – x=y, N(x) – x – натуральное число и функтор f(x) – следующее число (x+1).

x [N(x)y [E(f(x), y)z [E(f(x), z)E(y, z)]]].

Интерпретация формул производится следующим образом:

А) Считаем, что для каждой формулы определено множество объектов, о которых может идти речь, это множество называется областью определения формулы (обозначается D).

  1. Каждой константе ставим в соответствие один элемент из D.

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

  3. Определяем истинностное значение каждого предиката.

  4. Устанавливаем истинностное значение формулы по таблицам истинности (это можно сделать только в случае, если все переменные в формуле связаны кванторами – иначе, формула бессмысленна)

Пример.

//пример на интерпретацию (1)

x [P(x)→Q(x,f(x))]

A) D = {1, 2} – область определения

B) Константы отсутствуют

С) f (1) = 2 f (2) = 1

D) P (1) = 1 P (2) = 0

Q (1, 1) = 1 Q (1, 2) = 0 Q (2, 1) = 0 Q (2, 2) = 1

E) Вычисляем значение матрицы

x = 1

P (x) → Q (x, f (x)) = P (1) → Q (1, f(1)) = P(1) → Q (1, 2) =1 → 0 = 0

Таким образом:

x [P(x) → Q (x, f(x))] = 0 в данной интерпретации.

В этой же интерпретации формула

x [P(x) → Q (x, f(x))] = 1,

т.к.

при x = 2

P(x) → Q (x, f(x) = P(2) → Q (2, f (2)) = 0 → 0 = 1


Определения общезначимости, противоречивости и логического следствия точно соответствуют аналогичным понятиям в логике высказываний. Имеют место те же теоремы дедукции. Справедливыми остаются и эквивалентные преобразования.

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

А) Избавляются от операций ,  с помощью соответствующих правил (см. 2.1.1).

B) Добиваются, чтобы  стояло только перед атомом (используем законы Де Моргана см. 2.1.1)

С) Переносят кванторы в начало формулы, чтобы она имела вид:

//формула (2)

1 x1 2 x2 ….. n x n M [x1, … , xn]

В этом случае говорят, что формула представлена в ПНФ (предваренной норм форме). M[x1,…,xn] называется матрицей формулы.

Используются следующие эквивалентные преобразования:

//формулы (3)

x F(x) G = x [F(x) G]

в случае, если G не содержит переменную x:

1 x F (x) 2x G(x) = 1 x 2 y [F1(x) G2(y)],

т.е. в случае необходимости производим замену переменных.

В двух частных случаях можно избежать переименования переменной:

//формулы (4)

x F (x)  x G(x) = x [F(x)  G(x)]

 x F(x)   x G (x) =  x [F(x)  G(x)]

D) Добиваются, чтобы матрица была представлена в КНФ.

E) Избавляются от  путем замены связанных им переменных на константы.

//формула (5)

F = x1 xi-1  xi xi+1 xn M [x1 …, xi-1, xi ; xi+1; xn]

G = x1 xi-1 xi+1 xn M [x1, …, xi-1, a, xi+1, … xn],

где :

а – некоторая константа.

Таким образом, заменяем переменные под  на константы.

Это преобразование не является эквивалентным, однако оно сохраняет противоречивость, т.е. F- противоречива, тогда и только тогда, когда противоречива G. Этого достаточно, если мы пользуемся 2-й теоремой дедукции.


^ 2.2.2. Метод резолюции в ЛППП.

Литеры L1 и L2 называются контрарными, если они являются отрицанием друг друга c точностью до унификации (то есть одна из литер изначально является отрицанием другой или ее можно таковой сделать с помощью подстановки).

Примечание. Формальное определение подстановки будет приведено ниже.

Бинарной резольвентой клозов С1 и С2, содержащих контрарные литеры L1 и L2 назовается клоз C, полученный следующим образом:

С={C1\L1}{C2\L2}

Примечание. Очевидно, что данное определение аналогично соответствующему определению в логике высказываний.

Примеры.

//примеры - без подстановки и с подстановкой (6)

P (x)  Q (x, y)

P(x)  R(z)

Q(x, y)  R (z)

P (x)  Q (x, y)

P(a)  R (z)

{a/x}

Q(a, y) R (z)


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

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

Множество вида /подстановка (7)/ {ti/xi, … tn/xn}, где ti – термы, а xi – переменные называется подстановкой термов ti вместо переменных xi.

Если E – клоз, а Θ – подстановка, то EΘ – подстановочный частный случай, получаемый вследствие замены переменных xi на термы ti.

Пример.

//пример (8)

P (x)  Q (f (x), b, y)

{a/x, c/y}

P (a)  Q (f (a), b, c)

Примечание. Подстановка действительно приводит к переходу от более общего случая к частному и таким образом обеспечивает сохранение противоречивости.

Пусть даны 2 подстановки Θ и Ω. Применим подстановку Θ, а затем подстановку Ω. Тогда будем говорить, что применили композицию подстановок ΩΘ.

Подстановка Θ называется унификатором множества выражений {E1,..,En}, если E1Θ =E2Θ =….=EnΘ.

Подстановка Ω - есть наиболее общий унификатор множества выражений {E1,…,Ek}, если любой унификатор это множества выражений Θ можно получить путем композиции Ω с некоторой подстановкой Ψ. (Θ= ΩΨ).

П. С – дизъюнкт, а Θ - наиболее общий унификатор двух и более его литер, тогда СΘ называется склейкой дизъюнкта С.

Пример.

//пример склейки (9)

P (x)  Q (f(x), b, y)  P (a)

{a/x)

P (a)  Q (f(x), b, y)

Резольвентами дизъюнктов С1 и С2, содержащих контрарные литеры L1 и L2 называются бинарные резольвенты:

  1. клозов С1 и С2;

  2. любой склейки клоза C1 и клоза С2;

  3. клоза С1 и любой склейки клоза С2;

  4. любых склеек клоза С1 и С2

Последовательность получения резольвент из множества клозов, в результате которой получают пустой клоз, называется резолютивным выводом в ЛППП.

Примечание. Фактически, вывод сводится к последовательности вычисления бинарных резольвент и склеек.

Пример.

Аксиома 1. Мао Цзедун – человек

Аксиома 2. Все люди смертны.

Теорема. Мао Цзедун – смертен.

//пример формализации и вывода (10)

Вводим предикаты:

C (x) – x - человек

S (x) – x - смертен

Аксиома 1 C (Мао)

Аксиома 2 [C (x) → S (x)] =

Теорема S (Мао)


С (Мао) S (Мао)

С (x)  S (x) {Мао / x}

S (Мао)  S (Мао)


Здесь также справедлива теорема о полноте резолютивного вывода. Множество клозов S противоречиво, если и только если существует резолютивный вывод пустого клоза из S.

Очевидно, что для того чтобы проверить противоречиво ли множество клозов, следует перебрать множество попыток провести резолюции. Таким образом, строится дерево резолюций. Способ построения такого дерева фактически является стратегией проведения резолюции.

Формальный алгоритм незначительно отличается от имеющегося в ЛВ.

ВХОД: S – входное множество клозов.

ВЫХОД: OK – удается получить пустой клоз, NO – не удается.

M:=S; // - M-текущее множество клозов.

while M do

if not Choose (M, C1, C2, p1, p2) then return(NO);

N:=R(M, C1, C2, p1, p2); // - вычисление резольвенты.

M:=M  N; // - пополнение текущего множества.

end

return (OK); //получен пустой клоз

Примечание. Результат функции R здесь множество возможных резольвент клозов С1 и С2, содержащих контрарные литеры р1 и р2.


^ 2.2.3. Стратегии проведения резолюции.

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

Рассмотрим самые распространенные стратегии.

  1. Полный перебор. Проверяются все возможные варианты поиска резольвент на каждом шаге. Недостаток этой стратегии заключается в том, что очень высока трудоёмкость соответствующего алгоритма. Основное достоинство – полнота.

  2. Линейные резолюции. Линейным называется вывод, удовлетворяющий следующей схеме (рис ?):




Рис ? Схема линейной резолюции

//cхему подправить (11)


где Сi - центральные клозы, Вj - боковые. Боковой клоз всегда выбирается либо из входного множества (S), либо среди клозов, полученных на предыдущих шагах. Клоз C называется верхним в выводе. Под входным понимается само начальное множество опровергаемых клозов.

//тут формальное условие на Bj (12)

Bj S или Bj = Ci ,

где: i < j


Недостаток этой стратегии в том, что она не полна.

  1. Входная резолюция.

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

//формальное условие (13)

B; S

  1. Стратегия OL-вывода (Ordered Lined).

  2. Вывод на клозах Хорна (реализован в Прологе).

Примечание. Последние две стратегии будут рассмотрены подробнее, как наиболее часто применяющиеся на практике.


^ 2.2.4. Упорядоченный линейный вывод в ЛППП.

Будем считать, что литеры в клозе упорядочены. Для того чтобы сохранять информацию об отрезанных литерах, они не удаляются, а только обрамляются. Если на каком-то шаге получается клоз, содержащий две одинаковые литеры, то оставляется самая левая из них, после чего отбрасываются все обрамлённые литеры, за которыми не следуют необрамлённые. Эта операция называется отождествлением влево. Если в упорядоченном клозе последняя литера унифицируется с отрицанием одной из обрамлённых литер, то клоз называется редуцируемым и производится его редукция, то есть:

1) удаляется последнюю литеру и обрамленную литеру, с отрицанием которой унифицируется последняя литера;

2) отбросываются все обрамлённые литеры, за которыми не следуют необрамлённые.

Например, pqsq

pqsq

p

//Пример переделать под ЛППП (14)

P (x)  Q (x, f (x))  S (y)   Q (x, f (b))

{b/x}

P (b)  Q (b, f(b))  S (y)   Q (b, f ))

P (b)

Упорядоченной бинарной резольвентой (упорядоченной резольвентой) клозов C1 и C2, содержащих контрарные литеры L1 и L2 (причем L1 – последняя литера в клозе C) называется клоз C вида C={C1}{C2L2}, где C1 получен из С1 путём обрамления последней литеры.

Например, pq

qr

pqr

//пример переделать под ЛППП (15)

{b/x} P (x)  Q (x, f (a))

Q (b, a)  R (z)

P (b)  Q (b, f (a))  R (z)

Упорядоченным линейным выdодом (OL-выводом) пустого клоза из S (OL-опровержением множества S) называется вывод, удовлетворяющий следующим условиям:

  1. отрезаемая литера всегда последняя;

  2. вывод имеет следующий вид:




//cхему подправить (12 – аналогично)


где Сi - центральные клозы, Вj - боковые. Боковой клоз всегда выбирается либо из входного множества, либо среди клозов, полученных на предыдущих шагах. Клоз C называется верхним в выводе.

OL-вывод является так называемой почти полной стратегией.

^ Теорема о полноте OL-вывода. Если множество клозов S противоречиво, а множество {S/C} - выполнимо, где CS, то существует OL-вывод пустого клоза из S с верхним дизъюнктом C.

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


^ 2.2.5.Применение поиска в пространстве состояний при реализации автоматизированного логического вывода.

Пусть дан простой ориентированный граф G=(V,E), и пусть существует некоторая вершина S, не имеющая предков (в эту вершину не входит ни одна дуга). Эта вершина называется начальным состоянием. Все остальные вершины имеют хотя бы одного предка. Также существует Term – подмножество терминальных вершин (состояний). Такой граф называется или пространством состояний или пространством решений, его вершины называются состояниями, а его дуги – правилами.

Пространство состояний используется при решении многих прикладных задач, и в частности, при автоматизированном OL – опровержении множества клозов. В этом случае вершинам будут соответствовать пары клозов (Ci,Bj), где Cj - центральные клозы, Bj – боковые клозы.

^ Раскрытием вершины или состояния называется определение исходящих из неё дуг.

В случае построения пространства состояний для задачи OL-опровержения вершины раскрываются следующим образом:

  1. На (Ci,Bj) строится множество резольвент R.

  2. Производится отождествление влево во всех клозах из R, где это возможно.

  3. Заменяем все редуцируемые клозы в R на их редукции.

  4. Определяем всевозможные боковые клозы для всех клозов из R.

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

Приведем для простоты пример из логики высказываний.




Скачать 2.32 Mb.
оставить комментарий
страница1/7
Дата29.09.2011
Размер2.32 Mb.
ТипРеферат, Образовательные материалы
Добавить документ в свой блог или на сайт

страницы:   1   2   3   4   5   6   7
хорошо
  2
отлично
  1
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх