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

3. Линейные и монотонные функции. Функции, сохраняющие константу. Самодвойственные функции. Замкнутые классы и полные системы в.

Опр 1. Функция называется самодвойственной, если . Класс само-

двойственных функций обозначается S.

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

, где , . Множество всех линейных

функций обозначается L.

Опр 3. Говорят, что функция сохраняет константу 0 (константу 1), если

(). Множество функций, сохраняющих константу 0

или 1, обозначается соответственно и .

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

из , таких, что имеет место неравенство . В противном

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

чается M.

Опр 5. Наборы и называются соседними, если они имеют вид:

Опр 6. Пусть M — некоторое множество функций алгебры логики. Замыкание [M] мно-

жества M называется совокупностью всех функций из , являющихся суперпо-

зициями функций из множества M.

Опр 7. Множество M называется функционально замкнутым классом, если [M]=M.

Опр 8. Пусть M — замкнутый класс в . Подмножество R из M называется функци-

онально полной системой в M, если [R]=M.

Опр 9. Множество , содержащееся в замкнутом классе M (в т.ч. M=) называется

полным классом в M, если оно не является полной системой в M, но для каждой

функции

Опр 10. Система G называется независимой, если никакая функция не представ-

лена суперпозициями функций из .

Опр 11. Независимая система G называется базисом функционально замкнутого класса

K, если всякая функция из K есть суперпозиция функций из G.

Теорема 1. Система полна в , тогда и только тогда, когда она целиком не содержится

ни в одном классе ,, S, L, M.

Теорема 2. Булева функция немонотонная, тогда и только тогда, когда существует, хотя

бы два соседних набора , таких что

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

Лемма о несамодвойственной функции. Из несамодвойственной функции, путём подстановки функций , можно получить несамодвойственную функцию одной переменной, т.е. const 1 или 0.

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

3.1. Разлагая функцию в полином Жегалкина, выяснить является ли она линейной.

1) 2)

3) 4)

3.2. Выяснить, является ли линейной функция .

1) 2)

3) 4)

3.3. Самодвойственна ли функция .

1)

Класс S самодвойственных функций

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

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

Пример 16. Функция f(x)=x’ — самодвойственная. Действительно, так как

f(x’) = x» = x, а f*(х) = f ‘(x’) = x’ = f(x).

Пример 17. Докажем, что функция f(x,y,z) = xyz(xy) самодвойственная. Найдём ей двойственную:

= xzyzxxyyxy = xzyzxy = xy(xy)z.

Получили, что f*(x,y,z)=f(x,y,z). Самодвойственность доказана. O

Доказательство следует из определения.

Если f ‘(х₁‘,х₂‘,…,х_n‘) = f(х₁,х₂,…,х_n), то инверсия, применённая к обеим частям этого равенства, даст

Замечание. Эта равносильность говорит также о том, что самодвойственная функция на антиподах (х₁,х₂,…,х_n) и (х₁‘,х₂‘,…,х_n‘) принимает противоположные значения.

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

Пример 18. Рассмотрим функцию f(x,y,z) голосования. Она называется так потому, что принимает значение 1 только на тех наборах, в которых единиц больше, чем нулей Эту функцию ещё называют мажоритарной..

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

Достаточное условие несамодвойственности функции. Если количество единиц в векторе значений функции не равно количеству нулей, то такая функция не является самодвойственной.

Теорема о мощности класса S. Количество различных самодвойственных булевых функций, зависящих от n переменных, равно

Доказательство. Рассмотрим f(х₁,х₂,…,х_n)S, заданную таблицей истинности. Если на первом наборе она принимает значение , то, — согласно свойству самодвойственной функции, — на последнем наборе, который является антиподом первому, она принимает значение ‘.

То же можно сказать о значениях функции на втором и предпоследнем наборах и т.д. Следовательно, самодвойственная функция полностью определяется верхней половиной своего столбца значений, то есть булевым вектором длины 2 n /2=2 n-1 . Известно, что количество векторов длиной 2 n-1 равно 2 K , где K=2 n-1 . Значит, количество различных самодвойственных функций f(х₁,х₂,…,х_n) тоже равно |S|=2 К , где К=2 n-1 . O

Пример. Из элементарных 16 булевых функций самодвойственными являются лишь 4 (n=2, K=2 2-1 =2, |S|=2 2 ): тождественные функции х₁, х₂ и их инверсии х₁‘, x₂‘.

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

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

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

:

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

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

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

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

.

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

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

.

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

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). Здесь сразу ясно, что при замене каждой переменой на противоположную к сумме прибавляется единица.