Исследуем заданную функцию на самодвойственность
Функция самодвойственная, если на любой паре противоположных наборов (наборов, сумма десятичных эквивалентов которых равна 
, где п – количество переменных функции) функция принимает противоположные значения.
Построим таблицу: 
; вычислим значения функции на оставшихся наборах:
:
На наборах 0 и 7, 1 и 6 функция принимает одинаковые значения. Следовательно 
.
5. Проверим принадлежность заданной функции f1 классу монотонных функций. Из таблицы видно: 001< 010, но 
. Следовательно, функция 
.
Рассмотрим функцию 
.
1. Принадлежность функции классу К0:
.
Следовательно, 
.
2. Принадлежность функции классу К1:
.
Следовательно, 
.
3. Принадлежность функции классу К л.
.
Фиксируем набор 0000:
,
, 
.
Фиксируем набор 1000:
,
.
Фиксируем набор 0100:
,
.
Фиксируем набор 0010:
,
.
Фиксируем набор 0001:
.
.
.
Это равенство на других 11 наборах не выполняется. Действительно, для набора 1111 имеем
, 
, т.е. 
.
Следовательно, 
.
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) 
Класс самодвойственных функций и его замкнутость относительно суперпозиции. Критерий самодвойственности. Лемма о несамодвойственной функции.
Определение: Функция, совпадающая со своей двойственной функцией, называется самодвойственной.
Теорема: Класс самодвойственных функций замкнут относительно суперпозиции.
Определение: Наборы a=(a1, a2,…,an), a*=(¬a1, ¬a2,…,¬an) из 0 и 1 называется противоположными.
Следствие: Чтобы функция была самодвойственной необходимо и достаточно, чтобы на всяких двух противоположных наборах она принимала разные значения.
Лемма (о несамодвойственной функции): Подстановкой функций x и ¬x в несомодвойственную функцию можно получить одну из констант.
Определить принадлежность функции к классу S (самодвойственных функций) /
Помогите пожалуйста, нужно определить принадлежность функции к классу S (самодвойственных функций):
f(x,y,z)=(x→¬y)(¬x⊕z)
Алгоритм распознавания самодвойственной функции, заданной таблицей истинности. Очевидно, что для проверки самодвойственности булевой функции можно не получать двойственную ей функцию в явном виде, а лишь сравнивать значения исходной функции на противоположных наборах.
. 1
Функция самодвойственна, если и только если на противоположных наборах принимает противоположные значения.
f(000) =1
f(111)=1