Электрические цепи с бинарными потенциалами
T
, если
точка
(с потенциалом
) не
присоединена ни к одному из входов элемента AnOR-j.
Таким образом, все потенциалы v принимают булевские значения. Из (6) следует, что и все потенциалы у также принимают булевские значения, что и требовалось показать.
6. Обратное включение.
При обратном включении схемы АД выводы у являются входами, а выводы х являются выходами схемы АД. Все входные потенциалы у принимают булевские значения. Пусть, кроме того, существует такая S-строка в матрице G, что
.
(1)
Это означает, что булевский вектор у совпадает с S-строкой матрицы G. Пусть еще
(2)
и, следовательно,
(3)
Существование и
количество решений уравнения (4.1) относительно z определяется рангом
расширенной матрицы
. Но, по
условию, булевский вектор у совпадает с S-строкой матрицы G, т.е. совпадает с
одним из столбцов матрицы
.
Следовательно, ранг матрицы
равен рангу матрицы
. Таким образом,
существование и количество решений уравнения (4.1) определяется рангом матрицы
G. Точнее,
T если ранг матрицы G равен M (числу неизвестных), то (4.1) имеет единственное решение;
T если ранг матрицы G меньше M, то (4.1) имеет несколько решений;
T ранг матрицы
G не может быть больше M, т.к. матрица
имеет ровно столбцов.
Таким образом,
решение уравнения (4.1) будет единственным, если ранг матрицы
равен M или ранг G матрицы равен M. Это
верно, если выполняется следующее условие, которое в дальнейшем для краткости
будем называть как
Первое ранговое условие:
T в матрице
все M столбцов линейно независимы,
T в матрице
есть не менее M линейно независимых строк.
Если выполняется первое ранговое условие, решение уравнения (4.1) единственно, выполняется условие (1) и для строки S не существует линейно зависимых строк, то это решение имеет вид
(4)
Отсюда и из (5.4) следует, что
,
т.е. все потенциалы х принимают булевские значения, что и требовалось показать. Итак, для этого должно выполнятся
Второе ранговое условие:
T в матрице
все M столбцов линейно независимы,
T в матрице
все строки линейно независимы.
7. Таблица истинности для схемы АД
Из вышесказанного следует, что достаточное условие существования булевского решения для обратного включения заключается в следующем:
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 и исключении ТД онапревращается в указанный преобразователь. Отличие заключается в том, что преобразователь вычисляет ДНФ, а схема АД вычисляет как ДНФ, так и обратную ДНФ.
8. Пример.
Некоторая булевская схема АД приведена на фиг 8.1 и фиг.8.2. Она описывается таблицей истинности табл. 1. Эта таблица удовлетворяет условиям 1), 2), 3).
Таблица 1.
|
|
|
|||||||||
| X1 | X2 | X3 | Y1 | Y2 | Y3 | |||||
|
|
0 | 0 | 1 | 1 | 1 | 1 | ||||
| 0 | 1 | 1 | 1 | 1 | 0 | |||||
| 1 | 1 | 0 | 0 | 1 | 1 | |||||
| 1 | 0 | 1 | 1 | 0 | 1 | |||||

