Электрические цепи с бинарными потенциалами — страница 5

  • Просмотров 480
  • Скачиваний 12
  • Размер файла 114
    Кб

булевский вектор х совпадает с S-строкой матрицы В v см. (3). Покажем, что в этом случае все потенциалы у также принимают булевские значения. Из (4) следует, что (8) Из (5) и (7) следует, что T, если точка (с потенциалом) присоединена к одному из входов элемента AnOR-j, 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. любое в матрице В