Таблица истинности для схемы АД
Из вышесказанного следует, что достаточное условие существования булевского решения для обратного включения заключается в следующем:
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 и исключении ТД онапревращается в указанный преобразователь. Отличие заключается в том, что преобразователь вычисляет ДНФ, а схема АД вычисляет как ДНФ, так и обратную ДНФ.
Немного больше о технологиях >>>
Биотехнология России с точки зрения теории эволюции
Четырнадцатый том озаглавлен так: «Может ли разумный человек, учитывая опыт прошедших
веков, питать хоть малейшую надежду на светлое будущее человечества?»
Прочесть четырнадцатый том недолго. Он состоит всего из одного слова и точки: «Нет.»
К. Воннегут
В Новый год принято ...
Новый подход к методам химической очистки призабойной зоны ствола скважины при заканчивании открытым стволом
В скважинах, где традиционные методы их
заканчивания непригодны по геолого-техническим и экономическим соображениям, в
последние годы все больше используются современные системы заканчивания скважин
открытым стволом. Проведенный авторами анализ применимости таких систем имеет
н ...
