Как определить монотонность булевой функции

О порождении булевых функций в предположении монотонности Текст научной статьи по специальности «Математика»

Аннотация научной статьи по математике, автор научной работы — Вороненко А. А., Федорова В. С.

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

i Надоели баннеры? Вы всегда можете отключить рекламу.

Похожие темы научных работ по математике , автор научной работы — Вороненко А. А., Федорова В. С.

О сложности схем в базисах, содержащих монотонные элементы с нулевыми весами
О длине сертификата повторности в некоторых расширенных элементарных базисах
О порождающих системах в классах монотонных функций многозначной логики
Тестирование бесповторных функций в элементарном базисе
О максимальных неразделённых семействах подмножеств
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
i Надоели баннеры? Вы всегда можете отключить рекламу.

On the Boolean function generation under monotonicity

We consider the problem of the possibility of a Boolean function f definition such that for any monotone function g one could produce a number of sets of a given function f so that function g is the only one among the monotone functions matching with f on these sets. It is shown that there are no such functions for the set of all monotone functions. At the same time an example of a sequence of functions, each generating a large number of monotone functions is constructed.

Текст научной работы на тему «О порождении булевых функций в предположении монотонности»

А. А. Вороненко1, В. С. Федорова2

О ПОРОЖДЕНИИ БУЛЕВЫХ ФУНКЦИЙ В ПРЕДПОЛОЖЕНИИ МОНОТОННОСТИ

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

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

Расшифровка функций является ключевой задачей теории алгоритмического обучения, одного из активно развивающихся направлений современной дискретной математики, и заключается в следующем. Пусть фиксирован некоторый класс функций, для определенности булевых, и имеется черный ящик, в котором «содержится» некоторая неизвестная функция из этого класса. Требуется, задавая вопросы типа «Какое значение принимает неизвестная функция на данном входном наборе?», определить, какая именно функция находится в черном ящике? Предполагается, что каждый следующий вопрос может зависеть от ответов на предыдущие. Одной из классических задач такого рода является задача расшифровки монотонных булевых функций, решенная в 1966 г. Ж. Анселем [1]; с тех пор задача рассматривается в различных моделях расшифровки для функций из разных классов.

В данной работе предлагается модель порождения неверного образа дискретной функции на основе неверного предположения о ее свойстве (в данном случае монотонности) и верной информации о ее значениях. Эти результаты могут найти применение в решении задач защиты информации.

Для булевых векторов х = (xi. ,хп) и у = . ,уп) соотношение х ^ у выполняется тогда и только тогда, когда для любого i, 1 ^ г ^ п, выполнено x,i ^yi — Булева функция / называется [2, см., например, с. 17] монотонной тогда и только тогда, когда для любых векторов ж и у, таких, что х ^ у, выполняется соотношение f(x) ^ f(y)- Будем говорить, что (не обязательно всюду определенная) булева функция / порождает монотонную булеву функцию д, если существует такое множество наборов из области определения / (назовем их предъявляемыми наборами), что единственной монотонной функцией, совпадающей с / на этих наборах, является д. Булева функция /, которая порождает все монотонные функции, называется универсальной [3]. Впервые задача об изучении свойств порождения и универсальных функций была поставлена для класса линейных функций в работе [3], где было доказано, что требуемое количество предъявляемых наборов универсальной функции растет линейным образом относительно числа переменных порождаемой функции.

Нижней (верхней) тенью булевого набора х называется множество всех наборов, получаемых из х заменой одной (какой угодно) единицы на ноль (соответственно одного нуля на единицу). Верхним нулем (нижней единицей) монотонной функции / называется набор, на котором функция / равна нулю (соответственно единице), но при этом на всех наборах его верхней (соответственно нижней) тени она равна единице (соответственно нулю).

Теорема 1. Пусть f(xi. ,хт) — произвольная монотонная функция. Не обязательно всюду определенная булева функция g(xi. хт) порождает f(xi. хт) тогда и только тогда, когда g принимает значение 0 на всех верхних нулях f и 1 на всех нижних единицах /.

1 Факультет ВМК МГУ, проф., д.ф.-м.н., e-mail: dm6Qcs.msu.ru

2 Факультет ВМК МГУ, мл. научн. сотр., к.ф.-м.н., e-mail: fedorovavsQcs.msu.ru

* Работа выполнена при поддержке ФЦП «Научные и научно-педагогические кадры инновационной России» на 20092013 годы.

Доказательство. Достаточность. Докажем, что можно так выбрать множество предъявляемых наборов функции д, что для произвольного набора à, такого, что f(â) = a, a G , значение порожденной функции действительно совпадет с а на наборе à. Пусть а = 0. Тогда у монотонной функции / существует верхний ноль ß, такой, что à ^ ß. По условию теоремы g(ß) = 0. Предъявив этот набор д, в предположении монотонности получим f(â) = 0. Случай а = 1 рассматривается аналогично.

Необходимость. Пусть ß — верхний ноль функции f(x\. ,хт) и пусть g(ß) = 1. Наряду с /(ж 1. хт) рассмотрим функцию h(xi. хт), отличающуюся от /(жi. хт) только на наборе ß. Функция h(x 1. ,хт) также монотонна, и f(x\. ,хт) нельзя отличить от нее, предъявляя значения, общие для g и /. Теорема доказана.

Следствие. Универсальных монотонных функций не существует.

Напомним, что вес булевого набора — это число единиц в нем. Введем в рассмотрение симметрическую булеву функцию ш(хi. хп). Пусть здесь и далее п = 2к + 1, если п нечетно, и п 21,- + 2. если п четно. Положим ш <х) = 0, если вес набора х принадлежит множеству <0,1. А; — 1, к + 1>и ш(х) = 1, если вес набора х принадлежит множеству .

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

Лемма 1. Функция ш(хi. ,хп) порождает монотонную функцию f(xi. ,жп), равную нулю на всех наборах веса к — 1 и единице на всех наборах веса к + 2, если f(xi. ,хп) не имеет верхних нулей веса к и все верхние нули f(xi. ,хп) в (к + 1 )-м слое образуют множество, свободное от лунок.

Доказательство. Предъявим все наборы веса к + 2 и к — 1. На них обе функции ш(хi. хп) и f(x 1. ,хп) равны единице и нулю соответственно. В предположении монотонности f(xi. ,хп) данные значения полностью определяют значения этой функции на наборах всех весов, кроме к и к + 1. Предъявим значения ш(х\. хп) на множестве всех верхних нулей f(xi. ,хп) веса к + 1 и все единицы ш(х 1. ,жп), не попадающие в нижнюю тень точек этого множества. В предположении монотонности в силу отсутствия лунок получим искомую функцию f(x 1. ,жп). Лемма доказана.

Расстояние между наборами кода одной лунки не больше четырех и поэтому справедлива следующая

Лемма 2. Код с расстоянием не менее шести свободен от лунок.

Теорема 2. Для некоторой константы с > 0 булева функция ш

Доказательство. Достаточно воспользоваться леммами 1 и 2. Заметим, что двоичный логарифм общего числа кодов с расстоянием шесть не меньше максимальной мощности такого кода. Для ее оценки применим жадный алгоритм [2, см., например, с. 57-58]: на каждом шаге будем добавлять в код произвольный набор веса к + 1, исключая из рассматриваемого множества все наборы, удаленные от него на расстояния два и четыре. Количество таких наборов составляет 0(п4), а количество наборов веса к + 1 составляет fi

1. Hansel G. Sur le nombre des fonctions booléennes monotones de variables // C. R. Acad. Sei. Paris. 1966. 262. P. 1088-1090.

2. Алексеев В. Б. Лекции по дискретной математике. Учеб. пособие. М.: Инфра-М, 2012.

3. Вороиенко А. А. Об универсальных частичных функциях для класса линейных // Дискретная математика. 2012. № 3. С. 62-65.

Поступила в редакцию 07.09.12

ON THE BOOLEAN FUNCTION GENERATION UNDER MONOTONICITY

Voronenko A. A., Fedorova V. S.

We consider the problem of the possibility of a Boolean function / definition such that for any monotone function g one could produce a number of sets of a given function / so that function g is the only one among the monotone functions matching with / on these sets. It is shown that there are no such functions for the set of all monotone functions. At the same time an example of a sequence of functions, each generating a large number of monotone functions is constructed.

Keywords: monotone function, function generation, universal function.

Как определить монотонность булевой функции

Здравствуйте.
Булева ф-я f(x1. xk) задана вектором своих значений (битвектором длины 2^k)).
Они идут по порядку, т.е. в 0-й ячейке будет f(0,0,0..0) в 1-й — от 000..01 во второй — от 000..10 и т.д.
Как проверить на монотонность? (т.е. «неубываемость»?)

Re: Проверка булевой функции на монотонность.

От:	Аноним
Дата:	01.08.10 16:09
Оценка:	-2

U>Здравствуйте.
U>Булева ф-я f(x1. xk) задана вектором своих значений (битвектором длины 2^k)).
U>Они идут по порядку, т.е. в 0-й ячейке будет f(0,0,0..0) в 1-й — от 000..01 во второй — от 000..10 и т.д.
U>Как проверить на монотонность? (т.е. «неубываемость»?)

Для действительной функции двух и более переменных нет понятия монотонность.
Что такое монотонность для булевой функции нескольких переменных, это ещё более загадка.
думаю нужна переформулировка задачи.

Re[2]: Проверка булевой функции на монотонность.

От:	Аноним
Дата:	01.08.10 16:24
Оценка:	-1

Здравствуйте, Аноним, Вы писали:

U>>Здравствуйте.
U>>Булева ф-я f(x1. xk) задана вектором своих значений (битвектором длины 2^k)).
U>>Они идут по порядку, т.е. в 0-й ячейке будет f(0,0,0..0) в 1-й — от 000..01 во второй — от 000..10 и т.д.
U>>Как проверить на монотонность? (т.е. «неубываемость»?)

А>Для действительной функции двух и более переменных нет понятия монотонность.
А>Что такое монотонность для булевой функции нескольких переменных, это ещё более загадка.
А>думаю нужна переформулировка задачи.

а. оказывается есть монотонность для булевой:
http://ru.wikipedia.org/wiki/Булева_функция
это если в дизъюнктивной нормальной форме нет отрицаний переменных.
Но непонятно, это ли имелось ввиду . так как слово неубываемость тут вроде не к месту.

Re: Проверка булевой функции на монотонность.

От:	dilmah
Дата:	01.08.10 18:40
Оценка:

U>Булева ф-я f(x1. xk) задана вектором своих значений (битвектором длины 2^k)).
U>Они идут по порядку, т.е. в 0-й ячейке будет f(0,0,0..0) в 1-й — от 000..01 во второй — от 000..10 и т.д.
U>Как проверить на монотонность? (т.е. «неубываемость»?)

По одному проходу для каждой переменной (при этом максимизируется «локальность» обращений к массиву).
Что-то вроде:

bool is_monotonic(const std::vector& vec) < size_t shift = vec.size(); if ((shift - 1) & shift) < // vector size is NOT a power of 2, bailing out return false; >while ((shift /= 2) > 0) < size_t i = 0; while (i < vec.size()) < for (size_t j = shift; j--; ++i) if (vec[i] >vec[i + shift]) < // monotonicity is violated return false; >> i += shift; > > return true; >

Re: Проверка булевой функции на монотонность.

От:	Кодт
Дата:	01.08.10 19:05
Оценка:

Здравствуйте, ultrator, Вы писали:

U>Булева ф-я f(x1. xk) задана вектором своих значений (битвектором длины 2^k)).
U>Они идут по порядку, т.е. в 0-й ячейке будет f(0,0,0..0) в 1-й — от 000..01 во второй — от 000..10 и т.д.
U>Как проверить на монотонность? (т.е. «неубываемость»?)

Решение за O(2^k * k)

Функция монотонна, когда выполняется условие
f(xxx0xxx) То есть, если для каждого вектора X мы получим множество векторов таких, что некоторые нули из X там заменены на единицы, и проверим соблюдение этого условия f(X) Беда в том, что для O=000. 0 множество таких векторов — это все остальные.
Что делать?

А делать вот что. Проверять не все, а только с изменённым одним битом (итого, не более k).
Ибо,

То есть, по индукции мы охватим всё множество.

Интересно, можно ли быстрее?

Перекуём баги на фичи!
Re[2]: Проверка булевой функции на монотонность.

От:	dilmah
Дата:	01.08.10 19:15
Оценка:	37 (2)

К>А делать вот что. Проверять не все, а только с изменённым одним битом (итого, не более k).
К>Например, k=3.
К>Проверив, что
К>f(000) К>f(000) К>f(000)

код выше именно это и делает. Только порядок циклов у него другой — если сгруппировать эти сравнения так как выше, то доступ в массив будет не очень локален/линеен, поэтому нужно делать по проходу на каждую переменную.
То есть порядок проверок такой:
проход 1
f(000) f(001) f(010) f(011) проход 2
f(000) f(001) f(100) f(101) проход 3
f(000) f(010) f(100) f(110)
Re[2]: Проверка булевой функции на монотонность.

От:	Аноним
Дата:	02.08.10 11:28
Оценка:

Здравствуйте, Кодт, Вы писали:

К>Функция монотонна, когда выполняется условие
К>f(xxx0xxx) К>То есть, если для каждого вектора X мы получим множество векторов таких, что некоторые нули из X там заменены на единицы, и проверим соблюдение этого условия f(X) К>Беда в том, что для O=000. 0 множество таких векторов — это все остальные.
К>Что делать?

К>А делать вот что. Проверять не все, а только с изменённым одним битом (итого, не более k).

Спасибо. Так и делал.
Потом заметил ещё вот что:

вектор f «монотонен» «монотонны» левый и правый полувекторы, и правый >= левого.

На основе этого можно сделать алгоритм, который будет в несколько раз быстрее, но всё равно с O(2^k * k), т.е. не принципиально лучше.

К>Интересно, можно ли быстрее?

Re[3]: Проверка булевой функции на монотонность.

От:	Кодт
Дата:	02.08.10 17:26
Оценка:

Здравствуйте, Аноним, Вы писали:

К>>Интересно, можно ли быстрее?
А>Мне тоже.

Можно посчитать теоретическую оценку.
k-арная функция отображается на 2^k-арный вектор.
Всего k-арных функций — N(k) = 2^(2^k).
Из них, монотонных функций. это числа Дедекинда
M(k) ≈ 2^C(k,k/2)

Из этого следует. следует из этого. Чёрт, всё позабыл!

Помогите описать алгоритм, написанный на С++, на великом и могучем

Рылся в сети в поисках алгоритма программы проверки булевой функции на монотонность, к сожалению, нашёл только на С++, но сам им не владею. Буду очень признателен, если опишите чайнику на доступном языке.

Отслеживать
задан 25 окт 2016 в 20:45
3 2 2 бронзовых знака

лучше приложить картинку нормально, а не через десять кликов и на сайте, на котором ещё и видеореклама, пробивающаяся через фильтры. Но там же в тексте есть описание на русском языке. > Функция монотонна, когда выполняется условие f(xxx0xxx) <= f(xxx1xxx) >То есть, если для каждого вектора X мы получим множество векторов таких, что некоторые нули из X там заменены на единицы, и проверим соблюдение этого условия f(X)

25 окт 2016 в 21:01

Простите за кривую ссылку, поторопился. Так я понимаю такой принцип определения монотонный функции, но мне нужен именно алгоритм описанный кодом (

25 окт 2016 в 21:15

Код написан достаточно просто. Там нет ничего такого, что бы выходило за пределы формулы, описанной выше. Просто в коде пытаются это дело «преждевременно оптимизировать». Или думаете если просто перевести на русский, (if — если и тому подобное), то оно станет проще?

2.3.2. Основные замкнутые классы

А). Обозначим через К0 множество булевых функций F(X1, X2, …, Xn), сохраняющих константу 0, т. е. таких, что F(0, 0, … , 0) = 0.

Такими функциями являются, например, сама константа 0, конъюнкция Х1Х2, дизъюнкция , сумма по модулю два и др..

Не принадлежат классу К0 функции 1, , , и т. д.

Предложение. Класс функций К0 является замкнутым.

Доказательство. Действительно, пусть функция — является композицией функций F0, F1, … , Fs. Тогда , что и требовалось доказать.

Б). Пусть К1 – класс функций F(X1, X2, …, Xn), сохраняющих константу 1, т. е. таких, что F(1, 1, …, 1) = 1.

Например, константу 1 сохраняют функции 1, Х1Х2, , Х, и другие. Не сохраняют константу 1 функции , и т. д..

Предложение. Класс функций К1 является замкнутым.

Доказательство такое же, как и для класса К0.

В). Пусть KS – класс Самодвойственных функций F(X1, X2, …, Xn), т. е. таких, что .

Очевидно, функции и являются самодвойственными. Рассмотрим также . Тогда

— самодвойственная.

В общем случае, самодвойственность функции легко проверять по таблице истинности: если столбец значений, после замены нулей на единицы, единиц на нули и переворачивания, не меняется, то функция – самодвойственная (см. пример в 3).

Предложение. Класс KS является замкнутым.

Доказательство. Пусть функция является композицией самодвойственных функций F0, F1, …, FS. Применяя принцип двойствен-ности, находим

,

Что и требовалось доказать.

Г). Многочлены Жегалкина первой степени, т. е. функции вида , где , называются Линейными функциями. В действительности, линейная функция представляет собой сумму нескольких различных переменных и, возможно, константы

Понятно, что если вместо какой-либо переменной, или переменных подставить линейную функцию, то в результате (после возможных упрощений) снова получится линейная функция, и значит, справедливо

Предложение. Класс KL – линейных функций является замкнутым.

Д). Введём на множестве (Z2)n следующее отношение частичного порядка (свойства рефлексивности, антисимметричности и транзитивности легко проверяются). Если и — два упорядоченных бинарных набора, то положим , если . Если и , то ( как это и принято для отношения частичного порядка) будем писать: .

Определение. Булева функция F(X1, X2, …, Xn) называется монотонной, если для любых бинарных наборов и таких, что выполняется .

Монотонными являются, например функции 0, 1, Xy, . В общем случае, монотонность, функции легко проверить по диаграмме Хассе данного отношения, которая представляет собой N-мерный куб. В вершинах куба запишем соответствующие значения функции. Если найдётся хотя бы одно ребро, в верхней вершине которого записан 0 а в нижней 1, то функция – не монотонная; в противном случае, если, поднимаясь по рёбрам, значение функции не уменьшается, то она – монотонная. Ниже приведены примеры немонотонной функции F(X, Y) (ребро, на котором не выполняется условие монотонности, выделено) и монотонной функции G(X, Y, Z).

F(X, y)