Мы рассмотрим несколько подходов к вычислению неопределенности и обсудим их с содержательной точки зрения. Эти обсуждения объясняют причину возникновения такого понятия, как логическая энтропия и проясняют связь настоящего подхода с традиционным подходом в теории информации.
Если полагать, что входные переменные независимы и их значения 0 и 1 одинаково возможны, то возникает представление о неопределенности зависимости выходных значений от входных, как о характеристике y-сечения. Действительно, чем меньше y-сечение, тем больше определенность, какой промежуточный вычислитель будет вычислять выходные значения. В предельном случае, когда сечение содержит в точности один узел, понятно, что все вычисления при любом входном векторе единообразны. Если сечение имеет 2|y| узлов, то неопределенность максимальна, так как имеется возможность выбора из наибольшего числа вариантов вычислений.
Выберем в качестве показателя неопределенности выходных значений в зависимости от входных y, двоичный логарифм от числа узлов y-сечения программы pf. В последующем покажем, что такая мера полезна при исследовании ряда свойств булевских функций.
Рассмотрим простейший случай, когда все входные переменные y не зависимые и существенные. Полагаем, что в y-сечении имеется всего k узлов, каждый его узел соединен с стоком программы одним и тем же числом`t путей и число всех путей программы из истока в сток равно t.
Справедливо равенство log k = log t /`t. Доля путей, проходящих через один узел y-сечения среди всех путей программы pfравна p =`t/t. Тогда log k = - log p. Если обобщить эту формулу, полагая, что доли pi путей, проходящих через i-ый узел y-сечения программы pf в сток различны, и учесть равенство åi=1,k pi = 1, то получим равенство log k = - åi=1,k pi log pi.
Таким образом, получили формулу, выражающую меру неопределенности выходных значений от входных программы pf. Поэтому назовем логической энтропией функции f, определяемой аргументами y, величину
Hfy = -åi=1,k рi log рi.
Если ясно, о какой функции идет речь, то в обозначении энтропии Hfy будем опускать верхний индекс.
Попробуем получить ту же формулу несколько иным путем.
Пусть Nf есть множество всех означиваний логической функции f(x). Если множество x включает два не пересекающихся множества y, z переменных, то представим функцию f(x) в виде f(y, z). Назовем кортеж sy означиваний переменных y y-набором. Для функции f(y, z) определим отношение эквивалентности y-наборов:
s1y » s2y Û f(s1y, z) = f(s2y, z).
При этом говорим, что функция f(s1y, z) определяется тем классом эквивалентности, которому принадлежит y-набор s1y. Так как эквивалентность » определяется разложением функции f(y, z) по переменным y, то назовем ее y –эквивалентностью.
Пусть число всех классов y-эквивалентности равно k: S1, S2, …, Sk, полагаем их все занумерованными, s1y, s2y, …, sky – совокупность представителей всех этих классов и Ni есть множество всех единичных означиваний функции f(siy, z), i = 1, 2, …, k. Назовем множество Si ´ Ni означиваний переменных порождаемым i-ым классом y-эквивалентности. Таким образом, y–эквивалентность определяет разбиение множества Nf на k не пересекающихся подмножеств: Nf = Èi=1,k Si ´ Ni, i = 1, 2, …, k – по числу классов эквивалентности.
Функции f(siy, z), i = 1, 2, …, k, связаны с исходной функцией f(y, z) следующим образом: f(y, z) = Úi=1,k (ys1iÚ ys2iÚ …Ú ysmi) f(si1, z). Здесь s1i, s2i, …, smi – означивания переменных у, составляющие i-ый класс эквивалентности, i = 1, 2, …, k. В определенном смысле, означивания s1i, s1i, …, smi неразличимы, так как в исходной таблице им всем соответствует одна функция f(siy, z), которую обозначим fi(z).
Представим функцию f(y, z) следующим образом:
f(y, z) = Úi=1,k [ysi] f(si1, z),
где квадратными скобками [ysi] обозначены дизъюнкция конъюнктов, определяемых у–наборами из одного класса эквивалентности si = {s1i, s2i, …, smi}, i = 1, 2, …, k. Разлагая аналогично каждую функцию f(si1, z) по переменным z, получим следующее представление
f(y, z) = Úi=1,k j=1,h [ysi] [zlj] f(si1, lj) = Úi=1,k j=1,h [ysi] [zlj] fij.
По определению множества s1, s2, …, sk попарно не пересекаются. С другой стороны, множества l1, l2, …, lh могут пересекаться.