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

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

.

Очевидно эквивалентное определение самодвойственной функции:

Определение: S,если принимает противоположные значения на противоположных наборах.

x1	x2	x3	f(x1x2x3) S
0
0
0

Пример:

S S

S S

S S

S S

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

Определение:набор , если ;

Например:

наборы 0101 и 1001 не сравнимы.

Определение: M, если :

.

x

x1

x2

y

x1	x2	x3	f(x1x2x3) M

Метод определения монотонности функции f :

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

x1	x2	x3	f(x1x2x3) M

Для данной функции для единицы 001 большие наборы есть 101, 011, 111. Среди них есть ноль, набор 011. Поэтому функция немонотонная.

M M

M M

M M

M M

Линейные функции L .

Определение: линейные функции – функции, степень полинома Жегалкина которых не больше единицы .

Определение:степенью полинома Жегалкина называется максимальное число переменных в слагаемых этого полинома.

Степень равна 3.

Степень равна 1.

Степень 1 равна 0 ; степень 0 равна 0.

x1	x2	x3

Методы определения линейности функции f :

1.Способ Находим полином Жегалкина функции f и определяем его степень. Если степень , то функция линейная. В противном случае функция нелинейная.

2. Способ. Определяем существенные переменные функции f и рассматриваем две возможные линейные функции : сумма найденных существенных переменных и сумма существенных переменных плюс 1. Если исходная функция совпадает с одной из данных двух, то функция линейна. В противном случае функция нелинейная.

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

1) x₁ - существенная (по 1-ому и 5- ому) ,x₂ - существенная (по 3- ему и по 1-ому набору), x₃ не существенная . Если функция линейная, то она имеет вид либо x₁+x₂, либо x₁+x₂+1; подходит первое выражение, поэтому первая функция линейная.

вторая функция нелинейная

2) x₁ - существенная (по 4-ому и 8-ому),x₂- существенная (по 6-ому и 8-ому), x₃ не существенная :

вторая функция нелинейная

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

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

1) T₀

Рассмотрим T₀

T₀

Рассмотрим суперпозицию

и покажем, что полученная T₀. Для этого найдем значение на нулевом наборе :

2) T₁

Рассмотрим T₁

T₁

Рассмотрим :

S

Рассмотрим S

S

Рассмотрим :

М

Рассмотрим М

М

Рассмотрим суперпозицию

:и

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

Нетрудно видеть, что из того, что следует, что и .

В силу того, что :

L

Рассмотрим L

L

, где α и β - некоторые константы.

Рассмотрим .

.

Используя ассоциативность и коммутативность операции +, преобразуем к виду :

.

Степень не превосходит 1, следовательно L.

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

Упражнение Покажите, что переименование переменных не выводит функции из классов

.

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

Для того, чтобы система была полной, необходимо и достаточно, чтобы она целиком не содержалась ни в одном из пяти классов: T₀, T₁ , S, M, L.

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

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

Пример: .

По теореме о представлении любой булевой функции в виде СДНФ данная система полна. И в тоже время система не содержится ни в одном из классовT₀, T₁ , S, M, L, поэтому критерий Поста справедлив для данной системы.

Пример:

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

Пример: - не полная, так как

и критерий Поста справедлив для данной системы, т.к. L.

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

Необходимость : пусть система Kполна.

Покажем, что она не принадлежит ни одному из пяти классов. Допустим противное : система принадлежит одному из пяти классов. Пусть K T₀ .Т.е. все функции Kсохраняют 0. Но тогда и любая суперпозиция функций из Kбудет сохранять 0. Но тогда [K], и K - неполная. Пусть K T₁, тогда любая суперпозиция из Kсохраняет 1, тогда [K]. Пусть K S, тогда суперпозиция любых функций будет самодвовойственна, тогда [K].

Пусть K M, тогда [K]. Пусть K L, тогда [K]. Получаем противоречие (система не является полной, в силу замкнутости классов T₀, T₁, S, M, L относительно суперпозиций).

Достаточность : пусть система K не содержится ни в одном из пяти классов, т.е.

Построим заведомо полную систему .

I этап :

II этап :

I этап: и , и переименуем все их переменные в : и :

X	f0	f1
		1,0
	1,0

Теперь имеем четыре возможных случая в зависимости от значений функций и в 1 и в 0 соответственно.

1)

2)

3)

4)

Простейшими окажутся 1) и 4).

Рассмотрим 1) и 4) случаи.

1 случай :

X	f0	f1

т.е .

4 случай :

X	f0	f1

т.е .

Остались 2) и 3)

2 случай :

X	f0	f1

т.е .

Построим вывод :

.

M , следовательно по определению существует пара наборов (нижний строго больше верхнего), а значение функции наоборот :

Разобьем множество переменных на два множества и .

- переменные, которые не изменяются в двух данных наборах, а - все остальные переменные:

И теперь все переменные множества переименнуем в x, а во все переменные множества подставим соответствующие константы :

.

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

Например, пусть наборы были:

X1	x2	X3	x4	x5	fM

3 случай :

X	f0	f1

т.е .

Построим вывод :

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

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

Теперь в переменные подставим x, а в подставим : .

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

Например, пусть пара противоположных наборов, на которых равна нулю, имеют вид :

X1	x2	X3	x4	x5	f

Тогда .

I-ый этап завершен.

II этап :

Построим вывод :

Рассмотрим полином Жегалкина функции . .

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

Из всех слагаемых, содержащих и вынесем за скобку конъюнкцию этих двух переменных ; полином в скобках обозначим ; из всех слагаемых, содержащих только ,

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

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

Таким образом, получили функцию ,

где некоторые константы.

Имеем восемь случаев :

b1	b2	b3	f(x1,x2)

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

Таким образом, достаточно рассмотреть случаи:

1) ; 2) ; 3) ; 4) .

1)

Требуемая конъюнкция получена.

2) .

3) .

4)

Например, из получим . После группировки слагаемых получаем , полином равен 1, например, если , . Подставляем 1 в , 0 в , получаем функцию . Подставляем в переменную , получаем .

Упражнение 1:Исследовать на полноту:

1)

2)

3)

4)

5)

6)

Упражнение 2:Получить из функции функции .

1) 2) 4) 5) не полная 6) 0 0 0 1 1 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 1 0 1 0 1 1 1 0 0

Примеры:

1) Исследовать на полноту систему :

	T0	T1	S	M	L
f1	-	+	-	-	-
f2		-
f3

2) Исследовать на полноту систему

:

	T0	T1	S	M	L
f1	+	-	-	+	+
f2	-			+	+
f3				+	-
f4				+	-
f5				+

Система неполная, т.к. и монотонны, то и суперпозиция этих функций монотонны,поэтому пятая функция тоже монотонна.

Система принадлежит монотонному классу, поэтому неполна.

3) Можно ли из системы функций

получить функцию 0 :

	T0	T1	S	M	L
f1	-	-	+	-	+
f2			+
f3			+		+

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

4)Можно ли из системы функций

получить и , и если «да», опишите определяющие выражения :

	T0	T1	S	M	L
f1	+	-	-	-
f2	-
f3					-

Система полная, поэтому получить можно любые функции.

I :

II:

5)Можно ли из системы функций

получить функции

, и если “да”, опишите определяющие выражения :

	T0	T1	S	M	L
f1	-	-	-	-
f2					-

x1	x2	x3	f1
			0 -
			0 -

I :

Упражнения :Исследовать на полноту системы :

1) ; 2) ; 3) ;

4) ; 5) ;

Можно ли из соответствующих систем функций получить следующие функции , и если “да”, то напишите определяющее выражение:

6)из системы функций получить функцию ;

7)из системы функций

получить функцию 0 ;

8)из системы функций получить функции ;

9)из системы функций

получить функции

;

10) из системы функций получить функции ;