Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 98
Текст из файла (страница 98)
На самом высоком уровне требуется проанализировать функциональное назначение схемы. Например, действительно ли приведенная на рис. 8.2 схема выполняет сложение должным образом? Если на все входы подаются сигналы с высоким потенциалом, то каким является выход логического элемента л,? Интерес представляют также вопросы о структуре схемы. Например, каковыми являются все логические элементы, подключенные к первой входной клемме? Содержит ли эта схема з?о Часть Ш. Знания и рассуждения петли обратной связи? В этом и состоят задания, рассматриваемые в данном разделе. Сушествуют также более детализированные уровни анализа, включая те, которые относятся к определению продолжительности задержек, площади схемы, потреблению энергии, стоимости производства и т.д.
Для каждого из этих уровней могут потребоваться дополнительные знания. Сбор относящихся к делу знаний Что мы знаем о цифровых схемах? Для наших целей достаточно знать, что они состоят из проводов и логических элементов. Сигналы распространяются по проводам к входным клеммам логических элементов, а каждый логический элемент вырабатывает на выходной клемме сигнал, который распространяется по другому проводу. Чтобы определить, какими должны быть эти сигналы, нам необходимо знать, как логические элементы преобразуют свои входные сигналы. Сушествует четыре основных типа логических элементов; логические элементы АИР, Оп и хОк имеют две входные клеммы, а логический элемент НОт имеет одну входную клемму. Все логические элементы имеют одну выходную клемму.
Схемы, как и логические элементы, имеют входные и выходные клеммы. Для того чтобы рассуждать о функциональных назначениях и связях в электронной схеме, не нужно вести речь о самих проводах, о путях, по которым проложены провода, или о соединениях, в которых встречаются два провода. Играют роль только соединения между клеммами — можно утверждать, что одна выходная клемма соединена с другой, входной клеммой, не упоминая о том, что они фактически соединены проводами. В этой проблемной области имеется также множество других факторов, не имеющих отношения к нашему анализу, таких как размеры, форма, цвет или стоимость различных компонентов. Если бы нашей целью было нечто иное, чем проверка проектов на уровне логических элементов, то онтология была бы другой.
Например, если бы нас интересовала отладка неисправных электронных схем, то, по-видимому, целесообразно было бы включить в онтологию провода, поскольку неисправный провод может исказить проходящий по нему сигнал. С другой стороны, для устранения ошибок синхронизации потребовалось бы включить в рассмотрение задержки логических элементов. А если бы мы были заинтересованы в проектировании продукта, который оказался бы прибыльным, то имели бы значение такие данные, как стоимость производства электронной схемы и ее быстродействие в сравнении с другими продуктами на рынке. Определение словаря Теперь нам известно, что нужно вести речь о схемах, клеммах, сигналах и логических элементах.
На следующем этапе необходимо выбрать функции, предикаты и константы для их представления. Начнем с отдельных логических элементов и перейдем к схемам. Прежде всего необходимо иметь возможность отличать один логический элемент от других логических элементов. Это можно обеспечить, присвоив логическим элементам имена с помощью констант: х„х, и т.д. Хотя каждый логический элемент подключен к схеме своим индивидуальным способом, его поведение (способ преобразования входных сигналов в выходные) зависит только от типа. Для ссылки на тип Глава 8.
Логика первого порядка 371 логического элемента может использоваться функция". Например, можно написать туре(х,) =хОп. Тем самым вводится константа хОп для логического элемента конкретного типа; другие константы будут называться ОП, )Г)Ч)З и )ЧОТ. Функция туре не является единственным способом регистрации онтологических различий. Для этого можно было бы использовать бинаРный пРедикат, ТУРе(Хг, ХОП), или несколько отдельных предикатов типов, таких как ХОП (Х,) .
Любой из этих вариантов вполне подходит, но выбирая функцию туре, мы избегаем необходимости определять аксиому, в которой указано, что каждьш отдельный логический элемент может иметь только один тип, поскольку это уже гарантирует сама семантика функций. Затем рассмотрим клеммы. Логический элемент или цифровая схема может иметь одну или несколько входных клемм и одну или несколько выходных клемм. Можно было бы просто присвоить каждой из нпх имя с помощью константы, точно так же, как мы именовали логические элементы. Таким образом, логический эле- МЕНТ Хз МОГ бЫ ИМЕТЬ КЛЕММЫ С ИМЕНаМИ Х, ТП„Хттоз И Х,Оцсз. НО СЛЕДУЕТ ИЗбЕГатЬ тенденции к созданию длинных составных имен.
Назвав нечто х,тпы мы не сделаем его первой входной клеммой х-,; все равно потребуется указать это с помощью явного утверждения. По-видимому, лучше именовать клеммы логического элемента с помощью функции, так же, как мы именовали левую ногу короля Джона как ьеТСБеу(то)зп) . Таким образом, примем, что Тп (1, Х,) Обозначает первую входную клемму для логического элемента х,. Аналогичная функция Оис используется для выходных клемм.
Связь между логическими элементами может быть представлена с помощью предиката Ооппессес(, который принимает в качестве параметров имена двух клемм, как в выражении Осппессео(Оис(1,х,), Тп(1,х ) ). Наконец, необходимо знать, включен или выключен сигнал. Одна из возможностей состоит в использовании унарного предиката Оп, который принимает истинное значение, когда сигнал на клемме включен. Тем не менее при этом затрудняется постановка таких вопросов, как: "Каковы возможные значения сигналов на выходных клеммах схемы О,?" Поэтому введем в качестве объектов два "значения сигнала", 1 и О, и функцию Яйопп1, которая принимает имя клеммы в качестве параметра и указывает значение сигнала для этой клеммы. Регистрация общих знаний о проблемной области Одним из признаков наличия хорошей онтологии является то, что с ее использованиелг требуется определить очень немного общих правил, а признаком наличия хорошего словаря служит то, что каждое правило может быть сформулировано четко и кратко.
В рассматриваемом примере нам потребуется только семь приведенных ниже простых правил для описания всего, что нужно знать о цифровых схемах. 1. Если две клеммы соединены, то на них присутствует один и тот же сигнал: Чез, Ез Соппесеес)(ег, Сг) ~ Язяпа1(ег) = 51дпа1(ег) " Обратите внимание на то, что в этом разделе имена, начинающиеся с соответствующих букв (л „х: н т.д.), используются исключительно для того, чтобы данный пример стал более удобным для чтения. База знаний все еще должна содержать информацию о типе для всех этих логических элементов.
372 Часть Ш. Знания и рассуждения 2. Сигнал на каждой клемме равен либо 1, либо О (но не имеет оба значения одновременно): гг'С яддпа1(с) = 1 и Ягдлат(Е) = О 1аа 3. Преликат соплесседявляется коммутативным: 'г Ег, Сг СОППЕСЕЕд[ Ег, Ег) а» СОППЕОЕЕд(сг, Сг) На выходе логического элемента Оп присутствует 1 тогда и только тогда, когда на любом из его входов присутствует 1: [)д туре(д) = ОП ~ вддпа1 (Оие (1, д) ) = 1 аг г(л Ягдпа1 (7п (и, д) ) = 1 На выходе логического элемента )[ыР присутствует О тогда и только тогда, когда на любом нз его входов присутствует О: '7д туре(д) = лип =г Ягдпа1(Оие(1, д) ) = О аг Уп 51дпа1(тл(л, д) ) = 0 На выходе логического элемента х[)н присутствует 1 тогда и только тогда, когда на его входах присутствуют разные сигналы: ггд туре(д) = ХОИ ~ Бгдла1(Оие(1, д) ) = 1 о> Бддпа1(7п(1, д) ) Ф Бддпаз (7л[2, д) ) Выход логического элемента ЫОт противоположен его входу: ггд (туре(д) = НОТ) =г Ягдпа1(Оиь (1, д) ) Ф Ягдпаз (гп(1, д) ) Составление конкретного экземпляра задачи Схема, показанная на рис.
8.2, представлена как схема С, со следующим описанием. Прежде всего определим типы всех логических элементов: туре(х ) = хоп туре(Х ) = ХОП туре(Л ) = ЛНО туре(лг) = лно туре(О,) = Ои Затем покажем связи между ними: Соппесеед(Оис (1, Хг), 7п (1, Хг) ) Соппесеед(гп(1,Сг),гп(1,хг)) Соппеосед(Оие(1,Хг),гл(2,лг)) Соппеосед[тп(1,Сг),гп(1,лг)) Соппеосед(Оие(1.лг),7п(1,0г)) Соппессед(гп (2, Сг), гп (2, Хг) ) Сопл Сед[сил(1,Л,),7п(2, О,) ) Соппеооед(гп(2, Сг), тп(2, Аг) ) Соппессед(Оис(1,Хг),Оие(1,Сг)) Соппеосед(7п [3, Сг], 7п (2,Хг) ) Соппессед(Оис (1, Ог), Оис (2, Сг) ) Соппессед (7л (3, Сг), 7п (1, Лг) ) 373 Глава 8. Логика первого порядка Передача запросов процедуре логического вывода Какая комбинация входов вызовет появление 0 на первом выходе схемы С, (бит суммы) и появление 1 на втором выходе схемы С, (бит переноса)? 31г, гг зз Бгдпа1(тп(1, Сг) ) = зг л Бздпа1 (гп(2, Сг) ) = зг л Бздпа1 (Гп (3, Сг) ) = зз л Бг дпа1 (Оие (1, Сг) ) = О л Бхдпа1(Оие(2, Сг) ) = 1 Ответами являются такие подстановки значений вместо переменных х„з, и з,, что результирующее высказывание следует из базы знаний.
Существуют три такие подстановки: (згг'1, зг/1, ззг'О) (ггг'1, згг'С, ззг'1) (зз/О, згг'1, ззг'1) Каковы возможные множества значений сигналов на всех клеммах этой схемы сумматора? Ззг, зз, 1з, п„оз Бздпа1(тп(1, С,) ) = зг л Бхдпа1(тп(2, Сг) ) = хг л Бз'.дпа1 (Гп(3, Сг) ) = зз л Бхдпа1 (Оие(1, Сг) ) = оз л Бхдпа1 (Осе (2, Сг) ) = ог Этот последний запрос должен вернуть полную таблицу входов и выходов для данного устройства, которая может использоваться для проверки того, действительно ли эта схема правильно складывает свои входные данные. Это — простой пример пк проверки схемы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
