Определение словаря
Теперь нам известно, что нужно вести речь о схемах, клеммах, сигналах и логических элементах. На следующем этапе необходимо выбрать функции, предикаты и константы для их представления. Начнем с отдельных логических элементов и перейдем к схемам.
Прежде всего необходимо иметь возможность отличать один логический элемент от других логических элементов. Это можно обеспечить, присвоив логическим элементам имена с помощью констант: xl9 Х2 и т.д. Хотя каждый логический элемент подключен к схеме своим индивидуальным способом, его поведение (способ преобразования входных сигналов в выходные) зависит только от типа. Для ссылки на тип логического элемента может использоваться функция11. Например, можно написать Туре{Х±) =XOR. Тем самым вводится константа XOR для логического элемента конкретного типа; другие константы будут называться OR, AND и NOT. Функция Туре не является единственным способом регистрации онтологических различий. Для этого можно было бы использовать бинарный предикат, Type(xlfXOR), или несколько отдельных предикатов типов, таких как XOR (Х1). Любой из этих вариантов вполне подходит, но выбирая функцию Туре, мы избегаем необходимости определять аксиому, в которой указано, что каждый отдельный логический элемент может иметь только один тип, поскольку это уже гарантирует сама семантика функций.
Затем рассмотрим клеммы. Логический элемент или цифровая схема может иметь одну или несколько входных клемм и одну или несколько выходных клемм. Можно было бы просто присвоить каждой из них имя с помощью константы, точно так же, как мы именовали логические элементы. Таким образом, логический элемент хг мог бы иметь клеммы с именами Хг1пг, Хг1п2 и Х±Ои. Но следует избегать тенденции к созданию длинных составных имен. Назвав нечто Х11п1, мы не сделаем его первой входной клеммой хг; все равно потребуется указать это с помощью явного утверждения. По-видимому, лучше именовать клеммы логического элемента с помощью функции, так же, как мы именовали левую ногу короля Джона как LeftLeg{John). Таким образом, примем, что Znfl,) обозначает первую входную клемму для логического элемента Хг. Аналогичная функция Out используется для выходных клемм.
Связь между логическими элементами может быть представлена с помощью предиката Connected, который принимает в качестве параметров имена двух клемм, как в выражении Connected ( Ои t (1, Хг) , In (1, Х2) ).
Наконец, необходимо знать, включен или выключен сигнал. Одна из возможностей состоит в использовании унарного предиката On, который принимает истинное значение, когда сигнал на клемме включен. Тем не менее при этом затрудняется постановка таких вопросов, как: "Каковы возможные значения сигналов на выходных клеммах схемы СгТ Поэтому введем в качестве объектов два "значения сигнала", 1 и 0, и функцию Signal, которая принимает имя клеммы в качестве параметра и указывает значение сигнала для этой клеммы.
Регистрация общих знаний о проблемной области
Одним из признаков наличия хорошей онтологии является то, что с ее использованием требуется определить очень немного общих правил, а признаком наличия хорошего словаря служит то, что каждое правило может быть сформулировано четко и кратко. В рассматриваемом примере нам потребуется только семь приведенных ниже простых правил для описания всего, что нужно знать о цифровых схемах.
1. Если две клеммы соединены, то на них присутствует один и тот же сигнал:
Vfci,fc2 Соппесted(tlt t2) => Signal (ti) = Signal (fc2)
2. Сигнал на каждой клемме равен либо 1, либо 0 (но не имеет оба значения од-
новременно):
Vfc Signal (t) = 1 v Signal (t) = 0 1*0
3. Предикат Connected является коммутативным:
Vfci, t2 Connected( fci, t2) <=> Connected(t2, fci)
На выходе логического элемента OR присутствует 1 тогда и только тогда, когда на любом из его входов присутствует 1:
Vg Туре(д) = OR => Signal (Out (1, g) ) = 1 <=> Vn Signal (In(n, g) ) = 1
На выходе логического элемента AND присутствует 0 тогда и только тогда, когда на любом из его входов присутствует 0:
Vg Туре(д) = AND => Signal (Out (1, д) ) = 0 <=> Vn Signal (In(n, g) ) = 0
На выходе логического элемента XOR присутствует 1 тогда и только тогда, когда на его входах присутствуют разные сигналы:
Vg Туре(д) = XOR => Signal (Out (1, д) ) = 1 <=> Signal (In (1, g) ) * signal (In (2 , g) )
Выход логического элемента NOT противоположен его входу:
Vg (Туре(д) = NOT) Signal (Out (1, g) ) * signal ( Хл (1, g) )
Составление конкретного экземпляра задачи
Схема, показанная на рис. 8.2, представлена как схема С1 со следующим описанием. Прежде всего определим типы всех логических элементов:
Туре(Х±) = XOR Туре(Х2) = XOR Type (Ai) = AND Туре(А2) = AND Type(Oi) = OR
Затем покажем связи между ними:
Connected (Out (1, Хг) ,1п(1,Х2)) Connected (In (1, d) , In (1, Xi) ) Connected (Out (l,Xi) , Jn(2,A2) ) Connected(In(1, d) , In(1, Ai) ) Connected (Out (1, A2) , Jn(lf d) ) Connected(Jn (2, Ci) , Jn(2,Xi) ) Connected(Out (1, Ai) , Jn (2 , d) ) Connected( In(2 , Ci) , Jn(2,Ai) ) Connected (Out (1Д2) , Out (1, Ci) ) Connected( Jn(3 , Ci) , Tn(2 , X2) ) Connected(Out(l,Oi) lOut(2,C1)) Connected (In (3 , d) , In (1, A2) )
Передача запросов процедуре логического вывода
Какая комбинация входов вызовет появление 0 на первом выходе схемы d (бит суммы) и появление 1 на втором выходе схемы Сх (бит переноса)?
3ii,i2,i3 Signal (In(l, d) ) = ii л Signal (In (2 , Ci) ) = i2 л Signal (Jn(3 , Ci) ) = i3 л Signal (Out (1, Ci) ) = 0 л Signal (Out (2 , d) ) = 1
Ответами являются такие подстановки значений вместо переменных i1? i2 и i3, что результирующее высказывание следует из базы знаний. Существуют три такие подстановки:
{ii/l, i2/l, i3/0} {ii/1, i2/0, i3/l} {ii/0, i2/l, i3/l>
Каковы возможные множества значений сигналов на всех клеммах этой схемы сумматора?
3ii, i2t i3/ Oi, 02 Signal (In (1, d) ) = ii л Signal (Хл (2 , Ci) ) = i2 л Signal (In(3 , d) ) = i3 л Signal (Out (1, d) ) = oi л Signal (Out (2 ,Ci) ) = o2
Этот последний запрос должен вернуть полную таблицу входов и выходов для данного устройства, которая может использоваться для проверки того, действительно ли эта схема правильно складывает свои входные данные. Это — простой пример проверки схемы. Можно также применять приведенное здесь определение данной схемы для создания более крупных цифровых систем, для которых может осуществляться процедура проверки такого же рода (см. упр. 8.17). Для структурированной разработки базы знаний такого же рода подходят многие проблемные области, в которых более сложные понятия определяются на основе более простых понятий.