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


Преобразование исходного покрытия С0 комплекса К в множество простых импликант Z осуществляется с помощью операции умножения кубов.В результате первого шага (С00) (табл. 16) предусматривается выявление как новых кубов Сy (первой и более высокой размерности), так и кубов, которые не образуют новых кубов (включаются в множество Z0). Из полученных новых кубов образуется множество А1. Также формируется множество В10-Z0. Для следующего шага получения множества Z формируется множество С11U В1. Для уменьшения мощности множества кубов С1 выполним операцию поглощения (удаления) кубов, образующих множество С1, кубами из множества А1 1ÍС1).

Таблица 16

  С00 х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

Z00х01 0х10

1х01

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

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

Таблица 17

  С11 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 Ø

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

А2={хх10},

Z1=
00х0 .

000х

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

1х10 хх10

х110 1х10

=
C22UB2=
В2 = хх01 , х110 хх10 .

х010 х010 хх01

0х10 0х10

хх01

 

Таблица 18

  С22 хх10
  хх10 -
  хх01 Ø
  А3 Ø

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

Z2=
хх10 .

хх01

В32-Z2= Ø; C3=A3UB3= Ø.

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

,

00х0

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

хх01

хх10

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



Дата добавления: 2022-02-05; просмотров: 249;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.009 сек.