8.6. Реалізація булевих функцій схемами з функціональних елементів

Під функціональним елементом розуміють деякий пристрій, який має такі властивості: 1) він має п≥1 впорядкованих відростків зверху - входи і один відросток знизу -вихід;2) на входи цього пристрою можна подавати сигнали, які мають значення 0 та 1; 3) для кожного набору сигналів на входах пристрій на виході у той самий момент, коли надійшли сигнали на входи, видає один з сигналів (0 або 1);4) набір сигналів на входах однозначно визначає сигнал на виході, тобто, якщо у різні моменти на входи надійшли рівні набори сигналів, то в ці моменти на виході буде один і той самий сигнал. Кожному функціональному елементу з п входами ставлять у відповідність булеву функцію від п змінних. f(x₁, x₂, …, x_n) у такий спосіб. Входу з номером і (1≤і≤п) ставлять у відповідність зміннух_i, а кожному набору(а₁а₂,...,а_п) значень змінних - числова,f(а₁, a_2, ...,а_n), яке дорів­нює 0 або 1 залежно від сигналу, що видається на виході у разі подачі цього набору сигналів на входи функціонального елемента. Щодо функції f(x₁, x₂, …, x_n) кажуть, що даний функціональний елемент їїреалізує.

Рис. 8.9

Далі розглядатимемо лише функціональні елементи, зображені на рис. 8.9, які реалізують, відповідно, булеві функції заперечення, кон'юнкцію та диз'юнкцію.

Визначимо поняття схеми з функціональних елементів та їївходиівихід.

1. Кожний функціональний елемент є схемою з функціональних елементів з тими ж входами і виходом, що й у цього елемента.

2. Якщо S₁- схема з функціональних елементів і два її входи з'єднані (рис. 8.10), то отримана конструкція Sє схемою з функціо­нальних елементів. Входами схеми Sє всі не з'єднані входи S_lі ще один вхід, який відповідає двом з'єднаним входам схемиS₁.

Рис. 8.10Рис. 8.11

3. ЯкщоS₁ та S₂ - дві схеми з функціональних елементів, то конст­рукція яку отримують з'єднанням деякого входу схеми S₂ з вихо­дом схемиS₁, також є схемою з функціональних елементів (рис. 8.11). Входами схеми S є всі входи схеми S₁ і всі входи схеми S₂, за виключенням того, який з'єднаний з виходом схеми S₁. Виходом схеми S є вихід схемиS₂.

4. Якщо в схемі з функціональних елементів S₁ її вхід з'єднати з виходом деякого функціонального елемента з S без утворення циклу для будь-якого функціонального елемента (тобто вихід будь-якого функціонального елемента не повинен з'єднуватись з його входом, можливо, через інші елементи з S₁), то отримана конструкція є схемою з функціональних елементів (приклад такої конструкції наведено нарис. 8.12).

Означення схеми з функціональних елементів завершене Згідно з ним схема з функціональних елементів - це математичний об'єкт. Зазначимо, що вона має різні технічні застосування.

Очевидно, що схема з функціональних елементів реалізує певну булеву функцію. Оскільки допустимими є з'єднання елементів, які відповідають суперпозиціям відповідних елементарних функцій, а система{ }функціонально повна, то будь-яку булеву функцію можна реалізувати схемою з функціональних елементів, зображених на рис. 8.9.

Під час побудови схем використовують викладені у параграфі 8.5 методи мінімізації булевих функцій.

Приклад 8.33. Побудувати схему з функціональних елементів, яка реалізує булеву функцію .За методом карт Карно знаходимо мінімальну ДНФ (див. приклад 8.29) .Відповідну схему показано на рис. 8.13. ▲

Рис. 8.13

Однак, зазначимо, що мінімізація булевих функцій не вичерпує всіх можливостей мінімізації схем. Наприклад, схема, зображена нарис. 8.12, реалізує булеву функцію . Ця схе­ма має п'ять елементів - це менше, ніж містить символів операцій будь-яка формула булевої алгебри, яка реалізує цю функцію. Мето­ди побудови схем з функціональних елементів розглянуто в [7].

Нехай S - схема із елементів кон'юнкції, диз'юнкції та запере­чення, L_f(S)- кількість елементів у схемі яка реалізує булеву функціюf.Далі, нехайL(f)=minL_f(S),де мінімум береться за всіма схемами S, які реалізують функцію f. Уведемо функцію L(n)=maxL(f), де максимум береться за всіма булевими функціями від n змінних.

Теорема 8.31(теорема Шеннона-Лупанова). Для функціїL(n)виконується

причому для довільного ε>0 кількість булевих функційf, для яких прямує до 0 з ростом п.▲

Зауваження. ФункціюL(n) називаютьфункцією Шеннона(на честь американського математика К. Шеннона).Символ ~ тут озна­чає асимптотичну рівність: . Зміст другого твердженнятеореми полягає в тому, що з ростом n майже всі булеві функції реалі­зуються зі складністю, близькою до верхньою межі, тобтоL(n).▲

Теорема 8.31свідчить, що більшість булевих функцій (у разі n→∞) мають складні мінімальні схеми. Це означає, що практичну цінність, з огляду на побудову схем, має достатньо вузький клас булевих функ­цій. Тому поряд з універсальними методами побудови схем [7] необ­хідно мати методи, пристосовані для певних класів булевих функ­цій, які більшою мірою враховують їхні властивості. Далі ознайо­мимось з одним підходом до реалізації достатньо вузького класу функцій.

Покажемо, як схеми з функціональних елементів можна вико­ристати для додавання двох цілих додатних чисел у двійковій системі числення. Спочатку побудуємо схему, яка обчислюєх+у, де х тау- біти. Входи схеми - цех тау; на кожний із них може бути поданий сигнал 0 або 1. Конструкція буде об'єднанням двох схем (матиме два виходи). Вихідsдає суму бітів у даному розряді, а вихідс використовують для біту перенесення у наступний розряд. У табл. 8.10 наведені значення на входах і виходах схеми, яку називаютьпівсуматором. Саму схему наведено на рис. 8.14. Зазначимо, що з табл. 8.10 маємо:

Таблиця 8.10

Вхід		Вихід
x	y	s	c
0 0 1 1	0 1 0 1	0 1 1 0	0 0 0 1

Для того, щоб врахувати біт перенесення с, використовують схему, яку називають повним суматором. Входи цієї схеми такі: х, у та біт перенесення з попереднього розряду с_i Виходів два: сума s у даному розряді і нове перенесення с_i+1 (у наступний розряд). Відповідні булеві функції задані у табл. 8.11.

Зобразимо функції s та с_i+1 у досконалій диз'юнктивній нормаль­ній формі:

Таблиця 8.11

Вхід			Вихід
x	y	ci	s	ci+1
0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1	0 1 0 1 0 1 0 1	0 1 1 0 1 0 0 1	0 0 0 1 0 1 1 1

А ле замість того, щоб буду­вати повні суматори безпосе­редньо за вказаними форму­лами, використовують півсуматори. Схему повного сума­тора з використанням півсуматорів наведено на рис. 8.15.

Нарешті, нарис. 8.16 пока­зано, як повні суматори і пів- суматор використовують для додавання трирозрядних ці­лих чисел х₃х₂х₁ таy₃y₂y₁у двійковій системі числення. Результат - двійкове число s₄s₃s₂s₁. Зазначимо, щоs₄ (старший розряд суми) збігається зс₃. Аналогічно будують схему для додаванняп-розрядних двійкових чиселx_nx_n-1 … x₁таy_ny_n-1…y₁.

Задачі

1. Побудувати таблиці булевих функцій, які задані формулами а-г:

a)

б) ;

в) ;

г) .

2. Скільки булевих функцій від п змінних приймають однакові значення на протилежних наборах? Протилежні значення на протилежних наборах?

3. За функціямиf(x₁, …, х₂) таg(х₃,х₄) заданими векторно, побудувати векторне задания функції h:

а) =(1011), =(1001),h(x₂, x₃, x₄)=f(g(x₃, x₄), x₂);

б) =(1011), =(1001), h(x_1, x₂, x₃, x₄)=f(x_1, x₂)∨g(x₃, x₄).

2. Знайти фіктивні змінні функції:

а) f( )=(11110000);

б) f( )=(00110011);

в) f( ) = (11000011).

2. Використовуючи тотожні перетворення, довести рівносиль-ність формулF та G:

а) ;

б) ;

в)

2. За принципом двоїстості побудувати формулу, яка реалізує функцію, двоїсту доf:

а) ;

б) ;

в) .

2. Функції а -в задані векторами. Побудувати вектори для двоїс­тих функцій.

а)f( )=(11110000);б)f( )=(00101100);

в)f( )= (00111100).

2. Чи є функціяfдвоїстою до функції g?

а) , ;

б) , ;

в) , .

9. Задано формулу в алгебрі Жегалкіна. Побудувати рівносильну формулу в алгебрі Буля.

а) ; б) ; в) .

9. Задано формулу в алгебрі Буля. Побудувати рівносильну формулу в алгебрі Жегалкіна.

а) ;б) ; в) .

9. Зобразити функції а - в досконалою диз'юнктивною нор­мальною формою (використати таблицю функції):

а)f( )=(01101100); б)f( )=(10001110);

в) .

9. Перейти від диз'юнктивної нормальної форми а-г до доско­налої диз'юнктивної нормальної форми:

а) ; б)

в) ; г)

9. За допомогою тотожних перетворень побудувати досконалу диз'юнктивну нормальну форму функцій а - в:

а) ; б) ;

в) .

9. Для функцій задачі 11 побудувати досконалі кон'юнктивні нормальні форми (використати таблицю функції).

10. Перетворити диз'юнктивні нормальні форми із задачі 12 у кон'юнктивні нормальні форми.

11. Побудувати досконалі кон'юнктивні нормальні форми для функцій із задачі 15.

12. Підрахувати кількість функцій , для яких досконала кон'юнктивна нормальна форма є одночасно диз'юнктивною нор­мальною формою.

13. Методом невизначених коефіцієнтів побудувати поліном Жегалкіна для функцій а-в:

а) =(11111000);б) =(00110100);

в) =(0011100і).

9. На основі тотожних перетворень побудувати поліном Жегалкіна для функцій а-в:

а) ; б) ;

в)

9. З використанням властивості полінома Жегалкіна знайти істотні змінні функцій а - в:

а) ;

б) ;

в) .

9. Для функцій із задачі 11 перейти від досконалої диз'юнктивної нормальної форми до полінома Жегалкіна.

10. Довести, що система булевих функцій Qповна, для цього виразити функції деякої повної системи через функції системи Q:

а) Q={ }; б) Q={ , };

в)Q={ , ( ) }.

9. З'ясувати, яким із множин, T₁\T₂належать функції а-в:

а) ;

б) ;

в) .

9. З'ясувати, для яких значень п функція належить мно­жині T₁\T₂:

а) = х₁⨁х₂⨁...⨁х_n⨁1;

б) .

25. Підрахувати кількість булевих функцій n змінних у множинаха-г:

а)T₀∩T₁;б)T₀∪T₁;г)Т₀\Т₁

25. Які з функційа-г самодвоїсті?

а) ;

б) ;

в) (11110000); г) = (00101100).

25. З несамодвоїстої функціїfпідстановкою та х отримати константу:

а) ;б) .

25. Які з функційа-г монотонні?

а) ;б) ;

в) ; г) .

25. З немонотонної функціїfпідстановкою 0, 1 та х отримати функцію :

а) ;б) ;

25. Які з функційа-г лінійні?

а) ;б) ;

в) ;

г) = (1001011010010110).

25. Довести, що якщо - лінійна функція, відмінна від кон­станти, то . Чи правильне обернене твердження?

26. Суперпозицією констант 0 та 1, а також функції і нелінійної функціїfотримати кон'юнкціюху:

а) ; б) (01101110).

25. З'ясувати, чи можна отримати функціюfсуперпозицією функ­цій системи Q?

а) ,Q={ };

б) ,Q={ }

в) f=0, Q={ , 1}.

34. Чи можна з функції за допомогою суперпозиції отримати функцію ?

35. Серед лінійних функцій самодвоїстими є ті, у яких поліном Жегалкіна має непарну кількість змінних, а самодвоїстими - парну. Довести.

36. Серед лінійних функцій монотонними є лише константи 0,1 та тотожна функція х. Довести.

37. Використовуючи критерій повноти системи булевих функцій, з'ясувати, чи є система Q функціонально повною:

а) Q={ , , 1};

б)Q={ , , 0, 1};

в)Q={ , };

г)Q={ , , 1};

д)Q={ , };

е)Q={ 0};

ж)Q={ , 0, 1};

з)Q={ , };

и)Q={ , };

к)Q={0, 1, };

л)Q={(01101001), (10001101), (00011100)};

м)Q=(S\M)∪(L\(T₀∪T₁));

н)Q=(S∩M) ∪(L\M)∪(T₀\S);

п)Q=(M\( T₀∩T₁))∪(L\S).

34. Які неповні системи із задачі 37 є слабко функціонально повними?

35. Для кожної з наведених нижче функцій за методом Куайна побудувати скорочену диз'юнктивну нормальну форму та за

Імплікантною таблицею знайти всі тупикові та мінімальні диз'юнктивні нормальні форми:

а) ;

б) ;

в) ;

г) ;

д)N_f={(000),(001),(011),(100),(111)};

е)N_f={(001),(011), (101), (110)};

ж)N_f={(001), (011), (100), (110)};

и)N_f={(000),(010),(011),(100)}.

40. Для кожної з функцій із задачі 39 побудувати скорочену диз'юнктивну нормальну форму за методом Мак-Класкі.

41. Знайти мінімальні диз'юнктивні нормальні форми для функцій із задачі 39 за методом карт Карно.

42. Для кожної з функцій, наведених нижче, побудувати скоро­чену диз'юнктивну нормальну форму за методом Мак-Класкі та знайти всі мінімальні диз'юнктивні нормальні форми:

а) ;

б) ;

в) ;

г) .

40. Знайти мінімальні диз'юнктивні нормальні форми функцій із задачі 42 за методом карт Карно.

41. Для кожної з функцій, наведених нижче, побудувати скоро­чену диз'юнктивну нормальну форму за методом Блейка.

а) ;

б) ;

в) .

45. Для кожної з функцій, наведених нижче, побудувати скоро­чену диз'юнктивну нормальну форму за методом Нельсона.

а) ;

б) ;

в) .

45. Побудувати схеми з функціональних елементів кон'юнкції, диз'юнкції та заперечення, які реалізують функції:

а) ; б) ;

в) ;

г) ;

д) ; е) ;

ж) ; и) .

45. Скориставшись тотожністю

,

побудувати схеми з функціональних елементів кон'юнкції, диз'юнкції та заперечення для наведених нижче функцій:

a) ;б) ;

в) ;г) .

45. Побудувати схему з функціональних елементів кон'юнкції, диз'юнкції та заперечення, яка має 4 входи. На входи подають ком­бінації двійкового коду десяткових цифр 0,1,2,...,9. На виході має видаватись 1 в тому й лише в тому випадку, коли комбінації на входах відповідають одноцифровим числам:

а) непарним;

б) таким, що не діляться на 3;

в) таким, що не дорівнюють 4,5,6.

Скористатись методом карт Карно.