Нахождение множества простых импликант

Преобразование исходного покрытия С₀ комплекса К в множество простых импликант Z осуществляется с помощью операции умножения кубов.В результате первого шага (С₀*С₀) (табл. 16) предусматривается выявление как новых кубов С_y (первой и более высокой размерности), так и кубов, которые не образуют новых кубов (включаются в множество Z₀). Из полученных новых кубов образуется множество А₁. Также формируется множество В₁=С₀-Z₀. Для следующего шага получения множества Z формируется множество С₁=А₁U В₁. Для уменьшения мощности множества кубов С₁ выполним операцию поглощения (удаления) кубов, образующих множество С₁, кубами из множества А₁ (А₁ÍС₁).

Таблица 16

Для рассматриваемого примера получим:

00х0

1х10

00х0 000х А₁ 00х0

1х10 х110 1х10

А₁ = х110 хх01 после выполнения 000х

000х С₁= х010 Þ операцииÞС₁= х110

хх01 0х10 поглощения хх01

0000 В₁ х010

Z₀=Ø 0х01 0х10

1х01

Среди кубов С₀, возможно, находятся такие кубы, которые с кубами множества А₁ могут дать новые кубы или оказаться простыми импликантами после второго шага (С₁*С₁). При формировании таблицы для выполнения операции С₁*С₁ (табл. 17) следует учесть, что В₁*В₁ уже выполнялось на шаге С₀*С₀. Следовательно,

С₁*С₁=(А₁UВ₁)*(А₁UВ₁)=(А₁*А₁)U(А₁*В₁)U(В₁*А₁)U(В₁*В₁)=(А₁*А₁)U(А₁*В₁).

Таблица 17

В результате выполнения умножения С₁*С₁ получим:

А₂={хх10},

Z1=

00х0 _.

000х

Необходимо отметить, что куб хх01 не дал нового куба. Но это куб второй размерности и новые кубы может дать на третьем шаге (С₂*С₂). Поэтому его не следует включать в число кубов, образующих множество Z₁.

1х10 хх10

х110 1х10

=

C2=А2UB2=

В₂ = хх01 , х110 хх10 _.

х010 х010 хх01

0х10 0х10

хх01

Таблица 18

Таким образом, получим А₃= Ø, следовательно, новых кубов нет.

Z2=

хх10 _.

хх01

В₃=С₂-Z₂= Ø; C₃=A₃UB₃= Ø.

На этом процесс выявления простых импликант окончен.

,

00х0

- сформированное множество простых импликант.

Z=Z0UZ1UZ2=

000х

хх01

хх10

Необходимо выяснить, не содержатся ли в этом множестве “лишние” простые импликанты.