В картах наборы переменных, на которых функция принимает единичные значения, помечаются нечисловыми символами. Карта с нанесёнными на ней значениями ФАЛ называется диаграммой.
Карты, на которых коды наборов изображаются в восьмеричной системе счисления, называются картами Вейча.
Минимизация функций по методу Квайна
При минимизации по методу Квайна в базисе И, ИЛИ, НЕ исходная ФАЛ задаётся в СДНФ Целью минимизации является нахождение всех первичных импликант и выбор некоторых из них для минимальной записи функции.
Импликанта функции - некоторая логическая функция, обращаемая в нуль при наборе переменных, на котором сама функция также равна нулю.
Поэтому любой конъюнктивный терм, входящий в состав СДНФ, или группа термов, соединённых знаками дизъюнкции являются импликантами исходной ФАЛ. Импликанты имеют единичные значения только на подмножестве наборов из множества наборов, на которых исходная ФАЛ равна единице.
Первичная импликанта функции - импликанта типа элементарной конъюнкции некоторых переменных, никакая часть которой уже не является импликантой.
Задача минимизации по методу Квайна решается путём попарного сравнения всех импликант, входящих в ФАЛ, с целью выявления возможности их неполного склеивания по какой-то переменной на промежуточных этапах. При склеивании снижается ранг термов. Склеивание проводится до тех пор, пока не останется ни одного терма, допускающего склеивание с каким-либо другим термом. Термы, подвергшиеся склеиванию, отмечаются. Неотмеченные термы представляют собой первичные импликанты. После получения множества всех первичных импликант исследуется возможность нахождения простейшей записи ФАЛ. Для этого составляется таблица, в первой строке которой записаны минтермы исходной ФАЛ, а в первом столбце записаны все найденные первичные импликанты. Клетки этой таблицы помечаются в том случае, если первичная импликанта входит в состав какого-либо минтерма исходной ФАЛ. После этого задача упрощения сводится к тому, чтобы найти такое минимальное количество первичных импликант, которые покрывают все столбцы минтермов исходной ФАЛ.
Минимизация функций по методу Мак-Класки
Недостатком метода Квайна является - необходимость исчерпывающего попарного сравнения или сопоставления всех минтермов на этапе нахождения первичных импликант. С ростом числа минтермов увеличивается количество попарных сравнений.
Числовое представление ФАЛ позволяет упростить самый трудоёмкий первый этап. Все минтермы СДНФ ФАЛ записываются в виде их двоичных кодов, а все коды разбиваются по числу единиц на непересекающиеся группы.
Минтермы, подлежащие склеиванию, различаются только по одной переменной, а их коды - только в одном разряде. По этой причине сравнению подлежат только двоичные коды минтермов соседних групп.
Рассмотрев несколько методов минимизации ФАЛ, можно сделать вывод о том, что для решения нашей задачи наиболее подходящим является метод Мак-Класки.
Минимизируем Y:
Y=010001v010010v010011v010100v010101v010110v010111v011000v011001v110001v110010v110011v110100v110101v110110v110111v111000v111001
| i | xQ4Q3Q2Q1Q0 | Восьмеричное число |
| 2 | 010001 | 21 |
| 010010 | 22 | |
| 010100 | 24 | |
| 011000 | 30 | |
| 3 | 010011 | 23 |
| 010101 | 24 | |
| 010110 | 26 | |
| 011001 | 31 | |
| 110001 | 61 | |
| 110010 | 62 | |
| 110100 | 64 | |
| 111000 | 70 | |
| 4 | 010111 | 27 |
| 110011 | 63 | |
| 110101 | 65 | |
| 110110 | 66 | |
| 111001 | 71 | |
| 5 | 110111 | 67 |
Склеивание 1
| i | xQ4Q3Q2Q1Q0 | Восьмеричное число |
| 2 | 0100-1 | 21, 23 |
| 010-01 | 21, 25 | |
| 01-001 | 21, 31 | |
| -10001 | 21, 61 | |
| 01001- | 22, 23 | |
| 010-10 | 22, 26 | |
| -10010 | 22, 62 | |
| 01010- | 24, 25 | |
| 0101-0 | 24, 26 | |
| -10100 | 24, 64 | |
| 01100- | 30, 31 | |
| -11000 | 30, 70 | |
| 3 | 010-11 | 23, 27 |
| -10011 | 23, 63 | |
| 0101-1 | 25, 27 | |
| -10101 | 25, 65 | |
| 01011- | 26, 27 | |
| -010110 | 26, 66 | |
| -11001 | 31, 71 | |
| 1100-1 | 61, 63 | |
| 110-01 | 61, 65 | |
| 11-001 | 61, 71 | |
| 11001- | 62, 63 | |
| 110-10 | 62, 66 | |
| 11010- | 64, 65 | |
| 1101-0 | 64, 65 | |
| 11100- | 64, 66 | |
| 4 | -10111 | 27, 67 |
| 110-11 | 63, 67 | |
| 1101-1 | 65, 67 | |
| 11011- | 66, 67 |
Склеивание 2
| i | xQ4Q3Q2Q1Q0 | Восьмеричное число |
| 2 | 010--1 | 21, 23, 25, 27 |
| -100-1 | 21, 23, 61, 63 | |
| -10-01 | 21, 25, 61, 65 | |
| -1-001 | 21, 31, 61, 71 | A |
| 010-1- | 22, 23, 26, 27 | |
| -1001- | 22, 23, 62, 63 | |
| -10-10 | 22, 26, 62, 63 | |
| 0101-- | 24, 25, 26, 27 | |
| -1010- | 24, 25, 64, 65 | |
| -101-0 | 24, 26, 64, 66 | |
| -1100- | 30, 70, 31, 71 | B |
| 3 | -10-11 | 23, 27, 63, 67 |
| -101-1 | 25, 27, 65, 67 | |
| -1011- | 26, 27, 66, 67 | |
| 110--1 | 61, 63, 65, 67 | |
| 110-1- | 62, 63, 66, 67 | |
| 1101-- | 64, 65, 66, 67 |
Склеивание 3
| i | xQ4Q3Q2Q1Q0 | Восьмеричное число | |||||||||||||||||||
| 2 | -10--1 | 21, 23, 25, 27, 61, 63, 65, 67 | C | ||||||||||||||||||
| -10-1- | 22, 23, 26, 27, 62, 63, 66, 67 | D | |||||||||||||||||||
| -101-- | 24, 25, 26, 27, 64, 65, 66, 67 | E | |||||||||||||||||||
| 21 | 22 | 23 | 24 | 25 | 26 | 27 | 30 | 31 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 70 | 71 | ||||
| A | ´ | ´ | ´ | ´ | |||||||||||||||||
| B | Ä | ´ | Ä | ´ | |||||||||||||||||
| C | ´ | ´ | ´ | ´ | ´ | ´ | ´ | ´ | |||||||||||||
| D | Ä | ´ | ´ | ´ | Ä | ´ | ´ | ´ | |||||||||||||
| E | Ä | ´ | ´ | ´ | Ä | ´ | ´ | ´ | |||||||||||||
Y= -1100-v-10-1-v-101--
Минимизируем D4
D4 = 001001v001010v001011v001100v001101v001110v001111v010100v
v010110v010111v011000v011001v101011v110110
| i | xQ4Q3Q2Q1Q0 | Восьмеричное число |
| 2 | 001001 | 11 |
| 001010 | 12 | |
| 001100 | 14 | |
| 010100 | 24 | |
| 011000 | 30 | |
| 3 | 001011 | 13 |
| 001101 | 15 | |
| 001110 | 16 | |
| 010110 | 26 | |
| 011001 | 31 | |
| 4 | 001111 | 17 |
| 010111 | 27 | |
| 101011 | 53 | |
| 110110 | 67 |
Склеивание 1
| i | xQ4Q3Q2Q1Q0 | Восьмеричное число |
| 2 | 0010-1 | 11, 13 |
| 001-01 | 11, 15 | |
| 0-1001 | 11, 31 | A |
| 00101- | 12, 13 | |
| 001-10 | 12, 16 | |
| 00110- | 14, 15 | |
| 0011-0 | 14, 16 | |
| 0101-0 | 24, 26 | B |
| 01100- | 30, 31 | C |
| 3 | 001-11 | 13, 17 |
| -01011 | 13, 53 | D |
| 0011-1 | 15, 17 | |
| 00111- | 16, 17 | |
| 01011- | 26, 27 | E |
| -10110 | 26, 67 | F |
Склеивание 2
| i | xQ4Q3Q2Q1Q0 | Восьмеричное число | |
| 2 | 001--1 | 11, 13, 15, 17 | G |
| 001-1- | 12, 13, 16, 17 | H | |
| 0011-- | 14, 15, 16, 17 | I |
| 11 | 12 | 13 | 14 | 15 | 16 | 17 | 24 | 26 | 27 | 30 | 31 | 53 | 67 |
| A | ´ | ´ | |||||||||||
| B | Ä | ´ | |||||||||||
| C | Ä | ´ | |||||||||||
| D | ´ | Ä | |||||||||||
| E | ´ | Ä | |||||||||||
| F | ´ | Ä | |||||||||||
| G | ´ | ´ | ´ | ´ | |||||||||
| H | Ä | ´ | ´ | ´ | |||||||||
| I | Ä | ´ | ´ | ´ |
D4= 0101-0v01100-v-01011v01011-v-10110v001-1-v0011--
Минимизируем D3
D3 = 000100v000101v000110v000111v001000v001110v010001v010010v
v010011v010110v010111v100011v100101v100111v110001
| i | xQ4Q3Q2Q1Q0 | Восьмеричное число |
| 1 | 000100 | 4 |
| 001000 | 10 | A |
| 2 | 000101 | 5 |
| 000110 | 6 | |
| 010001 | 21 | |
| 010010 | 22 | |
| 3 | 000111 | 7 |
| 001110 | 15 | |
| 010011 | 23 | |
| 010110 | 26 | |
| 100011 | 43 | |
| 100101 | 45 | |
| 110001 | 61 | |
| 4 | 010111 | 27 |
| 100111 | 47 |
Склеивание 1
| i | xQ4Q3Q2Q1Q0 | Восьмеричное число |
| 1 | 00010- | 4, 5 |
| 0001-0 | 4, 6 | |
| 2 | 0001-1 | 5, 7 |
| -00101 | 5, 45 | |
| 00011- | 6, 7 | |
| 00-110 | 6, 15 | C |
| 0-0110 | 6, 26 | |
| 0100-1 | 21, 23 | D |
| -10001 | 21, 61 | E |
| 01001- | 22, 23 | |
| 010-10 | 22, 26 | |
| 3 | 0-0111 | 7, 27 |
| -00111 | 7, 47 | |
| 010-11 | 23, 27 | |
| 01011- | 26, 27 | |
| 100-11 | 43, 47 | F |
| 1001-1 | 45, 47 |
Склеивание 2