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

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

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

Функциональная полнота в слабом смыслеЛемма о нелинейной функции и лемма о немонотоннойфункции позволяют получить все булевы функции с помощьюнемонотонных функций, нелинейных функций и констант. Этоещё не функциональная полнота в обычном смысле, так как константы предполагаются данными с самого начала. Однако такоепредположение часто бывает оправданным в различных приложениях и прежде всего в синтезе логических схем, так как присхемной реализации константы 0 и 1 специальных элементов нетребуют. Поэтому имеет смысл ввести ослабленное понятиефункциональной полноты.Определение 16.1.

Система функций A   f1, f 2 ,...  P2называется функционально полной в слабом смысле, если любаябулева функция может быть представлена формулой над системой А  0,1 , т.е. является суперпозицией констант и функцийиз A .Теорема 16.1. Для того чтобы система функций A былафункционально полной в слабом смысле, необходимо и достаточно, чтобы она содержала хотя бы одну немонотонную и хотябы одну нелинейную функции.Доказательство.

Необходимость. Докажем от противного.Пусть A функционально полная система. Предположим, что Aне содержит немонотонную или нелинейную функции. Так как78классы монотонных и линейных функций замкнуты и содержатконстанты 0 и 1, то немонотонную или нелинейную функциинельзя получить суперпозицией функций из A и констант, т.е. Aне функционально полная система. Получили противоречие.Следовательно, наше предположение неверное, и необходимостьдоказана.Достаточность. Пусть A содержит немонотонную и нелинейную функции.

Тогда по лемме о немонотонной функции, подставляя в функцию f M  M вместо всех переменных константы итождественные функции, можно получить отрицание x . По лемме о нелинейной функции, подставляя в функцию f L  L вместовсех переменных константы и отрицания, можно получить либоконъюнкцию, либо отрицание конъюнкции.

Однако на первомэтапе отрицание уже получено, следовательно, всегда можно получить конъюнкцию.Система x , xy  0,1 - функционально полная. Так какx , xy  Aи x , xy  0,1  A  0,1 , то A  0,1 - функционально полная система, следовательно, A - функционально полная система в слабом смысле.Теорема доказана. □Пример 16.1.f  x, y, z    0010 1000 1.Дляфункцийиg  x, y, z   1001 0010 выяснить вопрос об их принадлежностиклассам T0 , T1, L, S , M .2. В случае, если некоторая функция представляет из себяфункционально полный класс, то:- выразить из неё с помощью суперпозиций функции 0, 1, x ,xy ;- реализовать функции 0, 1, x , xy на логических элементахфункции, представляющей функционально полный класс.3.

В случае, если некоторая функция представляет из себяфункционально полный в слабом смысле класс, то:- выразить из неё с помощью суперпозиций и фиксированияпеременных функции x , xy ;79- реализовать функции x , xy на логических элементах функции, представляющей функционально полный в слабом смыслекласс.Решение.1. Для функций f и g составим таблицы истинности:xyzfg0000100100010100110110010101001100111100Исследуем функцию f  x, y, z  .

Проверим f  x, y, z  на принадлежность классам Поста.f  0,0,0  0  f  T0 , f 1,1,1  0  f  T1.Так как наборы 0,0,0и1,1,1противоположны, иf  0,0,0   f 1,1,1  0 , то f  S .Для наборов  0,1,0   0,1,1 имеем f  0,1,0   f  0,1,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   010 100   x  0  y  1  z  0    x  1  y  0  z  0    x  1 y  z  1  x  y  1 z  1  xyz  xy  yz  y  xyz  xy  xz  x  xz  yz  x  yСледовательно Pf  xz  yz  x  y .Так как полином Жегалкина функции f содержит конъюнкцию, то f  L .80Для функции f составим критериальную таблицу:f  x, y, z T0 T1 S M+ - - -L-Функция f принадлежит классу T0 , поэтому система  f  неявляется функционально полным классом.

Так как f  M иf  L, то  f  - функционально полный в слабом смысле класс.Исследуем g  x, y, z  на принадлежность классам Поста.g  0,0,0  1  g  T0 , g 1,1,1  0  g  T1.Наборы1,0,1 и  0,1,0 противоположны, иg 1,0,1  g 1,0,1  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110   x  1 y  1 z  1   x  1 yz  xy  z  1  xyz  xy  xz  yz  x  y  z  1  xyz  yz  xyz  xy  1  x  y  z  xz  xyz .Следовательно, Pg  1  x  y  z  xz  xyz .Так как полином Жегалкина функции g содержит конъюнкцию, то g  L .Результаты анализа функции g  x, y, z  запишем в критериальную таблицу:81T0 T1 S M- - - -g  x, y, z L-Итак, функция g  x, y, z  не принадлежит ни одному из пятиклассов Поста, значит, система функций  g является функционально полным классом.2.

Так как система функций  g является функциональнополным классом, то выразим из неё с помощью суперпозицийфункции x , 0, 1, xy ;Построим отрицание x .Рассмотрим функцию s  x   g  x, x, x  . Найдём все значенияфункции s  x  :s  0   g  0,0,0   1s 1  g 1,1,1  0 s  x  x .Получили, что s  x   g  x, x, x  и s  x   x , поэтомуx  g  x, x, x  .Отрицание построено.Реализация отрицания x на логическом элементе функцииg  x, y, z  показана на рис. 16.1.Строим константу 0. Так как g  S , то найдём пару противоположных наборов  0,1,0  и 1,0,1 , на которых функция g равна0.

Выберем набор с наибольшим количеством единиц. В нашемслучае 1,0,1 , и введём функцию o  x  :o  x   g x1, x0 , x1  g  x, x , x   g  x, g  x, x, x  , x  .Найдём значения функции o  x   g  x, g  x, x, x  , x  на всех еёнаборах:o  0   g  0, g  0,0,0  ,0   g  0,1,0   0 ;o 1  g 1, g 1,1,1 ,1  g 1,0,1  0 .Получаем, что o  x   0 .82Так как o  x   0 и o  x   g  x, g  x, x, x  , x  , то0  g  x, g  x, x, x  , x  .Константа 0 построена.Реализация константы 0 на логических элементах функцииg  x, y, z  показана на рис. 16.1.хg« »«0»ggРис. 16.1. Реализация функций«1», 0, 1 на логических эле-ментах функции.Для получения константы 1 возьмём отрицание от функцииo  x  и обозначим полученную функцию e  x  .e  x   o  x   g  x, g  x, x, x  , x   g  g  x, g  x, x, x  , x  , g  x, g  x, x, x  , x  , g  x, g  x, x, x  , x  Итак, константа 1 получена:1  g  g  x, g  x, x, x  , x  , g  x, g  x, x, x  , x  , g  x, g  x, x, x  , x   .Реализация константы 1 на логических элементах функцииg  x, y, z  показана на рис.

16.1.Для построения конъюнкции из полинома Жегалкина строимвспомогательнуюфункциювидагдеxy  bx  cy  d ,b, c, d 0,1 . Например, можно сделать так:g  x, y,1  1  x  y  1  x 1  xy 1  xy  y  1.В результате получили выражение, у которого b  0 , c  1 , d  1.83Введём функцию k  x, y  :k  x, y   g  x  c, y  b,1  bc  d  g  x  1, y  0,1  g  x , y,1  g g  x, x, x  , y, g  g  x, g  x, x, x  , x  , g  x, g  x, x, x  , x  , g  x, g  x, x, x  , x  .Найдём значения функции k  x, y  на всех её наборах:k  0,0   g 1,0, g  g  0,1,0  , g  0,1,0  , g  0,1,0   g 1,0, g  0,0,0    g g  0,0,0  ,0, g  g  0, g  0,0,0  ,0  , g  0, g  0,0,0  ,0  , g  0, g  0,0,0  ,0   g 1,0,1  0 ;k  0,1  g 1,1, g  g  0,1,0  , g  0,1,0  , g  0,1,0   g 1,1, g  0,0,0    g g  0,0,0  ,1, g  g  0, g  0,0,0  ,0  , g  0, g  0,0,0  ,0  , g  0, g  0,0,0  ,0   g 1,1,1  0 ;k 1,0   g g 1,1,1 ,0, g  g 1, g 1,1,1 ,1 , g 1, g 1,1,1 ,1 , g 1, g 1,1,1 ,1  g 0,0, g  g 1,0,1 , g 1,0,1 , g 1,0,1  g  0,0, g  0,0,0    g  0,0,1  0 ;k 1,1  g g 1,1,1 ,1, g  g 1, g 1,1,1 ,1 , g 1, g 1,1,1 ,1 , g 1, g 1,1,1 ,1  g 0,1, g  g 1,0,1 , g 1,0,1 , g 1,0,1  g  0,1, g  0,0,0    g  0,1,1  1.Составим таблицу функции k  x, y  :84x0 0 1 1y0 1 0 1k  x, y  0 0 0 1Как видим, таблица функции k  x, y  совпадает с таблицей конъюнкции, следовательно, k  x, y   x  y .Так как k  x, y   x  y иk  x, y   g g  x, x, x  , y, g  g  x, g  x, x, x  , x  , g  x, g  x, x, x  , x  , g  x, g  x, x, x  , x  ,тоx y  g g  x, x, x  , y, g  g  x, g  x, x, x  , x  , g  x, g  x, x, x  , x  , g  x, g  x, x, x  , x  ,Конъюнкция построена.Реализация конъюнкции x  yg  x, y, z  показана на рис.

16.2.на логическом элементеу хg« »g«0»g«1»gРис. 16.2. Реализация конъюнкцииэлементах функции85«»на логических.3. С помощью фиксирования переменных выразим из функции f функцию x . Найдём два соседних наборах  0,1,0  и 0,1,1 , на которых нарушается монотонность. Определим функцию   x   f  0,1, x  и найдём её значения:  0   f  0,1,0   1   x  x . 1  f  0,1,1  0Так как   x   f  0,1, x  и   x   x , то x  f  0,1, x  .

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

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