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

Р₁Ì Р₂ Ì… Ì Р_n Ì Р_n+1 Ì…

Булев многочлен  можно упростить с помощью аксиом булевой алгебры. В процессе упрощения часто трудно решить, какие аксиомы и в каком порядке должны быть использованы. Но существуют некоторые систематические методы упрощения булевых многочленов. Недостатком большинства этих методов является возможность их практического внедрения, когда число переменных слишком велико. Соответствующая проблематика в теории булевых алгебр носит общее название проблема оптимизации или минимизации булевых многочленов; она важна для таких приложений, как упрощение переключательных схем.

Аналитические методы минимизации

Используя законы булевой  алгебры, можно получить для одной  и той же логической функции множество  эквивалентных представлений. Чем  проще аналитическое выражение  функции, тем экономичнее и проще ее практическая реализация на интегральных микросхемах. Сложность булевой функции определяется ее рангом, т.е. количеством переменных в ее конъюнктивных или дизъюнктивных членах.

Представление булевой функции  в Сов ДНФ в большинстве  случаев не является минимальным.

Используя операции поглощения и склеивания, его можно существенно  упростить. Часто используется неполное склеивание, при котором оба члена, участвовавших в склеивании (или  один из них), могут повторно склеиваться  с другими оставшимися членами Сов ДНФ.

В процессе минимизации важно  отыскать смежные конституенты, которые  отличаются только одним аргументом (в одну конституенту аргумент входит с инверсией, а в другую – без  нее).

Две смежные конституенты, склеиваясь, образуют импликанту рангом на единицу ниже, чем исходные конституенты.

Используя, например, неполное склеивание последней коституенты  в Сов ДНФ функции F₁ последовательно с остальными, приходим к следующему выражению:

Процесс многоступенчатого  склеивания приводит к импликантам, которые не склеиваются с другими. Такие импликанты называют простыми. Форма записи булевой функции  в ДНФ, состоящая только из простых  импликант, называется сокращенной  дизъюнктивной нормальной формой (Сокр ДНФ).

В некоторых случаях в  Сокр ДНФ могут содержаться лишние импликанты, которые могут быть исключены  без изменения значения функции.

Одним из методов отыскания  лишних импликант является метод  испытания членов: чтобы испытать некоторый член функции, следует исключить его из Сокр ДНФ и подставить в оставшееся выражение такие значения аргументов, которые обращают исключенный член в единицу. Если при такой подстановке оставшееся выражение окажется тождественно равным единице, то испытуемый член является лишним.

Найдем для примера  тупиковую форму Сокр ДНФ

.

Испытаем член AC. AC = 1, если A = 1 и C = 1. Подставим в оставшееся выражение  A = 1 и C = 1, получим

.

При B = 0 F(A, B, C) = 1·1 Ъ 0·0 = 1, но при  F(A, B, C) = 0·1 Ъ 0·0 = 0. Следовательно, член AC не лишний.

Испытаем член BC, равный 1 при B = 0, C = 1. При этом

.

Последнее выражение  равно 1 как при A = 1, так и при A = 0. Поэтому член  – лишний.

Испытание члена  по этой же методике показывает, что он не является лишним, в итоге тупиковая форма исходной функции имеет вид:

.

Определение. Назовем литералом любую переменную х_i и ее дополнение х_i¢, а также 0 и 1. Под произведением понимается произведение нескольких литералов, т.е. булев многочлен, в котором нет знака +. Дизъюнктивным выражением или просто выражением назовем буле многочлен, являющийся суммой произведений. Слагаемые в таком выражении назовем дизъюнктами [1, c.128].

Обсуждая упрощение  булевых многочленов, мы ограничимся  важным случаем сведения дизъюнктивных  выражений к «минимальным выражениям»  относительно специального условия минимальности. Обозначим через d_f общее число литералов в выражении f, а через e_f – число дизъюнктов. Мы говорим, что выражение f проще выражения j, если  d_f £ d_g, e_f £ e_g и хотя бы одно из этих неравенств строгое. Выражение f называется минимальным, если не существует выражения, которое было бы эквивалентно f  и проще f. Таким образом, мы будем искать «кратчайшее» выражение с наименьшим возможным числом литералов, которое было бы эквивалентно f. Такое минимальное выражение не всегда определено однозначно. Мы опишем несколько существующих методов упрощения. Они основаны на работе Куайна и были улучшены Мак-Класки, поэтому называется методом Куайна - Мак-Класки [2, c.36] и метод минимизации булевых функций с помощью карт Карно [7, c.96].

Минимизация булевых  функций с помощью карт Карно

Иногда удобно пользоваться несколько другим представлением диаграмм с цифровым кодом. Это карты  Карно. Примеры карт Карно приведены  на рисунке 2. По граням карты проставляются  двоичные коды - коды Грея, что дает возможность легко проставлять значения функции и находить результат. Правила минимизации с применение карт Карно такие же, как и для диаграмм Вейча.

х2х3 х1	00	01	11	10		х3х4 х1х2	00	01	11	10
0	000	001	011	010		00	0000	0001	0011	0010
1	100	101	111	110		01	0100	0101	0111	0110
						11	1100	1101	1111	1110
						10	1000	1001	1011	1010
	а)								б)

 

Рисунок 2- Карты Карно:

а) функции 3-х переменных;

б) функции 4-х переменных.

Для минимизации  функций относительно небольшого числа  переменной (не более шести) наиболее простым и наглядным является графический метод, использующий карты  Карно.

Карта Карно  – это прямоугольник, разбитый на квадраты, число которых равно числу наборов рассматриваемой функции, т. е. 2ⁿ. Клетки размечаются так, чтобы наборы, для которых возможны смежные конституенты, оказались бы в соседних клетках.

При заполнении карты Карно в ее клетки проставляют значения функции для соответствующих наборов, которые являются координатами клеток. Например, для функции двух переменных А и В (рис. 5) карта Карно имеет вид

Единицы, представленные в клетках, обозначают конституенты единицы рассматриваемой функции. Отыскание минимальной ее формы  сводится к определению варианта, при котором все конституенты единицы накрываются (охватываются контурами покрытия) наименьшим числом наиболее коротких импликант. Объединение клеток на карте эквивалентно выполнению операции склеивания.

Всегда нужно  стремиться к минимальному количеству контуров и максимальной площади  каждого из них, руководствуясь следующими правилами:

площадь контура покрытия должна быть S_k = 2^m-i клеток, где  – целое число, m.

      Особенности минимизации булевых функций большим числом  переменных

Рассмотрим  некоторые особенности работы с картами Карно для большого числа переменных. При числе переменных, равном или больше пяти, отобразить графически функцию в виде единой плоской карты невозможно. В таких случаях строят комбинированную карту, состоящую из совокупности более простых базовых карт, например карт для функции 4-х переменных. Процедура минимизации в этом случае состоит в том, что сначала находят минимальные формы внутри базовых карт, а затем, расширяя понятия соседних клеток, находят минимальные накрытия для совокупности карт. Соседними клетками являются клетки, совпадающие при наложении базовых карт друг на друга. Примеры карт Карно для булевых функций 5-ти и 6-ти переменных представлены на рис. 3 и 4. соответственно.

Рисунок 3-Карта Карно для булевой функции 5-ти переменных

х3х4 х1х2	00	01	11	10	00	01	11	10
00
01
11
10
		х5=0				х5=1

 

Рисунок 4- Карта Карно для булевой функции  шести переменных

х3х4 х1х2	00	01	11	10	00	01	11	10	00	01	11	10	00	01	11	10
00
01
11
10				(1)				(2)				(3)				(4)
х5х6		00				01				11				10

 

По  рисунку 4 можно сделать вывод, что  соседними являются для 1-й базовой карты -2-я и 4-я; для 2-й - 1-я и 3-я; для 3-й 2-я и 4-я; для 4-й - 1-я и 3-я.

При увеличении количества переменных на одну, площадь карты увеличивается  в два раза - к ней пририсовывается  еще такая же карта. При этом новая  переменная равняется 1 на новой карте, и 0 на той, которая была ранее.

Метод Куайна – Мак-Класки.

Определение. многочлен p влечет многочлен q, если для любых b₁,…., b_n Î В

р_в (b₁, …, b_n) = 1 влечет q_в (b₁, …, b_n) = 1;

в этом случае р называется импликантом для q. Простым импликантом многочлена р называется произведение , которое влечет р, но если в вычеркнуть хотя бы один сомножитель, то результат уже не влечет р. Произведение, сомножители-литералы которого образуют подмножество сомножителей-литералов другого произведения, называется подпроизведением последнего.

Пример. Произведение х₁х₃ является подпроизведением как х₁х₂х_3, так и х₁х₂¢х₃, и влечет выражение

р = х₁х₂х₃ + х₁х₂¢х₃ + х₁¢х₂¢х₃¢,

поскольку (х₁х₃)(1, i₂, 1) = 1 и р(1, i₂, 1) = 1, а для других значений аргументов х₁х₃ дает 0. Ни х_1, ни х₃ не влекут р; например, х₁(1, 1, 0) = 1, но р(1, 1, 0) = 0, поэтому х₁х₃ – простой импликант для р.

Теорема. Любой многочлен р Î P_n эквивалентен сумме всех своих простых импликантов.

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

Простые импликанты получаются из дизъюнктивной нормальной формы d булева многочлена р применением (слева направо) правила

yz + yz¢ ~ y,

когда это возможно. Более  общо, мы используем правило

        _(*)

где и - произведения. следующий пример поможет понять смысл описываемой процедуры.

Пример. Пусть р – булев многочлен, имеющий следующую дизъюнктивную нормальную форму:

d = wxyz’ + wxy’z’ + wx’yz + wx’yz’ + w’x’yz + w’x’yz’ + w’x’y’z

Мы используем правило и законы идемпотентности для тех (из общего числа ( ) = 21) пар дизъюнктов в d, для которых это возможно, тем самым «укорачивая» произведения. например, превый и второй дизъюнкты при использовании (*) дают wxz’. Если в процессе упрощения слагаемые используются хотя бы один раз, то оно помечается. Так как знак + стоит вместо Ú, выражение может быть использовано любое число раз, но помечается не более одного раза. Таким образом, все помеченные произведения содержат более короткие произведения и поэтому не могут быть простыми импликантами. В целом в первом раунде этого процесса мы переходим