Схемы из функциональных элементов

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

База индукции. Одна изолированная вершина является (тривиальной) логической сетью, причем одновременно входом и выходом (рис. 9.1).

«Индуктивный» переход основан на использовании трех операций.

1. Объединение непересекающихся сетей. Пусть – две непересекающиеся сети, имеющие соответственно n и m входов и p и q выходов. Теоретикомножественное объединение есть логическая сеть входами которой являются все входы , а выходами все выходы сетей (рис. 9.2).

Рис. 9.1

2. Операция присоединения элемента F. Пусть логическая сеть и элемент F таковы, что число n входов F не больше числа выходов . Объявим логической сетью фигуру, входами которой являются входы сети . При этом отождествим n выходов сети с n входами элемента F, а остальные выходы и выход элемента F объявим выходами сети . Такая сеть называется результатом подключения элемента F к логической сети (рис. 9.3).

3. Операция расщепления выхода. Пусть дана логическая сеть . Выделим в ней один из выходов с номером j. Объявим логической сетью фигуру, входами которой являются входы , а выходами – все выходы логической сети с номерами 1, 2, ¼, j – 1, j + 1, ¼ и еще два выхода, возникших из выхода с номером j сети .

Других логических сетей нет.

Схемой из функциональных элементов называется логическая сеть , входам и выходам которой приписаны различные буквы Полученную таким образом схему обозначим

Каждый элемент является элементарным преобразователем, который преобразует входной набор в выходные значения . Если на входы подать набор то, продвигаясь от входов к выходам, он будет переходить в набор , характеризующий состояние выходов, т.е. . Для произвольной системы булевой функции в исходной элементной базе существует схема система функций полна. В частности, в элементной базе {инвертор, конъюнктор, дизъюнктор} можно реализовать любую булеву функцию.