Рассмотрим однородную бинарную программу pf для функции f(y, z). Пусть N1, N2, …, Nk – множество узлов y-сечения и Т1, Т2, …, Тk – совокупности путей, проходящих из истока программы в сток через узлы соответственно N1, N2, …, Nk. Пусть мощности множеств Т1, Т2, …, Тk равны соответственно t1, t2, …, tk и t = åi=1,k ti. Каждый узел Ni определяет, с одной стороны, в точности один класс у-эквивалентности, а с другой, - единственную логическую функцию, определяемую всяким у-означиванием из этого класса эквивалентности. Следовательно, доля pi всех наборов, определяемых одним классом у-эквивалентности, соответствующего узлу Ni, равна отношению ti / t, i = 1, 2, …, k.
Достаточно понятно, что сложность зависимости функции f(y, z) от переменных y, в определенной степени, характеризует фактор-множество у-эквивалентности. Действительно, чем больше фактор-множество, тем больше различных подформул встречается в разложении логической функции по этим переменным. В терминах логической программы мощности этого фактор-множества соответствует числу узлов у–сечения. Поэтому введем следующее понятие.
Эффективной пропускной способностью одного узла у–сечения бинарной программы назовем величину t, такую, что log t = åi=1,k pi log ti, где pi есть относительная доля путей, проходящих через i-ю вершину y-сечения (åi=1,k pi = 1). Если полагать, что некоторая случайная величина А принимает значения log t1, log t2, …, log tk с вероятностями соответственно р1, р2, …, рk, то åi=1,k pi log ti есть математическое ожидание М[log A] этой величины. В точности так же можно рассуждать, рассматривая величины р1, р2, …, рk как доли путей, проходящих через соответствующие узлы y-сечения. Если эти доли одинаковы, то log t = log`t . Т.е. эффективная пропускная способность в таком случае совпадает с числом путей из истока в сток, которые проходят через одну вершину сечения.
Эффективным у–сечением назовем величину
Нy = log t – log t = log t – åi=1,k pi log ti
= -åi=1,k (ti/t) log (ti/t) = -åi=1,k pi log pi.
Если значение Нy велико, то при условии, что суммарное число t = åi=1,k ti всех путей из истока в сток постоянно, среднее число путей, проходящих через один узел сечения, мало, а число узлов в сечении, т.е. классов у–эквивалентности велико. Но это соответствует тому, что число различных подформул, участвующих в разложении функции по переменным у – велико. В итоге следует, что сложность зависимости исходной функции от переменных у велика.
Очевидно, что энтропия и эффективное сечение вычисляются по одной формуле. Но энтропия получена из соображений вычисления степени неопределенности выходных значений программы от входных. А эффективное сечение получено из анализа сложности зависимости функции от входных переменных.
В общем случае в обозначении энтропии будем указывать и логическую функцию, для которой оно определяется, т.е. будем обозначать ее как Hfy. Если ясно, о какой функции идет речь, то верхний индекс будем опускать.
Поясним с содержательной точки зрения введенное понятие энтропии. Пусть для произвольного события А, происходящего с определенной частотой, j(А) есть показатель его неожиданности, зависящий от частоты рА, с которой данное событие происходит: j(А) = -log2 рА. Чем ближе частота рА к единице, тем меньше его неожиданность и тем меньшее значение принимает показатель j(А). При приближении рА к нулю, показатель неожиданности возрастает. Тем самым свойства функции j(А) соответствуют содержательному пониманию степени неожиданности наступления события. Значение j(А) можно также назвать частной энтропией НА события А.
Пусть теперь имеются n различных проявлений A1, A2, …, Ak одной случайной величины, каждое из которых возникает с определенной частотой соответственно р1, р2, …, рk. Тогда формула для энтропии принимает вид
Hy = - pi j(А i)
и обозначает усреднение показателей неожиданности возможных проявлений одной случайной величины. Если рассматривать j(А i), как возможные значения одной случайной величины j(А), имеющей распределение pi, i = 1, 2, ..., k, то последнюю формулу можно представить так: Нy = М[j(А)] = М[НА]. Энтропия в таком случае представляет собой математическое ожидание частной энтропии НА.
Перейдем теперь к рассмотрению логических функций.
Пусть x(у) есть функция, значение которой от аргументов sу равно номеру того класса эквивалентности, которому принадлежит кортеж sу. Обозначим через pi долю таких наборов среди всех наборов, что значение функции x(у) равно i, i = 1, 2, …, k. В этом случае будем говорить, что переменные у имеют распределение p1, p2, …, pk. Нетрудно увидеть, что Si=1,k p(i) = 1. Назовем функцией, которая получается из f(y, z) подстановкой вместо аргументов y их значений из i-го класса эквивалентности - соответствующей значению pi. Следовательно, показатель неожиданности -log2 pi зависит от доли наборов, определяемых i-м классом у-эквивалентности. Чем больше наборов определяется i-м классом, тем меньше неожиданность того, что конкретные означивания будут им определяться. В терминах бинарной программы это выглядит так: чем больше путей определяется одним классом у–эквивалентности, тем большая доля вычислений осуществляется промежуточным вычислителем, который соответствует данному классу и ассоциируется с соответствующим узлом у-сечения программы. Логическая энтропия, определяемая переменными у, есть усредненный показатель неожиданности того, что конкретное вычисление будет реализовываться промежуточным вычислителем, соответствующим выделенному классу эквивалентности.