Дзержинский. Дискретная математика

Легко проверить, что они монотонны. Теорема 1.

(x1,…,xn) является монотонной тогда и только тогда, когда ее сокращенная ДНФ не содержит отрицаний.

Теорема 2.

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

[M] = M

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

Проведем это доказательство для частного вида суперпозиция, отсюда ясно как сделать его для общего случая.

Пусть

(x1,…,xn), (x1,…,xn), (, ) M. (21.4)

Рассмотрим

F(x1,…,xn) = ( (x1,…,xn), (x1,…,xn)). (21.5)

Требуется доказать что F M, тем самым будет доказано, что класс M замкнут.

Пусть , , причем (т.е. i i ). Следует доказать F( ) F( ). Из того, что , , M что ( ) ( ); F ( ) F ( ).

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

Двойственность, напомним, вводилась следующим образом:(x1,…,xn), – булева функция.

(x1,…,xn) = (, …, ). (28.1)

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

f= ( , …, ), т.е. другими словами:

= f (, …, ) (28.2)

или

f (x1,…,xn) = (, …, ). (28.3)

Теорема.

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

[S] = S.

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

Вытекает из принципа двойственности.

Пусть (, …, ), (, …, ), … (, …, ) S (28.4)

43

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

F(, …, ) = ( (, …, ), …, (, …, )). (28.5)

Нужно доказать: = F. Принцип двойственности:

(, …, ) = (, …, ), … (, …, )

В силу самодвойственности

= (, …, ) = F(, …, ) (28.6)

ч.т.д.

2.24 Классы функций, сохраняющих константу.

Определение: классом функций, сохраняющим 0, называются все булевы функции (, …, ), для которых выполнено: (0, …,0) = 0. Обозначение: .

Классом функций, сохраняющих 1, называются все булевы функции (, …, ), для которых выполняется (1, …, 1) = 1. Обозначение: .

Эти оба класса оказываются замкнутыми.

Теорема.

Классы функций, сохраняющих const, являются замкнутыми

F(, …, ) = ( 2(, …, ), …, s (, …, )). (29.2)

Проверим это, вычислив:

F(0, …, 0) = ( 2 (0, …, 0), …, s (0, …, 0)) = (0, …, 0) = 0 (29.3)

Таким образом [] = .

Вторая часть теоремы доказывается аналогично. Подведем итоги.

Замкнутыми являются классы L, M, S, , . Эти классы называются основными замкнутыми классами функций.

2.25 Теорема о функциональной полноте (Поста).

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

Теорема.

44

Система булевых функций = {, …, }, является функционально полной тогда и только тогда, когда она не содержится целиком ни в одном из основных замкнутых классах функций.

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

Лемма 1 (о несамодвойственной функции).

Если булева функция 1 (, …, ) несамодвойственна ( S), то, подставляя в нее вместо , …, переменную x или , можно получить булеву функцию (x), тождественно равную const (0; 1).

(x) = (24.1)

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

x, 1

(24.2)

x, 0

0 = ,

1 =

(чтобы проверить, нужно рассмотреть 0 = 0; 1 = = 1). Рассмотрим (x) = ( 1 1 , 2 2 , …, n n ).

Поскольку (, …, ) несамодвойственная, найдется хотя бы один

набор 1, …, n , такой что f* ( 1, …, n) ( 1, …, n), иначе бы эта функция была бы самодвойственной.

Другими словами ( 1 , …, n ) ( 1, …, n) т.е. всего два значения:

( 1 , …, n ) = ( 1, …, n),

хотя бы на одном наборе. Покажем, что (0) = (1).

(0) = ( 0 1 , 0 2 , …, 0 2 ) = ( 1 , …, n )

Заметим, что

(1 1 , 1 2 , …, 1 2 )= (1).

Начали с (0), а закончим в (1) (0) = (1), т.о. – const.

Пример.

(, ,) = (10110110)

Проверим, что S (не является самодвойственной).

Если =( 1, …, n), то =( 1 , …, n )

( 1 0 1 1 0 1 1 0) – не самодвойственная.

45

(000) = 1 cамодв. (111) = 0_______(инверсия)(001) = 0 самодв. (110) = 1(010) = 1 несамодв. (101) = 1

Достаточно найти 1 несамодвойственный набор, и функция будет несамодвойственна.

( , , )

(1)= (0,1,0) = 1(0)= (1,0,1) = 1

(0)= (1)=1 (0)= (1), ч.т.д.

Лемма 2 (о немонотонной функции).

Если функция M (, …) – немонотонная, то, подставив в нее вместо одного из переменных x, а вместо остальных некоторые const (0, 1), можно получить функцию (x) = .

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

Носит конструктивный характер, показывая, как решать задачи. Т.к. M найдутся два набора = ( 1, …, n); = ( 1, … n ) такие, что ; ( )

( ).

Соединим две вершины , куба некоторым путем, проходящим по ребрам , т.е. , что 1 2 … k< , и .

Пример.

Рис.21.

Поскольку i, i+1 являются соседними вершинами в кубе , они отличаются лишь одной координатой.

Имеется ( ) = 1, ( ) = 0.

46

Пусть вариация значения функции происходит на паре соседних вершин i ;

т.е. ( i) = 1, ( i+1) = 0. Раз эти вершины соседние, то они отличаются одной координатой (пусть, например, в ) .

имеет такой вид:

i = (0, 1, 2, …, N-1) = i+1 (1, 1, 2, …, N-1)

(x) = (x,х1 ,х2 , …, хn).

Проверим, что (x) = :

(0) = (0, 1, 2, …, N-1) = ( i) = 1 = x ;

(1) = (1, 1, 2, …, N-1) = ( i+1) = 0 = x

Ч.т.д.

Лемма 3 о нелинейной функции.

Если булева функция (, …, ) L нелинейна, то с помощью подстановки вместо переменных , …, величин x, или 0, 1 constant, взятие отрицания от самой функции можно получить конъюнкцию & .

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

Одновременно конструктивно показывается, как это сделать. Представим функцию (, …, ) в виде МЖ. Поскольку нелинейна, то найдется в МЖ одночлен, слагаемое, содержащее произведение каких-либо переменных. Пусть, например, & . Сгруппируем все слагаемые, содержащие & , и вынесем их за скобки. Затем сгруппируем остальные слагаемые, содержащие , и вынесем за скобки. Затем сгруппируем остальные слагаемые, содержащие , и вынесем за скобки. Среди остальных сгруппируем слагаемые и вынесем за скобки. Получим:

(, …, ) = 0 (, …, ) 1 (, …, ) 2 (, …, ) 3 (, …, ).

не зависит, ни от , ни от

Придадим , …, такие значения 3, …, n , чтобы 0 ( 3, …, n ) 0.

Обозначим значение 1( 3, …, n) = a; 2( 3, …, n) = b; 3( 3, …, n) = c. Какие это числа (a, b, c) зависит от функции.

Тогда можно записать, что булева функция:

(, , 3, …, n) = 1 a b с

Важное свойство двоичной суммы:

x d=

Рассмотрим функцию без индекса:

(, ) = ( b, a, ( 3, …, n ) ab с Если ab с 0, то (, ) = (, ,( 3, …, n)).

47

Проверим, что:

(, ) = & = ( b) & ( a)

a( b) b( a) c

ab c.

Раскроем теперь все скобки (будем иметь в виду, что d d = 0, т.е. можно приводить подобные):

(, ) = a b ab

a ab b ab c ab

c =

ч.т.д.

Пример (на использование леммы).

= (1111 0001) – булева функция трех переменных (, , ). Проверим, что

L. Найдем МЖ для нее в самом общем виде:

(, , ) =

.

Коэффициенты , , …, находятся из условия.

Всего будет восемь равенств и находим восемь неизвестных коэффициентов. Ответ будет таким:

Значит a = 1; b = 0; c = 1.

(, ) = (, 1, 1) 1 = (, , 1) = & .

Следствие из рассмотрение результата данного примера нам важно:

= (, , 1).

48

2.26 Доказательство теоремы о функциональной полноте.

Мы рассматриваем вопрос, когда система = {, …, } полна, т.е. через формулы можно вывести любую булеву функцию. Мы ввели пять основных классов , , L, M, S. Теорема утверждает, что если не содержится целиком в каком-либо из классов, то она полна. Это необходимые и достаточные условия.

1.Необходимость.

Пусть система полна. Докажем, что она не содержится целиком в одном из замкнутых классов. Вспомним определение замкнутого класса. Если бы система принадлежала , то из функций , путем суперпозиций над получались бы функции только из (по определению замкнутого класса) система не была бы полна. Для любого другого класса аналогично.

некоторые из f0, f1, f2, f3, f4 могут совпадать.

1) Покажем, что из функций можно получить Const 0, 1 (с помощью суперпозиции). Поскольку f0 f0(0, 0, …, 0) 0 f0 = 1. Возможно а) f0

(1, …, 1) = 1; б) f0 (1, …, 1) = 0.

Рассмотрим для а): (x) = f0 (x, x, …, x). Тогда

(0) = f0 (0, …,0) = 1; (1) = f0 (1, …,1) = 1. Итак

(x) = f0 (x, …, x) 1 («Тождественная единица»).

Поскольку f0 f0 (1, 1) = 0. Т.к. const «1», мы уже получили, то теперь получим «0».

0 = f1 (f0(x, …, x), f0(x, …, x), …, f0(x, …, x)).

Рассмотрим теперь б): (x) = f0(x, …, x). Тогда получаем (0) = f0(0, …, 0) = 1;

(1) = f0 (1, …, 1) = 0 (x) = .

Теперь применим лемму 1 о несамодвойственной функции. Можно, согласно нее, взять f4 S, и подставить в нее вместо , …, x и , и получить Const. Какую Const – не ясно, «0» или «1».

Если при этом получится 0, то Const 1 получаем так:

1 = (0) = f0 (0, …,0).

Если же по лемме 1 получится constant 1, то

0 = (1) = f0 (1, …, 1).

49

1.Проверим полноту. Для f0.

2.Для f1.

3.Для L. Воспользуемся предыдущим примером. По его результатам

L f2.

4.Для M. ( ; ( ) ( ))

Возьмем = (000), = (100); но f ( ) f ( ). Функция тоже немонотонная.

5.Остался класс S. f S (т.к. если взять значение (000) (000)).

6.Выразим через классы const 0, 1.

Для этого берем f(, , ), т.к. она .

f (0, 0, 0) = 1; f(0, 0, 0) = 1, т.е. это случай а) нашего доказательства (x) = f(xxx) 1.

Реализация

Рис.23.

Далее:

f (, , ) ; f (1, 1, 1) = 0.

Реализация рис.24.

Рис.24.

Будем искать отрицание: .

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

, ) M. ; f ( ) f ( ). После чего мы cоединяем вершины. Для и делать этого уже не надо – они рядом.

(x) = f (x, 0, 0) = . Схема решения рис.25.

Рис.25.

51

Соответствующие функциональные схемы приведены выше.

Можно построить функциональную схему для любой булевой функции.

Через функциональные элементы можно выразить любое арифметическое действие, интеграл, дифференциал и т.д.

С помощью леммы о нелинейной функции для

f1 (, , ) 1.

С помощью можно получить &:

& = f1 (, , 1) (См. выше)

Можно пользоваться ͞ для &.

Однако, посмотрев внимательно на f1, f2, схемы можно нарисовать проще, чем по алгоритму (менее громоздко).

Легко понять, что f легко задать аналитически. f1 =

Замечание к ФЭ ͞ . Можно получить проще, если заметить, что f1 (, , ) = ,

Т.е. что , - несущественные переменные.

Рис.26. Схема для конъюнкции

52