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

Монотонная булевая функция.

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

Булевая функция
Помогите решить пример. По заданной Булевой функции. ((D v F) → (C ^ D) v (D ^ C )).

Булевая функция трех переменных
Функция: F(x,y,z)=¬(x∪¬y→( z≡¬x )) 1) Каким классам Поста принадлежит эта функция? 2).

Монотонная функция не менее чем от двух переменных
Доказать, что функция, существенно зависящая не менее чем от двух переменных, монотонна тогда и.

Булевая функция на форме элемента
Здравствуйте, почему-то в документе «Принятие к учёту» не получается добавить на форму реквизит.

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

Булевая матрица
Вообщем задание реализовать библиотеку классов где имеется конструктор с параметрами и базовый.

Источник

Раздел 1. Математическая логика

Тема 1. Логика высказываний

Тема 2. Булевы функции

В этой теме рассматриваются всюду определенные функции, заданные на множестве B=<0,1>. Такие функции называются булевыми. Основная цель темы – доказать критерий полноты класса функций – теорему Поста.

§1. Замкнутость и полнота

§2. Самодвойственные функции

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

На множестве B= <0,1>в этом параграфе будем смотреть, как на частично упорядоченное множество с отношением 0 1.

На множестве B n введем порядок прямого произведения, т.е.

для любых a₁,…,a_n, b₁,…,b_n Î B. Например, (1,0,0,1) £ (1,0,1,1), (1,0,1,0) £ (1,0,1,1). В то же время, неверно, что (1,0,0,1) £ (1,0,1,0).

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

Примерами монотонных функций являются q (x), i (x), x × y, x Ú y. Функции n (x), x ® y, x+y немонотонны.

Монотонность функции означает, что если в какой-то вершине диаграммы она принимает значение 1, то и всюду выше функция принимает то же значение 1. Функция f(x₁,x₂,x₃)=x₁+x₂ × x₃ монотонной не является, так как в вершине (1,1,0) она принимает значение 1, а в вершине (1,1,1), которая выше первой, принимает значение 0.

Класс всех линейных функций обозначим буквой М. Убедимся в том, что М – это замкнутый класс. Монотонность тождественной функции очевидна. Пусть f(x₁,…,x_n) Î M и y₁,…,y_n – новые переменные. Возьмем два набора значений переменных y₁,…,y_n : a=(a₁,…,a_n), b=(b₁,…,b_n) таких, что a £ b. Но эти векторы будут наборами значений переменных x₁,…,x_n, и поэтому выполняется неравенство f(a) £ f(b). Это означает, что М замкнут относительно переименования аргументов.

g_k(b₁,…,b_n))=h(b₁,…,b_n). (Знак неравенства поставлен в силу монотонности функции f). Мы доказали, что класс М замкнут относительно суперпозиции.

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

Лемма. Пусть f(x₁,…,x_n) – немонотонная функция. Тогда замыкание класса K=1,…,x_n), q (x), i (x)> содержит n (x).

На этой цепи найдутся соседние точки c=(c₁,…,c_n) и d=(d₁,…,d_n) такие, что c d, f(c)=1 и f(d)=0. Поскольку c и d – соседние точки, то

Для удобства обозначений будем считать, что c₁=…=c_i-1=0,c_i+1=…c_n=1. Рассмотрим функцию g(x)=f( q (x),…, q (x),x; i (x),…, i (x)), где точка с запятой отделяет i-ю компоненту от (i+1)-ой. Ясно, что g(x) принадлежит замыканию класса K.

Источник

Презентация по математике на тему «Монотонные булевы функции»

«Управление общеобразовательной организацией:
новые тенденции и современные технологии»

Свидетельство и скидка на обучение каждому участнику

Описание презентации по отдельным слайдам:

Монотонные булевы функции Авторы презентации: преподаватель математики ГПОУ ЯО ЯГК Холманова Вероника Михайловна M

Отношение предшествовать на B M По аналогии с отношением «меньше или равно» на рассмотрим отношение «предшествовать» на B

M Сравнимые элементы Bn Два элемента и называются сравнимыми между собой, если либо первый из них предшествует второму, либо второй предшествует первому, то есть: или Элементы (01) и (10) – несравнимые элементы B2

Класс монотонных булевых функций обозначается символом M. Булева функция n переменных называется монотонной, если для любых двух её аргументов, сравнимых между собой, из того, что первый предшествует второму следует, что значение функции на первом аргументе предшествует значению функции на втором аргументе: M Монотонные булевы функции

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

Задача: исследовать функцию на принадлежность к классу монотонных булевых функций. Исследование булевой функции на монотонность M

0 0 1 1 0 1 1 0 1 1 0 0 Вектор задаёт булеву функцию двух переменных Исследование булевой функции на монотонность M

0 0 1 1 0 1 1 0 1 1 0 0 Исследование булевой функции на монотонность M

0 0 1 1 0 1 1 0 1 1 0 0 Исследование булевой функции на монотонность M

Отсутствие в булевом векторе после единиц нулей является достаточным условием монотонности булевой функции, заданной вектором Исследование булевой функции на монотонность M (по достаточному условию монотонности) f=(00000111),

Достаточное условие монотонности функции, заданной булевым вектором, не является необходимым. Исследование булевой функции на монотонность M f = (0 1 0 1) 0 0 1 1 0 1 1 0 1 1 0 0

Исследование булевой функции на монотонность M Если после единиц в булевом векторе присутствуют нули, функция нуждается в проверке на монотонность по определению Булева функция может быть как монотонной, так и немонотонной

Задача: исследовать функцию на принадлежность к классу монотонных булевых функций Исследование булевой функции на монотонность M

Зададим булеву функцию таблицей значений Исследование булевой функции на монотонность M 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 0 0 0 1 1 0 0 1 0 1 0 1 0 1 0 0 0 0 1 0 1 0 1 1 0 1 1 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0

Исследование булевой функции на монотонность M f=(01000100)

Исследование булевой функции на монотонность M 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 0 0 0 1 1 0 0 1 0 1 0 1 0 1 0 0 0 0 1 0 1 0 1 1 0 1 1 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 Второй и третий аргументы не сравнимы между собой

Исследование булевой функции на монотонность M 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0

Курс повышения квалификации

Дистанционное обучение как современный формат преподавания

Курс повышения квалификации

Методика обучения математике в основной и средней школе в условиях реализации ФГОС ОО

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

Математика: теория и методика преподавания в образовательной организации

Ищем педагогов в команду «Инфоурок»

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

Работа может быть использована учителем для организации факультативных занятий по математике или информатике в 11 классе в рамках изучения темы «Функции алгебры логики».

Номер материала: ДБ-1596240

Не нашли то, что искали?

Вам будут интересны эти курсы:

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.

Учителя о ЕГЭ: секреты успешной подготовки

Время чтения: 11 минут

Рособрнадзор разрешил провести ВПР по некоторым предметам на компьютерах

Время чтения: 0 минут

Российские юниоры завоевали 6 медалей на Международной научной олимпиаде

Время чтения: 2 минуты

Во всех педвузах страны появятся технопарки

Время чтения: 1 минута

В Минпросвещения рассказали о формате обучения школьников после праздников

Время чтения: 1 минута

Правительство направит регионам почти 92 миллиарда рублей на ремонт и оснащение школ

Время чтения: 1 минута

Учителя о ЕГЭ: секреты успешной подготовки

Время чтения: 11 минут

Подарочные сертификаты

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

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

Источник

Монотонные функции алгебры логики

Определение. Булева функция f(x₁, …, x_n) называется монотонной (принадлежит классу 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(β’).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где γ и δ – булевы векторы. Так как αβ, и булевы функции f₁(x₁, …, x_n), …, f_m(x₁, …, x_n) монотонны, то γδ. Поскольку функция f (y₁, …, y_m) также монотонна, то f (γ)≤ f (δ), следовательно, f(α)≤ f(β), то есть f(x₁, …, x_n) монотонна, и класс M замкнут. •

Доказательство. Рассмотрим немонотонную функцию f(x₁, …, x_n). Согласно утверждению о условии немонотонности, существует пара соседних наборов α=a₁… a_n и β=b₁… b_n таких, что αβ и f(α) > f(β), то есть

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сравним первую строку с пятой, вторую с шестой, третью с седьмой, четвертую с восьмой.
Имеем:
1) 000 – 0 – условие монотонности НЕ выполняется

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

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

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

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

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

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

Источник

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

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

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

Множество функций, сохраняющих 1. Определяется условием f (1, 1, 1) = 1.

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

Монотонные. Выполнено условие: если набор α меньше набора β, то f (α) ≤ f (β).

Например, набор (0, 1, 0) меньше набора (1, 1, 1). А про наборы (1, 1, 0) и (1, 0, 1) нельзя сказать, что один меньше другого.

Для проверки функции на монотонность используют рисунок, называемый диаграммой Хассе.

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

При этом, если будет нарушение монотонности, оно обнаружится на диаграмме.

Например, для функции нарушение монотонности происходит следующим образом: (0, 0, 1) f (0, 1, 1), поскольку f (0, 0, 1) =1, f (0, 1, 1) = 0.

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

Ответ на задачу о проверке принадлежности булевой функции к классам замкнутости записывают так:

T0	T1	L	M	S
f	+	+	–	–	–
	–	–	–	–	–

Здесь T0 означает функции, сохраняющие 0, T1 – функции, сохраняющие 1, L – линейные, M – монотонные, S – самодвойственные.

Ответ в таблице приведён, разумеется, для функции .

Применение теоремы Пóста

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

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

Выражать каждую булеву функцию неудобно, поэтому можем ограничиться получением конъюнкции и отрицания.

Если мы это сделаем, то сможем получить дизъюнкцию через отрицание и конъюнкцию, а затем каждую булеву функцию через её СДНФ.

Представление конъюнкции и отрицания через данную функцию f (x, y, z) и её отрицание

Первый шаг в такой работе – вычисление и . Получим две противоположные функции от одной переменной.

Далее возможны два случая: или это 0 и 1, или это x и .

(Например, для функции получим , )

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

Если есть две константы: по немонотонности найдутся два набора, на которых нарушается монотонность. Например, (0, 0, 1) f (0, 1, 1). Тогда поставим x на место разряда, на котором нарушается монотонность.

В данном случае обозначим h (x) = f (0, x, 1). Эта функция переводит 0 в 1, а 1 в 0, следовательно, h (x) – это отрицание.

Если есть отрицание, то по несамодвойственности найдутся два инверсных набора (наборы, получающиеся заменой 0 на 1 и 1 на 0), значения в которых одинаковы.

Тогда подставим в один из этих наборов x вместо 1 и вместо 0. Например, f (1, 0, 0) = f (0, 1, 1) = 0. Рассмотрим функцию . Поскольку её значение не меняется при инверсии набора, то значение равно константе. В данном случае 0. Чтобы получить 1, возьмём отрицание f. Таким образом, в данном примере .

Итак, мы получили две константы и отрицание. Теперь нужно получить дизъюнкцию. Получим её с помощью нелинейности. Многочлен Жегалкина содержит хотя бы одно произведение. Например, f (x, y, z) = z + xy + yz. Если мы получим выражение, целиком состоящее из произведения двух переменных, то наша цель достигнута.

В нашем примере можно принять z = 0 и получить: f (x, y, 0) = xy.

Осталось выразить 0, причём только через f и отрицание этой функции.

.

Подставим одно выражение в другое.

Теперь воспользуемся этим нулём.

Таким образом, можем записать ответ:

Обращаем ваше внимание на то, что в ответе не должно быть констант, в выражении для конъюнкции не должно быть отрицания х.

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

Не обязательно получать произведение xy. Например, произведение xz, если вы его получите, тоже будет решением задачи.

Не обязательно одно из чисел принимать именно за 0. Можно принять его за 1. Например, в случае 1 + z + xy замена z = 1 быстрее приведёт к цели, чем замена z = 0.

Во многих случаях для получения конъюнкции поможет отрицание. Например, для случая f (x, y, 0) = x + xy можно вынести x за скобку и получить выражение x (y + 1) = .

Тогда получим . Но нам нужно получить не , а xy.

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

Наконец, иногда получается не xy, а . Например, . В этом случае нужно взять .

В целом, заключительная задача творческая, и её решение, вообще говоря, не однозначно определено.

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

Источник