Игошин Математическая логика и теория алгоритмов (1019110), страница 104
Текст из файла (страница 104)
Ясно, что от формы записи запроса зависит скорость вычисления ответа, и поэтому далеко не безразлично, какую запись запроса выбрать. Две формулы называют равносильными, если в любых состояниях и в любых системах данных этим формулам отвечает один и тот же результат вычислений (ответ).
Другими словами, равносильные формулы — это формулы, имеющие одинаковое семантическое содержание. Тогда под запросом можно понимать не одну формулу, а весь класс равносильных ей формул. Правда, здесь возникают трулности, связанные с необходимостью уточнить понятие состояния и с необходимостью предвидеть все возможные состояния базы данных. Эти трудности преодолеваются с помощью математической логики. В математической логике имеется еще один (синтаксический) подход к определению той же равносильности формул, не требующий обращения к состояниям (к семантике). Он основан на подходящем формализованном исчислении. В каждом таком исчислении, как мы знаем, имеется понятие формулы, некоторые формулы объявляются аксиомами исчисления и указываются правила вывода.
Две формулы Ри 6объявляются эквивалентными, если формула Г <-«6 (или (à — > 6) н н (6 -» Г), или (- Г ч 6) н (Г ~ — 6)) выводима из аксиом (т.е. является теоремой исчисления). Доказывается метатеорема адек- 418 ватности исчисления: две формулы равносильны в семантическом смысле тогда и только тогда, когда они эквивалентны в указанном сейчас синтаксическом смысле. Имеется и еще одно применение аксиоматического подхода в теории баз данных. В схему базы данных, как правило, включается определенный набор аксиом, которым должны удовлетворять состояния. В общем случае система аксиом базы данных — это некоторый набор формул в языке первой ступени, связанном с данной базой. Аксиомы выделяют определенный набор состояний и вносят определенное содержание в набор Ф, в общем, бессодержательных символов отношений.
В базах данных эти ограничения называют еше ограничениями целостности. В различных конкретных ситуациях они возникают естественным образом. Например, в рассмотренном выше примере базы данных студенческой группы добавим еще один одноместный предикат 9(х), означающий, что студент х получает стипендию. Тогда можем ввести аксиому: (Лз)(ф,(х, з),~ фз(х, з)) -+ -~Цх). Эта аксиома означает, что во всех рассматриваемых состояниях наличие «двойки» или «тройки» хотя бы по одному предмету лишает студента права на стипендию. 9 42. Математическая логика и системы искусственного интеллекта Коротко можно сказать, что под искусственным интеллектом понимается раздел информатики, изучающий методы, способы и приемы моделирования и воспроизведения с помощью компьютера разумной деятельности человека, связанной с решением задач. По су1цеству, всякая задача, для которой неизвестен алгоритм решения, может быть отнесена к искусственному интеллекту.
Основными проблемами в области искусственного интеллекта являются поиск и представление знаний. Цель исследований при этом состоит не только в разработке новых теоретических построений, но и в создании для компьютеров соответствующих программ наиболее общего характера. Использование компьютеров в качестве материальной основы искусственного интеллекта позволяет как бы изнутри взглянуть на мыслительные процессы, протекающие в человеческом мозгу. Проблематика искусственного интеллекта имеет тесные взаимосвязи с лингвистикой, психологией и логикой, которые изучают явления, относящиеся к познанию, пониманию и умозаключениям. Эти связи носят взаимный характер: с одной стороны лингвисты, психологи, специалисты в области математической логики переводят в компьютерные программы те новые модели, 419 которые они разрабатывают, а с другой — исследователи в области искусственного интеллекта изучают эти модели и пытаются воссоздать на их основе логику эффективных методов решения задач.
Впервые после фундаментального пересмотра картины мира, связанного с именами Коперника и Дарвина, разработка методов искусственного интеллекта возвращает нас к вопросу о месте человека в природе. По существу, впервые оспаривается исключительность человеческого разума. Основными разделами искусственного интеллекта являются теория представления знаний, теория обработки информации, выраженной на естественном языке, теория восприятия и распознания образов, автоматическое доказательство математических теорем, моделирование игр, робототехника, теория и создание экспертных систем. Как и раньше, в этом параграфе мы кратко акцентируем внимание на роли математической логики в теориях, связанных с искусственным интеллектом.
История развития и предмет искусственного интеллекта как науки. Искусственный интеллект как наука насчитывает уже около полувека. Это одна из тех научных дисциплин, становление и бурное развитие которых напрямую связаны с созданием и динамичным совершенствованием вычислительных машин. Начало исследований в области искусственного интеллекта связывают с работами А. Ньюэлла, Г. Саймона, Дж.
Шоу, которые в 1950-х гг. исследовали процессы решения различных задач. Первой программой искусственного интеллекта стала созданная ими программа «Логик- теоретик» (о ней говорилось в начале 542), предназначенная для доказательства теорем в формализованном исчислении высказываний и работа которой была впервые продемонстрирована 9 августа 1956 г.
В 1957 г. была создана первая программа для игры в шахматы ХВВ (Мев е11, Язав, Ятоп). Эти программы и созданная позже программа «Универсальный решатель задач» были основаны на так называемом эвристическом методе. (Эвристика — это правило, которое позволяет сделать выбор при отсутствии точных теоретических оснований. Эвристика — своего рода антипод алгоритма.) Эти работы положили начало первому этапу исследований в области искусственного интеллекта, когда эвристический метод решения задачи рассматривается как свойственный человеческому мышлению вообще, для которого характерно возникновение «догадок» о пути решения задачи с последующей их проверкой.
Это был путь составления программ, моделирующих мышление. Этот подход, кстати, и обусловил появление и дальнейшее распространение термина «искусственный интеллект». (Отметим из этой области программу, созданную в 1960 г. Дж. Гелернтером, которая доказывала теоремы из школьного курса геометрии лучше, чем ее создатель.) В конце 1950-х гг. появились также работы в области искусственного интеллекта, которые в противоположность ранним рабо- 420 там Ньюэлла и Саймона, больше относились к формальным математическим представлениям, нежели к эвристическим.
Способы решения задач в этих исследованиях развивались на основе методов математической логики. Моделированию же человеческого мышления придавалось второстепенное значение. Мощный толчок в развитии этого направления оказала разработка в 1960-е гг. Робинсоном метода резолюций для доказательства' теорем в логике предикатов и являющегося, по крайней мере теоретически, исчерпывающим методом доказательства (см. э' 39). Методологическое значение этих работ заключалось в том, что основное внимание в исследованиях по искусственному интеллекту переместилось с разработки методов воспроизведения в компьютере человеческого мышления на разработку машинно-ориентированных методов решения задач, т.е. на разработку программ, способных решать «человеческие задачи».
Исследовательским полигоном для развития методов искусственного интеллекта на первом этапе являлись всевозможные игры, головоломки, математические задачи (задача об обезьянах и бананах, милиционерах и людоедах, Ханойской башне, игра в 15 и др.). В конце 1960-х гг.
стали делаться первые попытки применения разработанных методов для решения задач не в искусственных, а в реальных проблемных средах. Они натолкнулись на большие трудности, связанные прежде всего с проблемами описания знаний о внешнем мире, организации их хранения и достаточно эффективного поиска, введения в память ЭВМ новых знаний и устранения устаревших (в том числе автоматического их извлечения из среды), проверки полноты и непротиворечивости знаний и т.п. Эти проблемы привели к постановке задачи создания интегральных роботов, т.е. таких устройств, которые реализовали бы целый спектр «интеллектуальных» функций, таких, как восприятие информации о внешней среде, целенаправленное поведение, формирование действий, обучение, общение с человеком и другими роботами.
Для формирования целенаправленного поведения интегральный робот должен прежде всего обладать необходимым комплексом знаний о реальном мире, в котором он функционирует. Эти знания должны быть заложены в робот в виде модели внешнего мира или, точнее, модели проблемной среды, т.е. той части внешнего мира, которая существенна для решения задач, ставящихся перед роботом. Модель проблемной среды — это совокупность взаимосвязанных сведений, необходимых и достаточных для решения соответствующего класса задач.
В систему знаний робота должны быть заложены и алгоритмы, позволяющие воспроизводить «мысленные» преобразования среды и строить на этой основе план решения очередной задачи. Проведение работ, связанных с созданием интегральных роботов, можно считать вторым этапом исследований по искусственному интеллекту. 421 С середины !970-х гг. начался третий этап исследований систем искусственного интеллекта. Его характерной чертой явилось смещение центра внимания исследователей с создания автономно функционирующих систем, самостоятельно (или в условиях ограниченного общения с человеком) решающих в реальной среде поставленные перед ними задачи, к созданию человекомашинных систем, соединяющих в единое целое интеллект человека и способности вычислительных машин для достижения общей цели — решения задачи, поставленной перед интегральной человекомашинной решающей системой.
На первый план выдвинулась не разработка отдельных методов машинного решения задач, а разработка методов и средств, обеспечивающих тесное взаимодействие человека и вычислительной системы в течение всего процесса решения задачи с возможностью оперативного внесения человеком изменений в ходе этого процесса. Представление знаний в системах искусственного интеллекта. Теория представления знаний — фундаментальнейший раздел искусственного интеллекта. Ее назначение — найти такие способы описания и представления фактов, общих сведений, закономерностей, правил и предписаний об окружающем мире, которые позволят использовать все эти знания с помощью некоторых универсальных и формальных процедур анализа, рассуждения и синтеза, доступных для программной реализации на ЭВМ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
