Будем говорить, что логическая функция f(x, y) представляет вычислимое отношение R(x, y), если имеет место отношение: R(x, y) Û f(x, y) = 1. Здесь в отношении R(x, y) переменные x и y обозначают двоичные числа, а в логической функции f(x, y) эти же обозначения x и y обозначают кортежи логических переменных.
Это определение можно сузить, когда отношение R определяет вычислимую функцию F. В этом случае говорим, что логическая функция f представляет вычислимую функцию F, если имеет место эквивалентность: F(x) = y Û f(x, y) = 1. В этом случае назовем переменные x – входными, а y – выходными.
Теперь можно говорить о вычислениях применительно к логической функции, так как каждое единичное означивание переменных x, y соответствует единственному вычислению F(x) = y. Поэтому в качестве исследуемых систем будут выступать логические функции, обладающие хорошо описываемыми конструкцией и поведением.
Самой булевской функции f(x) можно поставить в соответствие некоторый вычислитель, вычисляющий значение выходных переменных по входным. В результате возникает вопрос о неопределенности значений выходных переменных, когда известны значения всех или некоторых входных. При этом выходные переменные от входных зависят не обязательно функциональная, это может быть и более общая зависимость, когда один входной кортеж определяет несколько выходных. В последнем случае выходные кортежи рассматриваются как неразличимые. Будем рассматривать в качестве вычислителя так называемую бинарную программу pf, которая определяется следующим образом.
Бинарная программа pf для функции f(x1, x2, …, xn) представляет собой ор-дерево с единственным корнем (истоком), которому приписана функция f(x1, x2, …, xn), и двумя висячими узлами, одному из которых приписано значение 1 (1-сток), другому 0 (0-сток), а дуги помечены литерами xi или`xi, i = 1, 2, …, n. Если два узла сети соединяются путем, дуги которого не содержат ортогональных меток, то будем называть такой путь проводящим. Каждый узел дерева достижим из истока. Проводящий путь, дуги которого помечены метками, образующими множество {xj1s1, xj2s2, …, xjmsm} литер, где s1, s2, …, sm Î {0, 1}, назовем определяющим это множество.
Внутренние узлы и дуги программы помечены следующим образом.
Каждой дуге приписана в точности одна литера xi или`xi, i = 1,2, …, n.Из каждого внутреннего узла ведут в точности две дуги, которым приписаны литеры xi и`xi, i = 1,2, …, n.Если в узел N сети ведет проводящий путь, дуги которого помечены метками xj1s1, xj2s2, …, xjmsm , то этому узлу приписана функция, которая получается из исходной в результате присваивания переменным xj1, xj2, …, xjm значений соответственно s1, s2, …, sm.Если узлы сети соответствуют эквивалентным функциям, то они склеиваются. При этом узлу приписана в точности один представитель из класса эквивалентных функций.Для каждого из 2n двоичных наборов sх переменных в сети имеется путь ведущих из истока либо в 1-сток либо в 0-сток, множество меток дуг которого покрывается компонентами sх.Из определения программы легко увидеть, что если sx есть совокупность меток некоторого 1-проводящего пути, то при означивании sx функция f принимает значение 1. Поэтому sx есть единичное означивание для f. Так как логическая функция однозначно характеризуется перечислением своих 1-проводящих путей, то будем изображать бинарные программы лишь перечисляя их 1-проводящие пути. В этом случае бинарная программа представляет собой двухполюсник с истоком и 1-стоком.
В бинарной программе pf каждое вычисление представлено единственным путем из истока в сток. Так как бинарная программа pf реализует одну вычислимую функцию, то можно ограничиться рассмотрением программ, для которых все пути из истока на начальных отрезках содержат дуги, помеченные литерами, образованными только из входных переменных у, и после этих отрезков путей дуг с такими метками не встречается. Такие бинарные программы назовем однородными.
Введем еще одно определение.
y-сечением однородной бинарной программы pf назовем множество всех ее узлов, которыми завершаются все пути, начинающиеся в истоке и дуги которых помечены литерами, образованными лишь по переменным y.
Применительно к бинарным программам можно говорить о некоторой неопределенности выходных значений от входных в реализуемых вычислениях. Действительно, если для программы pf задан входной вектор sy, то он задает единственный путь из истока в некоторый узел N программы. Нам удобно мыслить узел N как некоторый промежуточный вычислитель. Он может соединяться со стоком несколькими путями, каждый из которых характеризуется собственными выходными значениями. В случае функциональной зависимости этот путь один, в противном случае один входной вектор определяет несколько выходных. И в рамках этой совокупности значений нельзя указать, какой именно выходной вектор появится на выходе вычислителя. В связи с этим можно говорить только о различении множеств выходных векторов, которые определяются различными промежуточными вычислителями (или по-другому, узлами y-сечения).