Логические схемы (схемы из функциональных элементов)

Многие элементы в современной электронике являются устройствами, преобразующими некоторые входные сигналы (данные) в выходные. Логические схемы, в отечественной литературе чаще называемые схемами из функциональных элементов, представляют собой математическую модель таких устройств, в которых временем выполнения преобразования входов в выходы можно пренебречь.

Чтобы не усложнять определение, зафиксируем конкретный базис B0={

, ¬} и определим схемы в этом базисе.

Определение 2.1. Логической схемой (схемой из функциональных элементов) в базисе B0 называется размеченный ориентированный граф без циклов S=(V,E), в котором

вершины, в которые не входят ребра, называются входами схемы, и каждая из них помечена некоторой переменной (разным вершинам соответствуют разные переменные);
в каждую из остальных вершин входит одно или два ребра; вершины, в которые входит одно ребро помечены функцией ¬, а вершины, в которые входят по два ребра, - одной из функций
или
. Такие вершины называются функциональными элементами.

Как и для деревьев, для ориентированных графов без циклов можно естественным образом ввести понятие глубины.

Определение 2.2. Глубина вершины v

V в схеме S=(V,E) - это максимальная длина пути из входов S в v .

Глубиной D(S) схемы S назовем максимальную из глубин ее вершин.

Пусть входы схемы S помечены переменными x1, … , xn. С каждой вершиной v

V схемы S свяжем булеву функцию fv(x1,… , xn), реализуемую в этой вершине. Определим fv индукцией по глубине v .

Определение 2.3.

Базис: v имеет глубину 0. Тогда это входная вершина, которая помечена некоторой переменной xi. Положим fv(x1,… , xn) = xi.

Шаг индукции. Пусть всем вершинам w глубины

k уже сопоставлены функции fw и пусть v - произвольная вершина глубины k+1. Тогда

если v помечена ¬ и в нее входит ребро (w,v) , то положим
$f_v(x_1,\ldots , x_n) = \neg f_w(x_1,\ldots , x_n) ;$
если v помечена
и в нее входят два ребра (w1,v) и (w2,v), то положим
$f_v(x_1,\ldots , x_n) = f_{w_1}(x_1,\ldots , x_n) \wedge f_{w_2}(x_1,\ldots , x_n);$
если v помечена
и в нее входят два ребра (w1,v) и (w2,v), то положим

$f_v(x_1,\ldots , x_n) = f_{w_1}(x_1,\ldots , x_n) \vee f_{w_2}(x_1,\ldots , x_n).$

Нетрудно понять, что шаг индукции в этом определении корректен, так как, если в схеме S имеется ребро (w,v) и глубина вершины v равна k+1, то глубина вершины w не превосходит k и для нее fw уже определена по индукционному предположению.

Содержание Вперед