Algorithm for searching prohibitions of boolean functions.pdf Будем обозначать P2(n) множество всех булевых функций от n переменных. Определение 1. Говорят, что булева функция f еР2(n) имеет запрет y1... ym Е Е {0,1}m, если система булевых уравнений f (xi,... ,xra+i-1) = yi, i =1,...,m, (1) несовместна. Если для любых m Е N и y1... ym Е {0,1}m система (1) совместна, то функция f называется функцией без запрета. Определение 2. Графом де Брёйна Gn(f) функции f Е P2(n) называют граф, у которого вершины — это все булевы векторы длины n — 1, а дуги поставлены во взаимно однозначное соответствие всевозможным булевым векторам длины n так, что вектору b1b2 ... соответствует дуга, направленная от вершины b1b2 ... bn-1 к вершине b2b3 ... и помеченная значением f (b1b2 ... bn). Вершину графа Gn(f) назовём особой вершиной типа 5 Е {0,1}, если обе исходящие из неё дуги помечены значением 5. Будем говорить, что вектор y1y2 ... yn является продолжением вектора x1x2 ... xn, если y1... yn-1 = x2 ... xn. Утверждение 1. В графе де Брёйна Gn(f) функции f Е P2(n), n > 1, имеющей запрет, есть хотя бы одна особая вершина. Доказательство. Среди всех запретов функции f выберем любой запрет минимальной длины m. Пусть это есть e1... em. Так как m — минимальная длина запрета, граф Gn(f) является (m — 1)-полным графом де Брёйна, т.е. для любой последовательности y1 ...ym-1 Е {0,1}m-1 существует путь, её несущий. Рассмотрим последовательность e1 ...em-1. Для неё в Gn(f) есть несущий путь, пусть он оканчивается в вершине v. Так как e1... em — запрет, из вершины v нет дуги, помеченной em, т. е. обе исходящие из v дуги имеют значение em и, следовательно, v — особая вершина. ■ Задача 1. Предлагается следующий алгоритм поиска некоторого запрета функции f еР2(п). Пусть Mf0, Mj — множества булевых векторов длины n, на которых функция f принимает значения 0 и 1 соответственно; через S(V) для V С {0,1}n будем обозначать множество всевозможных продолжений векторов из V. Работу алгоритма можно представить как построение следующего двоичного дерева. Вершинам дерева соответствуют множества булевых векторов длины n, дугам — значения 0 и 1. Корню дерева сопоставим множество {0,1}n. На каждом последующем шаге выбирается вершина ветвления, которой приписано множество V наименьшей мощности, если таких вершин несколько, то выбираем любую из них. Из выбранной вершины порождаются два потомка: левому (правому) потомку приписывается множество M° П S(V) (соответственно Mj П S(V)) и ведущая к нему дуга помечается нулём (соответственно единицей). Если некоторой вершине u соответствует пустое множество, то запрет найден — это последовательность меток дуг пути из корня в вершину u. Если вершине u соответствует одноэлементное множество {xl... xn}, то проверяем, является ли вектор x2 ... xn особой вершиной (типа 8) в графе де Брёйна функции f, и если да — запрет найден, это el... em-l8, где el... em-l —последовательность меток дуг пути от корня до вершины u. Эта проверка легко выполняется по вектору значений функции f: вычисляется h = f (x2,... , xn, 0) ф f (x2,... , xn, 1) и, если h = 0, то x2 . . . xn — особая вершина типа f (x2,...,x,n, 0). После каждого ветвления проверяем, есть ли среди полученных вершин неперспективные. Вершина объявляется неперспективной (и ветвление из неё не производится), если её метка (сопоставленное ей множество векторов) совпадает с меткой какой-либо вершины, встречавшейся ранее. Стоит заметить: это не значит, что при ветвлении из неперспективной вершины не будет найден запрет; это будет повторение одних и тех же действий. Для быстрого поиска вершины с заданной меткой будем хранить пройденные вершины в списке, индексированном по мощностям меток. Если на каком-то шаге все вершины дерева объявлены неперспективными, а запрет ещё не найден, то у функции нет запрета. По сравнению с алгоритмом 1, приведённым в [1], этот алгоритм более пригоден для практической реализации, так как в нём все шаги детально проработаны. Задача 2. Для поиска запрета минимальной длины в исходном алгоритме нужно при нахождении запрета не завершать работу, а запомнить запрет и продолжать построение дерева таким же образом, пока не найдётся другой запрет; если он короче имеющегося, то запоминаем его. Дерево строится до тех пор, пока не исключим все вершины. При этом меняется критерий неперспективности вершины: вершина v, метка которой совпадает с меткой встречавшейся ранее вершины u, считается неперспективной в случае, если длина пути от корня до v больше или равна длине пути от корня до u. Для этого в списке пройденных вершин наряду с меткой каждой вершины будем хранить длину пути от неё до корня. Если найден запрет длины l, то все вершины l-го яруса объявляются неперспективными. Задача 3. Назовём запрет тупиковым, если никакое его подслово не является запретом. Задача поиска всех тупиковых запретов до заданной длины l решается так же, как задача 2, но с запоминанием всех найденных запретов. Вершина объявляется неперспективной, если её метка совпадает с меткой предка (в этом случае можем получить запрет, но он не будет тупиковым), или она находится на расстоянии l от корня. Алгоритм поиска произвольного запрета был применён ко всем функциям от 2, 3 и 4 переменных; результаты приведены в табл. 1. Таблица 1 Количество функций, имеющих запрет n Кол-во функций с запретом Кол-во функций без запрета 2 10 6 3 226 30 4 64954 582 В табл. 2 приведены данные о среднем времени работы алгоритма поиска произвольного запрета для функций с количеством аргументов больше 5. Таблица 2 Время работы алгоритма n Среднее время, с n Среднее время, с 5 0,00019 13 0,128 6 0,0004 14 0,307 7 0,00091 15 0,698 8 0,0021 16 1,548 9 0,0047 17 3,461 10 0,011 18 7,552 11 0,025 19 16,528 12 0,061 20 33,312 21 77,999 В дальнейшем предполагается разработать и реализовать алгоритмы решения задач 1-3 с помощью обхода дерева в ширину и в глубину (поиск с возвратом) и сравнить трудоёмкости этих алгоритмов (по количеству построенных вершин дерева и сложности их обработки).

Скачать электронную версию публикации