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

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

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

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

Определение 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(в).

Тема 9.3.Замкнутые классы. Монотонные функции

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

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

Пример 9.4:

а) Множество всех дизъюнкций, то есть функций вида является замкнутым классом.

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

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

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

Определение:Функцияназываетсямонотонной, если для любых двух двоичных наборов длиныиз того, чтоследует.

Пример 9.5:

а) Функция монотонна.

б) Дизъюнкция и конъюнкция любого числа переменных являются монотонными функциями.

в) Рассмотрим две функции от трёх переменных, заданных следующей таблицей.

Функция , очевидно, не является монотонной, так как, например, а. Монотонность функциилегко установить непосредственной проверкой.

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

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

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

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

Но поскольку всякая булева формула без отрицаний является суперпозицией дизъюнкций и конъюнкций, из данной теоремы непосредственно получаем следствие.

Следствие.Класс монотонных функций является замыканием системы функций .

Тема 9.4.Теоремы о функциональной полноте

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

Лемма о немонотонных функциях.Если функция немонотонна, то подстановкой констант из неё можно получить отрицание.

Смысл леммы заключается в том, что для функции существует такая подстановкаконстанты, что функция оставшейся одной переменной является отрицанием.

Лемма о нелинейных функциях. Если функция нелинейна, то с помощью подстановки констант и использования отрицаний из неё можно получить дизъюнкцию или конъюнкцию.

Иначе говоря, существует представление дизъюнкции и конъюнкции в виде суперпозиции констант, отрицаний и нелинейной функции .

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

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

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

Очевидно, что из обычной полноты системы следует её слабая полнота.

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

Доказательство:

1) Необходимость. Классы монотонных и линейных функций замкнуты и содержат 0 и 1. Поэтому если не содержит немонотонных или нелинейных функций, то их нельзя получить с помощью суперпозиций функций из системыи констант.

2) Достаточность. Пусть содержит немонотонную и нелинейную функцию. Тогда по лемме 1 подстановкой констант из монотонной функции получаем отрицание, а затем по лемме 2 из нелинейной функции с помощью отрицаний и констант получаем дизъюнкцию и конъюнкцию.

Пример 9.6:

а) Система функционально полна в слабом смысле, так как конъюнкция нелинейна, а операциянемонотонна.

б) В функционально полной системе единственная функция – штрих Шеффера – нелинейна и немонотонна.

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

Определение:Функцияназываетсясохраняющей ноль, если выполняетсяисохраняющей единицу, если выполняется.

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

Теорема (вторая – основная – теорема о функциональной полноте).Для того чтобы система функций была функционально полной (в сильном смысле), необходимо и достаточно, чтобы она содержала: 1) нелинейную функцию, 2) немонотонную функцию, 3) функцию, не являющуюся самодвойственной, 4) функцию, не сохраняющую ноль, 5) функцию, не сохраняющую единицу.

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

Пример я сам придумал, поэтому здесь, да, всё очевидно.

Но вот если в нём разделить вектор значений пополам и сравнивать 1101 и 1110, то несмотря на предшествование эти наборы не сравнимы.

• U-mail
• Профиль

Но вот если в нём разделить вектор значений пополам и сравнивать 1101 и 1110, то несмотря на предшествование эти наборы не сравнимы.

Ну вот!
Если они не сравнимы, значит функция немонотонна.
Т.е. несравнимость этих половинок означает, что на некоторых наборах значений переменных условие монотонности выполняется, а на некоторых нет.
Причем наборы значений переменных здесь попарно сравнимы.

• U-mail
• Дневник
• Профиль

Всё таки не до конца понятно, но тем не менее, уже ближе к цели.

Спасибо за ответ!

• U-mail
• Профиль

mad-math, ну, задайте вопросы )
Я с удовольствием отвечу.
Давайте так. Вот таблица для вашей функции.
000 1
001 1
010 0
011 1
100 1
101 1
110 1
111 0

Сравним первую строку с пятой, вторую с шестой, третью с седьмой, четвертую с восьмой.
Имеем:
1) 000 -< 100; 1<=1 — условие монотонности выполняется
2) 001 -< 101; 1<=1 — условие монотонности выполняется
3) 010 -< 110; 0 <=1 — условие монотонности выполняется
4) 011 -< 111; 1 > 0 — условие монотонности НЕ выполняется

Что мы видим?
Во-первых, мы видим, что все взятые наборы переменных сравнимы и значит сравнение значений функции на них легитимно.
Во-вторых мы видим, что если бы функция была монотонна, то две половинки вектора значений были бы сравнимы. Потому что под номерами 1), 2), 3), 4) после точки с запятой как раз выполняется поэлементное сравнение первой и второй половин вектора f.

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

• U-mail
• Дневник
• Профиль

Спасибо большое за желание помочь, просто мне неудобно напрягать людей.

Сейчас распишу мои размышления. Поправьте, если я где-то ошибаюсь.

Пусть есть функция `f(0001 0010)`.

Условие `(0001) preceq (0010) ` может быть переписано в виде системы:
`<(0 <= 0), (0 <= 1) , (0 <= 0), (1 <= 0):>`

Необходимость верности этой системы и исходного условия обусловлена тем, что:
`<(000 preceq 100), (001 preceq 101) , (010 preceq 110), (011 preceq 111):>`

Я правильно размышляю?

• U-mail
• Профиль

• U-mail
• Дневник
• Профиль

Пусть есть функция `f(0001 0001)`.

1. Условие `(0001) preceq (0001) ` может быть переписано в виде системы:
`<(0 <= 0), (0 <= 1) , (0 <= 0), (1 <= 1):>`

Необходимость верности этой системы и исходного условия обусловлена тем, что:
`<(000 preceq 100), (001 preceq 101) , (010 preceq 110), (011 preceq 111):>`

Далее, разбиваем `(0001)_1` на `(00)_ <1>и (01)_<1>, и `(0001)_2` на (00)_ <3>и (01)_<4>`.

2.1. Условие `(00)_ <1>preceq (01)_ <2>` может быть переписано в виде системы:
`<(0 <= 0), (0 <= 1) :>`

Необходимость верности этой системы и исходного условия обусловлена тем, что:
`<(000 preceq 010), (001 preceq 011):>`

2.2. Условие `(00)_ <21>preceq (01)_ <22>` может быть переписано в виде системы:
`<(0 <= 0), (0 <= 1) :>`

Необходимость верности этой системы и исходного условия обусловлена тем, что:
`<(100 preceq 110), (101 preceq 111):>`

Далее, разбиваем аналогично и получаем:

3.1. Условие `(0)_ <1>preceq (0)_ <2>` может быть переписано в виде системы:
`<(0 <= 0) :>`

Необходимость верности этой системы и исходного условия обусловлена тем, что:
`<(000 preceq 001):>`

3.2. Условие `(0)_ <3>preceq (1)_ <4>` может быть переписано в виде системы:
`<(0 <= 1) :>`

Необходимость верности этой системы и исходного условия обусловлена тем, что:
`<(010 preceq 011):>`

3.3. Условие `(0)_ <5>preceq (0)_ <6>` может быть переписано в виде системы:
`<(0 <= 0) :>`

Необходимость верности этой системы и исходного условия обусловлена тем, что:
`<(100 preceq 101):>`

3.4. Условие `(0)_ <7>preceq (1)_ <8>` может быть переписано в виде системы:
`<(0 <= 1) :>`

Необходимость верности этой системы и исходного условия обусловлена тем, что:
`<(110 preceq 111):>` (1)

Фактически, это получается удобная и упрощенная форма перебора всех наборов, сравнения их и значений функций на них, и определения монотонности функции по определению.

Да, теперь всё понятно. Главное, что в системах, таких как (1), в силу особенности подхода наборы оказываются сравнимыми, я раньше запутался в этом, и потому возникло полное непонимание. Спасибо большое!

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

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

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

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

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

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

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

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

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

,

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

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

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

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