Нахождение множества простых импликант
Преобразование исходного покрытия С0 комплекса К в множество простых импликант Z осуществляется с помощью операции умножения кубов.В результате первого шага (С0*С0) (табл. 16) предусматривается выявление как новых кубов Сy (первой и более высокой размерности), так и кубов, которые не образуют новых кубов (включаются в множество Z0). Из полученных новых кубов образуется множество А1. Также формируется множество В1=С0-Z0. Для следующего шага получения множества Z формируется множество С1=А1U В1. Для уменьшения мощности множества кубов С1 выполним операцию поглощения (удаления) кубов, образующих множество С1, кубами из множества А1 (А1ÍС1).
Таблица 16
С0*С0 | х010 | 0х10 | 0х01 | 1x10 | |||
х010 | - | ||||||
0х10 | - | ||||||
00у0 | 00у0 | - | |||||
0х01 | ø | ø | 000у | - | |||
1у10 | у110 | ø | ø | - | |||
1х01 | ø | ø | ø | ух01 | ø | - | |
А1 | 00х0 | х110 | 000х | хх01 | |||
1х10 |
Для рассматриваемого примера получим:
00х0
1х10
00х0 000х А1 00х0
1х10 х110 1х10
А1 = х110 хх01 после выполнения 000х
000х С1= х010 Þ операцииÞС1= х110
хх01 0х10 поглощения хх01
0000 В1 х010
Z0=Ø 0х01 0х10
1х01
Среди кубов С0, возможно, находятся такие кубы, которые с кубами множества А1 могут дать новые кубы или оказаться простыми импликантами после второго шага (С1*С1). При формировании таблицы для выполнения операции С1*С1 (табл. 17) следует учесть, что В1*В1 уже выполнялось на шаге С0*С0. Следовательно,
С1*С1=(А1UВ1)*(А1UВ1)=(А1*А1)U(А1*В1)U(В1*А1)U(В1*В1)=(А1*А1)U(А1*В1).
Таблица 17
С1*С1 | 00х0 | 1х10 | 000х | х110 | хх01 | |
00х0 | - | |||||
1х10 | у010 | - | ||||
000х | ø | - | ||||
х110 | 0у10 | ø | - | |||
хх01 | 000у | ø | ø | - | ||
х010 | 00у0 | ху10 | Ø | |||
0х10 | ух10 | 00у0 | Ø | |||
А2 | ø | хх10 | ø | хх10 | Ø |
В результате выполнения умножения С1*С1 получим:
А2={хх10},
|
000х
Необходимо отметить, что куб хх01 не дал нового куба. Но это куб второй размерности и новые кубы может дать на третьем шаге (С2*С2). Поэтому его не следует включать в число кубов, образующих множество Z1.
1х10 хх10
х110 1х10
|
|
х010 х010 хх01
0х10 0х10
хх01
Таблица 18
С2*С2 | хх10 | |
хх10 | - | |
хх01 | Ø | |
А3 | Ø |
Таким образом, получим А3= Ø, следовательно, новых кубов нет.
|
хх01
В3=С2-Z2= Ø; C3=A3UB3= Ø.
На этом процесс выявления простых импликант окончен.
,
00х0
|
|
хх01
хх10
Необходимо выяснить, не содержатся ли в этом множестве “лишние” простые импликанты.
Дата добавления: 2022-02-05; просмотров: 262;