Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


ћинимизаци€ функционального представлени€




ћЌќ∆≈—“¬.

ќпределим функцию от фрагментов, €вл€ющихс€ множествами. ‘ункцией будем называть взаимооднозначное отображение элементов группы множеств јi в элементы множества —. ≈сли каждому элементу — соответствует некоторый элемент јi, такую функцию называют всюду значимой

— = f (Ai)

f Ц функци€ переводит элементы Ai во множество —.

≈сли пересечение множеств обозначать как функциональную операцию –, то

– (ј,¬) = ј¬

Ќа единичном множестве 1 заданы множества ј,¬,—. ¬ этом случае с помощью известной операции над множествами переводим исходное множество в какое-либо другое.

f (ј,¬,—) = ј¬— È ј — È ¬ È È ј¬ È A— È — È ¬;

«аписанное выражение назовем формулой. ќпределим сложность формулы, как количество, содержащихс€ в ней исходных множеств. ƒл€ приведенного примера сложность =20. ѕри аналазе формул первым вопросом €вл€етс€: Ђћожно ли уменьшить сложность формулы?ї —делаем это на примере примен€€ законы дистрибутивности и поглощени€

f(ј,¬,—) = ј¬— È ј È ¬ È È ј(¬ È —) È (¬ È —) =

= ј¬— È ј È B È È ¬ È — = ¬È ј È È — =

= È ¬ È — = È =1

f(ј,¬,—) = ј— È — È ¬— È ј¬— È ј¬ È ¬ = ј— È — È ¬ È ј¬ =

=¬ È ј— È —;

»ли:

F(ј,¬,—) = ј— È — È ¬— È ј¬— È ј¬ È ¬ = ј— È — È ¬— È ј¬ È È ¬ = ј— È — È ¬— È ¬ = — È ¬

 ак видно из примеров минимизаци€ одних и тех же функций может дать разные результаты при применении одних и тех же законов.

 

—“јЌƒј–“Ќџ≈ ‘ќ–ћџ ѕ–≈ƒ—“ј¬Ћ≈Ќ»… ‘ќ–ћ”Ћ

ћЌќ∆≈—“¬.

Ќа 1 определении ћ123 совокупность ћi назовем порожд-ми множествами пространства и определим ћi по универсальной формуле:

ћi ; di =1;

Midi = di={0;1}

i ; di =0;

ћi = i = {0,1}

Mi; i=0;

 

Mi, di Ц первичный термом

Ki = idi - конституентой

n - число порожденных множеств.

ѕеречислим все конституенты нашего примера:

 0 = 1 2 3  1 = 1 2ћ3  2 = 1ћ2 3  3 = 1ћ2ћ3

 4 = ћ1 2 3  5 = ћ1 2ћ3  6 = ћ1ћ2 3  3 = ћ1ћ2ћ3

 

ќчевидно, что каждой приведенной коституенте может быть сопоставлено двоичное трехразр€дное число, причем каждый разр€д будет равен di первичного терма:

 0 = 000;  1 = 001;  2 = 010;  4 =011;  5 = 100;  6 = 110;  7 = 111.

≈сли учесть,что каждой конституенте длины ѕ можно сопоставить n разр.

двоичное число, то общее количество конституент равно:

N = 2n

1) ¬ыражени€, заданные с помощью формул,могут быть упрощены.

2) Ќеобходимые шаги дл€ упрощени€ не всегда очевидны и сложность упрощени€ находитс€ в пр€мой зависимости от числа аргументов в формуле.

3) ƒл€ упрощени€ выражени€ произв. вида и произв. количества аргументов необходимо использовать математический аппарат минимизации функций подмножеств.

ѕересечение двух различных конституент - пустое множество.

ѕересечение двух конституент Ц есть пересечение всех первичных термов их составл€ющих, если конституенты не равны, то найдетс€ хот€ бы 1 разр€д с несовпадающими первичными термами.

ќбозначим этот разр€д через i.

Midi *Midi*= Æ

ќбъединение всех коституент,порожденных множествами Mi на универсальном множестве равно самому универсальному множеству:

I= (Mi È i)

n=1 M1, 1 M1+ 1=I

 

n=k j = I

— помощью конституент, образованных множествами Mi,можно представить исходное универсальное множество.

1. ѕроиллюстрируем на графическом примере:

(универсальное множество I, внутри ћ1-квадрат, ћ2-треугольник, ћ3-круг).

 
 

 


¬ дополнение к рассматриваемым свойствам,рассмотрим сколько множеств на I можно образовать из конституент.

ƒл€ этого произвольному множеству сопоставим m-разр€дное двоичное число,где m-длина конституент. ѕри этом 0-отсутствие конституенты, 1-присутствует.

“ак например, двоичному числу

01101001 соответствует множество, из объединенных 0,3,5,и 6 конституент.

¬место двоичных чисел можно использовать их дес€тичный эквивалент:

d = 1+23+25+26 = 1+8+32+64 = 40+ 65 = 105

≈сли любому, образованному из конституент, множеству соответствует m-разр€дное двоичное число, то таких множеств может быть 2m,а так как число конституент = 2n, где n-число образованных множеств,то общее число, которое образуетс€ из конституент = 22^n

ƒл€ иллюстрации это количество -256.

–ассмотрев пон€тие конституент зададимс€ вопросом:ї ак конституенты св€заны с функци€ми от образующих множеств?ї

ћј“≈ћј“»„≈— »≈ ”“¬≈–∆ƒ≈Ќ»я.

ћножество Mi равно объединению всех конституент,содержащих Mi

–ассмотрим равенство:

I = j-1

¬озьмем пересечение левых и правых частей с Mi

Mi = j-1Mi

–ассмотрим выражение  j,Mi. ƒл€ него возможны два случа€:

1.Kj не содержит в себе Mi, Ki*Mi = Æ

2.Kj Ì Mi, Kj*Mi =Kj

—ледовательно, Mi можно представить в виде:

 

ћi = l

 

kl -конституенты,содержащие Mi.

“≈ќ–≈ћј.

Ћюба€ функци€ от порождающих множеств представима в виде объединени€ конституент.

»з аксиоматичного построени€ следует,что все операции представимы через операции объединени€ и отрицани€.

—ледовательно, достаточно доказать,что объединение порождающих множеств представимо через объединение конституент, а так же,что отрицание объединени€ конституент,так же представимо через объединение множеств.

ƒл€ доказательства рассмотрим объединение произвольно образованных множеств Mi и ћк.

—огласно утверждению (Mi È ћк),записывающихс€ в виде:

 

 

ћi È ћк = j+ l ћi È ћк = j

при этом ћ Ц различно,так как различно число совпадающих конституент в представлени€х множеств Mi ићк.

ќстаетс€ доказать,что дополнени€ к объединению конституент в свою очередь есть объединение конституент.

“ак как универсальльное множество €вл€етс€ объединением всех конституент, €сно,что если вз€ть объединение некоторых из них, то оставшиес€ конституенты будут дополнительными к исходному объединению.

–ассмотрим пример:

‘ункци€ от множеств ј,¬,—

f(A,¬,—) = ј(¬ È ((— ј)\¬)) = ј(¬ È ((— È — )\¬)) = ј(¬ È (— È ј) ) =

ј(¬ È — È ј ) = ј¬ È ј = ј È ј¬— È ј¬

»з пересечени€ ј¬ получена ј¬— È —. ясно,чтобы получит трех-разр€дную конституенту, необходимо до термов ј¬ добавить —, а так как произв-но множество ћ:

ћ(— È ) = ћ— È ћ ј¬ = ј¬— È ј¬

то просто получим из ј¬ трехразр€дную конституенту.

»так, люба€ функци€ от порождающих множеств, может быть представлена в виде объединени€ коституент и оно называетс€ совершенной норм. антора (—Ќ‘ ).

≈сли в представлении функции участвовали конституенты меньшей длины, то оно называетс€ норм. формой  антора (Ќ‘ ).

ƒл€ получени€ –‘  нужно минимизании —Ќ‘  любым (аналитическим, графическим,графо-аналитическим способом).

Ќазовем интервалами универсального пространства ранга n все коституенты длина l =1, n

≈сли кака€-либо —1 (интерв.) = —2È —3, то говор€т что —1 включает в себ€ —2 и —3 или —1 покрывает —2 и —3

»з этого следует, что функци€,представленна€ в —Ќ‘  равна:

f (A,¬,—) = j= l

где Cl - интервалы,покрывающие все конституенты  j .

≈сли рассмотреть предыдущий пример,то можно заметить,что f(ј,¬,—):

f (A,¬,—) = ј¬ È ј

где, ј¬ покрывает ј¬— и ј¬ , а втор. совпадает с ј .

 

√–ј‘»„≈— јя ћ»Ќ»ћ»«ј÷»я ‘”Ќ ÷»» ќ“

“–≈’ ѕ≈–≈ћ≈ЌЌџ’.

 

¬ведем геометрическое представление интервалов при n=3.

ƒл€ этого каждой из 8 конституент, сопоставив вершину трехмерного куба и двоичный эквивалент. ѕри этом расположим вершины так,чтобы их двоичные представлени€ отличались лишь в одном разр€де.

 
 

 

 


—опоставим коституенты с их двоичным эквивалентом:

000 Ц ; 001 Ц C; 010 Ц ¬ ; 011 Ц ¬—; 100 Ц ј ;

101 Ц ј —; 110 Ц ј¬ ; 111 Ц ј¬—.

–ассмотрим более сложные интервалы:

È ¬ =

ќ Ц ќ, где Ч - отсутствие разр€да

√еометрически - сопоставл€етс€ ребро соединени€ вершины 000 и 010.

«апишем соответствие ребер интервала:

-00 = ; -01 = —; -10 = ¬ ;

0-0 = ; 0-1 = —; 1-0 = ј ;

00- = ; 01- = ¬; 10- = ј ;

-11 = ¬—; 1-1 = ј—; 11- = ј¬.

ѕо аналогии ребра конституенты можно объеденить в грань.

ј¬ È ¬ È ¬ È ¬— = ¬

—оответстви€ граней:

--0 = ; --1 = —

-0- = ; -1- = ¬;

0-- = ; 1-- = ј.

ƒл€ представлени€ функции на кубе,участвующие интервалы выдел€ютс€.

111 110

 

 

101 100

 

001 000

f(A,¬,—) = — È ¬

111 B 110

¬ этом примере видно,что конституенты ¬ и

¬— покрытые ¬

101 100 и ¬ и ј¬ покрытые ¬ можно покрыть одним

001 000 интервалом ¬.

f(A,¬,—) = — È ¬

и так как сложность уменьшилась с трех до двух, была произведена минимизаци€ функции.

 

ћ»Ќ»ћ»«ј÷»я ‘”Ќ ÷»» “–≈’ ѕ≈–≈ћ≈ЌЌџ’

√–ј‘»„≈— »ћ —ѕќ—ќЅќћ.

f(M123) = 1 2ћ3 + 1ћ2ћ3 + ћ1ћ2ћ3 + ћ1 2 3

111 110

 

 

101 100

 

001 000

f(M123) = 1ћ3 + ћ2ћ3 + ћ1 2 3

 

ћ»Ќ»ћ»«ј÷»я ‘”Ќ ÷»» — ѕќћќў№ё  ј–“

 ј–Ќќ.

 

√рафический способ минимизации удобен дл€ трех,четырех переменных, а дл€ функции п€ти переменных и выше применение графического метода невозможно.

ѕоэтому дл€ использовани€ принципа этого метода дл€ большеге количества переменных предложена модернизаци€.

»де€: развернуть куб на плоскости

000 001 011 010 000

       

100 101 111 100 100

»сход€ из развертки куба, строитс€ таблица:

ћ1 ћ2ћ3 00 01 ћ3 11 10

       
1      

ћ1

ћ2

 

 

ѕостроенна€ таблица Ц карта  ј–Ќќ.

¬ ней отмечены конституенты,присутствующие в функции, подобно тому, как отмеченные вершины куба объеденены в ребра и грани.

ќбъед. и еден. карты (интервалы).

ќбъединение единиц в интнрвалы в карте иначе называют склеиванием.

Ётапы заполнени€ карты  ј–Ќќ.

1. ¬се конституенты, присутствующие в функции занос€тс€ в карту с помощью единиц в соответствующие клетки.

2. ¬ыдел€ют интервалы на карте по следующим принципам:

а) в один интервал объедин€ют только соседние единицы по вертикали или горизонтали;

б) в один интервал можно объеденить 2к единиц, где k=0,1,2,3,4,Е.

в) карта циклически замкнута по вертикали и горизонтали.

г) в выделенный интервал объединено максимально возможное количество единиц.

¬сего на карте выделено 3 интервала, в каждый вход€т те минитермы в которых он полностью находитс€.

«апишем минимальную функцию:

f(M123) = ћ1ћ3 + ћ2ћ3 + ћ1 2 3

ѕример:

ћинимизировать функцию:

f(M123)= 1 2 3 + ћ1 2 3 + 1 2 ћ3 + ћ1 2 ћ3 + ћ1ћ2ћ3 +

+ 1ћ2 3 + ћ1ћ2 3

 

00 01 ћ3 11 10

       
1      

ћ1

ћ2

f(M123) = 2 + ћ1 + 3

ѕри правильном объединении функцию больше минимизировать невозможно.

 арта  арно дл€ 4-х переменных:

ћ1ћ2 ћ3ћ4 00 01 11 10

00          
          ћ2
11          
          ћ1

ћ 3

ћ4

f(M123) = ћ1ћ4 + ћ2ћ4 + 1 2 4

 

ѕример:

f(M1234) (3,4,5,7,9,11,12,13 конституенты)

ћ1ћ2 ћ3ћ4 00 01 11 10

           
           
           
           

 

3 - 0011 4 - 0100 5 - 0101 7 - 0111 9 - 1001

11- 1011 12 - 1100 13 - 1101

f(M1234)= ћ2 3+ 1ћ3ћ4 1 2ћ4

 

 

 арты  арно дл€ 5-ти переменных:

ћ4 ћ5

ћ1ћ2 ћ3ћ4ћ5 001 ћ3 011 010 110 111 101 100

                 
01                
ћ2 11                
ћ1 10                

 

ѕри выделении интервалов необходимо соблюдать дополнительные правила:

1) ¬се интервалы должны быть симметричны относительно исходных размеров карт;

2) ≈сли 2 единицы наход€тс€ симметрично границы раздела они считаютс€ соседними.

f(ћ12345) = ћ2 3 ћ5 + ћ1 3 ћ4 ћ5 + ћ1 2 ћ3ћ4 5

f(ћ12345) = 1 ћ2 3 4ћ5 + 1 ћ2 3 ћ4 ћ5 +

+ ћ1ћ2 3 4 ћ5 + ћ1 ћ2 3 ћ4 ћ5 + ћ1 2 3 4 ћ5 +

+ ћ1 2 3 ћ4 ћ5 + 1 ћ2 3 ћ4 5 + ћ1 ћ2 3 ћ4 5 +

+ 1ћ2ћ3 ћ4 5 + ћ1 ћ2ћ3 ћ4 5 + ћ1 2ћ3 ћ4 ћ5 +

+ ћ1 2ћ3 4 ћ5

ћ1ћ2 ћ3ћ4ћ5 001 011 010 110 111 101 100

                 
                 
                 
                 

 

f(ћ12345) = ћ2 3 ћ5 + ћ2 ћ4 5 + ћ1 2 ћ5

 

јппарат работы с картами и их преимущество.

 

1) ѕростота применени€.

2) Ќагл€дность расположени€ интервалов.

 

Ќедостатки:

1) —ложность работы возростает намного быстрее, чем увеличиваетс€ число элементов функции.

2) “рудоемкость алгоритмизации.

»сход€ из недостатков следует, что дл€ работы с функци€ми большего числа переменных нужны иные методы, причем они должны быть не графическими а аналитическими.

ƒл€ компьюторной технологии существует отличный от рассмотренного метода минимизации множеств,который называетс€ метод  вайна.

ћ»Ќ»ћ»«ј÷»я ‘”Ќ ÷»» ћ≈“ќƒќћ  ¬ј…Ќј.

ћаксимальный интервал Ia, который не содержитс€ ни в каком другом интервале Ia Ë Iк

где Iк - все интервалы функции, кроме Ia.

–ассмотрим функцию, заданную в —Ќ‘ :


N Ki F
     
     
     
     
     
     
     
     

 

¬ левой части двоичный эквивалент конституент,а в правой присутствует ли она в функциональном представлении или нет.

 роме интервалов,представленные конституентами выделим другие интервалы более крупные.

 


 

001 0х1

011 х11

100 1х0 - максимальные интервалы относительно конституент.

110 11х

 

Ћемма.

≈сли в представление функции включен не максимальный интервал, то этот интервал может быть преобразован с помощью вычеркивани€ первичных термов.

ƒоказательство:

»сход€ из определени€, в функциональном представлении присутствует интервал, содержащий не максимум,а состо€щий из некоторых первичных термов не максимальный интервал. —ледовательно, максимальный интервал мажет быть получен вычеркиванием незначительных термов из немаксимального интервала.

ћ = ј + ¬ = ј + ¬

¬ Ц максимальный интервал

¬ Ì ¬ - не максимальный интервал

¬ычеркиванием терма Ц получим максимальный интервал.

“упиковой формой Цназываетс€ нормальна€ форма  антора, из которой не может быть вычеркнут ни один терм без изменени€ представлени€ функции.

ћинимальной формой Ц называетс€ тупикова€форма, минимальной сложности

¬ыражени€ дл€ максимальных интервалов называютс€ простыми импликантами.

“≈ќ–≈ћј.

¬се тупиковые,а следовательно и минимальные формы содержатс€ в объединении всех простых импликант.

ƒоказательство:

»з определени€ следует,что если вЌ‘  присутствует неминимальный интервал,то она не €вл€етс€ тупиковой и не €вл€етс€ минимальной.

—ледовательно, тупиковой и минимальной формой есть объединение некоторых простых импликант из множества всех простых импликант.

—огласно вышеуказанной теореме 1-й шаг метода  вайна состоит в выделении простых импликант функции и составлении таблицы.

—троки соответствуют простым импликантам.

—толбцы Ц конституентам функции.

 

           
0х1          
х11          
1х0          
11х          

≈сли конституента содержитс€ соответственном максимальном интервале, то в клетке ставитс€ 1, если нет, то клетка остаЄтс€ пустой.

2-й шаг

—остоит в том, что из множества простых импликант составл€ютс€ всевозможные подмножества, обладающие свойствами:

1. Ёлементы подмножества суммарно покрывают все конституенты функции.

2. ѕри вычеркивании любого элемента подмножества свойство 1 не выполн€етс€.

ѕодмножество, удовлетвор€ющее свойствам называетс€ минимальными покрыти€ми таблицы  вайна.

 

“≈ќ–≈ћј

¬озможные минимальные покрыти€ таблицы  вайна представл€ют все тупиковые формы функционального представлени€, среди которых содержатс€ и минимальные формы.

ƒоказательство:

Ќеобходимость следует из того, что тупиковые и минимальные формы есть объединение простых импликант. ƒостаточность следует из того, что не возможно вычеркнуть простую импликанту, а следовательно любой первичный термин, без нарушени€ покрыти€ всех конституент функции.

 





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2016-12-05; ћы поможем в написании ваших работ!; просмотров: 523 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

Ќе будет большим злом, если студент впадет в заблуждение; если же ошибаютс€ великие умы, мир дорого оплачивает их ошибки. © Ќикола “есла
==> читать все изречени€...

753 - | 590 -


© 2015-2023 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.172 с.