Перейти к содержимому

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

  • автор:

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).

Исследуем заданную функцию на самодвойственность

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

Построим таблицу: ; вычислим значения функции на оставшихся наборах:

:

На наборах 0 и 7, 1 и 6 функция принимает одинаковые значения. Следовательно .

5. Проверим принадлежность заданной функции f1 классу монотонных функций. Из таблицы видно: 001< 010, но . Следовательно, функция .

Рассмотрим функцию .

1. Принадлежность функции классу К0:

.

Следовательно, .

2. Принадлежность функции классу К1:

.

Следовательно, .

3. Принадлежность функции классу К л.

.

Фиксируем набор 0000:

,

, .

Фиксируем набор 1000:

,

.

Фиксируем набор 0100:

,

.

Фиксируем набор 0010:

,

.

Фиксируем набор 0001:

.

.

.

Это равенство на других 11 наборах не выполняется. Действительно, для набора 1111 имеем

, , т.е. .

Следовательно, .

булева-алгебра — Выяснить является ли функция самодвойственной:

1)$%(x \wedge y) \vee(x \wedge z) \vee (y \wedge z)$%, пытался сначала наклыдвать отрицание на всю функцию, потом на каждый член, ничего толком не выражалось, хотелось бы хотя бы идею услышать
2)Привести пример самодвойственной линейной функции

задан 11 Дек ’15 21:26

1 ответ

1) Это известная «функция голосования», она самодвойственна. Из формулы легко заметить, что функция равна 1 тогда и только тогда, когда хотя бы два из трёх значений переменных (то есть большинство) принимают значение 1. Тогда понятно, что при смене всех значений на противоположные, большинство значений станет противоположным, а это и означает самодвойственность.

При желании, можно в этом же самом убедиться и при помощи формул, хотя такой способ выглядит сложнее. По принципу двойственности, для функции $%xy\lor xz\lor yz$% из условия, двойственной будет $%(x\lor y)(x\lor z)(y\lor z)$%. Она тождественно равна предыдущей, что проверяется при помощи применения дистрибутивного закона. Если раскрыть все скобки, то получится дизъюнкция 8 конъюнкций, среди которых будут $%xy$%, $%xz$%, $%yz$%, а также $%xyz$%, но последняя из них «поглощается» любой из предыдущих.

К сказанному можно добавить, что эта же функция следующим образом представляется полиномом Жегалкина: $%xy+xz+yz$%. Здесь также можно непосредственно проверить, что при замене каждой из переменных на её отрицание (прибавляем единицу), функция принимает противоположное значение: $%(x+1)(y+1)+(x+1)(z+1)+(y+1)(z+1)=xy+xz+yz+1$%. Всё остальное, что встречается дважды, сокращается при сложении по модулю 2.

Наконец, есть совсем прямой способ проверки: для исходной функции составляем таблицу, и при стандартном порядке следования наборов получается вектор значений 00010111. Вторая часть набора является «отражением» первой относительно середины с заменой 0 на 1 и обратно; это и есть самодвойственность.

2) Пример здесь тривиален: можно взять тождественную функцию $%x$%. Подходит также отрицание $%\bar$%, а если нужен пример функции, существенно зависящей от трёх переменных, то годится $%x+y+z$% (сумма по модулю 2). Здесь сразу ясно, что при замене каждой переменой на противоположную к сумме прибавляется единица.

Класс самодвойственных функций и его замкнутость относительно суперпозиции. Критерий самодвойственности. Лемма о несамодвойственной функции.

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

Теорема: Класс самодвойственных функций замкнут относительно суперпозиции.

Определение: Наборы a=(a1, a2,…,an), a*=(¬a1, ¬a2,…,¬an) из 0 и 1 называется противоположными.

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

Лемма (о несамодвойственной функции): Подстановкой функций x и ¬x в несомодвойственную функцию можно получить одну из констант.

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

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