Пример. Создание экспертной системы строительства дома на участке.
Такого рода экспертная система легко разбивается на ряд подсистем: организация
садового участка, кухни, гаража, спальни, комнат общего пользования и интегри
рующей системы знаний.
Все включенные экспертные системы могут разрабатываться независимо друг
от друга, иметь независимые базы знаний и модули представления знаний при
наличии однотипного интерфейса с интегрирующей системой.
Кроме методологии общего планшета при разработке систем, основанных на знаниях, применяются следующие методологии:
□ Метод решения проблем основывается на накоплении и создании библиотеки последовательности действий, необходимых для решения проблемы, и набора знаний, позволяющего эти действия совершить. Достоинство метода — возмож
ность многократного использования. Недостаток — необходимость создания библиотеки знаний и методов.
□ Методология моделирования получения знаний сочетает в себе черты методоло
гии архитектуры планшета (деление проблемы на составные части) и метода решения проблем (накопления методов и знаний).
Вопросы для самопроверки
1. Как вы понимаете термин «управление знаниями»?
2. Какие процессы включаются в управление знаниями?
3. Из каких этапов состоит жизненный цикл управления знаниями?
4. Чем отличаются друг от друга понятия «данные», «информация» и «знания»?
5. Как развивались информационные системы?
6. Какие способы классификации знаний вы знаете?
7. Какие модели представления знаний вам известны?
8. Приведите пример продукционной модели представления знаний.
9. Дайте определение семантической сети.
10. Что такое «фрейм»? Что такое «слот»?
11. Перечислите признаки интеллектуального поведения.
12. Какие типы систем, основанных на знаниях, вам известны?
13. Дайте определение экспертной системы.
14. Из каких основных элементов состоит экспертная система?
15. Каковы достоинства и недостатки экспертных систем?
Литература
107 16. В чем суть методологии построения баз данных?
17. Что такое «искусственная нейронная сеть»?
18. Перечислите характеристики нейронной сети?
19. Какие типы нейронных сетей вам известны?
20. Каков алгоритм работы системы, основанной на прецедентах?
21. В каком виде знание представлено в искусственной нейронной сети? В экс
пертной системе? В системе, основанной на прецедентах?
22. Что такое «генетический алгоритм» и для чего он применяется?
23. Что такое интеллектуальный агент?
24. Что может быть источниками данных в процессе добычи данных?
25. На основе каких функций производится добыча данных?
26. В чем различие инженерии знаний и управления знаниями?
27. Что такое «получение знаний»? Какую роль этот процесс играет в инженерии знаний?
28. Перечислите четыре основных типа интервью.
29. Почему стандартная методология разработки информационных систем часто не подходит для инженерии знаний?
30. Какие специфические методологии применяются в инженерии знаний?
Литература
1. Башмаков А. И., Башмаков И. А. Интеллектуальные информационные техноло
гии. М.: Издательство МГТУ им. Баумана, 2005.
2. Гаврилова Т. А , Хорошевский В. Ф. Базы знаний интеллектуальных систем. СПб.:
Питер, 2000.
3. Джанетто Карен, Уилер Энн. Управление знаниями. М.: Добрая книга, 2005.
4. Емельянова Н. 3, Партыка Т. JI., Попов И. И. Основы построения автоматизиро
ванных информационных систем. М.: Ф ОРУМ -ИФРА-М , 2007.
Г лава 4
Логические основы информатики
4.1. Представление о высказываниях и логических операциях
4.2. Алгебра логики
4.3. Построение коммутационных схем на основе алгебры логики
Алгебра логики (алгебра высказываний) и основы математической логики игра
ют важную роль в информатике. Математическая логика присутствует в различ
ных разделах информатики: в виде двоичной логики, на
которой основана работа цифровых компьютеров; в виде специальной алгебры логики, лежащей в основе математической модели реляционных баз данных; в виде правил, определяющих функционирование алгоритмов и программ, работу интеллектуальных и эксперт
ных систем. Таким образом, логика для информатики является фундаментальным предметом, изучение которого дает ключ к множеству других разделов.
4.1. Представление о высказываниях и логических операциях
4.1.1. Понятие высказывания
Основным понятием математической логики является понятие простого вы
сказывания.
4.1. Представление о высказываниях и логических операциях
109
В алгебре логики все высказывания рассматриваются только с точки зрения их логического значения. Каждое высказывание либо истинно, либо ложно, и ни одно высказывание не может быть одновременно истинным и ложным.
Пример. Волга впадает в Каспийское море. Значение высказывания — «истина».
Лондон — столица Франции. Значение высказывания — «ложно».
Карась не рыба. Значение высказывания — «ложно».
Число 6 делится на 2 и на 3. Значение высказывания — «истина».
Если юноша окончил среднюю школу, то он получает аттестат зрелости. Значение
высказывания — «истина».
Предложения «Вперед, гардемарины!» или «Какова сейчас температура воздуха
за окном?» не являются высказываниями, поскольку не несут в себе однозначных
сведений об истинности или ложности. Таким образом, высказыванием обычно
являются повествовательные (но не вопросительные и не восклицательные)
предложения.
Высказывание, представляющее собой одно утверждение, принято называть
простым, или элементарным. Примерами элементарных высказываний являются первое и второе высказывание в приведенном примере.
Высказывания, которые получаются из элементарных с помощью граммати
ческих связок «не», «и», «или», «если», «то», «тогда и только тогда», принято на
зывать сложными, или составными. В приведенном примере третье высказывание получается из простого высказывания «Карась — рыба» путем добавления отри
цания «не»; четвертое высказывание образовано из элементарных высказываний
«Число 6 делится на 2», «Число 6 делится на 3», соединенных союзом «и». Пятое высказывание получается из простых высказываний «Юноша окончил среднюю школу» и «Юноша получает аттестат зрелости» путем добавления грамматической связки «если ..., то ...». Аналогично, сложные высказывания могут быть получены из простых высказываний путем добавления грамматических связок «или», «тогда и только тогда».
В дальнейшем элементарные высказывания мы будем обозначать малыми бук
вами латинского алфавита; истинное значение высказывания цифрой 1, а ложное значение — цифрой 0. Например, если высказывание а истинно, то будет справед
лива запись а
= 1, если высказывание а ложно, то а
= 0.
Всякая точная наука, в данном случае математическая логика, абстрагируется от многих побочных явлений в изучаемых ею объектах и рассматривает в некото
рой мере идеализированную картину. Аналогично и в других науках, например, геометрия рассматривает точки, лишенные геометрических размеров, и линии, лишенные толщины.
При изучении логики высказываний предполагается, что все простые выска
зывания, входящие в рассмотрение, обладают одним из двух свойств — являются истинными либо ложными. Математические утверждения обладают этим свой
ством, и так как до сих пор математическая логика изучала в первую очередь логику математических доказательств, то такая абстракция особенно оправданна.
110
Глава 4. Логические основы информатики
4.1.2. Соглашения о языке алгебры высказываний
Используются различные обозначения (нотации) как для самих высказываний, так и для операций алгебры высказываний (алгебры логики). Возможные варианты сведены в табл. 4.1.
Таблица 4 .1 . Обозначения в алгебре высказываний
Понятие
Возможные обозначения
Обозначения, принятые
в данной книге
Высказывание
Строчные и прописные буквы латинского алфавита: а, Ь, с ,
..., z, А, В, С,
...,
Z; прописные буквы русского алфавита:
А, Б, В , Я
Строчные буквы латин
ского алфавита: а, Ь, с ,
...,
Z
Истинность
Прописная или строчная русская буква
И (и); слово истина; прописная или строчная латинская буква Т
( t ) ; слово true; цифра
1
Цифра 1
Ложность
Прописная или строчная русская буква Л
(л), слово ложь; прописная или строчная латинская буква F
( f ) ; слово fa l se, цифра
0
Цифра 0
Отрицание,
опровержение,
инверсия
Символ
или -
Символ надчеркивания
Конъюнкция, логическое «и»
Символ &, д или •. Кроме того, иногда знак между двумя высказываниями просто опускают
Символ А
Дизъюнкция, логическое «или»
Символ
V
Символ
V
Импликация
Символ Э или ->
Символ Э
Эквивалентность
Символ ,
* *
или *=►
Символ
+ *
Равносильность
Символ
В
Символ =
4.1.3. Логические операции над высказываниями
Над высказываниями можно выполнять следующие логические операции: от
рицание, конъюнкция, дизъюнкция, импликация и эквивалентность.
Операция отрицания высказывания х обозначается х и читается «не х» или
«неверно, что х».
Логическое значение высказывания х можно описать с помощью следующей таблицы:
X
X
1 0
0 1
4.1. Представление о высказываниях и логических операциях
111
Таблицы подобного вида принято называть
таблицами истинности.Пусть
х — высказывание. Так как
х также является высказыванием, можно образовать отрицание высказывания
х, то есть высказывание
х, которое называ
ется двойным отрицанием высказывания
х. Ясно, что логические значения
х и х совпадают.
Пример. Пусть имеется высказывание х «река Волга впадает в Каспийское море». Тогда высказывание «Неверно, что река Волга впадает в Каспийское море» будет отрицанием, то есть х, а высказывание «Неверно, что река Волга не впадает в Каспийское море» — двойным отрицанием, то есть f .Операция
конъюнкции высказываний
х и
у обозначается символом д, а выраже
ние
х л
у читается
«х и
у». Высказывания
х и
у называются членами конъюнкции.
Логические значения операции конъюнкции описываются следующей таблицей истинности:
XУх л у1 1
1 1
0 0
0 1
0 0
0 0
Пример. Если мы обозначим высказывание «6 делится на 2» как л:, а «6 делится на 3» как у , их конъюнкцией будет высказывание «6 делится на 2 и 6 делится на 3, которое записывается как х л
у и является истинным.Из определения операции конъюнкции видно, что союз «и» в
алгебре логики употребляется в том же смысле, что и в повседневной речи. Но в обычной речи не принято соединять союзом «и» два высказывания, далеких друг от друга по содержанию, а в алгебре логики рассматриваются конъюнкции любых двух вы
сказываний.
Из определения операции конъюнкции и отрицания ясно, что высказывание
х а х всегда ложно.
Операция
дизъюнкции высказываний
х и
у обозначается символом v, а вы
ражение
х v
у читается как
«х или
у». Высказывания
х и
у называются членами дизъюнкции.
112
Глава 4. Логические основы информатики
Логические значения операции дизъюнкции описываются следующей таблицей истинности:
X
У
хм у
1
1
1
1
0
1
0
1
1
0
0
0
Пример. Обозначим высказывание «В треугольнике DFE угол D острый» какх,
а высказывание «В треугольнике DFE угол Е острый» как у . Тогда дизъюнкция
хм у этих высказываний «В треугольнике DFE угол D или угол Е острый» ис
тинна, так как обязательно истинно хотя бы одно из высказываний.
В повседневной речи союз «или» употребляется в различном смысле: исклю
чающем и не исключающем. В алгебре логики союз «или» всегда употребляется в не исключающем смысле.
Из определения операции дизъюнкции и отрицания ясно, что высказывание
х
v
х всегда истинно.
Операция импликации высказываний х и у обозначается символом
Э,
а вы
ражение х
Э
у читается как «если х, то у». Высказывание х называют условием, или посылкой, высказывание у — следствием, или заключением, а высказывание
х
Э
у — следованием, или импликацией.
Логические значения операции импликации описываются следующей таблицей истинности:
X
У
х Э у
1
1
1
1
0
0
0
1
1
0
0
1
Пример. Обозначив высказывание «Число 12 делится на 6» как х, а высказывание
«Число 12 делится на 3» как у , мы получим импликацию x D у, которая отражает
высказывание «Если число 12 делится на 6, то оно делится на 3» и является ис
тинным.
Употребление слов «если..., то...» в алгебре логики отличается от употребления их в обыденной речи, где мы, как правило, считаем, что если высказыванием ложно, то высказывание «Если х, то у» не имеет смысла. Кроме того, строя предложение
4.2. Алгебра логики
113
«Еслих, то г/», мы всегда подразумеваем, что предложение
у вытекает из предложе
ниях. Употребление слов «если..., то...» в математической логике не требует этого, поскольку в ней смысл высказываний не рассматривается.
Операция
эквивалентности высказываний
х и
у обозначается символом «-», а выражение
х у читается «для того чтобы
х, необходимо и достаточно, чтобы г/» или
«х тогда и только тогда, когда
у». Высказывания
х и
у называются членами эквивалентности.
Логические значения операции эквивалентности описываются следующей таблицей истинности:
XУх + * у1 1
1 1
0 0
0 1
0 0
0 1
Пример. Обозначив высказывание «Треугольник SPQ с вершиной S и основанием PQ равнобедренный» какх, а высказывание «В треугольнике SPQ с вершиной S и основанием PQ Z.P = Z.Q» как у , мы можем записать высказывание «Треугольник SPQ с вершиной S и основанием PQ равнобедренный тогда и только тогда, когда Z.P = Z.Q» в форме эквивалентности х ** у. Эквивалентность является истинной, так как высказывания либо одновременно истинны, либо одновременно ложны.Эквивалентность играет важную роль в математических доказательствах. И з
вестно, что значительное количество теорем формулируется в форме необходимых и достаточных условий, то есть в форме эквивалентности. В этом случае, зная об истинности или ложности одного из двух членов эквивалентности и доказав ис
тинность самой эквивалентности, мы приходим к заключению об истинности или ложности второго члена эквивалентности.
4.2. Алгебра логики
4.2.1. Понятие формулы алгебры логики
С помощью логических операций над высказываниями можно строить сложные высказывания. При этом порядок выполнения операций определяется скобками.
Например, из трех высказываний,
х, г/,
2, можно построить два высказывания:
(х а у ) v z и
х Э (г/ v
(х л
z)).
114
Глава 4. Логические основы информатики
Первое высказывание есть дизъюнкция конъюнкции
х, у и отрицания выска
зывания
z. Второе высказывание есть импликация, посылкой которой является высказывание
х, а заключением — отрицание дизъюнкции высказывания
у и конъ
юнкции высказываний
х, г.Формулы алгебры логики будем обозначать прописными буквами латинского алфавита Л,
В , С ,....
Буквенные обозначения формул алгебры логики используются в основном в определениях, когда надо обозначить некоторые общие для формул закономерности.
Для
того чтобы логическими высказываниями, сформулированными на есте
ственном языке, можно было оперировать при помощи алгебры логики, их необ
ходимо формализовать, то есть перевести с естественного языка на язык символов алгебры логики. Для этого рекомендуется следующая процедура:
1. Если высказывание простое, то ему ставится в соответствие элементарная фор
мула.
2. Если высказывание составное, то для составления соответствующей формулы нужно:
1) выделить все элементарные высказывания и логические связки, образующие данное составное высказывание;
2) заменить их соответствующими символами (различные элементарные вы
сказывания обозначатся различными символами);
3) расставить скобки в соответствии со смыслом данного высказывания.
П равша записи формулы:
Пример. (х л у ) v z = X A y v z — мы опустили скобки, в которые была взята операция дизъюнкции.______х Э (у v (х д z)) я х Э у v (х д z) — мы опустили скобки, в которые было заключена формула со знаком отрицания над ней.Логическое значение формулы алгебры логики полностью определяется ре
зультатом логических операций над значениями входящих в нее элементарных высказываний. Например, логическим значением формулы
х л
у v
z в случае, если х = 1, г/ = 1, z = О, будет истина, то есть
х к у ч z= 1.
4.2. Алгебра логики
115
Таблица истинности позволяет полностью описать все возможные значения любой формулы в зависимости от значений входящих в нее элементарных вы
сказываний.
Очевидно, что если в формуле
п элементарных высказываний, то она принимает
2
п значений, состоящих из нулей и единиц, и результирующая таблица содержит
2
п строк.
Для
формулы таблица истинности имеет видXУXУхм ухм ух v
yD х v
у1 1
0 0
1 0
0 1
0 0
1 0
1 1
0 1
1 0
1 0
0 0
0 1
1 1
0 0
4.2.2. Равносильные формулы алгебры логики
Равносильность формул будем обозначать знаком з, тогда запись означает, что формулы
А и
В равносильны.
Скачать 14.49 Mb.