Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Реалізація булевих функцій схемами з функціональних елементів
|
|
Під функціональним елементом розуміють деякий пристрій, який має такі властивості: 1) він має п≥ 1 впорядкованих відростків зверху - входи і один відросток знизу -вихід; 2) на входи цього пристрою можна подавати сигнали, які мають значення 0 та 1; 3) для кожного набору сигналів на входах пристрій на виході у той самий момент, коли надійшли сигнали на входи, видає один з сигналів (0 або 1); 4) набір сигналів на входах однозначно визначає сигнал на виході, тобто, якщо у різні моменти на входи надійшли рівні набори сигналів, то в ці моменти на виході буде один і той самий сигнал. Кожному функціональному елементу з п входами ставлять у відповідність булеву функцію від п змінних. f (x 1, x 2, …, xn) у такий спосіб. Входу з номером і (1≤ і≤ п) ставлять у відповідність зміннухi, а кожному набору(а1а2,..., ап) значень змінних - числова, f(а1, a 2, ..., аn), яке дорівнює 0 або 1 залежно від сигналу, що видається на виході у разі подачі цього набору сигналів на входи функціонального елемента. Щодо функції f (x 1, x 2, …, xn) кажуть, що даний функціональний елемент їїреалізує.
Рис. 8.9
Далі розглядатимемо лише функціональні елементи, зображені на рис. 8.9, які реалізують, відповідно, булеві функції заперечення, кон'юнкцію та диз'юнкцію.
Визначимо поняття схеми з функціональних елементів та її входиівихід.
1. Кожний функціональний елемент є схемою з функціональних елементів з тими ж входами і виходом, що й у цього елемента.
2. Якщо S 1- схема з функціональних елементів і два її входи з'єднані (рис. 8.10), то отримана конструкція S є схемою з функціональних елементів. Входами схеми S є всі не з'єднані входи S lі ще один вхід, який відповідає двом з'єднаним входам схеми S 1.
Рис. 8.10Рис. 8.11
3. Якщо S 1 та S 2 - дві схеми з функціональних елементів, то конструкція яку отримують з'єднанням деякого входу схеми S 2 з виходом схеми S 1, також є схемою з функціональних елементів (рис. 8.11). Входами схеми S є всі входи схеми S 1 і всі входи схеми S 2, за виключенням того, який з'єднаний з виходом схеми S 1. Виходом схеми S є вихід схеми S 2.
4. Якщо в схемі з функціональних елементів S 1 її вхід з'єднати з виходом деякого функціонального елемента з S без утворення циклу для будь-якого функціонального елемента (тобто вихід будь-якого функціонального елемента не повинен з'єднуватись з його входом, можливо, через інші елементи з S 1), то отримана конструкція є схемою з функціональних елементів (приклад такої конструкції наведено нарис. 8.12).
Означення схеми з функціональних елементів завершене Згідно з ним схема з функціональних елементів - це математичний об'єкт. Зазначимо, що вона має різні технічні застосування.
Очевидно, що схема з функціональних елементів реалізує певну булеву функцію. Оскільки допустимими є з'єднання елементів, які відповідають суперпозиціям відповідних елементарних функцій, а система{ 
}функціонально повна, то будь-яку булеву функцію можна реалізувати схемою з функціональних елементів, зображених на рис. 8.9.
Під час побудови схем використовують викладені у параграфі 8.5 методи мінімізації булевих функцій.
Приклад 8.33. Побудувати схему з функціональних елементів, яка реалізує булеву функцію 
.За методом карт Карно знаходимо мінімальну ДНФ (див. приклад 8.29) 
.Відповідну схему показано на рис. 8.13. ▲
Рис. 8.13
Однак, зазначимо, що мінімізація булевих функцій не вичерпує всіх можливостей мінімізації схем. Наприклад, схема, зображена нарис. 8.12, реалізує булеву функцію 
. Ця схема має п'ять елементів - це менше, ніж містить символів операцій будь-яка формула булевої алгебри, яка реалізує цю функцію. Методи побудови схем з функціональних елементів розглянуто в [7].
Нехай S - схема із елементів кон'юнкції, диз'юнкції та заперечення, Lf (S)- кількість елементів у схемі яка реалізує булеву функцію f. Далі, нехайL(f)=minLf(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 |
Для того, щоб врахувати біт перенесення с, використовують схему, яку називають повним суматором. Входи цієї схеми такі: х, у та біт перенесення з попереднього розряду сi Виходів два: сума s у даному розряді і нове перенесення с i +1 (у наступний розряд). Відповідні булеві функції задані у табл. 8.11.
Зобразимо функції s та с i +1 у досконалій диз'юнктивній нормальній формі:
Таблиця 8.11
| Вхід | Вихід | |||
| x | y | ci | s | ci+ 1 |
Але замість того, щоб будувати повні суматори безпосередньо за вказаними формулами, використовують півсуматори. Схему повного суматора з використанням півсуматорів наведено на рис. 8.15.
Нарешті, нарис. 8.16 показано, як повні суматори і пів- суматор використовують для додавання трирозрядних цілих чисел х 3 х 2 х 1 та y 3 y 2 y 1у двійковій системі числення. Результат - двійкове число s 4 s 3 s 2 s 1. Зазначимо, що s 4 (старший розряд суми) збігається зс3. Аналогічно будують схему для додаванняп-розрядних двійкових чиселxnxn-1 … x1таynyn-1…y1.
Задачі
1. Побудувати таблиці булевих функцій, які задані формулами а-г:
a) 
б) 
;
в) 
;
г) 
.
2. Скільки булевих функцій від п змінних приймають однакові значення на протилежних наборах? Протилежні значення на протилежних наборах?
3. За функціями f (x 1, …, х2) та g (х 3, х4) заданими векторно, побудувати векторне задания функції h:
а) 
=(1011), 
=(1001), h (x 2, x 3, x 4)= f (g (x 3, x 4), x 2);
б) =(1011), =(1001), h (x 1, x 2, x 3, x 4)= f (x 1, x 2)∨ g (x 3, x 4).
4. Знайти фіктивні змінні функції:
а) f (
)=(11110000);
б) f()=(00110011);
в) f (
) = (11000011).
5. Використовуючи тотожні перетворення, довести рівносиль-ність формул F та G:
а) 
;
б) 
;
в) 
6. За принципом двоїстості побудувати формулу, яка реалізує функцію, двоїсту до f:
а) 
;
б) 
;
в) 
.
7. Функції а -в задані векторами. Побудувати вектори для двоїстих функцій.
а) f ()=(11110000); б) f ()=(00101100);
в) f (
)= (00111100).
8. Чи є функція f двоїстою до функції g?
а) 
, 
;
б ) 
, 
;
в) 
, 
.
9. Задано формулу в алгебрі Жегалкіна. Побудувати рівносильну формулу в алгебрі Буля.
а ) 
; б ) 
; в ) 
.
10. Задано формулу в алгебрі Буля. Побудувати рівносильну формулу в алгебрі Жегалкіна.
а ) 
; б ) 
; в ) 
.
11. Зобразити функції а - в досконалою диз'юнктивною нормальною формою (використати таблицю функції):
а) f ()=(01101100); б) f ()=(10001110);
в) 
.
12. Перейти від диз'юнктивної нормальної форми а-г до досконалої диз'юнктивної нормальної форми:
а ) 
; б ) 
в) 
; г) 
13. За допомогою тотожних перетворень побудувати досконалу диз'юнктивну нормальну форму функцій а - в:
а ) 
; б ) 
;
в ) 
.
14. Для функцій задачі 11 побудувати досконалі кон'юнктивні нормальні форми (використати таблицю функції).
15. Перетворити диз'юнктивні нормальні форми із задачі 12 у кон'юнктивні нормальні форми.
16. Побудувати досконалі кон'юнктивні нормальні форми для функцій із задачі 15.
17. Підрахувати кількість функцій 
, для яких досконала кон'юнктивна нормальна форма є одночасно диз'юнктивною нормальною формою.
18. Методом невизначених коефіцієнтів побудувати поліном Жегалкіна для функцій а-в:
а) 
=(11111000); б) =(00110100);
в) 
=(0011100і).
19. На основі тотожних перетворень побудувати поліном Жегалкіна для функцій а-в:
а) 
; б) 
;
в) 
20. З використанням властивості полінома Жегалкіна знайти істотні змінні функцій а - в:
а ) 
;
б) 
;
в ) 
.
21. Для функцій із задачі 11 перейти від досконалої диз'юнктивної нормальної форми до полінома Жегалкіна.
22. Довести, що система булевих функцій Q повна, для цього виразити функції деякої повної системи через функції системи Q:
а) Q ={ 
}; б) Q ={ 
, 
};
в) Q ={ 
, (
) 
}.
23. З'ясувати, яким із множин, T 1 \T 2належать функції а-в:
а) 
;
б ) 
;
в) 
. 
24. З'ясувати, для яких значень п функція належить множині T 1 \T 2:
а ) 
= х1⨁ х2⨁...⨁ х n ⨁ 1;
б) 
.
25. Підрахувати кількість булевих функцій n змінних у множинах а-г:
а) T 0∩ T 1; б) T 0∪ T 1; г)Т0\Т1
26. Які з функційа-г самодвоїсті?
а) 
;
б) 
;
в) 
(11110000); г) 
= (00101100).
27. З несамодвоїстої функції f підстановкою 
та х отримати константу:
а ) 
; б) 
.
28. Які з функційа-г монотонні?
а) 
; б) 
;
в) 
; г) 
.
29. З немонотонної функції f підстановкою 0, 1 та х отримати функцію 
:
а ) 
; б ) 
;
30. Які з функційа-г лінійні?
а) 
; б) 
;
в) 
;
г) 
= (1001011010010110).
31. Довести, що якщо 
- лінійна функція, відмінна від константи, то 
. Чи правильне обернене твердження?
32. Суперпозицією констант 0 та 1, а також функції і нелінійної функції f отримати кон'юнкціюху:
а ) 
; б) 
(01101110).
33. З'ясувати, чи можна отримати функцію 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 0∪ T 1));
н) Q =(S ∩ M) ∪ (L \ M)∪ (T 0\ S);
п) Q =(M \(T 0∩ T 1))∪ (L \ S).
38. Які неповні системи із задачі 37 є слабко функціонально повними?
39. Для кожної з наведених нижче функцій за методом Куайна побудувати скорочену диз'юнктивну нормальну форму та за
Імплікантною таблицею знайти всі тупикові та мінімальні диз'юнктивні нормальні форми:
а ) 
;
б ) 
;
в ) 
;
г ) 
;
д)Nf={(000), (001), (011), (100), (111)};
е ) Nf={(001), (011), (101), (110)};
ж)Nf={(001), (011), (100), (110)};
и)Nf={(000), (010), (011), (100)}.
40. Для кожної з функцій із задачі 39 побудувати скорочену диз'юнктивну нормальну форму за методом Мак-Класкі.
41. Знайти мінімальні диз'юнктивні нормальні форми для функцій із задачі 39 за методом карт Карно.
42. Для кожної з функцій, наведених нижче, побудувати скорочену диз'юнктивну нормальну форму за методом Мак-Класкі та знайти всі мінімальні диз'юнктивні нормальні форми:
а ) 
;
б ) 
;
в ) 
;
г ) 
.
43. Знайти мінімальні диз'юнктивні нормальні форми функцій із задачі 42 за методом карт Карно.
44. Для кожної з функцій, наведених нижче, побудувати скорочену диз'юнктивну нормальну форму за методом Блейка.
а) 
;
б ) 
;
в) 
.
45. Для кожної з функцій, наведених нижче, побудувати скорочену диз'юнктивну нормальну форму за методом Нельсона.
а) 
;
б) 
;
в) 
.
46. Побудувати схеми з функціональних елементів кон'юнкції, диз'юнкції та заперечення, які реалізують функції:
а) 
; б) 
;
в) 
;
г) 
;
д) 
; е ) 
;
ж) 
; и) 
.
47. Скориставшись тотожністю
,
побудувати схеми з функціональних елементів кон'юнкції, диз'юнкції та заперечення для наведених нижче функцій:
a) 
; б) 
;
в) 
; г) 
.
48. Побудувати схему з функціональних елементів кон'юнкції, диз'юнкції та заперечення, яка має 4 входи. На входи подають комбінації двійкового коду десяткових цифр 0, 1, 2,..., 9. На виході має видаватись 1 в тому й лише в тому випадку, коли комбінації на входах відповідають одноцифровим числам:
а) непарним;
б) таким, що не діляться на 3;
в) таким, що не дорівнюють 4, 5, 6.
Скористатись методом карт Карно.