Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
4
Тема: Мінімізація функцій за допомогою карт Карно.
Мета: навчитися мінімізувати функції за допомогою карт Карно.
Завдання:
Для кожного варіанта задана функція від п'яти змінних номерами відсутніх конституант. Мінімізувати функцію за допомогою карт Карно. Визначити складність функції до та після мінімізації. Визначити всі можливі тупикові та мінімальні форми. Проаналізувати отримані результати. Індивідуальні варіанти завдань представлені в таблиці А.1 (додаток А).
Теоретичні основи
Графічний спосіб мінімізації функцій зручний для трьох, у крайньому випадку для чотирьох аргументів. Для того, щоб використовувати сам принцип цього методу для більшої кількості змінних була запропонована його модернізація. Ідея полягає в розгортці куба на площині. Покажемо цю розгортку на малюнку.
011 111
1
100 101 111 110 100
Виходячи з розгортки куба побудуємо наступну таблицю.
|
00 |
01 |
11 |
10 |
|
|
0 |
1 |
1 |
||
|
1 |
1 |
1 |
Побудована таблиця називається картою Карно. У карті позначено конституенти, присутні у функції. Подібно тому, як відмічені вершини куба поєднувалися в ребра й грані, поєднуються й одиниці карти в так звані інтервали. В інтервали можна поєднувати 2m одиниць, тобто 2,4,8…і т.д. Покажемо об'єднання одиниць і зчитування мінімальної форми на карті Карно.
|
М3 |
|||||
|
00 |
01 |
11 |
10 |
||
|
0 |
1 |
1 |
|||
|
М1 |
1 |
1 |
1 |
||
|
М2 |
Усього на карті виділено три інтервали. В кожний інтервал входять ті мінітерми, у яких він повністю перебуває. Виходячи з карти, мінімальна форма має вигляд :
__ __ __
f(М1, M2 , M3) = М1 M3 + M2 M3 + М1 M2, M3
Як видно, результат повністю збігається з попереднім. Покажемо, як виглядають карти Карно для чотирьох змінних.
|
00 |
01 |
11 |
10 |
|
|
00 |
1 |
1 |
||
|
01 |
1 |
1 |
||
|
11 |
1 |
1 |
||
|
10 |
1 |
1 |
Можна скласти карти Карно для п'яти й більше аргументів, однак, з ростом числа аргументів складність роботи з картою зростає швидше, і при цьому процес оптимізації важко алгоритмізувати.
Зміст звіту:
Контрольні питання.
Таблиця А.1 – Варіанти завдань
|
Номер варіанта |
відсутні конституенти |
Номер варіанта |
відсутні конституенти |
|
|
1 |
5, 9, 17, 26 |
17 |
7, 10, 11, 13, 29 |
|
|
2 |
4, 10, 15, 29 |
18 |
1, 4, 6, 7, 12, 30 |
|
|
3 |
7, 12, 13, 16, 26 |
19 |
5, 8, 10, 22, 30 |
|
|
4 |
3, 5, 18, 21 |
20 |
1, 4, 7, 12, 16, 27 |
|
|
5 |
2, 10, 22, 23 |
21 |
8, 14, 23, 26, 31 |
|
|
6 |
6, 9, 14, 20, 21 |
22 |
2, 6, 15, 20, 27 |
|
|
7 |
6, 7, 9, 21, 22 |
23 |
5, 15, 21, 27, 29 |
|
|
8 |
1, 3, 12, 23, 30 |
24 |
2, 4, 8, 11, 25, 30 |
|
|
9 |
5, 10, 11, 13, 28 |
25 |
11, 18, 27, 29, 31 |
|
|
10 |
8, 11, 16, 23 |
26 |
9, 13, 16, 20, 29 |
|
|
11 |
5, 16, 20, 26 |
27 |
7, 12, 22, 25, 31 |
|
|
12 |
6, 7, 22, 24, 30 |
28 |
0, 4, 8, 11, 22, 27 |
|
|
13 |
8, 20, 24, 30 |
29 |
13, 17, 24, 27, 28 |
|
|
14 |
1, 7, 13, 24, 28 |
30 |
7, 15, 25, 27, 29 |
|
|
15 |
2, 6, 12, 15, 26 |
31 |
1, 5, 9, 17, 23, 27 |
|
|
16 |
9, 11, 15, 21, 26 |
32 |
11, 16, 23, 25, 29 |