Лекции по информатики 2 (стр. 14 из 43)
Применение к отрицанию не родитель (Надя, х) и определению родитель (х, у) ¬ мама(х, у) рассматриваемой процедуры приводит к выводу утверждения не мама (Надя, х), означающему «Надя не является мамой никому». Для этого отрицания машина найдет два конкретных противоречащих ему факта мама (Надя, Оля) и мама (Надя, Сережа). Используя конструктивную процедуру вывода ответов из отрицаний, компьютер даст два конкретных ответа - х = Оля и х = Сережа.
Закон тождества - четвертый общий логический закон, указанный Аристотелем:
«Предмет рассмотрения должен быть определен
и не должен меняться до конца обсуждения»
Данный закон носит фундаментальный характер для работы экспертных систем - правильные выводы и решения могут быть получены от экспертных систем только при строгом совпадении определений вещей из рассматриваемой предметной области.
Расхождения в понимании и определении предметных понятий могут приводить и, как правило, приводят к логическим ошибкам и получению неправильных выводов и результатов, что наблюдается среди людей, не обладающих необходимыми профессиональными знаниями.
Примером нарушения закона тождества является подмена предмета, когда два собеседника осознанно или неосознанно говорят о разных вещах, что приводит их к непониманию, спорам и разногласиям. Классический пример нарушения - ситуация: «я - про Фому, а он - про Ерему».
В системе Пролог и в системах искусственного интеллекта вывод ответов на сложные вопросы основан на принципе унификации (взаимосогласования) ответов. По этой причине экспертные системы на ЭВМ в отличии от людей могут производить вывод ответов на сложные вопросы только в соответствии с принципом унификации.
Принцип унификации ответов состоит в том, что общие переменные во взаимосвязанных вопросах должны получать одинаковые значения. Пример ответа на сложносоставной вопрос, состоящий из двух подвопросов:
? мама (z, у), мама(у, Оля) - Кто мама у мамы Оли?
z = Зина
у = Надя
Вывод ответов на сложносоставные вопросы состоит в выделении подвопросов и поиске на них ответов по частям:
? мама (z, у), мама (у, Оля)
¤ \
? мама (z,у) ?мама(у, Оля)
¤ \ ¤
z = Зина у = Надя
В данном примере общим элементом в выделяемых подвопросах ? мама (z, у) и ? мама (у, Оля) является переменная «у». Ответом на первый подвопрос ? мама (z, у) будут значения z = Зина и у = Надя. Ответы на второй подвопрос ? мама (у, Оля) в соответствии с принципом взаимосогласования будет проводиться для значения у = Надя.
Принцип вывода взаимосогласованных ответов в системе Пролог распространяется и на сложносоставные правила, включаемые в базы знаний и процедуры логического вывода. Приведем примеры сложных определений:
бабушка (z, х) ¬ мама(z, у), мама(у, х);
бабушка (z, х) ¬ мама (z,у), папа(у, х);
дедушка (z, х) ¬ папа (z, у), мама (у, х);
дедушка (z, х) ¬ папа (z, у), папа (у, х);
При наличии этих правил в памяти ЭВМ можно получить следующие вопросы о бабушках и дедушках:
? бабушка (z, Оля) - Кто бабушка у Оли?
z = Зина
? дедушка (z, Надя) - Кто дедушка у Нади?
нет
Принцип унификации в системе и языке Пролог является общим механизмом логического вывода ответов на сложные вопросы в базах знаний на Прологе и тем самым - конструктивной реализацией закона тождества для машинных систем искусственного интеллекта. Таким образом работа экспертных систем на ЭВМ основана строго на выполнении требований законов логики - закона тождества и закона достаточных оснований.
В о п р о с ы
1. В чем состоит закон противоречия?
2. В чем заключается закон исключения третьего?
3. Как используется закон вывода следствий?
4. Как используется закон отрицания следствий?
5. В чем недостатки закона двойного отрицания?
6. В чем состоит закон достаточных оснований?
7. В чем заключается закон тождества?
8. В чем состоит принцип унификации?
9. Как согласуются ответы на сложные вопросы?
3 а д а н и я
1. Укажите примеры двойного отрицания для утверждений:
а) «сегодня был дождь»; в) «х = 2» и «х = 3»;
б) «х = 0» или «у = 0»; г) «5 не делится на 2 и на 3».
2. Пусть утверждение А «прошел дождь», а утверждение В «на улице сыро». Истинны ли следующие суждения?
а) А Þ В (прямое доказательство);
б) В Þ А (обратное доказательство);
в) не А Þне В (противоположное доказательство);
г) не ВÞ не А (противоположное обратному).
3. Предложите систему признаков и понятий для описаний
а) класса «Млекопитающие»; в) класса «Рыбы»;
б) класса «Птицы»; г) класса «Насекомые».
В систему понятий введите следующие признаки: окрас, продолжительность жизни, умения ползать, летать, ходить и т. д.
4. Составьте базу знаний по всемирной географии. В базу знаний включите сведения о странах: название столицы, число жителей, тип государства, размеры страны, континент.
5. Составьте базу знаний по городам своей страны. В базу знаний включите сведения о размерах городов, числе жителей, расстоянии от столицы, названии самых крупных заводов, фабрик, музеев, стадионов и т. п.
6. Составьте базы данных
а) по литературе; г) по истории;
б) по зоологии; д) по ботанике;
в) об автомобилях; е) по кулинарии.
Глава 4. ОСНОВЫ АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ
4.1. Основные свойства алгоритмов
Алгоритм относится к фундаментальным понятиям информатики. На понятии алгоритма построено все основные принципы программирования - составления программ для вычислительных машин.
Алгоритм - это совокупность действий со строго определенными правилами выполнения. В информатике изучаются различного рода алгоритмы - диалоговые алгоритмы, алгоритмы обработки данных, вычислительные алгоритмы, алгоритмы управления роботами, станками и другими техническими устройствами.
Пример диалогового алгоритма:
Алгоритм Блок-схема
алг «приветствие»¯
нач запрос («Ваше имя=», NN)запрос («Ваше имя=», NN) ¯
вывод («Добрый день», NN) вывод («Добрый день», NN) кон¯
Для описания алгоритмов используются блок-схемы, изображенные справа, или структурированная запись, приведенная слева. Блок-схемы наглядны. Однако блок-схемы трудно рисовать, в них сложно вносить изменения и исправления из-за сложности перерисовки рамок и стрелок. Однако блок-схемы до сих пор требуются отечественными стандартами на документирование программ.
Достоинство записи алгоритмов и программ в структурированной форме заключается в простоте их чтения и ввода с экрана ЭВМ, а также в простоте внесения изменений и исправлений с использованием даже самых простейших редакторов тестов. По этим причинам зарубежом блок-схемы уже давно не используются ни для документирования, ни для обучения, а все современные языки построены на принципах структурного программирования.
Приведем примеры описания алгоритма и программы в структурированной записи:
АлгоритмПрограмма
алг «приветствие» ' приветствие
нач сls
запрос («Ваше имя=», NN) input «Ваше имя=», NN$
вывод («Добрый день», NN) print «Добрый день», NN$
кон end
Алгоритм, приведенный слева, записан на псевдокоде. Псевдокод - это язык записи структурированных алгоритмов в качестве документации к программам для ЭВМ. Особенность псевдокода заключается в том, что описания на нем выполняются на родном языке — русском, английском, украинском, казахском, немецком и т. п.
Программа, приведенная справа, записана на языке Бейсик - языке программирования персональных ЭВМ. Языками программирования называются формализованные языки, используемые для записи программ на ЭВМ. Одним из них является язык Бейсик.
Достоинства псевдокода заключаются в том, что описания алгоритмов, записанные на родном языке, намного проще читать и понимать, чем запись программ на языке с иностранной лексикой. По этим причинам псевдокод используется как основное средство документирования программ во всех ведущих фирмах, занимающихся разработкой программ.
С точки зрения информатики алгоритмы, записанные в такой обобщенной записи, позволяют выразить общую логику работы программ, независимо от используемых языков программирования и типов ЭВМ. При этом алгоритмы, записанные в такой обобщенной форме, могут быть реализованы с помощью различных языков программирования для самых различных типов ЭВМ.
В качестве примера приведем реализацию этого же диалогового алгоритма на самой ранней версии языка Бейсик, использовавшегося на самых первых персональных компьютерах:
АлгоритмПрограмма
алг «приветствие» 10 ' приветствие
нач 20 сls
запрос («Ваше имя=», NN) 30 input «Ваше имя=», NN$
вывод («Добрый день», NN) 40 print «Добрый день», NNS
кон 50 end
Основные свойства алгоритмов и программ для вычислительных машин - однозначность, результативность, правильность и массовость. Этими свойствами алгоритмы отличаются от различного рода расплывчатых и неоднозначных предписаний, инструкций и кулинарных рецептов, которые могут толковаться и исполняться многими способами.