КАТЕГОРИИ:
Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)
Нахождение множества простых импликант
|
|
|
|
Преобразование исходного покрытия С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},
|
00х0 .
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= Ø, следовательно, новых кубов нет.
|
хх10 .
хх01
В3=С2-Z2= Ø; C3=A3UB3= Ø.
На этом процесс выявления простых импликант окончен.
,
00х0
|
|
хх01
хх10
Необходимо выяснить, не содержатся ли в этом множестве “лишние” простые импликанты.
|
|
|
|
|
Дата добавления: 2014-12-26; Просмотров: 514; Нарушение авторских прав?; Мы поможем в написании вашей работы!