Решение минимальных форм булевых многочленов с помощью метода Куайна – Мак-Класки

от wxyz’ и wxy’z’ к wxz’

от wx’yz и wx’yz’ к wx’y

от wxyz’ и wx’yz’ к wyz’

от 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, -}: вместо x_i’ и x_i запишем 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’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

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

Шаг 4. В силу теоремы сумма всех простых импликантов для р эквивалентна р. поэтому для каждого слагаемого дизъюнктивной нормальной формы d многочлена р должен существовать простой импликант, являющийся произведением этого слагаемого. для выявления возникшего соответствия удобно использовать таблицу простых импликантов. столбцы этой таблицы индексируются дизъюнктами из d, а строки – простыми импликантами, вычисленными в шаге 3. на пересечении i-й строки и j-го столбца ставится крестик û, если простой импликант из i-й строки является подпроизведением произведения из j-го столбца. Говорят, что одно произведение покрывает, если первое является подпроизведением второго. Для того, чтобы найти сумму простых импликантов, которая будет эквивалентна d , мы из множества всех простых импликантов выбираем подмножество таким образом, чтобы каждое слагаемое в d  покрывалось по крайней мере одним импликантом из подмножества. Тогда минимальной формой будет сумма простых импликантов с наименьшим числом членов и наименьшим числом букв. Простой импликант называется главным членом, если он покрывает произведение, не покрываемое никаким другим простым импликантом; сумма всех главных членов называется ядром. сначала мы находим ядро, затем обозначаем через q₁,…,q_k произведения, не покрываемые простыми импликантами из ядра; простые импликанты, не входящие в ядро, обозначим через р₁,…,р_m. Далее формируем таблицу, столбцы которой индексируются элементами q_i, а строки – элементами р_i. Крестик û на месте (i, j) указывает, что р_i покрывает q_j.

Теперь образуем произведение сумм. Каждый сомножитель соответствует одному из q_j и является суммой тех р_i, который покрывают этот q_j. Используя законы булевой алгебры, мы преобразуем это выражение в простейшую возможную сумму произведений. Каждое из этих произведений представляет подмножество элементов р_i, которые покрывают все q_j. Далее рассматриваем произведения с наименьшим числом сомножителей. Из этих кратчайших произведений выбираем те, что содержат наименьшее общее число литералов. Теперь каждое из полученных произведений переписываем в виде суммы составляющих его простых импликантов, складываем с ядром, получая минимальную сумму произведений, эквивалентную р.

 

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 0 0 0 1 0 0 1 0 0 0 0	ü ü ü	(2) (3) (4)
2 единицы	0 0 1 1 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 1	ü ü ü ü	(5) (6) (7) (8)
3 единицы	0 1 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0 1 1 1 0 0	ü ü ü ü ü	(9) (10) (11) (12) (13)
4 единицы	0 1 1 1 1 1 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 - 0 0 0 - 0 0 - 0 0 0 0	ü ü J
(2)(5) (2)(7) (3)(5) (4)(8)	0 0 - 1 0 0 - 0 1 0 0 0 1 - 0 1 0 0 0 -	ü ü ü I
(5)(10) (6)(9) (7)(10) (7)(12) (8)(11)	0 - 1 1 0 0 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 - 1 0 1 1 1 - - 1 1 1 0 1 1 -1 0 1 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) 0 0 0 0 0

(2) 0 0 0 1 0

(3) 0 0 1 0 0

(4) 1 0 0 0 0

(5) 0 0 1 1 0

(6) 0 1 0 0 1

(7) 0 1 0 1 0

(8) 1 0 0 0 1

(9) 0 1 1 0 1

(10) 0 1 1 1 0

(11) 1 0 1 0 1

(12) 1 1 0 1 0

(13) 1 1 1 0 0

(14) 0 1 1 1 1

(15) 1 1 1 1 0

(16) 1 1 1 1 1

-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); это и есть q₁. Простыми импликантами p_i, не входящими в ядро, являются С, F, I, J. Новая таблица имеет вид

	(4) 1 0 0 0 0
0 - - 1 0 С
0 1 1 - 1 F
1 0 0 0 - I	û
- 0 0 0 0 J	û

 

Это обозначает, что мы получаем две минимальные форы:

1. D + H + G + B + E + A + I, если использовать I, и
2. D + H + G + B + E + A + J, если выбрать J.

В обычных обозначениях минимальная форма (i) такова:

v’w’z’ + v’wy’z + vw’y’z + wyz’ + vwxz’ + wxy + vw’x’y’.

 

 

 

ЗАКЛЮЧЕНИЕ

По результатам проведённого курсового исследования по теме «Минимальные формы булевых многочленов» можно  сделать следующие выводы.

При всей простоте своей  аксиоматики теория булевых алгебр весьма содержательна. Мы находим в ней немало трудных и глубоких проблем, многие из которых ещё не решены. Эти проблемы весьма разнообразны, они соприкасаются с логикой и теорией множеств, с теорией вероятностей и анализом. Такое обилие точек соприкосновения со смежными математическими дисциплинами роднит теорию булевых алгебр с функциональным анализом, к которому она близка и по своему общему математическому стилю.

Существуют различные  методы нахождения минимальных форм булевых многочленов. В своей курсовой работе мы исследовали методы - метод Куайна - Мак-Класки и метод минимизации булевых функций с помощью карт Карно. Он предназначен для нахождения множества простых импликант для функций, заданных совокупностью наборов, на которых функция равна единице, или дизъюнктивной совершенной нормальной формой. Умение минимизировать логические функции имеет огромное значение при проектировании устройств цифровой электроники.

 

СПИСОК ЛИТЕРАТУРЫ

1. Владимиров, Д.А. Булевы алгебры. – М.: Наука, 1969. – 254 с.
2. Дискретная математика и математические вопросы кибернетики / Под ред. С.В. Яблонского, О.Б. Лупанова. – М.: Наука, 1974. – 138 с.

3. Каган, Б.М. Электронные вычислительные машины и системы. - М.: Энергоатомиздат, 1985. – 232 с.

4. Кретова, Л.Д. Элементы математической логики: методические указания к практическим и индивидуальным занятиям / Л.Д. Кретова, Н.Б. Ускова, В.В. Посметьев. - Воронеж: ВГТУ, 2005. - 21 с.