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