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

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

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

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

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

x1 x2 x3 f(x1x2x3) Самодвойственные функции S - student2.ru S
0
0
0

Пример:

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

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

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

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

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

Определение:набор Самодвойственные функции S - student2.ru , если Самодвойственные функции S - student2.ru ;

Например: Самодвойственные функции S - student2.ru

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

Определение: Самодвойственные функции S - student2.ru M, если Самодвойственные функции S - student2.ru :

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

x
x1
x2
y


x1 x2 x3 f(x1x2x3) Самодвойственные функции S - student2.ru M Самодвойственные функции S - student2.ru
 
 
 
 
 
 
 
 

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

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

x1 x2 x3 f(x1x2x3) Самодвойственные функции S - student2.ru M

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

Самодвойственные функции S - student2.ru M Самодвойственные функции S - student2.ru M

Самодвойственные функции S - student2.ru M Самодвойственные функции S - student2.ru M

Самодвойственные функции S - student2.ru M Самодвойственные функции S - student2.ru M

Самодвойственные функции S - student2.ru M Самодвойственные функции S - student2.ru M

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

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

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

Степень Самодвойственные функции S - student2.ru равна 3.

Степень Самодвойственные функции S - student2.ru равна 1.

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

x1 x2 x3 Самодвойственные функции S - student2.ru Самодвойственные функции S - student2.ru Самодвойственные функции S - student2.ru

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

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

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

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

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

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

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

2) x1 - существенная (по 4-ому и 8-ому),x2- существенная (по 6-ому и 8-ому), x3 не существенная :

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

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

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

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

1) T0

Рассмотрим Самодвойственные функции S - student2.ru T0

Самодвойственные функции S - student2.ru T0

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

Самодвойственные функции S - student2.ru и покажем, что полученная Самодвойственные функции S - student2.ru T0. Для этого найдем значение Самодвойственные функции S - student2.ru на нулевом наборе :

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

2) T1

Рассмотрим Самодвойственные функции S - student2.ru T1

Самодвойственные функции S - student2.ru T1

Рассмотрим Самодвойственные функции S - student2.ru :

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

S

Рассмотрим Самодвойственные функции S - student2.ru S

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

Рассмотрим Самодвойственные функции S - student2.ru :

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

М

Рассмотрим Самодвойственные функции S - student2.ru М

Самодвойственные функции S - student2.ru М

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

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

рассмотрим произвольную пару сравнимых наборов Самодвойственные функции S - student2.ru и Самодвойственные функции S - student2.ru : Самодвойственные функции S - student2.ru и покажем, что выполнено : Самодвойственные функции S - student2.ru .

Нетрудно видеть, что из того, что Самодвойственные функции S - student2.ru следует, что Самодвойственные функции S - student2.ru и Самодвойственные функции S - student2.ru .

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

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

L

Рассмотрим Самодвойственные функции S - student2.ru L

Самодвойственные функции S - student2.ru L

Самодвойственные функции S - student2.ru , где α и β - некоторые константы.

Рассмотрим Самодвойственные функции S - student2.ru .

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

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

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

Степень Самодвойственные функции S - student2.ru не превосходит 1, следовательно Самодвойственные функции S - student2.ru L.

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

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

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

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

Для того, чтобы система Самодвойственные функции S - student2.ru была полной, необходимо и достаточно, чтобы она целиком не содержалась ни в одном из пяти классов: T0, T1 , S, M, L.

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

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

Пример: Самодвойственные функции S - student2.ru .

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

Пример: Самодвойственные функции S - student2.ru

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

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

Пример: Самодвойственные функции S - student2.ru - не полная, так как Самодвойственные функции S - student2.ru Самодвойственные функции S - student2.ru

и критерий Поста справедлив для данной системы, т.к. Самодвойственные функции S - student2.ru Самодвойственные функции S - student2.ru L.

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

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

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

Пусть K Самодвойственные функции S - student2.ru M, тогда Самодвойственные функции S - student2.ru [K]. Пусть K Самодвойственные функции S - student2.ru L, тогда Самодвойственные функции S - student2.ru [K]. Получаем противоречие (система не является полной, в силу замкнутости классов T0, T1, S, M, L относительно суперпозиций).

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

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

Построим заведомо полную систему Самодвойственные функции S - student2.ru .

I этап : Самодвойственные функции S - student2.ru

II этап : Самодвойственные функции S - student2.ru

I этап: Самодвойственные функции S - student2.ru и Самодвойственные функции S - student2.ru , и переименуем все их переменные в Самодвойственные функции S - student2.ru : Самодвойственные функции S - student2.ru и Самодвойственные функции S - student2.ru :

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

X f0 f1
1,0
1,0

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

1) Самодвойственные функции S - student2.ru

2) Самодвойственные функции S - student2.ru

3) Самодвойственные функции S - student2.ru

4) Самодвойственные функции S - student2.ru

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

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

1 случай :

X f0 f1

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

4 случай :

X f0 f1

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

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

2 случай :

X f0 f1

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

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

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

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

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

Разобьем множество переменных Самодвойственные функции S - student2.ru на два множества Самодвойственные функции S - student2.ru и Самодвойственные функции S - student2.ru .

Самодвойственные функции S - student2.ru - переменные, которые не изменяются в двух данных наборах, а Самодвойственные функции S - student2.ru - все остальные переменные:

Самодвойственные функции S - student2.ru И теперь все переменные множества Самодвойственные функции S - student2.ru переименнуем в x, а во все переменные множества Самодвойственные функции S - student2.ru подставим соответствующие константы :

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

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

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

X1 x2 X3 x4 x5 fM

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

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

3 случай :

X f0 f1

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

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

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

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

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

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

Теперь в переменные Самодвойственные функции S - student2.ru подставим x, а в Самодвойственные функции S - student2.ru подставим Самодвойственные функции S - student2.ru : Самодвойственные функции S - student2.ru .

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

Например, пусть пара противоположных наборов, на которых Самодвойственные функции S - student2.ru равна нулю, имеют вид :

X1 x2 X3 x4 x5 f

Тогда Самодвойственные функции S - student2.ru .

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

II этап :

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

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

Рассмотрим полином Жегалкина Самодвойственные функции S - student2.ru функции Самодвойственные функции S - student2.ru . Самодвойственные функции S - student2.ru .

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

Из всех слагаемых, содержащих Самодвойственные функции S - student2.ru и Самодвойственные функции S - student2.ru вынесем за скобку конъюнкцию этих двух переменных Самодвойственные функции S - student2.ru ; полином в скобках обозначим Самодвойственные функции S - student2.ru ; из всех слагаемых, содержащих только Самодвойственные функции S - student2.ru ,

вынесем за скобку Самодвойственные функции S - student2.ru : Самодвойственные функции S - student2.ru ; из всех слагаемых, содержащих Самодвойственные функции S - student2.ru , вынесем Самодвойственные функции S - student2.ru : Самодвойственные функции S - student2.ru ; останутся слагаемые, которые не содержат ни Самодвойственные функции S - student2.ru , ни Самодвойственные функции S - student2.ru , обозначим этот полином Самодвойственные функции S - student2.ru .

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

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

Самодвойственные функции S - student2.ru Таким образом, получили функцию Самодвойственные функции S - student2.ru ,

где Самодвойственные функции S - student2.ru некоторые константы.

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

b1 b2 b3 f(x1,x2)
Самодвойственные функции S - student2.ru
Самодвойственные функции S - student2.ru
Самодвойственные функции S - student2.ru
Самодвойственные функции S - student2.ru
Самодвойственные функции S - student2.ru
Самодвойственные функции S - student2.ru
Самодвойственные функции S - student2.ru
Самодвойственные функции S - student2.ru

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

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

1) Самодвойственные функции S - student2.ru ; 2) Самодвойственные функции S - student2.ru ; 3) Самодвойственные функции S - student2.ru ; 4) Самодвойственные функции S - student2.ru .

1) Самодвойственные функции S - student2.ru

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

2) Самодвойственные функции S - student2.ru .

3) Самодвойственные функции S - student2.ru .

4)

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

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

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

1) Самодвойственные функции S - student2.ru

2) Самодвойственные функции S - student2.ru

3) Самодвойственные функции S - student2.ru

4) Самодвойственные функции S - student2.ru

5) Самодвойственные функции S - student2.ru

6) Самодвойственные функции S - student2.ru

Упражнение 2:Получить из функции Самодвойственные функции S - student2.ru функции Самодвойственные функции S - student2.ru .

1) Самодвойственные функции S - student2.ru 2) Самодвойственные функции S - student2.ru 4) Самодвойственные функции S - student2.ru 5) Самодвойственные функции S - student2.ru не полная 6) Самодвойственные функции S - student2.ru Самодвойственные функции S - student2.ru Самодвойственные функции S - student2.ru Самодвойственные функции S - student2.ru Самодвойственные функции S - student2.ru 0 0 0 1 1 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 Самодвойственные функции S - student2.ru 1 0 0 1 0 1 0 1 0 0 1 1 0 1 0 1 1 1 0 0 Самодвойственные функции S - student2.ru

Примеры:

1) Исследовать на полноту систему Самодвойственные функции S - student2.ru :

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

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

Самодвойственные функции S - student2.ru :

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

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

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

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

Самодвойственные функции S - student2.ru получить функцию 0 :

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

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

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

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

Самодвойственные функции S - student2.ru получить Самодвойственные функции S - student2.ru и Самодвойственные функции S - student2.ru , и если «да», опишите определяющие выражения :

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

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

I : Самодвойственные функции S - student2.ru

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

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

II: Самодвойственные функции S - student2.ru

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

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

Самодвойственные функции S - student2.ruполучить функции

Самодвойственные функции S - student2.ru, и если “да”, опишите определяющие выражения :

  T0 T1 S M L
f1 - - - -  
f2         -
x1 x2 x3 f1
0 -
0 -

I : Самодвойственные функции S - student2.ru

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

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

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

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

1) Самодвойственные функции S - student2.ru ; 2) Самодвойственные функции S - student2.ru ; 3) Самодвойственные функции S - student2.ru ;

4) Самодвойственные функции S - student2.ru ; 5) Самодвойственные функции S - student2.ru ;

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

6)из системы функций Самодвойственные функции S - student2.ruполучить функцию Самодвойственные функции S - student2.ru ;

7)из системы функций Самодвойственные функции S - student2.ru

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

8)из системы функций Самодвойственные функции S - student2.ruполучить функции Самодвойственные функции S - student2.ru ;

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

Самодвойственные функции S - student2.ruполучить функции

Самодвойственные функции S - student2.ru ;

10) из системы функций Самодвойственные функции S - student2.ruполучить функции Самодвойственные функции S - student2.ru ;

Наши рекомендации