Логическая энтропия
( Logic Entropy
Preprint, Inst. Appl. Math., the Russian Academy of Science)

De non apparetibus et non existentibus eadem est ratio.

О том, чего не видно и о том,

чего не  существует, судят одинаково. (лат.)

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

Более формально это выглядит так.

Пусть булевская функция f(x₁, x₂, …, x_n) служит информационной моделью физической системы. Ее объекты кодируются наборами вида (s₁, s₂, …, s_n) признаков, s_i Î {0, 1}, i = 1, 2, …, n, при котором функция f истинна. Тем самым, число различных объектов не превосходит мощности множества

{(s₁, s₂, …, s_n)| f(s₁, s₂, …, s_n) = 1}

единичных означиваний функции f.

В [1] введено понятие неопределенности физической системы (x₁, x₂, …, x_n), определяемой переменными x₁, x₂, …, x_i, i  n. Аналогично определяется неопределенность ее информационной модели f(x₁, x₂, …, x_n), определяемой переменными x₁, x₂, …, x_i, i  n. Как будет показано неопределенность функции f(x₁, x₂, …, x_n), определяемая переменными x₁, x₂, …, x_i, обладает следующими свойствами.

1.                     Ее значение зависит от числа k подфункций, которые получаются в результате разложения функции по переменным x₁, x₂, …, x_i. При увеличении k (при прочих равных условиях) неопределенность возрастает.

2.                     Неопределенность определяется относительными долями мощностей соответствующих множеств å₁, å₂, .., å_k означиваний переменных x₁, x₂, …, x_i, приводящих к эквивалентным функциям. Если все множества å₁, å₂, .., å_k одинаковы и доля каждого равна 1/k, то неопределенность монотонно возрастает с ростом k.

3.                     При переходе от означивания переменных x₁, x₂, …, x_i, к означиванию переменных x₁, x₂, …, x_i, x_i+1 их неопределенность зависит от неопределенности, определяемой переменными x₁, x₂, …, x_i.

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

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

Пусть f(У, w) есть булевская функция, множество У ее аргументов назовем входными переменными и w – выходными. При определенных значениях s_Y ее входных переменных и s_w - выходных f(s_Y, s_w) = 1. Тем самым, функция f определяет отображение, ставящее в соответствие входным значениям - выходные. В общем случае, один входной кортеж определяет несколько выходных.

Напомним, что логическая функция f(Y, w) представляет вычислимую двоичную функцию j(Y) если: f(Y, w) = 1 ój(Y) = w.

Назовем кортеж s_y означиваний (не обязательно всех) входных переменных y y-набором. Тем самым, для логической функции f(Y, w), представляющей вычислимую функцию, верно, что всякий ее y-набор определяет некоторое множество w-наборов.

Нам потребуется следующее определение.

Бинарной программой p_f для логической функции f(x₁, x₂, …, x_n) называется ор-дерево с единственным корнем (истоком), которому приписана функция f(x₁, x₂, …, x_n), и двумя висячими узлами, одному из которых приписано значение 1 (1-сток), другому 0 (0-сток), а дуги помечены литерами x_i или`x_i, i = 1, 2, …, n. Если два узла сети соединяются путем, дуги которого не содержат ортогональных меток, то назовем его проводящим. Каждый узел дерева достижим из истока. Проводящий путь, дуги которого помечены метками, образующими множество {x_j1^s₁, x_j2^s₂, …, x_jm^s_m} литер, где s₁, s₂, …, s_m Î {0, 1}, назовем определяющим это множество.

Внутренние узлы и дуги программы помечены следующим образом.

1.            Каждой дуге приписана в точности одна литера x_i или`x_i, i = 1,2, …, n.

2.            Из каждого внутреннего узла ведут в точности две дуги, которым приписаны литеры x_i и`x_i, i = 1,2, …, n.

3.            Если в узел N ведет проводящий путь, дуги которого помечены метками x_j1^s₁, x_j2^s₂, …, x_jm^s_m , то этому узлу приписана функция, которая получается из исходной в результате присваивания переменным x_j1, x_j2, …, x_jm  значений соответственно s₁, s₂, …, s_m. Узлы, соответствующие эквивалентным функциям, склеиваются. При этом узлу приписан в точности один представитель класса эквивалентности.

4.            Для каждого из 2ⁿ двоичных наборов s_х переменных имеется путь проводящий из истока либо в 1-сток либо в 0-сток, множество меток дуг которого покрывается компонентами s_х.

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

Пусть функция f(Y, w) представляет вычислимую двоичную функцию j. В бинарной программе p_f каждое вычисление j(s_Y) = s_w представлено единственным путем из истока в сток. Ограничимся рассмотрением программ, для которых все пути из истока на начальных отрезках содержат дуги, помеченные литерами, образованными только из входных переменных y, и после этих отрезков дуг с такими метками не встречается. Такие бинарные программы назовем однородными.

Введем еще одно определение.

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

Применительно к вычислениям, реализуемым бинарными программами, можно говорить о неопределенности выходных значений от входных. Действительно, если задан y-набор s_y, то он задает единственный путь программы p_f из истока в некоторый узел N. Нам удобно мыслить узел N как некоторый промежуточный вычислитель. Он может соединяться со стоком несколькими путями, каждый из которых характеризуется собственными выходными значениями. И только по входным значениям нельзя определить, какой именно выходной вектор появится на выходе такого вычислителя. В связи с этим можно говорить лишь о различении множеств выходных векторов, которые определяются различными узлами y-сечения.

Мы рассмотрим несколько различных подходов к вычислению неопределенности и дадим их содержательные интерпретации. Это прояснит связь настоящего подхода с традиционным в Теории информации.

В последующем, главным образом мы будем рассматривать логические функции, представляющие всюду определенные вычислимые функции. Во избежание путаницы, мы всегда будем указывать, какие логические функции рассматриваем, если это не вытекает из контекста. Очевидно, что если логическая функция f(Y, w) представляет всюду определенную вычислимую функцию j(Y), то при любом y-наборе s_y функция f(s_y, w) не является тождественным нулем. В этом случае j(s_y) = {s_w: f(s_y, s_w) = 1 при любых подстановках на места не означенных переменныъ}.

Если полагать, что входные переменные независимы и их значения 0 и 1 одинаково возможны, то можно говорить о неопределенности зависимости выходных значений от входных, как о характеристике y-сечения. Действительно, чем меньше y-сечение, тем больше определенность, какой промежуточный вычислитель вычислеят выходные значения. В предельном случае, когда сечение содержит в точности один узел, при любом входном векторе все вычисления осуществляются одним вычислителем. Если сечение имеет 2^|y| узлов, то неопределенность максимальна, так как имеется возможность выбора из наибольшего числа доступных вычислителей.

Выберем в качестве показателя неопределенности выходных значений в зависимости от входных y, двоичный логарифм от числа узлов y-сечения программы p_f. Полагаем, что все входные переменные y независимы, y-сечение состоит из k узлов, каждый его узел соединен с истоком одним и тем же числом`t путей и число всех путей программы из истока в y-сечение равно t.

Справедливо равенство log k = log (t /`t ). Доля путей, ведущих в один узел y-сечения среди всех путей программы p<sub>f</sub> из истока в y-сечение равна p<sub>y</sub> =`t /t. Тогда log k = - log p_y. Если предположить, что доли p_y(i) путей, ведущих в i-ый узел y-сечения программы p_f различны, наложив требование, чтобы выполнялось равенство å_i=1,k p_y(i) = 1, то получим более общую формулу - å_i=1,k p_y(i) log p_y(i), которая выражает неопределенность означенных переменных. Еще раз подчернем, что рассматриваемое сечение определяется в результате означивания подмножества входных переменных y. Из этого следует, что

log k - å_i=1,k p_y(i) log p_y(i).

Доля p_y(i) в общем случае зависит от способа построения бинарной программы выше y-сечения. Чтобы в этом убедиться, рассмотрим два примера.

Пример 1. Пусть функция f(x₁, x₂, y₁, y₂, z) =

(x₁`x<sub>2</sub> Ú`x₁`x<sub>2</sub>)(y<sub>1</sub>y<sub>2</sub>Ú`y₁`y<sub>2</sub>)f<sub>1</sub>(z)Ú(`x₁x₂)(y₁y₂Ú`y<sub>1</sub>`y₂)f₁(z)Úx₁x₂(`y<sub>1</sub>y<sub>2</sub>Úy<sub>1</sub>`y₂)f₂(z).

Здесь z – это не пустой набор переменных отличных от x₁,x₂,y₁,y₂. Начальный фрагмент бинарной программы для этой функции приведен на рис.1. Здесь для каждого узла вначале указан его номер, затем (в скобках) - доли путей, ведущих из истока в этот узел, от числа всех приведенных путей. Так в узел 1 ведут два пути, которые получаются в результате означиваний переменных {x₁ = 1, x₂ = 0} и {x₁ = x₂ = 0}. На рис. 1 этим путям соответствует одна дуга, помеченная {x₁`x<sub>2</sub>}È{`x₁`x₂}. Соответствие между меткой дуги и соответствующими означиваниями очевидно. Всего же путей из истока, которые получаются в результате означиваний переменных x₁ и x₂, четыре. Следовательно, доля всех путей из истока в узел 1 среди всех путей равна ½. Аналогично вычисляются доли путей, ведущие в остальные узлы.

Построим для этой функции бинарную программу с другим порядком означиваний переменных, как на рис.2. Видно, что доли путей ведущих в узлы, которым приписаны одинаковые функции для первой программы и для второй (узлы 4 и 5 первой программы  соответствуют узлам 3 и 4 второй) отличаются.

Рис. 1

Рис. 2

Пример 2. Пусть логическая функция  f(x₁, x₂, y₁, y₂, z) =

(x₁`x<sub>2</sub>Ú`x₁`x<sub>2</sub>)(y<sub>1</sub>y<sub>2</sub>Ú`y₁y₂Ú`y<sub>1</sub>`y₂)f₁(z)Ú(`x<sub>1</sub>x<sub>2</sub>)(y<sub>1</sub>y<sub>2</sub>Úy<sub>1</sub>`y₂)f₁(z)Úx₁x₂`y<sub>1</sub>`y₂f₂(z).

Здесь z – это не пустой набор переменных отличных от x₁, x₂, y₁, y₂. Начальный фрагмент бинарной программы для этой функции приведен на рис.3.

Рис. 3

Рис. 4

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

Введем ряд определений.

Пусть i-ый узел y-сечения соединен N_yz|y(j₁|i), N_yz|y(j₂|i), …, N_yz|y(j_k|i) путями в точности с узлами соответственно j₁, j₂, …, j_k yz-сечения и N_yz = N_yz|y(j₁|i) + N_yz|y(j₂|i) + …+ N_yz|y(j_k|i) – это число всех путей, ведущих из i-го узла в yz-сечение. Тогда величина p_yz|y(j_s| i) = N_yz|y (j_s| i)/N_yz – есть доля путей, ведущих из i-го узла y-сечения в j_s-ый узел yz-сечения, s = 1, 2, …, k среди всех путей из i-го узла y-сечения в yz-сечение. Понятно, что å_s=1,k p_yz|y(j_s| i) = 1, так как j₁, j₂, …, j_k – это все узлы yz-сечения, в которые имеются пути из i-го узла y-сечения.

Пусть в бинарной программе i-ый узел y-сечения соединен путями в точности с узлами j₁, j₂, …, j_k yz-сечения; h₁, h₂, …, h_m – суть все узлы yzu-сечения, в которые мы попадаем из узлов j₁, j₂, …, j_k yz-сечения (см.рис.5). Тем самым из i-го узла y-сечения в узлы h₁, h₂, …, h_m yzu-сечения мы можем попасть только через какой-либо узел из j₁, j₂, …, j_k yz-сечения.

Рис.5

Из определения следует равенство:

å_t=1,k p_yzu|yz(h_s | j_t) p_yz|y(j_t | i) = p_yzu|y(h_s | i).

Действительно, i-ый узел y-сечения соединен путями с узлами j₁, j₂, …, j_k yz-сечения и доля таких путей, ведущих в j_t–ый узел равна p_yz|y(j_t | i). В свою очередь j_t–ый узел соединен с некоторыми узлами из совокупности h₁, h₂, …, h_m yzu-сечения, причем доля таких путей, ведущих из j_t–го узла в h_s-ый узел равна p_yzu|yz(h_s | j_t). Но тогда доля путей из i-го узла y-сечения в h_s-ый узел yzu-сечения равна указанной сумме. 

Справедливы следующие равенства:

å_s=1,m p_yzu|y(h_s | i) = 1; å_t=1,k p_yz|y(j_t | i) = 1; å_s=1,m p_yzu|yz(h_s | j_t) = 1, t = 1, 2, …, k.

Последнее равенство выполняется для тех пар узлов, которые соединены путями.

Теорема 1. Для  всяких, не пересекающихся множеств y, z, u  аргументов имеет место равенство å _{t=1,k, s=1,m} p_yzu|yz(h_s|j_t) p_yz|y(j_t|i) = 1.

Доказательство. По определению å_t=1,k p_yz|y(j_t | i) = 1.

Для каждого из узлов j₁, j₂, …, j_k yz-сечения имеем равенство å_s=1,m p_yzu|yz(h_s | j_t) = 1, t = 1, 2, …, k.

Умножая каждый член первой суммы на å_s=1,m p_yzu|yz(h_s | j_t), получаем равенство å_s=1,m å_t=1,k p_yzu|yz(h_s | j_t) p_yz|y(j_t | i) = 1.

Теорема доказана.

Определим рекурсивно величину p_z(i) как долю путей, проходящих из истока в i-ый узел z-сечения бинарной программы.

Пусть z = z₁z₂…z_m – последовательность аргументов и однородная бинарная программа имеет z₁-сечение, z₁z₂-сечение, …, z₁z₂…z_m-сечение, причем множества путей заданы следующими значениями: N_{z1z2…zm| z1z2…zm-1}(i| j_m-1), N_{z1z2…zm-1| z1z2…zm-2}(j_m-1| j_m-2), …, N_{z1z2| z1} (j₂| j₁), N_z1(j₁) при соответствующем именовании узлов сечений. Нетрудно увидеть, что число N_z1z2…zm(i) всех путей из истока программы в i-ый узел z-сечения равно сумме

å_{j1,j2,…,jm-1}N_{z1z2…zm|z1z2…zm-1}(i|j_m-1) N_{z1z2…zm-1|z1z2…zm-2}(j_m-1|j_m-2)…

… N_{z1z2| z1}(j₂| j₁) N_z1(j₁),

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

å_jm-1 N_{z1z2…zm| z1z2…zm-1}(i| j_m-1) N_z1z2…zm-1 (j_m-1).

Здесь N_z1z2…zm-1 (j_m-1) – это число путей, ведущих из истока в j_m-1-ый узел z₁z₂…z_m-1-сечения.

Обозначим N_z общее число различных путей из истока в z-сечение и разделим каждый член последней суммы на величину N_z. Тогда отношение 

N_{z1z2…zm| z1z2…zm-1}(i| j_m-1) N_z1z2…zm-1(j_m-1)/N_z

представляет собой долю всех путей из истока в i-ый узел z-сечения, проходящих через j_m-1-ый узел  z₁z₂…z_m-1-сечения среди общего множества путей из истока в z-сечение.

Доля p_z1z2…zm-1(j_m-1) путей из истока в z₁z₂…z_m-сечение, проходящих через узел j_m-1 z₁z₂…z_m-1-сечения также определяется общим числом таких путей среди остальных, ведущих в  z₁z₂…z_m-сечение. Причем только часть p_{z1z2…zm| z1z2…zm-1}(i| j_m-1) из них ведет далее в i-ый узел z₁z₂…z_m-сечение. Эти рассуждения позволяют ввести такое индуктивное определение.

Базис конструкции. Если множество аргументов пусто, то p_l(1) = 1. В этом случае узел l-сечения - это исток бинарной программы.

Индуктивное построение. Пусть для некоторой последовательности z аргументов p_z(j) есть доля путей из истока в j-ый узел z-сечения, y – это новая переменная и p_zy|z(i | j) – доля путей, ведущих из в j-го узла z-сечения в i-ый узел zy-сечения. Тогда p_zy(i) = å_j p_zy|z(i | j) p_z(j).

Это определение распространяется на произвольные множества аргументов y и z следующим образом.

p_yz(i) = å_j p_yz|y(i | j) p_y(j).

Пусть z = z¢ u и мы уже получили, что p_yz¢(h) = å_j p_{yz¢ |y}(h | j) p_y(j). По определению

p_yz¢u(i) = å_h=1,q p_{yz¢u |yz¢}(i | h) p_yz¢(h) = å_h=1,q p_{yz¢u |yz¢}(i | h) å_j=1,k p_{yz¢ |y}(h | j) p_y(j) =

å_h=1,q,j=1,k p_{yz¢u |yz¢}(i | h) p_{yz¢ |y}(h | j) p_y(j).

Известно, что å_h=1,q p_{yz¢u |yz¢}(i | h) p_{yz¢ |y}(h | j) = p_{yz¢u |y} (i | j). Следовательно,

p_yz¢u(i) = å_j=1,k p_{yz¢u |y} (i | j) p_y(j).

Справедливо утверждение.

Теорема 2. Справедливо равенство å_i=1,h p_z(i) = 1, где суммирование ведется по всем узлам z-сечения.

Доказательство. Пусть p_u(j) есть известная доля путей из истока в узел j  u-сечения, y – это переменная, z = uy и å_j=1,k p_u ( j) = 1. По определению, p_uy(i) = å_j=1,k p_uy|u(i | j) p_u(j), где p_uy|u(i | j) – относительная доля путей, ведущих из j-го узла u-сечения в i-ый узел uy-сечения. Следовательно, произведение p_uy|u(i | j) p_u(j) есть доля путей из истока в в i-ый узел uy-сечения, проходящих через j-ый узел u-сечения.

å_i=1,h p_uy(i) = å_i=1,h å_j=1,k p_uy|u(i | j) p_u(j) = å_j=1,k(å_i=1,h p_uy|u(i | j)) p_u(j) = å_j=1,k p_u(j) = 1.

При доказательстве мы использовали равенства å_i=1,h p_uy|u(i | j) = 1 и å_j=1,k p_u(j) = 1.

Теорема доказана.

Назовем логической энтропией функции f, определяемой переменными y, величину

H^f_y = -å_i=1,k p_y(i) log p_y(i),

где суммирование ведется по всем узлам y-сечения.

Из определения логической энтропии следует, что в общем случае ее значение зависит от порядка означивания переменных y в бинарной программе. Это поясняют примеры 1 и 2. Опишем класс логических функций, для которых логическая энтропия H^f_y определяется лишь видом множества y переменных и не зависит от порядка их означивания.

Справедливо следующее утверждение.

Лемма 3. Пусть f(x, w) представляет всюду вычислимую функцию w = (x) и y  x. Тогда разложение этой функции по переменным y приводит к одному выражению с точностью до перестановки конъюнктивных и дизъюнктивных членов.

Доказательство следует из того, что при любом означивающем y-наборе s_y в разложении присутствует конъюнкция, первым членом которой является конъюнкт y^sy и вторым функция, которая получается из f(x, w) в результате этого означивания.

Теорема 4. Значение H^f_y не зависит от порядка означиваний переменных y, а определяется только множеством y.

Из этого следует, что логическая энтропия H^f_y функции f(Y, w), представляющей физическую систему w = (Y), где  - всюду определенная функция совпадает с ее энтропией, определяемой переменными y, как она введена в [1]. 

Если же функция f(Y, w) представляет не всюду определенную вычислимую функцию, то логическая энтропия зависит от порядка означивания переменных.

Если ясно, о какой функции идет речь, то в обозначении H^f_y будем опускать верхний индекс.

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

Определим по функции f(y, z) отношение y–эквивалентности y-наборов:

s¹_y » s²_y Û f(s¹_y, z) = f(s²_y, z).

При этом говорим, что функция f(s¹_y) определяется тем классом эквивалентности, которому принадлежит y-набор s¹_y.

Пусть число всех классов y-эквивалентности равно k: s¹, s², …, s^k; s¹₁ Î s¹, s²₁ Î s², …, s^k₁ Î s^k суть представители этих классов и  есть множество всех единичных означиваний функции f(sⁱ_y, z), i = 1, 2, …, k. Назовем множество sⁱ ´  означиваний - порождаемым i-ым классом y-эквивалентности. Пусть  есть множество всех единичных означиваний функции f(y, z). Тогда y–эквивалентность определяет разбиение множества  на k не пересекающихся подмножеств:  = È_i=1,k sⁱ ´ , i = 1, 2, …, k – по числу классов эквивалентности.

Функции f(sⁱ_y, z), i = 1, 2, …, k, связаны с исходной функцией f(y, z) очевидным образом:

f(y, z) = Ú_i=1,k (y^s₁ⁱÚ y^s₂ⁱÚ …Ú y^s_mⁱ) f(sⁱ₁, z).

Здесь s₁ⁱ, s₂ⁱ, …, s_mⁱ – означивания переменных у, составляющие i-ый класс эквивалентности, i = 1, 2, …, k, они определяют одну функцию f(sⁱ₁, z), (обозначим её f_i).

Представим функцию f(y, z) следующим образом:

f(y, z) = Ú_i=1,k [y^si] f_i,

где [y^si] обозначает дизъюнкцию конъюнктов, определяемых всеми у–наборами одного класса эквивалентности sⁱ = {s₁ⁱ, s₂ⁱ, …, s_mⁱ}, i = 1, 2, …, k.

Разлагая каждую функцию f(sⁱ₁, z) по переменным z, получим равенство

f(y, z) = Ú_{i=1,k j=1,h} [y^si] [z^lj] f(s₁ⁱ, l₁^j) = Ú_{i=1,k j=1,h} [y^si] [z^lj] f_ij.

Сокращенно это разложение обозначим так: f(y, z) =  Ú_{i=1,k j=1,h} [y^siz^lj] f_ij. Множества s¹, s², …, s^k попарно не пересекаются, но множества l¹, l², …, l^h  могут пересекаться.

Мы рассматриваем логические функции, представляющие лишь всюду определенные вычислимые функции. Поэтому каждая функция  f_ij не равна тождественному нулю, i = 1, 2, …, k, j = 1,2, …, h. Несколько различных пар (i, j) индексов могут определять эквивалентные логические функции f_ij. Перечислим все классы yz-эквивалентности. Пусть t-ый класс yz-эквивалентности характеризуется множеством {(i, j₁), (i, j₂), …, (i, j_q)} пар индексов в разложении функции f(y, z). Тогда мы говорим, что t-ый класс yz-эквивалентности порожден i-ым классом y-эквивалентности.

Разложение функции f(y, z) по переменным y и z, можно представить ее в виде матрицы M_f, как на рис.5.

Рис. 5

Здесь f_ij обозначает функцию f(s₁ⁱ, l₁^j), i-ая строка соответствует i-му классу y-эквивалентности, i=1, 2, …, k, j-ый столбец - j-му классу z-эквивалентности, j=1, 2, …, h. В общем случае нескольким парам (i, j), где i – номер столбца и j – номер строки, может соответствовать один класс эквивалентности yz-наборов. Но число классов yz-эквивалентности не больше числа таких различных пар. Все порожденные одним i–м y-классом yz-классы характеризуются эквивалентными функциями из одной i–ой строки.

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

Определим p_yz|y(j|i) как условную долю j-го yz-класса, порожденного i-м y-классом среди всех yz-классов, порожденных i-м y-классом. Из разложения функции f по переменным и определения бинарной программы понятно, что все введенные ранее равенства относительно условных и абсолютных долей сохраняются при новой интерпретации. В частности, определение абсолютной доли p_y(i) i-го y-класса среди остальных y-классов выглядит так.

Базис конструкции. При пустом множестве аргументов имеется единственный класс эквивалентности, который определяется самой функцией f и поэтому доля его p_l(1) = 1.

Индуктивное построение. Пусть для некоторой последовательности z аргументов p_z(j) есть доля j-го класса z-эквивалентности среди остальных z-классов, y – это новая переменная и p_zy|z(i | j) – доля i-го zy-класса среди всех zy-классов, порожденных j-м z-классом. Тогда p_zy(i) = å_j p_zy|z(i | j) p_z(j).

Рассмотрим однородную бинарную программу p_f для функции f(y). Пусть N₁, N₂, …, N_k – суть все узлы y-сечения и Т₁, Т₂, …, Т_k – совокупности путей, проходящих из истока программы в узлы соответственно N₁, N₂, …, N_k, причем мощности множеств Т₁, Т₂, …, Т_k равны соответственно t₁, t₂, …, t_k и t = å_i=1,k t_i. Каждый узел N_i соответствует, с одной стороны, в точности одному классу у-эквивалентности, а с другой, - единственной логической функции, определяемой всяким у-набором из этого класса у-эквивалентности. По определению, доля p_y(i) всех наборов, определяемых одним классом у-эквивалентности, соответствующего узлу N_i, совпадает с долей p_y(i) путей из истока в i-ый узел y-сечения. i = 1, 2, …, k.

При таком определении абсолютной доли, выполняется теорема, аналогичная Теореме 1.

Теорема 5. Имеет место равенство å_i p_z(i) = 1.

Если мы рассматриваем логические функции, представляющие всюду определенные вычислимые функции, то верно следующее утверждение.

Лемма 6. Пусть p_y(i) есть доля i-го класса y-эквивалентности, q_z(j) – доля j-го класса z-эквивалентности. Тогда доля yz-наборов, которые характеризуются принадлежностью y-наборов i-му классу y-эквивалентности и z-наборов j-му классу z-эквивалентности среди всех yz-наборов равна произведению р_y(i)q_z(j),  i = 1, 2,…, k, j = 1, 2, …, h.

Доказательство. Все логические функции f_ij, i=1, 2, …, k, j=1, 2, …. h не являются тождественно нулевыми. Следовательно, для каждого y-набора s_rⁱ Î sⁱ и для каждого z-набора l_q^j Î l^j все конъюнкты вида y^sriz^lqj входят в разложение исходной функции.

Лемма доказана.

С другой стороны, если рассматривать логические функции, представляющие не всюду определенные функции, то утверждение места не имеет. Действительно, в этом случае некоторые функции матрицы M_f могут быть тождественно нулевыми и, следовательно, для y-набора s_rⁱ Î sⁱ для некоторых z-наборов l_q^j Î l^j конъюнкты вида y^sriz^lqj могут не входить в разложение исходной функции. Следовательно, не все yz-наборы, у которых y-наборы из класса sⁱ, характеризуются принадлежностью z-наборов какому-либо классу z-эквивалентности.

Сложность зависимости функции f(y) от переменных y характеризуется фактор-множеством у-эквивалентности. Действительно, чем больше фактор-множество, тем больше различных подформул встречается в разложении логической функции по этим переменным. В терминах бинарной программы мощности фактор-множества у–эквивалентности соответствует число узлов у–сечения.

Если p_y(i) есть доля путей, проходящих из истока в i-ый узел y-сечения, то обратная величина t_y(i) = 1/ p_y(i) пропорциональна числу путей, ведущих из истока в этот узел, i = 1,2, …, k. å_i=1,k p_y(i) log t_y(i) есть математическое ожидание случайной величины log t_y(i), i = 1,2, …, k, с распределением p_y(i).

Введем следующее определение.

Эффективной пропускной способностью одного узла у–сечения бинарной программы назовем величину t, такую, что log t = å_i=1,k p_y(i) log t_y(i). Таким образом, эффективную пропускную способность можно представлять как математическое ожидание величины, пропорциональной числу путей, проходящих через один узел y-сечения. Поэтому эффективная пропускная способность отличается от «реальной» некоторой аддитивной константой. Если доли p_y(i) одинаковы, то log t = log`t . В этом случае эффективная пропускная способность совпадает с числом путей из истока, которые проходят через один узел y-сечения.

Введем величину t = å_i=1,k t_y(i) которая пропорциональна общему числу путей, ведущих из истока в y-сечение. Величину Н_y = log (t/t) назовем эффективным у–сечением. Тем самым эффективное у–сечение есть мера сложности бинарной программы, расположенной выше у–сечения: при большем эффективном сечении Н_y и при постоянном числе всех путей из истока в у–сечение, среднее число путей, проходящих через один узел сечения, мало, а число узлов в сечении - велико. Но чем шире у–сечение, тем сложнее зависимость логической функции от переменных у, так как число различных подформул, участвующих в разложении функции по переменным у  больше. Поэтому зависимости исходной функции от переменных у выражается сложнее.

Н_y = log (t/t) = log t – log t = log t – å_i=1,k p_y(i) log t_y(i)

= -å_i=1,k (t_y(i)/t) log (t_y(i)/t) = -å_i=1,k p_y(i) log p_y(i).

Как видно, величина эффективного y-сечения и энтропии логической функции совпадают. Заметим, что энтропия получена из определения неопределенности выходных значений от входных, а эффективное сечение получено из анализа сложности зависимости функции от ее аргументов.

2. Некоторые интерпретации логической энтропии. Поясним с содержательной точки зрения понятие логической энтропии.

Пусть f(y, z) есть логическая функция и x(у) есть функция, значение которой от аргументов s_у равно номеру того класса у-эквивалентности, которому принадлежит кортеж s_у. Обозначим долю таких y-наборов, при которых значение функции x(у) равно i, i = 1, 2, …, k, среди всех наборов через p_i. Будем говорить, что переменные у имеют распределение p_у(1), p_у(2), …, p_у(k). Понятно, что S_i=1,k p_у(i) = 1. Назовем функцию, которая получается из f(y, z) подстановкой y–наборов из i-го класса эквивалентности - соответствующей значению p_i. Следовательно, показатель неожиданности -log₂ p_i функции x(у) зависит от доли наборов, определяемых i-м классом у-эквивалентности. Чем больше наборов в i-м классе, тем меньше неожиданность того, что конкретное означивание ему принадлежит. В терминах бинарной программы это выглядит так: чем больше путей определяется одним классом у–эквивалентности, тем большая доля вычислений осуществляется промежуточным вычислителем, который соответствует данному классу и ассоциируется с соответствующим узлом у-сечения программы. Логическая энтропия, определяемая переменными у, есть усредненная неожиданность того, что конкретное вычисление будет реализовываться промежуточным вычислителем, соответствующим конкретному классу у-эквивалентности (в терминах бинарной программы – некоторому узлу y-сечения).

В теории информации энтропия служит мерой свободы системы: чем больше у системы степеней свободы, т.е. чем меньше на нее наложено ограничений, тем больше ее энтропия. Поэтому энтропия максимальна при одинаковой доле наблюдаемых событий, а всякое отклонение от него приводит к ее уменьшению. В пределе, когда доля одного события равна 1, энтропия равна нулю. Применительно к логической энтропии, под степенями свободы понимается число классов у-эквивалентности. Чем их меньше, тем больше определенность, какой промежуточный вычислитель используется для продолжения вычисление. И наоборот, чем больше классов эквивалентности и чем однороднее доли p₁, p₂, …, p_k, тем больше возможностей для выбора того или иного промежуточного вычислителя и, следовательно, больше неопределенность.

В терминах сложности логической функции эти рассуждения выглядят так: если переменные y определяют небольшое фактор-множество, то они описывают лишь небольшое число различных свойств логической функции. Очевидно, что для описания небольшого числа свойств требуется меньше параметров (в нашем случае - аргументов) и наоборот, чем разнообразнее проявления системы, тем больше параметров необходимо для ее описания. При прочих равных условиях, более сложная система наблюдателю кажется менее определенной и наоборот, чем больше определенности у наблюдателя, тем проще зависимость демонстрируемого поведения системы от входных параметров. В данном контексте под сложностью зависимости системы от аргументов y понимается число классов у-эквивалентности. Это согласуется с определением неопределенности функции от переменных у, как сложности зависимости от этих аргументов. Чем меньше классов у-эквивалентности, тем, с одной стороны, меньше средний показатель неожиданности, а с другой, - тем проще выражается зависимость функции от этих аргументов. Если же классов эквивалентности много, то больше средний показатель неожиданности и функция сложнее зависит от аргументов у. Тем самым, чем больше энтропия Н_y, тем сложнее выражается зависимость функции от аргументов у и наоборот.

Приведем теперь интерпретацию логической энтропии с позиций статистической модели равновероятных последовательностей. Для этого представим логическую функцию f(y, z) таблицей истинности, в которой приведены лишь ее единичные означивания. Разложение по y выглядит следующим образом:

f(y, z) = Ú_i=1,k [y^si] f(sⁱ₁, z).

Полагаем, что все переменные y случайны и независимы, и p_y(i), i = 1, 2, …, k, есть доля наборов, включающих y-поднаборы из i-го класса y-эквивалентности в достаточно большом случайно порожденном множестве единичных означиваний, мощность которого равна N. Тогда число наборов, обладающих y–поднаборами из i-го класса y-эквивалентности, равно N_i = N p_y(i).

По закону больших чисел во всяком достаточно большом подмножестве единичных означиваний доля означиваний, порожденных i-м классом y-эквивалентности совпадает с p_y(i), i = 1, 2, …, k и доли наборов, порожденных каждым из k классов y-эквивалентности, не зависят от вида множества единичных означиваний. Поэтому из N наборов N_i = N p_y(i) порождены i-м классом и вероятность выбора такого множества единичных означиваний, которая характеризуется распределением p_y(i), i = 1, 2, …, k, по классам y-эквивалентности, равна q = p_y(1)^N1p_y(2)^N2 … p_y(k)^Nk = (p_y(1)^p_y⁽¹⁾p_y(2)^p_y⁽²⁾ … p_y(k) ^p_y^(k))^N. Неопределенность H^* всего множества единичных означиваний равна - log q. Поэтому H^* = -N å_i=1,k p_y(i) log p_y(i). Но тогда -å_i=1,k p_y(i) log p_y(i) = H^*/N представляет собой среднюю неопределенность, которая приходится на единственное единичное означивание.

Тем самым, получили еще одну  интерпретацию логической энтропии: формула -å_i=1,k p_y(i) log p_y(i) определяет среднюю неопределенность, которая приходится на одно единичное означивание функции f(y, z), если их классификация осуществляется с помощью y-эквивалентности при достаточно большом числе независимо порожденных единичных означиваний.

Наконец, еще одна трактовка логической энтропии основывается на следующих рассуждениях.

Пусть y-эквивалентность порождает k классов. Присвоим каждому из N единичных означиваний функции f(y, z) номер того класса из {1, 2, …, k}, порождением которого он является. Число различных перестановок N единичных означиваний из которых N_i = N p_i обладают номером i, равно

.

Тогда энтропия этого случайного множества

H* = log M = log N! - å_i=1,k log N_i!.