Монотонная булева функция как определить

Класс М монотонных функций

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

Определение 1. Пусть б=(б₁б₂…б_n) и в=(в₁в₂…в_n) — элементы из В n . Будем говорить, что б предшествует (младше) в, и обозначать бв, если б_k в_k для k=1,2,…,n, причём хотя бы для одного k имеет место строгое неравенство.

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

Вот пара примеров несравнимых между собой векторов.

Из примеров видно, что несравнимые наборы — это те, в которых есть компоненты типа (01) в одном наборе и (10) в другом наборе на соответствующих местах.

Определение 3. Функция f(х₁,…,х_n) называется монотонной (принадлежит классу М), если для любых двух сравнимых между собой наборов б, в В n из того, что б предшествует в, следует, что f(б) не больше f(), то есть бв f(б) f(в).

Если же существует такая пара наборов, что бв, но f(б) > f(в), то функция f(х1,…,хn) — немонотонная По аналогии с непрерывными функциями, которые изучаются в курсе математического анализа, функции алгебры логики можно было бы назвать неубывающими. Но поскольку мы не будем иметь дело с невозрастающими функциями, можно говорить просто о монотонности..

Пример 20. Тождественная функция f(x) = x является монотонной, поскольку б=(0) (1)=в и f(б)=0 < 1=f()

Пример 21. f(x,y) = xy — монотонная функция.

Действительно, наборы (01) и (10) несравнимы, их в расчёт брать не будем. Для других наборов имеем:

(00) (01) и f(0,0)=0 1= f(0,1).

(00)— (11) и f(0,0)=0 1= f(1,1).

(01) (11) и f(0,1)=1 1= f(1,1).

(10)— (11) и f(1,0)=1 1= f(1,1).

Мы убедились, что xy равна 0 лишь на наборе (00), который предшествует всем остальным наборам, так что условие монотонности функции выполняется.

Пример 22. f(x,y)=x&y — монотонная функция, т.к. равна 1 лишь на наборе (11), которому предшествуют все остальные.

Пример 23. Константы 0 и 1 являются монотонными функциями, т.к. для любых наборов будет f(б)=f(в).

Пример 24. f(x)=x’ — немонотонная функция, т.к. при б=(0) и в=(1) имеем бв, но f(б)=1> 0=f(в).

Пример 25. f(x,y)=xy — немонотонная функция.

Но при (00)—- (10) получим

Условие монотонности функции не выполняется!

Пример 26. Определим монотонность функции сложение по модулю 2:

Наборы (01) и (10) несравнимы, их в расчёт брать не будем.

Для других наборов имеем:

(00) (01) и f(0,0)=0 1= f(0,1).

(00)— (10) и f(0,0)=0 1= f(1,0).

(00) (11) и f(0,0)=0 0= f(1,1).

(10) (11) и f(1,0)=1 > 0= f(1,1).

Последнее условие говорит о том, что функция x+y немонотонна.

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

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

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

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.

Русская Википедия : Монотонная булева функция

Монотонная булева функция — булева функция, которая монотонно возрастает (точнее не убывает) по каждому аргументу. Класс всех монотонных булевых функций является одним из пяти предполных классов.

Определение

Булева функция называется монотонной, если из того, что она принимает значение $1$ на некотором наборе аргументов $a$ , следует, что она принимает значение $1$ на всяком наборе аргументов $b$ , который получается из набора аргументов $a$ путём замены произвольного числа нулей на единицы [1] .

Говорят, что набор $\tilde = (\alpha_1, . \alpha_n)$ предшествует набору $\tilde = (\beta_1, . \beta_n)$ , $\tilde \preccurlyeq \tilde (\tilde не больше \tilde ), если \alpha_i \leqslant \beta_i для всех i = 1, . n .$

Если \tilde \preccurlyeq \tilde и \tilde \neq \tilde , то говорят, что набор \tilde строго предшествует набору \tilde , \tilde \prec \tilde .

Наборы \tilde и \tilde называются сравнимыми, если \tilde \preccurlyeq \tilde либо \tilde \preccurlyeq \tilde .

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

Шаблон:РамкаБулева функция $f(\tilde_n)$ называется монотонной, если для любых двух сравнимых наборов $\tilde_n$ и $\tilde_n$ таких, что $\tilde \preccurlyeq \tilde , имеет место неравенство f(\tilde_n) \leqslant f(\tilde_n) . [2] Шаблон:Конец рамки$

Множество всех монотонных функций алгебры логики обозначается через $M$ , а множество всех монотонных булевых функций, зависящих от $n$ переменных $M^$

См. также

Предполные классы
Линейная булева функция

Примечания

Обмен криптовалют — www.bestchange.ru
Криптовалютная биржа Binance
HIVE OS — операционная система для майнинга
e4pool — Мультивалютный пул для майнинга.

AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР;
computeruniverse.net — Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);

DigitalOcean — американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;

Викиум — Онлайн-тренажер для мозга
Like Центр — Центр поддержки и развития предпринимательства.
Gamersbay — лучший магазин по бустингу для World of Warcraft.
Ноотропы OmniMind N°1 — Усиливает мозговую активность. Повышает мотивацию. Улучшает память.
Санкт-Петербургская школа телевидения — это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России.
Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме.
Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео.
Умназия — Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет
SkillBox — это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона.
«Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется.
StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.
Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено.
StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.

↑Капитонова Ю. В., Кривой С. Л., Летичевский А. А. Лекции по дискретной математике. — СПб., БХВ-Петербург, 2004. — ISBN 5-94157-546-7, с 112
↑ «Журавлев Ю. И., Флёров Ю. А., Федько О. С.» Дискретный анализ. Комбинаторика. Алгебра логики. Теория графов : учеб. пособие — М. МФТИ, 2012—248 с. — ISBN 978-5-7417-0423-3

Русская Википедия
Булева алгебра
Страницы, где используется шаблон «Навигационная таблица/Телепорт»
Страницы с телепортом
Википедия
Статья из Википедии
Статья из Русской Википедии

2.2.3.3. Монотонные функции

Наборы (0, 1) и (1, 0) несравнимы. Также несравнимы наборы (0, 1) и ( 1, 1, 0).

Определение. Функция f(x₁, x₂, …, x_n) называется монотонной, если для всяких наборов a = (a₁, …, a_n) и b = (b₁, …, b_n) условие a  b влечет f(a)  f(b).

Утверждение. Функция монотонна тогда и только тогда, когда ее сокращенная ДНФ не содержит отрицаний.

Следствие. Функция монотонна тогда и только тогда, когда ее МДНФ не содержит отрицаний.

Выяснить, являются ли функции монотонными:

f = 00100110;
f = 00110111.

Решение. 1. Сокращенная ДНФ для функции f= 00100110 имеет вид Поскольку сокращенная ДНФ содержит отрицания, то функция не является монотонной. 2. Сокращенная ДНФ для функции f= 00110111 имеет вид Поскольку сокращенная ДНФ не содержит отрицаний, то функция является монотонной. Теорема.КлассM= f|abf(a)f(b)> монотонных функций замкнут относительно суперпозиций.2.2.3.4. Теорема Поста о функциональной полнотеТеорема Поста (признак полноты системы булевых функций).Для того чтобы система булевых функций f₁, …,f_m> была полной, необходимо и достаточно, чтобы для каждого из пяти функционально замкнутых классовT₀,T₁,L,M,Sнашлась хотя бы одна функцияf_iиз системы, не принадлежащая этому классу.Пример. Выяснить к каким функционально замкнутым классам принадлежит булева функция f=01001110, используя теорему Поста. Решение. Строим таблицу значений и треугольник Паскаля (табл. 59): Таблица 59

Слагаемые полинома Жегалкина x₁ x₂ x₃ f g Треугольник Паскаля

1 0 0 0 0 0 f = 0 1 0 0 1 1 1 0

x₃ 0 0 1 1 1 1 1 0 1 0 0 1

x₂ 0 1 0 0 0 0 1 1 1 0 1

x₂x₃ 0 1 1 0 1 1 0 0 1 1

x₁ 1 0 0 1 1 1 0 1 0

x₁ x₃ 1 0 1 1 1 1 1 1

x₁ x₂ 1 1 0 1 0 0 0

x₁ x₂ x₃ 1 1 1 0 0 0

Полином Жегалкина имеет вид: f=x₃+x₂x₃+x₁+x₁x₃.

f(0, 0, 0) = 0fT₀;

f(1, 1, 1) = 1fT₁;

f(0, 0, 0) =f(1, 1, 1), а наборы (0, 0, 0) и (1, 1, 1) являются противоположными, то fS;

так как в полиноме Жегалкина присутствуют слагаемые, представляющие собой конъюнкцию нескольких переменных, то fL;

сокращенная ДНФ функции имеет вид: , так как она содержит отрицания, то fM.

Сведем полученные данные:

T₀ T₁ S L M

f + — — — —

Пример 49. Доказать полноту системы . Решение. Введем обозначения: f₁ = x₁ + x₂, f₂ = x₁  x₂, f₃ = 1. Построим единую таблицу для функций (табл. 60). Таблица 60

Слагаемые № х₁ х₂ f₁ = х₁+х₂  Паскаля f₂ =х₁х₂  Паскаля f₃ =1  Паскаля

1 0 0 0 0 0 1 1 0 0 0 1 1 1 1 1 1 1 1

х₂ 1 0 1 1 1 0 1 1 1 0 0 1 0 0 0

х₁ 2 1 0 1 1 1 1 1 0 1 0 0

х₁х₂ 3 1 1 0 0 1 1 1 0

Полином Жегалкина:

f T₀ T₁ L M S

f₁ + — + — —

f₂ + + — + —

f₃ — + + + —

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

Похожие публикации:

Removable device в биосе что это

Как описать указатель на начало массива

Как писать код на python

Как сделать эхо в сони вегас