от w’x’yz и w’x’yz’ к w’x’y
от w’x’yz и w’x’y’z к w’x’z
от wx’yz и w’x’yz к x’yz
от wx’yz’ и w’x’yz’ к x’yz’
Здесь использованы, и потому должны быть помечены, все семь слагаемых.
В общем, эта процедура повторяется снова и снова с использованием только помеченных выражений (которые становятся короче). Прочие произведения суть простые импликанты и остаются неизменными.
В нашем примере второй раунд упрощения осуществляет переход
от wx’y и w’x’y к x’y
от x’yz и x’yz’ к x’y
Четыре выражения - wx’y, w’x’y, x’yz, x’yz’ – помечены. Остальные произведения, а именно wxz’, wyz’, w’x’z не могут быть упрощен. следовательно, р эквивалентно такой сумме простых импликантов:
р ~wxz’ + wyz’ + w’x’z + x’y.
Как уже было сказано, Мак-Класки улучшил это метод. Чтобы описать улучшенный алгоритм, используем многочлен
d = wxyz’ + wxy’z’ + wx’yz + wx’yz’ + w’x’yz + w’x’yz’ + w’x’y’z
Шаг 1. Считая переменные упорядоченными по алфавиту (или по номерам), поставим в соответствие каждому произведению последовательность символов из {0, 1, -}: вместо xi’ и xiзапишем 0 и 1 соответственно, а вместо опущенных переменных запишем черточку. Например, вместо w’x’y’z запишем 0001, а вместо w’x’z – 00-1.
Шаг 2. Произведения, рассматриваемые как троичные n-ки, разбиваются на классы эквивалентности в соответствии с числом единиц. Упорядочим классы по возрастанию этого числа. В нашем примере:
w’x’y’z0 0 0 1
w’x’yz’0 0 1 0
w’x’yz0 0 1 1
wx’yz’1 0 1 0
wx’yz1 0 1 1
wxyz’1 1 1 0
wxy’z’1 1 0 0
Шаг 3.Используя правило (*), нужно складывать только произведения из соседних классов, т.е. когда числа единиц в соответствующих последовательностях отличаются лишь на 1. При этом мы должны сравнивать выражения из соседних классов, имеющих черточки в одних и тех же позициях. Если два таких выражения отличаются точно в одной позиции, то они имеют вид р = i1i2…ir…in и q = i1i2…ir’…in, где все ik лежат в {0, 1, -}, а irлежит в {0, 1}. Тогда (*) сводит p, q к i1i2…ir-1 - ir+1 …in, причем p и q должны быть помечены. В рассматриваемом примере это дает такие четверки (метки относятся к следующему раунду, тогда как в предыдущем списке все произведения следовало пометить):
0 0 - 1
0 0 1 --
- 0 1 0-
- 0 1 1-
1 0 1 --
1 - 1 0
1 1 - 0
Помеченные выражения не являются простыми импликантами и во втором раунде этого шага дают единственное выражение
- 0 1 -
Итак, мы нашли все простые импликанты, а именно
0 0 1 - w’x’z
- 0 1 0 wyz’
- 0 1 1 wxz’
1 0 1 - x’y
Так как сумма всех простых импликантов необязательно является минимальным выражением, алгоритм требует выполнения ещё одного шага.
Шаг 4. В силу теоремы сумма всех простых импликантов для р эквивалентна р. поэтому для каждого слагаемого дизъюнктивной нормальной формы d многочлена р должен существовать простой импликант, являющийся произведением этого слагаемого. для выявления возникшего соответствия удобно использовать таблицу простых импликантов. столбцы этой таблицы индексируются дизъюнктами из d, а строки – простыми импликантами, вычисленными в шаге 3. на пересечении i-й строки и j-го столбца ставится крестик -, если простой импликант из i-й строки является подпроизведением произведения из j-го столбца. Говорят, что одно произведение покрывает, если первое является подпроизведением второго. Для того, чтобы найти сумму простых импликантов, которая будет эквивалентна d , мы из множества всех простых импликантов выбираем подмножество таким образом, чтобы каждое слагаемое в d покрывалось по крайней мере одним импликантом из подмножества. Тогда минимальной формой будет сумма простых импликантов с наименьшим числом членов и наименьшим числом букв. Простой импликант называется главным членом, если он покрывает произведение, не покрываемое никаким другим простым импликантом; сумма всех главных членов называется ядром. сначала мы находим ядро, затем обозначаем через q1,…,qk произведения, не покрываемые простыми импликантами из ядра; простые импликанты, не входящие в ядро, обозначим через р1,…,рm. Далее формируем таблицу, столбцы которой индексируются элементами qi, а строки – элементами рi. Крестик - на месте (i, j) указывает, что рi покрывает qj.
Теперь образуем произведение сумм. Каждый сомножитель соответствует одному из qj и является суммой тех рi, который покрывают этот qj. Используя законы булевой алгебры, мы преобразуем это выражение в простейшую возможную сумму произведений. Каждое из этих произведений представляет подмножество элементов рi, которые покрывают все qj. Далее рассматриваем произведения с наименьшим числом сомножителей. Из этих кратчайших произведений выбираем те, что содержат наименьшее общее число литералов. Теперь каждое из полученных произведений переписываем в виде суммы составляющих его простых импликантов, складываем с ядром, получая минимальную сумму произведений, эквивалентную р.
II.РЕШЕНИЕ МИНИМАЛЬНЫХ ФОРМ БУЛЕВЫХ МНОГОЧЛЕНОВ С ПОМОЩЬЮ МЕТОДА КУАЙНА – МАК-КЛАСКИ
Задача.Определим форму булева многочлена р, заданного в дизъюнктивной нормальной форме
d = v’w’x’y’z’ + v’w’x’yz’ + v’w’xy’z’ + v’w’xyz’ + v’wx’y’z + v’wx’yz’ + v’wxy’z + v’wxyz’ + v’wxyz + vw’x’y’z’ + vw’x’y’z + vw’xy’z + vwx’yz’ + vwxy’z’ + vwxyz’ + vwxyz
Решение:
Шаги 1 и 2
| 0 единиц | 0 0 0 0 0 | - | (1) |
| 1 единица | 0 0 0 1 00 0 1 0 01 0 0 0 0 | --- | (2)(3)(4) |
| 2 единицы | 0 0 1 1 00 1 0 0 10 1 0 1 01 0 0 0 1 | ---- | (5)(6)(7)(8) |
| 3 единицы | 0 1 1 0 10 1 1 1 01 0 1 0 11 1 0 1 01 1 1 0 0 | ----- | (9)(10)(11)(12)(13) |
| 4 единицы | 0 1 1 1 11 1 1 1 0 | -- | (14)(15) |
| 5 единиц | 1 1 1 1 1 | - | (16) |
Шаг 3. Комбинация строк (i) и (j) дает сокращение, указанное в строке (i)(j):
| (1)(2)(1)(3)(1)(4) | 0 0 0 - 00 0 - 0 0- 0 0 0 0 | --J |
| (2)(5)(2)(7)(3)(5)(4)(8) | 0 0 - 1 00 - 0 1 00 0 1 - 01 0 0 0 - | ---I |
| (5)(10)(6)(9)(7)(10)(7)(12)(8)(11) | 0 - 1 1 00 1 - 0 1 0 1 - 1 0 - 1 0 1 0 1 0 - 0 1 | -H--G |
| (9)(14)(10)(14)(10)(15)(12)(15)(13)(15) | 0 1 1 - 10 1 1 1 -- 1 1 1 01 1 -1 01 1 1 - 0 | F---Е |
| (14)(16)(15)(16) | - 1 1 1 1 1 1 1 1 - | -- |
Повторение этого шага с новыми строками дает нам
| (1)(2)(3)(5) | 0 0 - - | D |
| (2)(5)(7)(10) | 0 - - 1 0 | C |
| (7)(10)(12)(15) | - 1 - 1 0 | B |
| (10)(15)(14)(16) | - 1 1 1 - | A |
Пометки «птичкой»- и буквами сделаны после процесса упрощения. найденные простые импликанты обозначены буквами А, В, …J.
Шаг 4. Формируем таблицу простых импликантов, где индексы столбцов – слагаемые из d – представлены в виде двоичных столбцов.
| (1)00000 | (2)00010 | (3)00100 | (4)10000 | (5)00110 | (6)01001 | (7)01010 | (8)10001 | (9)01101 | (10)01110 | (11)10101 | (12)11010 | (13)11100 | (14)01111 | (15)11110 | (16)11111 |
| -111- А | - | - | - | - | |||||||||||
| -1-10 В | - | - | - | - | |||||||||||
| 0--10 С | - | - | - | - | |||||||||||
| 00--0 D | - | - | - | - | |||||||||||
| 111-0 E | - | - | |||||||||||||
| 011-1 F | - | - | |||||||||||||
| 10-01 G | - | - | |||||||||||||
| 01-01 H | - | - | |||||||||||||
| 1000- I | - | - | |||||||||||||
| -0000 J | - | - |
В наших кратких обозначениях ядро, т.е. сумма главных членов, есть D + H + G + B + E + A. Единственным произведение, не покрываемым ядро, является (4); это и есть q1. Простыми импликантами pi, не входящими в ядро, являются С, F, I, J. Новая таблица имеет вид