Курсовая работа: Минимальные формы булевых многочленов

Четыре выражения - 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, -} : вместо x_i ’ и x_i запишем 0 и 1 соответственно, а вместо опущенных переменных запишем черточку. Например, вместо w ’ x ’ y ’ z запишем 0001 , а вместо w ’ x ’ z – 00-1 .

Шаг 2 . Произведения, рассматриваемые как троичные n -ки, разбиваются на классы эквивалентности в соответствии с числом единиц. Упорядочим классы по возрастанию этого числа. В нашем примере:

w ’ x ’ y ’ z 0 0 0 1

w ’ x ’ yz ’0 0 1 0

w ’ x ’ yz 0 0 1 1

wx ’ yz ’1 0 1 0

wx ’ yz 1 0 1 1

wxyz ’1 1 1 0

wxy ’ z ’1 1 0 0

Шаг 3. Используя правило (* ), нужно складывать только произведения из соседних классов, т.е. когда числа единиц в соответствующих последовательностях отличаются лишь на 1 . При этом мы должны сравнивать выражения из соседних классов, имеющих черточки в одних и тех же позициях. Если два таких выражения отличаются точно в одной позиции, то они имеют вид р = i ₁ i ₂ … i_r … i_n и q = i ₁ i ₂ … i_r ’… i_n , где все i_k лежат в {0, 1, -} , а i_r лежит в {0, 1}. Тогда (* ) сводит p , q к i ₁ i ₂ … i_{r -1} - i_{r +1} … i_n , причем 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

Так как сумма всех простых импликантов необязательно является минимальным выражением, алгоритм требует выполнения ещё одного шага.