10.4 Контрольні запитання та завдання
1. Сформулюйте теорему Поста.
2. Який набір булевих функцій називається нескоротнім?
3. Сформулюйте висновок з теореми Поста.
4. Чи можна подати монотонну функцію формулою булевої алгебри без заперечень? Обґрунтуйте відповідь.
5. У чому полягає монотонність булевих функцій?
6. Який набір булевих функцій називається функціонально повним?
7. Перелічіть основні замкнуті класи булевих функцій.
8. Дайте визначення булевих функцій, що зберігають нуль та одиницю.
10.5 Приклади аудиторних і домашніх задач
1. Функція f1 є несамодвоїста функція, f2 – не зберігаюча 0, f3 – нелінійна, f4 – немонотонна та не зберігаюча 1, f5 – немонотонна. З яких функцій може бути складена повна система функцій?
2. Дослідіть дані функції на монотонність:
a) yxy;
б) xyyx;
в) x~y;
г) x(yx);
д) x(xy);
е) (xy)(xz)(yz).
3. Доведіть функціональну повноту кожної з функцій:
а) штрих Шиффера;
б) стрілка Пірса.
4. Доведіть повноту алгебри Жегалкіна.
6. З’ясуйте, чи зберігають 0 і 1 функції диз’юнкції, складання за модулем два, стрілка Пірса, еквівалентності?
7. З’ясуйте, чи самодвоїсті функції імплікації, штрих Шиффера, стрілка Пірса (за допомогою тотожних перетворень і таблиць істинності).
8. Використовуючи теорему Поста, з’ясуйте, чи будуть повними такі набори булевих функцій. Які з них є мінімально повними?
а)
;
б)
;
в)
;
г)
;
д)
;
е)
;
ж)
.
11 Практичне заняття № 9 методи мінімізації булевих функцій
11.1 Мета заняття
Набути навичок вибору мінімальної формули серед множини еквівалент-них формул, що задають дану булеву функцію. Навчитися мінімізувати булеві функції методом карт Карно.
11.2 Методичні рекомендації до самостійної роботи студентів
Під час підготовки до практичного заняття крім конспекту лекцій рекомендується використовувати [1, c. 155-182; 2, c. 155-182; 3, 50-55; 9, c. 56-59; 12, c. 69-95; 17, c. 23-63].
При вивченні і повторенні матеріалу слід звернути увагу на такі питання:
імпліканта, імпліцента, проста імпліканта, проста імпліцента;
скорочена диз’юнктивна (кон’юнктивна) нормальна форма;
повна система імплікант (імпліцент);
диз’юнктивне (кон’юнктивне) ядро;
тупикова диз’юнктивна (кон’юнктивна) нормальна форма;
критерії мінімізації; карти Карно для булевих функцій від n змінних;
частково-визначені булеві функції;
правила склеювання контурів карт Карно.
11.3 Приклади розв’язання типових завдань
1. Частково-визначена булева функція f(x,y,z,t) подана картою Карно (рис. 11.1). Отримати мінімальні КНФ та ДНФ.
Для мінімальної ДНФ доповнимо карту найбільш підходящими значеннями (клітинки, які позначено *) (рис. 11.2).
Рисунок 11.1
Прямокутнику
f1
відповідає елементарна диз’юнкція
,
f2
відповідає t.
Мінімальна ДНФ має вигляд
.
Для отримання мінімальної КНФ доповнимо
карту, як показано на рис. 11.3.
Рисунок 11.2
Рисунок 11.3
На
рис. 11.3 прямокутнику f1
відповідає елементарна кон’юнкція
,
а f2
– у.
Мінімальна КНФ має
вигляд
.
2.
Побудувати мінімальну
ДНФ і мінімальну КНФ для функції
f(x,y,z,t):
.
Для заданої функції карта Карно має вигляд:
Для мінімальної ДНФ |
Для мінімальної КНФ |
|
|
Мінімальна
ДНФ= |
Мінімальна
КНФ= |
