bulevy-funktsii-i-postr.-log.-skhem (1016573), страница 9

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 9)

Её реализация на логическом элементе g  x, y, z  показана на рис.12.1 б).g«0»g«1»а)б)Рис. 12.1. Реализация констант 0 и 1на логическом элементе.13. Лемма о немонотонной функцииЛемма 13.1 (о немонотонной функции). Из любой немонотонной булевой функции f  x1,..., xn  , подставляя вместо всех пе-ременных функции x, 0, 1, можно получить функцию   x   x .Доказательство. Пусть f  M , тогда существуют такиенаборы   1, 2 ,..., n  и    1,  2 ,...,  n  , что   и f    f  . Выделим те разряды i1 ,..., ik наборов  и  , на которых они различаются.

Очевидно, в наборе  эти разряды равны 0, а в наборе  - 1. Рассмотрим последовательность наборов 0 ,1,..., k такую, что   0 1 ...  k   . Набор  i 1 по69лучается из набора  i заменой одного из нулей, расположенногов одной из позиций i1 ,..., ik , на единицу. Образованные наборы i 1 и  i являются соседними, и для них выполняется соотношение  i i 1 , поэтому ii 1 . Поскольку f    1 и f     0 ,среди наборов  0 ,1 ,..., k найдутся два соседних  i и  i 1 , такие что f i   1 и f i 1   0 .

Пусть они различаются в r-омi  1,... r 1,0, r 1,..., n иi 1  1,... r 1,1, r 1,..., n  . Определим функцию  x   f 1,... r 1, x, r 1,..., n  .Так как   0   f i   1 и  1  f i 1   0 , то   x   x .разрядеЛемма доказана. □Пример13.1.Изнемонотоннойфункцииf  x, y, z   1001 1100 получить функцию x . Построить логическую схему, реализующую функцию x на логическом элементеf  x, y, z  .Решение. На соседних наборах  000  и  001 нарушаетсямонотонность функции f , т.к.

1  f  000   f  001  0 . Рассмот-рим функцию   x   f  0,0, x  . Найдём все значения этой функции:  0  f  0,0,0  1;  1  f  0,0,1  0 . Получаем, что  x   x . Отрицание построено x  f  0,0, x  .0 х« »Рис. 13.1. Реализация функциилогическом элементе70на.Реализация функции x на логическом элементе f  x, y, z показана на рис. 13.1.14. Лемма о нелинейной функцииЛемма14.1 (о нелинейной функции). Из любой нелинейнойбулевой функции f  x1,..., xn  , подставляя вместо всех перемен-ных функции x , x , y , y , 0, 1, можно получить   x, y   x  y или  x, y   x  y .Доказательство.

Пусть f  x1,..., xn   L . Рассмотрим полиномЖегалкина этой функции. Из нелинейности функции следует, чтов полиноме присутствуют слагаемые вида xi1  xi2  ... . Не ограничивая общности рассуждений, будем считать, что присутствуетпроизведение x1  x2  ... . Таким образом, полином Жегалкина данной функции имеет видf  x1,..., xn   x1  x2  P1  x3 ,..., xn   x1  P2  x3 ,..., xn   x2  P3  x3 ,..., xn   P4  x3 ,..., xn  ,P1  x3 ,..., xn   0 .гдеИначеговоря,существуютa3 , a4 ,..., an  E2  0,1 такие, что P1  a3 , a4 ,..., an   1.

Рассмотримвспомогательную функциюf  x1, x2 , a3 , a4 ,..., an   x1  x2 1  x1  b  x2  c  d ,где b, c, d 0,1 . Определим функцию h  x1, x2  :h  x1, x2   f  x1  c, x2  b, a3 , a4 ,..., an    x1  c    x2  b  1   x1  c   b   x2  b   c  d  x1x2  x1b  x2c  bc  x1b  bc  x2c  bc  d  x1x2 , bc  d  0; x1x2  bc  d   x1x2 , bc  d  1.Лемма доказана.

□Пример14.1.Изнелинейнойфункцииg  x, y, z    0010 1000 получить функцию x  y . Построить логи71ческую схему, реализующую функцию x  y на логическом элементе g  x, y, z  .Решение. Составим таблицу функции g  x, y, z  :xyzg  x, y, z 0000001001010110Найдём полином Жегалкина.g  x, y , z  x  a y b a,b,c  | g  a,b,c 11001101011001110 z  c    x  a  y  b  z  c   0,1,0 1,0,0   x  0  y  1  z  0    x  1  y  0  z  0    x  1 y  0 z  1   x  0  y  1 z  1   z  1  x  1 y  x  y  1   z  1 xy  y  xy  x    z  1 y  x  xz  yz  x  y .Итак, g  x, y, z   xz  yz  x  y .При помощи полинома Жегалкина надо построить вспомогательную функцию вида xy  bx  cy  d , где b, c, d 0,1 .

Придавпеременной z значение y , получимg  x, y, y   x  y  y  y  x  y  xy  y  x  y  xy  x .Исходя из общего вида вспомогательной функции, в данном случае имеем b  1, c  0 , d  0 .Определим функцию h  x, y  :h  x, y   g  x  c, y  b, y  b   g  x  0, y  1, y  1  g  x, y , y  .Найдём значение функции h  x, y   g  x, y , y  на всех еёнаборах:72x0011y0101h  x, y  g  0,1,1  0 g  0,0,0   0 g 1,1,1  0 g 1,0,0  1Как видим, таблица функции h  x, y  совпадает с таблицейТаккакh  x, y   x  y .h  x, y   g  x, y , y  и h  x, y   x  y , то x  y  g  x, y , y  .

Конъюнкция построена.конъюнкции,следовательно,х« »Рис. 14.1. Реализация конъюнкции на ЛЭ.Реализация конъюнкции x  yg  x, y, z  показана на рис. 14.1.на логическом элементе15. Теорема Поста о полноте системы булевыхфункцийОпределение 15.1.СистемабулевыхA   f1, f2 ,...  P2 называется полной, если  A  P2 .функцийУтверждение 15.1.

Пусть A — замкнутый класс и  A  P2 .Если В  A, то B - неполная система (подмножество неполнойсистемы будет также неполной системой).Доказательство. Пусть В  A, тогда  В   A  A  P2 и В  P2 . Следовательно, B - неполная система. Утверждение до-казано.□73Теорема 15.2 (теорема Поста). Система булевых функцийA   f1, f2 ,...  P2 является полной в P2 тогда и только тогда, когда она не содержится целиком ни в одном из следующих классов: T0 , T1, S , M , L .Доказательство. Необходимость докажем от противного.Пусть A — полная система (т.е.

 A  P2 ) и K - любой из классовT0 , T1, S , M , L .Предположим,чтотогдаA K, A   K   K  P2 и  A  P2 , т.е. A — неполная система. Получили противоречие. Следовательно, наше предположение, чтосистема содержится в одном из классов T0 , T1, S , M , L , неверное. Необходимость доказана.Достаточность. Пусть A  T0 , A  T1, A  S , A  M , A  L .Тогда в A существуют функцииf0  T0 , f1  T1, f S  S , f M  M , f L  L .Достаточно показать, что  A   f0 , f1, f S , f M , f L   P2 .

Разобьём доказательство на три части: получение отрицания, констант и конъюнкции.a) Получение x .Рассмотрим функцию f0  x1,..., xn   T0 и введём функцию0  x   f0  x, x,..., x  . Так как функция f 0 не сохраняет нуль, то0  0  f0  0,0,...,0   1 . Возможны два случая: либо 0 1  0 и0  x   x , либо 0 1  1 и 0  x   1. Если получим искомое от-рицание, то построение завершено. Иначе рассмотрим функциюf1  x1,..., xn   T1 и аналогичным образом введём функцию1  x   f1  x, x,..., x  . Так как функция f1 не сохраняет единицу, то1 1  f1 1,1,...,1  0 .

Возможны также два случая: либо 1  0   1и 1  x   x , либо 1  0   0 и 1  x   0 . Если получим отрицание,то построение завершено. Если же в обоих случаях получилиськонстанты, то применяем лемму о немонотонной функции. Согласно данной лемме, если подставить в функцию f M  M вме-74сто всех переменных константы и тождественные функции, томожно получить отрицание. Таким образом, отрицание получено.b) Получение констант 0 и 1. Имеем функцию f S  S .

Согласно лемме о несамодвойственной функции, подставляя вместовсех переменных функции f S отрицание, которое получено впункте a), и тождественную функцию, можно получить константы: 0,1   f S , x  . Константы получены.c) Получение конъюнкции x  y . Имеем функцию f L  L . Согласно лемме о нелинейной функции, подставляя в функцию f Lвместо всех переменных константы и отрицания (которые былиполучены на предыдущих шагах доказательства), можно получить либо конъюнкцию, либо отрицание конъюнкции.

Однако напервом этапе отрицание уже получено, следовательно, всегдаможно получить конъюнкцию:  xy, xy    f L ,0,1, x  . Конъюнкцияполучена.В результате получили, что  f0 , f1, f S , f M , f L    xy, x   P2Последнее равенство следует из пункта 2 теоремы 9.3. В силулеммы 9.2 достаточность доказана.Теорема доказана. □f  x, y, z   1001 0100 ;Пример.15.1. Даны функции:g  x, y, z   1001 0110 .1. Можно ли из функции f  x, y, z  с помощью суперпозицийполучить g  x, y, z  ?2. Верно ли, что f  x, y, z    g  ?Решение.Выпишем таблицу функций f и g .xyzfg0001100100010000111175100001011111001111001. Исследуем функцию f  x, y, z  . Проверим f  x, y, z  напринадлежность классам Поста.f  0,0,0  1  f  T0 ,f 1,1,1  0  f  T1.Так как наборы  0,0,1 и 1,1,0  противоположные иf  0,0,1  f 1,1,0   0 , то f  S .Для наборов  0,0,0   0,0,1 имеем f  0,0,0   f  0,0,1 , значит f  M .Найдём полином Жегалкина для f  x, y, z  :f  x, y , z   a,b,c  | f  a,b,c 1 x  a  y  b  z  c   1  a  1  b  1  c   000  011101  x  0  y  0  z  0    x  0  y  1  z  1    x  1  y  0  z  1    x  1 y  1 z  1   x  1 yz  x  y  1 z   x  1  y  1 z  1  yz   xyz  xz   x  1 yz  y  z  1  yz   xyz  xz   x  1 y  z  1  xyz  xz  xy  xz  x  y  z  1  xyz  xz  xyz  xy  x  y  z  1.Так как в полиноме Жегалкинаf  x, y, z   xyz  xy  x  y  z  1присутствуют конъюнкции, то f  L .Результаты анализа функции f  x, y, z  запишем в критериальную таблицу:f  x, y, z T0 T1 S M L- - - -76Строки таблицы соответствуют функциям исследуемогомножества булевых функций, а столбцы - классам Поста.

Знак«+» (плюс) в клетке таблицы означает, что функция принадлежитклассу Поста, знак «–» (минус) - не принадлежит.Функция f  x, y, z  не принадлежит ни одному из классовПоста, значит, система функций  f  является функциональнополным классом. Поэтому с помощью суперпозиций из функцииf  x, y, z  можно получить любую булеву функцию, в частностиg  x, y, z  .2.

Проверяем функцию g  x, y, z  на принадлежность классамПоста.g  0,0,0  1  g  T0 , g 1,1,1  0  g  T1.Так как на противоположных наборах1  g  0,0,0   g 1,1,1  0 , 0  g  0,0,1  g 1,1,0   1,0  g  0,1,0   g 1,0,1  1, 1  g  0,1,1  g 1,0,0   0 ,то g  S .Для наборов  0,0,0   0,0,1 имеем g  0,0,0   g  0,0,1 , значит g  M .Найдём полином Жегалкина для функции g  x, y, z  :g  x, y , z   a,b,c  | g  a,b,c 1 x  a  y  b  z  c   1  a  1  b  1  c   000  011101110   x  1 y  1 z  1   x  1 yz  x  y  1 z  xy  z  1   x  1  y  1 z  1  yz   xyz  xz  xyz  xy   x  1 yz  y  z  1  yz   xz  xy   x  1 y  z  1  xz  xy  xy  xz  x  y  z  1  xz  xy  x  y  z 177Так как в полиноме Жегалкина g  x, y, z   x  y  z  1 нетконъюнкций, то g  L .Критериальная таблица для функции g имеет вид:g  x, y, z Система gT0 T1 S M L- - + +не является функционально полной, так какg  S , поэтому f   g  .16.

Характеристики

Список файлов учебной работы