О. Л. КУЗЬМИНА
Научный руководитель – Д. Г. МЕЩАНИНОВ, к. ф.-м. н., доцент
Московский энергетический институт (технический университет)
ОПТИМАЛЬНЫЙ ПОЛИНОМ ЖЕГАЛКИНА,
ДООПРЕДЕЛЯЮЩИЙ ЧАСТИЧНУЮ БУЛЕВУ ФУНКЦИЮ
Рассматривается задача о нахождении доопределения частичной функции, которому соответствует полином Жегалкина наименьший в смысле числа слагаемых. Получен и программно реализован новый алгоритм решения этой задачи, основанный на использовании алгебраической структуры кольца булевых функций, в частности, на использовании явного описания идеалов этого кольца в терминах характеристических функций. Рассмотрен частный случай строения множества неопределенности, позволяющий напрямую вычислить искомое доопределение.
Пусть f(x) – булева функция n переменных, значения которой на произвольном множестве XÌ{0,1}n неизвестны. Пусть также |X| = m. Функцию f(x) можно доопределить 2m различными способами, каждому из которых будет соответствовать некоторый полином Жегалкина [1] определенной длины. При исследовании логических схем, описываемых полиномами Жегалкина, нередко возникает задача о нахождении такого доопределения f(x) на множестве X, которому будет соответствовать полином с наименьшим числом одночленов.
Множество булевых функций является коммутативным кольцом R с единицей. Пусть I(Y) – множество функций из R, равных нулю на Y. Тогда всякий идеал I кольца R имеет вид I(Y) для некоторого YÌ{0,1}n. Сопоставление Y↔I(Y) определяет взаимно однозначное соответствие между идеалами кольца R и подмножествами из {0,1}n. Характеристическая функция подмножества Х есть функция fX такая, что fX принимает значение 1 только на Х. Пусть Y={0,1}n\X. Базис идеала I(Y) как пространства над полем из двух элементов составят характеристические функции fx, точек xÎX. Тогда любые два доопределения функции f(x) отличаются на функцию, являющуюся линейной комбинацией характеристических функций точек xÎX. Следовательно, перебор всех доопределений сводится к перебору 2m линейных комбинация характеристических функций. Будем говорить, что точке x=(x´1,…,x´n) соответствует одночлен полинома Жегалкина gx, если переменная xi входит в gx тогда и только тогда, когда x´i = 1. Введем на множестве одночленов отношение частичного порядка: gx < gy если "i: xiÎgx Þ xiÎgy.
Теорема 1. Полином Жегалкина характеристической функции fx является суммой одночлена gx и всех одночленов gy: gx < gy.
Эта теорема показывает, что полиномы характеристических функций точек можно определить непосредственно.
Также рассматривается частный случай строения множества X. Именно, пусть для всякого хÎХ и всякого уÎ{0,1}n\Х верно, что х>y или х и у несравнимы.
Теорема 2. В этом случае оптимальное доопределение частичной функции может быть найдено по прямым формулам, без использования перебора всех доопределений.
Предлагаемый метод имеет вычислительную сложность порядка (2n + 2m)×2m, что при больших n существенно ниже, чем вычислительная сложность метода, описанного в [1], которая равна O((2n - m)3×2m). Кроме того, предлагаемый метод имеет существенное преимущество перед методом, изложенным в [1], в случае, когда для одного и того же множества переменных рассматриваются различные множества неопределенности X.
Список литературы
1. , «Полиномиальная реализация частичных булевых функций и систем». Москва. 2003.
