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

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

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

Классу T1 не принадлежат функции 0, x , x  y ,x | y , x  y.6011.3. Класс самодвойственных функцийОпределение 11.3.1. Булеву функциюf   x1, x2 ,..., xn   f  x1, x2 ,..., xn называют двойственной к функции f  x1, x2 ,..., xn  ,а наборы  x1, x2 ,..., xn  и  x1, x2 ,..., xn  называют противоположными.Применяя определение, для функции f  x, y, z   1001 0101построим таблицу двойственной функции f   x, y, z  :x y zf  x, y, z f   x, y, z 0 0 01f   0,0,0   f  0, 0, 0   f 1,1,1  1  00 0 10f   0,0,1  f  0, 0, 1   f 1,1,0   0  10 1 00f   0,1,0   f  0, 1, 0   f 1,0,1  1  00 1 11f   0,1,1  f  0, 1, 1   f 1,0,0   0  11 0 00f  1,0,0   f  1, 0, 0   f  0,1,1  1  01 0 11f  1,0,1  f  1, 0, 1   f  0,1,0   0  11 1 00f  1,1,0   f  1, 1, 0   f  0,0,1  0  11 1 11f  1,1,1  f  1, 1, 1   f  0,0,0   1  0Итак, для функции f  x, y, z   1001 0101 двойственной будет функция f   x, y, z    0101 0110  .Теорема 11.3.1 (принцип двойственности).Пусть Ф  x1, x2 ,..., xn   f  f1, f 2 ,..., f n  , тогдаФ  x1, x2 ,..., xn   f  f1 , f 2 ,..., f n .Доказательство.Ф  x1, x2 ,..., xn   f  f1  x1,..., xn  , f 2  x1,..., xn  ,..., f n  x1,..., xn   61 ff f f1  x1,..., xn , f 2  x1,..., xn ,..., f n  x1,..., xn  1 x1,..., xn , f2  x1,..., xn ,..., f n  x1,..., xn   f  f , f ,..., f .12nТеорема доказана.

□Класс самодвойственных функций определяется следующимобразом:S  f  x1,..., xn   P2 | f  x1,..., xn   f   x1,..., xn  .Пример 11.3.1. Доопределить функциюh  x, y, z   1  10  1  так, чтобы h  S . Выяснить вопрос о принадлежности построенной функции к классам T0 и T1 .Решение. Доопределим функцию h , используя определениесамодвойственной функции.Рассмотрим пары противоположных наборов: 000 и 111 ;  001 и 110 ;  010 и 101 ; 100 и  011 .Используя известные значения функции h , получим:h  000   1  h 111  0 ; h  010   1  h 101  0 ;h  011  0  h 100   1; h 110   1  h  001  0 .В результате имеем:xyzh  x, y, z 0001001-01010110100-101-1101111-h  x, y, z  1 0 1 0 1 0 1 0Проверим функцию на принадлежность классам T0 и T1 :h  000  1  h  T0 ; h 111  0  h  T1 .6211.4.

Класс монотонных функцийОпределение 11.4.1. Говорят, что набор  n предшествуетнабору  n , если  i  i i  1,2,..., n . Обозначают:  n  n .Рассмотрим наборы  3   001 ,  3   010  ,  3   011 . Длянаборов  3 и  3 неравенства, полученные при сравнении координат, имеют вид 0  0 , 0  1 и 1  0 . Поэтому набор  3 не предшествует набору  3 . Для наборов  3 и  3 неравенства имеютвид 0  0 , 0  1, 1  1, поэтому  3 3.Определение 11.4.2.

Наборы  n и  n называются сравнимыми, если  n  n или  n  n , иначе наборы называются несравнимыми.Определение 11.4.3. Набор  n непосредственно предшествует набору  n , если  n  n и они соседние. Обозначают:nn.Определение 11.4.4. Булева функция f  x1, x2 ,..., xn  называ-ется монотонной, если для любых сравнимых наборов  и выполняется импликация   f    f    .Определим класс монотонных функций:M  f  x1,..., xn   P2 |  ,  :    f    f   .Пример 11.4.1. Доопределить функциюf  x, y, z    101  0  так, чтобы f  M . Выяснить вопрос о принадлежности построенной функции к классам T0 и T1 .Решение.

Доопределим функцию f , используя определениемонотонной функции.Выпишем все наборы, между которыми можно установитьотношение непосредственного предшествования. Если функцияопределена на наборе, то снизу под набором запишем её значение. Имеем:63 000 1  000  000  2  000  000  3  000  001  011 111 ;11 001 101 111 ;1 010   011 111 ;0100 010  110  111 ;100  101 111 ;100  110  111.0Используя полученные цепочки и определение монотоннойфункции имеем:- так как f 110  0 , то на всех наборах, предшествующихнабору 110  , функция f тоже должна равняться нулю, т.е.f 100  f  000  0 ;- так как f  001  1, то на всех наборах, которым предшествует набор  001 , функция f тоже должна равняться единице,т.е.

f 101  f 111  1.В результате получим:xyzf  x, y, z 000-001101000111100-101-1100111-f  x, y, z  0 1 0 1 0 1 1 1Проверим функцию на принадлежность классам T0 и T1 :f  000  0  f  T0 ; f 111  1  f T1 .6411.5. Класс линейных функцийОпределение 11.5.1. Булева функция f  x1, x2 ,..., xn  называется линейной, еслиf  x1, x2 ,..., xn   a0  a1x1  ...  an xn , гдеai  0,1 .Класс линейных функций определяется следующим образом:L   f  x1,..., xn   P2 | f  x1, x2 ,..., xn   a0  a1x1  ...  an xn  .Пример 11.5.1. Доопределить функциюg  x, y, z      1  010так, чтобы g  L . Выяснить вопрос о принадлежности построенной функции к классам T0 и T1 .Решение. Доопределим функцию g , учитывая, что она линейная.

Запишем общий вид линейной функции от переменныхx, y , z :g  x, y, z   a0  a1x  a2 y  a3 z .Подставляя наборы значений аргументов, на которых определена функция, получим систему соотношений:g  011  1  a0  a1  0  a2 1  a3 1;g 101  0  a0  a1 1  a2  0  a3 1;g 110  1  a0  a1 1  a2 1  a3  0 ;g 111  0  a0  a1 1  a2 1  a3 1;илиa0  a2  a3  1;a0  0;a  a  a  0;a  1; 013 1a0  a1  a2  1;a2  0;a0  a1  a2  a3  0; a3  1.Итак, g  x, y, z   0  1 x  0  y  1 z  x  z . Исходя из этойформулы, найдём значения функции g на тех наборах, на которых она не была определена:65g  001  0  1  1; g  010  0  0  0 ; g 100  1  0  1.В итоге имеем:xyzg  x, y, z 000-001-010-0111100-101011011110g  x, y, z  0 1 0 1 1 0 1 0Проверим функцию на принадлежность классам T0 и T1 :g  000  0  g  T0 ; g 111  0  g  T1.11.6.

Замкнутость классов T0, T1, S, M и LТеорема 11.6.1. Классы T0 , T1, S , M , L замкнуты.Доказательство. Чтобы доказать, что некоторый класс Kзамкнут, достаточно показать, что если функция реализована ввиде формулы над K , то она принадлежит K .Пусть K один из классов T0 , T1, S , M , L , f , f1,..., f n  K иФ  x1,..., xn   f  f1  x1,..., xn  , f 2  x1,..., xn  ,..., f n  x1,..., xn   .При K  T0 ,Ф  0,...,0   f  f1  0,...,0  ,..., f n  0,...,0    f  0,...,0   0 ,следовательно, Ф  T0 и T0 замкнут.При K  T1,Ф 1,...,1  f  f1 1,...,1 ,..., f n 1,...,1   f 1,...,1  1,следовательно, Ф  T1 и T1 замкнут.При K  S ,Ф  x1,..., xn   f  f1  x1,..., xn  ,..., f n  x1,..., xn   f   f1  x1,..., xn  ,..., f n  x1,..., xn    f  f1  x1,..., xn  ,..., f n  x1,..., xn    Ф  x1,..., xn  ,66следовательно, Ф  S и S замкнут.При K  M , если   , то f1    f1  ,...

... ... f n    f n  ,и  f1   ,..., f n   f1  ,..., f n  . Следовательно,      Ф    f  f1   ,..., f n     f  f1    ,..., f n      Ф    ,поэтому Ф  M и M замкнут.При K  L , имеемf  a0  a1x1  ...  an xn ,f1  a10  a11x1  ...

 a1n xn ,...............f n  a0n  a1n x1  ...  ann xn .Подставляем выражения для функций f , f1,..., f n в формулу:Ф  x1,..., xn   f  f1  x1,..., xn  ,..., f n  x1,..., xn    a0  a1 f1  x1,..., xn   ...  an f n  x1,..., xn   a0  a1 a10  a11x1  ...  a1n xn  ...  an a0n  a1n x1  ...  ann xn  c0  c1x1  ...  cn xn .Следовательно, Ф  L и L замкнут.Теорема доказана. □12. Лемма о несамодвойственной функцииЛемма 12.1 (о несамодвойственной функции).

Из любойнесамодвойственной булевой функции f  x1,..., xn  , подставляявместо всех переменных функции x и x , можно получить  x   const .Доказательство. Пусть f  S , тогдаf  x1, x2 ,..., xn   f  x1,..., xn  .67Следовательно, существует набор   1,..., n  , на которомf 1,..., n   f 1,..., n   f 1,..., n   f 1,..., n .Построим функцию   x   f  x  1,..., x   n  , тогда  0  f  0  1,...,0   n   f 1,..., n  , 1  f 1  1,...,1   n   f 1,..., n  .Так как f 1,..., n   f 1,..., n  , то   0    1 и   x   const .Заметим, что замена переменных x1,..., xn функции f выражениями x   i , i  1,..., n удовлетворяет условию теоремы, так как x,  i  0,x i   x ,  i  1.Лемма доказана.

□Пример12.1.Изнесамодвойственнойфункцииg  x, y, z   1001 1100  получить константы 0 и 1. Построить логическую схему, реализующую константы 0 и 1 на логическомэлементе g  x, y, z  .Решение. Строим константу 0. Для этого найдём пару противоположных наборов, на которых функция g равна нулю. Этонаборы  001 и 110  .

Выберем набор 110  , и рассмотрим функцию o  x  :o  x   g x1, x1, x0  g  x, x, x  .Найдём значения функции o  x  на её наборах:o  0  g  0,0,1  0 ; o 1  g 1,1,0   0 .Поэтому, o  x   0 .Константа 0 построена, 0  g  x, x, x  . Её реализация на логическом элементе g  x, y, z  показана на рис. 12.1 а).Строим константу 1. Для этого найдём пару противоположных наборов, на которых функция g равна единице.

Это наборы 011 и 100 . Выберем набор  011 , и рассмотрим функциюе x :68е  x   g x0 , x1, x1  g  x , x, x  .Найдём значения функции е  x  на её наборах:е  0   g 1,0,0   1; е 1  g  0,1,1  1.Следовательно, е  x   1 .Константа 1 построена, 1  g  x , x, x  .

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

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