Таблица истинности для схемы АД
Из вышесказанного следует, что достаточное условие существования булевского решения для обратного включения заключается в следующем:
1. матрица G удовлетворяет ранговому условию;
2. вектор у совпадает с одной из строк матрицы G;
3. все элементы AnAND соединены со всеми элементами AnNOT (математически это означает, что матрица B является бинарной);
4. любое в матрице В должно принимать оба значения v 0 и 1 (в любом столбце матрицы В должен присутствовать и 0, и 1).
Схему АД будем описываеть таблицей, которая имеет вид
, где матрицы B и G удовлетворяют вышеперечисленным условиям.
Будем называть схему АД булевской, если она удовлетворяет условиям 1) и 3), а вектор у, совпадающий с одной из строк матрицы G, будем называть правильным вектором. Булевская схема АД, на которую подан правильный вектор y, имеет булевское решение.
Булевская схема АД описывается таблицей истинности, которая имеет вид
. При булевском решении
или
.
Последнее выражение есть дизъюнктивная нормальная форма - ДНФ. Таким образом, схема АД, удовлетворяющая указанным условиям, удовлетворяет, кроме того, системе уравнений
,
где каждое уравнение является ДНФ. Если задается вектор х, то вычисляется вектор у, т.е. функция, соответствующая системе ДНФ. Если же вектор у задается, а вектор х вычисляется, то схема АД вычисляет функцию, обратную системе ДНФ v обратную ДНФ.
Отметим явную аналогию между схемой АД и преобразователем, реализующим ДНФ. При замене в схеме АД элементов AnAND, AnOR, AnNOT элементами AND, OR, NOT и исключении ТД онапревращается в указанный преобразователь. Отличие заключается в том, что преобразователь вычисляет ДНФ, а схема АД вычисляет как ДНФ, так и обратную ДНФ.
Немного больше о технологиях >>>
О возможном способе возникновения сил природы и их связи между собой
В
1687г. Исаак Ньютон объяснил движение небесных тел и многих земных явлений
наличием притяжения всех тел друг к другу. С тех пор многие пытаются объяснить,
каким образом два тела могут на расстоянии взаимодействовать друг с другом [1].
Примерно через 100лет эксперименты с эле ...
Молекулы-русалки
Эта история начинается с
одного из многочисленных увлечений Бенджамина Франклина, выдающегося
американского ученого и респектабельного дипломата. Будучи в 1774 году в
Европе, где он улаживал очередной конфликт между Англией и Североамериканскими
Штатами, Франклин в свободное вр ...
