ГЛАВА ТРЕТЬЯ. ВОПРОСЫ АНАЛИЗА И СИНТЕЗА НЕВРЕМЕННЫХ СХЕМ

3-1. ЛОГИЧЕСКИЕ СЕТИ

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

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

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

Такую адекватную математическую схему мы будем называть логической сетью.

Дадим более четкое определение понятия логической сети. Пусть мы имеем конечное множество А

И пусть нам задано множество В, элементами которого являются упорядоченные пары элементов множества А

Здесь — любые из элементов множества

Пусть, наконец, нам задано некоторое множество элементами которого являются логические функции

Установим однозначное отображение множества А на т. е. сопоставим каждому элементу множества А один из элементов множества

Определение 3-1. Совокупность множества А и В совместно с однозначным отображением множества А на множестве называется логической сетью.

Геометрической интерпретацией логической сети служит некоторая схема логической сети, которая строится следующим образом.

Рис. 3-1. (см. скан)

На плоскости в произвольном порядке располагаются элементы множества А (для их обозначения будем использовать кружок). Эти элементы называются вершинами графа (рис. 3-1,а). Символ соответствующего данному кружку элемента (т. е. номер) пишется рядом с этим кружком. Внутри

кружка вписывается элемент множества сопоставленный при отображении А на элементу, соответствующему данному кружку. Наконец, все кружки соединяются между собой ориентированными стрелками согласно элементам множества В. Элементу соответствует стрелка, идущая от кружка, сопоставленного элементу к кружку, сопоставленному элементу Эти стрелки носят название дуг графа.

Пример 3-1. Пусть

и отображение А на задано как

Соответствующая схема заданной логической сети показана на рис. 3-1,а.

Рассмотрим множество аргументов

Произведем теперь отображение некоторых подмножеств множества X на некоторые элементы множества А

где X — некоторое подмножество множества X.

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

Геометрической интерпретацией множества С являются дуги, проведенные из соответствующих входов схемы к вершинам графа, сопоставленным нужным элементам множества А.

Пример 3-2. Для логической сети рис. 3-1,а заданы:

Соответствующая схема логической сети чриведеиа на рис. 3-1,б.

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

Теперь ограничим отображение множества А на следующим образом. Потребуем, чтобы функция сопоставляемая вершине с номером зависела от стольких аргументов, сколько дуг входит в данную вершину. Эквивалентным требованием является органичение на элементы множеств В и С при заданном отображении А на Суммарное число пар вида не должно превышать числа аргументов, имеющихся у функции, сопоставленной вершине с номером Логическую сеть, для которой выполнено это требование, назовем правильной.

Определение 3-2. Упорядоченная и правильная логическая сеть называется регулярной логической сетью (РЛС).

В дальнейшем будем рассматривать только правильные логические сети, а на протяжении этого раздела ограничимся рассмотрением только регулярных логических сетей. Рассмотрим, наконец, множество выходов

Произведем теперь взаимно однозначное отображение некоторого подмножества А множества А на множество Геометрической интерпретацией этого отображения будут дуги, направленные от элементов множества А к соответствующим элементам множества Элементы множества как и элементы множества X, будем обозначать жирными точками.

Пример 3-3. Для логической сети рис. 3-1, б определено множество

и взаимно однозначное отображение

Соответствующая схема логической сети приведена на рис. 3-1,в.

После отображения некоторых вершин графа на множество У в графе могут остаться вершины, из которых не выходит ни одной дуги. Такие вершины назовем

тупиковыми и исключим их, а также ребра, идущие к ним. Оставшуюся после этого схему логической сети будем называть логическим многополюсником. Если множество X содержит элементов, а множество У содержит элементов, то такой логический многополюсник будем называть логическим -полюсником.

Пример 3-4. Для регулярной логической схемы, данной на рис. 3-1,в, вершина 6 является тупиковой. После ее удаления остается логический -полюсник, вход у которого является фиктивным, поэтому он опущен на схеме логической сети (рис. 3-1,г).

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