Монотонность функции мат логика

Определение. Булева функция f(x1, …, xn) называется монотонной (принадлежит классу M), если для любой пары наборов α и β таких, что αβ, выполняется условие f(α)≤ f(β) (назовем его условием монотонности).

Примеры. Исследуем мажоритарную булеву функцию.

Перебор пар начнем с наборов α=000 и β=001: для них αβ и выполнено условие монотонности f(000)=f(001). Отметим, что набор α таков, что любой другой набор β является последователем α, и, казалось бы, следует анализировать каждую из этих пар. Однако f(α)=0, поэтому условие f(α)≤ f(β) будет выполнено для любого набора β. Значит, в качестве α достаточно рассмотреть лишь те наборы, на которых функция принимает значение единица: 011, 101, 110 и 111. Кроме того, наборы в таблице истинности расположены в естественном порядке, значит, наборы –последователи лежат ниже предшественников. Набор α=011 имеет единственного последователя β=111 и f(011)=f(111), то есть условие монотонности для этой пары не нарушено. Рассмотрим остальные возможные пары наборов: α=101, β=111 и α=110, β=111 (набор α=111 последователей не имеет). Для них условие монотонности также не нарушено. Значит, мажоритарная функция монотонна.

Из элементарных булевых функций монотонными являются, например, конъюнкция и дизъюнкция. Не являются монотонными, например, штрих Шеффера и стрелка Пирса. •

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

Утверждение о условии немонотонности. Для любой пары наборов α и β таких, что αβ и f(α) > f(β), найдется пара соседних наборов α’, β’ с теми же свойствами: α’β’ и f(α’) > f(β’).

Доказательство. Если α и β – соседи, то утверждение верно (α’=α, β’=β). Иначе вычислим расстояние d (по Хэммингу) между наборами α=a1… an и β=b1… bn и начнем строить цепочку наборов γ, …, γd такую, что

и любые два расположенных рядом набора γi –1i (i=1, …, d) являются соседями. Очередной набор γi получим из предыдущего набора γi –1 заменой значения одной из ортогональных компонент наборов γi –1 и β (это будет замена 0 на 1, так как αβ), затем проверим условие немонотонности f(γi –1)>f(γi). Если оно выполнено, утверждение доказано (α’=γi –1, β’=γi). Иначе получим и исследуем очередной набор. В худшем случае, когда постоянно выполняется условие монотонности, имеем

Читайте также:  Можно ли смотреть dvd на ps4

но тогда f(γd –1)=1 и f(β)=0, значит, условие немонотонности выполнится для последней пары: α’=γd –1 и β’=γd=β. •

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

Если f(α)>f(β), то смена значения функции с 1 на 0 произойдет по крайней мере на одной из четырех пар соседей. •

Алгоритм распознавания монотонной булевой функции (основан на утверждении о условии немонотонности).

Начало. Задана таблица истинности булевой функции.

Шаг 1. Сравниваем значения функции на наборах, соседних по первой переменной, то есть верхнюю половину столбца значений функции (вектор φ1) с нижней половиной (вектор φ1). Если условие φ1φ1 нарушено, то функция не монотонна, идем на конец.

Шаг 2. Сравниваем значения функции на наборах, соседних по второй переменной, то есть верхние четвертины столбца значений функции (векторы φ’2, φ”2) с нижними четвертинами (векторами φ’2, φ”2) в каждой половине. Если хотя бы одно из условий φ’2φ’2 и φ”2φ”2нарушено, то функция не монотонна, идем на конец.

Шаги 3 –n. Аналогично сравниваем восьмые, шестнадцатые части, и так далее. Если ни одно из проверяемых условий не нарушено, то функция монотонна.

Примеры. Рассмотрим две булевых функции (первая – мажоритарная).

Проверим на монотонность мажоритарную функцию. Сравниваем половины столбца значений: φ1=0001 0111=φ1. Сравниваем четвертины: φ’2=00 01=φ’2, φ”2=01 11=φ”2. Сравниваем осьмушки: 0 0 , 0 1, 0 1 , 1 1 . Следовательно, мажоритарная функция монотонна.

Проверим на монотонность функцию g(x,y,z). Сравниваем половины столбца значений: φ1=0110 0111=φ1. Сравниваем четвертины: так как φ’2=01 не предшествует φ’2=10, функция g(x,y,z) не монотонна. •

Теорема о замкнутости класса M. Множество всех монотонных булевых функций является замкнутым классом.

Доказательство. Рассмотрим суперпозицию любых булевых функций из M, то есть функцию

и покажем, что она монотонна. Подставим в суперпозицию любую пару наборов α и β таких, что αβ, получим:

где γ и δ – булевы векторы. Так как αβ, и булевы функции f1(x1, …, xn), …, fm(x1, …, xn) монотонны, то γδ. Поскольку функция f(y1, …, ym) также монотонна, то f(γ)≤ f(δ), следовательно, f(α)≤ f(β), то есть f(x1, …, xn) монотонна, и класс M замкнут. •

Читайте также:  Метод решения задачи целочисленного программирования

Лемма о немонотонной булевой функции. Если булева функция немонотонна, то из нее подстановкой вместо аргументов констант 0 и 1 и переменной x можно получить инверсию переменной x .

Доказательство. Рассмотрим немонотонную функцию f(x1, …, xn). Согласно утверждению о условии немонотонности, существует пара соседних наборов α=a1… an и β=b1… bn таких, что αβ и f(α) > f(β), то есть

Пусть α и β – соседи по k –й компоненте, тогда

Подставим в функцию f(x1, …, xn) вместо каждого аргумента xi либо константу ai, если i ≠ k, либо переменную x, если i = k (подстановка константы и переменной допустима по условию теоремы). В результате получим функцию одного аргумента

Покажем, что g(x)= x :

Итак, инверсия x получена. •

Пример. Рассмотрим функцию f(y,z) = y ↓ z.

Она немонотонна, так как существует пара наборов α=00 и β=10 таких, что αβ и f(α)>f(β). Так как α и β – соседи по первой компоненте, то, согласно доказательству леммы, положим y=x и подставим вместо z константу 0, получим:

Определения и примеры

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

На множестве B=0,1 введём полный порядок: будем считать, что 0 n .

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

Пример. б=(001100), в=(001110); б11, б22, б33, б44, б5 n сравнимы. Поэтому не надо путать частичный порядок на В n с полным упорядочением, которое использовалось при задания булевой функции таблицей или вектором её значений.

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

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

Читайте также:  Моя страница одноклассники войти татьяна

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

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

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

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

Определение [ править | править код ]

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

Говорят, что набор α

= ( α 1 , . . . α n ) <displaystyle < ilde <alpha >>=(alpha _<1>. alpha _)> предшествует набору β

= ( β 1 , . . . β n ) <displaystyle < ilde <eta >>=(eta _<1>. eta _)> ( α

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

Булева функция f ( x

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

Читайте также:

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Adblock detector