Геометрическая интерпретация двоичных функций. 1 страница

Пример.

Предполные классы двоичных функций.

4)

3).

2).

L

L

М

М

S

S

M M

M M

M M

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

S S

S S

S S

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

Сохраняющие единицу- T1.

T_{0 :} T_1:

T₀, T₁

T₀, T₁

T₀ , T₁

T₀, T₁

T₀, T₁

T₀ , T₁

T₀ , T₁

T₀, T₁

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

.

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

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

x1	x2	x3	f(x1x2x3) S
0
0
0

Пример:

S S

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

Например:

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

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

.

x

x₁

x₂

y

x1	x2	x3	f(x1x2x3) M

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

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

x1	x2	x3	f(x1x2x3) M

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

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

Рассмотрим :

Рассмотрим М

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

:и

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

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

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

Рассмотрим 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, а в подставим : .

Дата добавления: 2017-01-13