Многие элементы в современной электронике являются устройствами, преобразующими некоторые входные сигналы (данные) в выходные. Логические схемы, в отечественной литературе чаще называемые схемами из функциональных элементов, представляют собой математическую модель таких устройств, в которых временем выполнения преобразования входов в выходы можно пренебречь.
Чтобы не усложнять определение, зафиксируем конкретный базис B0={
Определение 2.1. Логической схемой (схемой из функциональных элементов) в базисе B0 называется размеченный ориентированный граф без циклов S=(V,E), в котором
Как и для деревьев, для ориентированных графов без циклов можно естественным образом ввести понятие глубины.
Определение 2.2. Глубина вершины v
Глубиной D(S) схемы S назовем максимальную из глубин ее вершин.
Пусть входы схемы S помечены переменными x1, … , xn. С каждой вершиной v
Определение 2.3.
Базис: v имеет глубину 0. Тогда это входная вершина, которая помечена некоторой переменной xi. Положим fv(x1,… , xn) = xi.
Шаг индукции. Пусть всем вершинам w глубины
если v помечена ¬ и в нее входит ребро (w,v) , то положим
если v помечена
если v помечена
Нетрудно понять, что шаг индукции в этом определении корректен, так как, если в схеме S имеется ребро (w,v) и глубина вершины v равна k+1, то глубина вершины w не превосходит k и для нее fw уже определена по индукционному предположению.