Ћекции.ќрг


ѕоиск:




 атегории:

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

 

 

 

 


јнал≥тичне поданн€ булевих функц≥й




¬ище згадувалось, що ≥снуЇ анал≥тичний спос≥б (форма) заданн€ булевих функц≥й, були розгл€нут≥ прост≥ приклади. “ут розгл€немо ун≥версальн≥ (канон≥чн≥) форми представленн€, €к≥ дають можлив≥сть одержати анал≥тичну форму безпосередньо виход€чи з таблиц≥ ≥стинност≥ дл€ дов≥льноњ булевоњ функц≥њ. ÷€ форма у подальшому може бути спрощена. ќск≥льки м≥ж множиною анал≥тичних представлень ≥ множиною цифрових схем, €к≥ реал≥зують булеву функц≥ю, ≥снуЇ взаЇмно однозначна в≥дпов≥дн≥сть, то в≥дшуканн€ канон≥чних форм представленн€ булевоњ функц≥њ €вл€Їтьс€ початковим етапом синтезу цифровоњ схеми, €ка њњ реал≥зуЇ. Ќайб≥льш широкого застосуванн€ набула досконала дизТюнктивна нормальна форм (ƒƒЌ‘).

–озгл€немо, €к можна зд≥йснити перех≥д в≥д табличного заданн€ буле≠воњ функц≥њ до анал≥тичного њњ представленн€.

«вертаЇмо увагу, що надал≥, з метою спрощенн€ запис≥в, зам≥сть символу дизТюнкц≥њ У Ф будемо вживати символ У+Ф ≥ трактувати його €к лог≥чне додаванн€, символ конТюнкц≥њ Ф Ф будемо опускати або зам≥нювати символом Ф∙Ф ≥ трактувати це €к лог≥чне множенн€ задане за замовчуванн€м або €вне, а операц≥ю ≥нверс≥њ будемо позначати символом Ф¯Ф.

10. ƒизТюнктивна форма. ѕрипустимо, що маЇмо булеву функц≥ю в≥д n аргумент≥в (зм≥н≠них), тобто n -м≥сну булеву функц≥ю. “ак €к будь-€ка зм≥нна може приймати одне ≥з двох значень 0 або 1, то дв≥йков≥ набори значень зм≥нних (€к уже в≥дм≥чалось) можна розгл€дати €к записи де€ких ц≥лих чисел у дв≥йков≥й систем≥ численн€, тобто записи вигл€ду .  ожному такому запису можна поставити у в≥дпов≥дн≥сть дес€ткове число , €ке одержуЇтьс€ за формулою

.

÷е число, €к в≥домо, Ї номером в≥дпов≥дного набору. “ак, дл€ чотири≠м≥сноњ булевоњ функц≥њ номером набору 1101 Ї число

.

ЌагадаЇмо, що номери набор≥в n -м≥сноњ булевоњ функц≥њ зм≥нюютьс€ в≥д 0 до .

–озгл€немо де€кий ф≥ксований наб≥р зм≥нних , на €кому задана функц≥€ алгебри лог≥ки.

ќзначенн€ 1.  онТюнкц≥€ зм≥нних з набору X або њх заперечень вигл€ду , де означаЇ або , або (j =0,1,..., k), називаЇтьс€ елементарною конТюнкц≥Їю, €кщо в н≥й кожна зм≥нна зустр≥чаЇтьс€ не б≥льше одного разу.

ƒо елементарних конТюнкц≥й в≥днос€ть також вирази, що складаютьс€ з одн≥Їњ зм≥нноњ (в пр€м≥й або ≥нверсн≥й форм≥), розгл€даючи њх €к одном≥сн≥ елементарн≥ конТюнкц≥њ.  онстанту 1 зручно розгл€дати €к 0-м≥сну елементарну конТюнкц≥ю. Ќаприклад, елементарними конТюнкц≥€ми Ї: , а вирази , елементарними конТюн≠кц≥€ми не €вл€ютьс€.

ќзначенн€ 2. ƒизТюнкц≥€ елементарних конТюнкц≥й вигл€ду:

,

де Ц елементарн≥ конТюнкц≥њ Ц називаЇтьс€ дизТюнктивною нормальною формою (ƒЌ‘).

Ќаприклад, функц≥€ , де , Ц Ї дизТюнктивною нормальною формою (ƒЌ‘).

ќзначенн€ 3. ≈лементарна n -м≥сна конТюнкц≥€, що включаЇ в себе вс≥ зм≥нн≥ набору X (в пр€м≥й або ≥нверсн≥й форм≥), називаЇтьс€ м≥нтермом (конТюнктивним термом ) або конституентою одиниц≥.

“аким чином м≥нтерми дл€ n -м≥сноњ функц≥њ €вл€ють собою лог≥чний добуток вигл€ду , де кожна ≥з зм≥нних може входити в пр€м≥й або ≥нверсн≥й форм≥. « цього випливаЇ, що максимальне число р≥зних м≥нтер≠м≥в дл€ набору з n зм≥нних дор≥внюЇ . Ќеважко встановити, що кожний конкретний м≥нтерм приймаЇ значенн€ 1 т≥льки на Їдиному набор≥, а на вс≥х ≥нших наборах Ц приймаЇ значенн€ 0.

Ќаприклад, лог≥чн≥ добутки (конТюнкц≥њ): €вл€ютьс€ м≥нтермами зм≥нних €к≥ приймають значенн€ 1 на наборах: 0000, 1010, 1111, €ким в≥дпов≥дають дес€тков≥ номери: 0, 10, 15. «розум≥ло, що на ≥нших 12 наборах, кожний ≥з розгл€нутих м≥нтерм≥в приймаЇ значенн€ 0.

ќзначенн€ 4. ƒизТюнкц≥€ вигл€ду:

,

де Ц ус≥ конституанти одиниц≥ функц≥њ називаЇтьс€ доско≠налою дизТюнк≠тивною нормальною формою (ƒƒЌ‘).

якщо прийн€ти до уваги, що дизТюнкц≥€ вигл€ду дор≥внюЇ 1, коли хоча би одна з≥ зм≥нних приймаЇ значенн€ 1, то можна легко виразити будь-€ку булеву функц≥ю €к дизТюнкц≥ю м≥нтерм≥в (конституант одиниц≥), €к≥ в≥дпов≥дають тим наборам, на €ких функц≥€ дор≥внюЇ 1.

“еорема. Ѕудь-€ку булеву функц≥ю (тотожно) можна Їдиним способом представити у вигл€д≥ досконалоњ дизТюнктивноњ нормальноњ форми.

ƒоведенн€. –озгл€немо лог≥чну формулу

(1)

‘ормула (1) Ї дизТюнкц≥Їю елементарних конТюнкц≥й. ѕерший член формули Ц це конТюнкц≥€ значенн€ функц≥њ на нульовому набор≥: та заперечень ус≥х зм≥нних цього набору. ƒругий член формули Ц конТюнкц≥€ значенн€ функц≥њ на першому набор≥: , заперечень перших аргумент≥в цього на≠бору та аргументу без запереченн€. ¬ останньому член≥ маЇмо конТюн≠≠кц≥ю значенн€ функц≥њ на останньому набор≥ аргумент≥в та цих аргумент≥в без запереченн€.

« наведеноњ формули бачимо, що коли в набор≥ аргумент набуваЇ значенн€ 0, то в елементарну конТюнкц≥ю, €ка знаходитьс€ в квадратних дужках, в≥н входить ≥з запереченн€м, а €кщо 1 Ц то без запереченн€.

—праведлив≥сть ц≥Їњ формули очевидна. якщо, наприклад, в≥зьме≠мо наб≥р , то в л≥в≥й частин≥ матимемо . ” прав≥й частин≥ вс≥ елементарн≥ конТюнкц≥њ, кр≥м другоњ, дор≥внюють нулю, а друга набуде вигл€ду

,

тобто те саме, що ≥ в л≥в≥й частин≥.

“аким чином, при будь-€ких наборах, в л≥в≥й ≥ прав≥й частинах завжди будемо мати одинаков≥ вирази.

« доведеноњ теореми випливаЇ, що будь-€ку булеву функц≥ю можна однозначно представити в анал≥тичному вигл€д≥

, (2)

де символ У Ф означаЇ лог≥чну суму м≥нтерм≥в, на €ких функц≥€ дор≥внюЇ 1. ќдержана форма ≥ Ї ƒƒЌ‘.

ѕриклад 5. «аписати ƒƒЌ‘ дл€ функц≥й, заданих таблицею ≥стинност≥ (табл. 12).

“аблиц€ 12

–озвТ€занн€. «апишемо ƒƒЌ‘ у вигл€д≥ лог≥чноњ суми лог≥чних добутк≥в значень функц≥њ на в≥дпов≥дн≥ м≥нтерми, €к≥ записуютьс€ у вигл€д≥ елементарних конТюнкц≥й, утворених зм≥нними у пр€м≥й або ≥нверсн≥й форм≥: €кщо значенн€ зм≥нноњ 1, то пр€ма форма, а €кщо 0, то Ц ≥нверсна.

. .

Ћегко бачити, що функц≥€ Ї не що ≥нше €к сума за модулем 2 трьох зм≥нних, тобто .

‘ункц≥€ називаЇтьс€ мажоритарною (вона приймаЇ значенн€, €ке приймаЇ б≥льш≥сть зм≥нних) ≥ позначаЇтьс€ .

ѕриклад 6. ¬ к≥мнат≥ Ї три вимикач≥ осв≥тленн€. –озробити схему, €ка даЇ можлив≥сть зд≥йснювати вмиканн€ ≥ вимиканн€ осв≥тленн€ будь-€ким вимикачем незалежно в≥д положенн€ ≥нших двох вимикач≥в. ќдне положенн€ вимикача будемо вважати нульоваим (0), а друге одиничним (1). ќск≥льки Ї три вимикач≥, то схема повинна реал≥зувати булеву функц≥ю в≥д трьох аргумент≥в. —кладемо таблицю ≥стинност≥ ц≥Їњ функц≥њ при умов≥, що вс≥ три вимикач≥ знаход€тьс€ в стан≥ 0. “од≥ зм≥на положенн€ будь-€кого вимикача повинно викликати вмиканн€ осв≥тленн€. “обто на наборах 001, 010 ≥ 100 функц≥€ повинна дор≥внювати 1. ѕодальша зм≥на положенн€ будь-€кого вимикача повинно приводити до вимиканн€ осв≥тленн€. “обто на наборах 011, 101 ≥ 110 функц≥€ повинна дор≥внювати 0. ѕодальша зм≥на положенн€ будь-€кого вимикача повинно приводити до вмиканн€ осв≥тленн€, що даЇ F(1,1,1)=1. “аблицю значень функц≥њ , наведено в (табл. 13).

ѕредставимо одержану булеву функц≥ю у форм≥ (1)

“аблиц€ 13

       
       
       
       
       
       
       
       

 

–ис. 8

Ќа рис. 8 наведено комб≥-нац≥йну схему, виконану в систем≥ проектуванн€ MAX+plus II, €ка реа-л≥зовуЇ побудовану булеву функц≥ю.

Ќа рис. 9 наведено результати моделюванн€, що св≥дчить про правильн≥сть роботи схеми.

 

20.  онТюнктивна форма Ц це друга в≥дома форма представленн€ функц≥й, €ка будуЇтьс€ аналог≥чно до дизТюнктивноњ форми.

ќзначенн€ 5. Ћог≥чна сума будь-€коњ к≥лькост≥ р≥зних зм≥нних, що вход€ть ≥з запереченн€м або без нього, називаЇтьс€ елементар≠ною дизТюнк≠ц≥Їю.

Ќаприклад, елементарними дизТюнкц≥€ми Ї:

, , .

ќзначенн€ 6.  онТюнкц≥€ елементарних дизТюнкц≥й вигл€ду:

,

Ц називаЇтьс€ конТюнктивною нормальною формою ( Ќ‘).

Ќаприклад, функц≥€

,

де , , ≠Ц Ї конТюнктив≠ною нормальною формою ( Ќ‘).

ќзначенн€ 7.  онституентою нул€ (макстермом) дл€ функц≥њ n аргумент≥в, називають елементарну дизТюнкц≥ю n аргумент≥в, €ка набуваЇ значенн€ 0 т≥льки на одному набор≥, а на вс≥х ≥нших Ц значенн€ 1.

Ќаприклад, набору 0110, зм≥нних в≥дпов≥даЇ конституента нул€ вигл€ду . Ћегко переконатись, що даний макстерм приймаЇ значенн€ 0 т≥льки на вказаному набор≥, Ц на вс≥х ≥нших наборах приймаЇ значенн€ 1.

ќзначенн€ 8.  онТюнкц≥€ вигл€ду:

,

де Ц ус≥ конституенти нул€ функц≥њ , називаЇтьс€ доскона≠лою конТюнк≠тивною нормальною формою (ƒ Ќ‘).

ѕриклад 7. ƒл€ розгл€нутих у приклад≥ 3 функц≥й (табл. 11) побувати ƒ Ќ‘.

–озвТ€занн€. ћаЇмо:

30. ƒосконала пол≥ном≥альна нормальна форма. Ћегко переконатись, що в ƒƒЌ‘ можна зам≥нити операц≥ю дизТюнкц≥ю на операц≥ю додаванн€ за модулем 2, причому р≥вн≥сть збер≥гаЇтьс€. ÷€ форма називаЇтьс€ досконалою пол≥ном≥альною нормальною формою (ƒѕЌ‘). ƒл€ функц≥й з прикладу 3, маЇмо:

.

40.  анон≥чний пол≥ном ∆егалк≥на Ц це пол≥ном вигл€ду

де

“еорема ∆егалк≥на. Ѕудь-€ка лог≥чна функц≥€ може бути представлена у вигл€д≥ канон≥чного пол≥нома ∆егалк≥на.

ѕриклад 8. ¬иразити у вигл€д≥ пол≥нома ∆егалк≥на функц≥ю .

–озвТ€занн€. «аданий вираз будемо шукати у вигл€д≥ пол≥нома з невизначеними коеф≥ц≥Їнтами вигл€ду

.

ѕри маЇмо ; при д≥станемо ; при д≥станемо ; при д≥станемо , зв≥дки . “аким чином, .

якщо у ƒѕЌ‘ ус≥ зм≥нн≥ в ≥нверсн≥й форм≥ зам≥нити у в≥дпов≥дност≥ з сп≥вв≥дношенн€м (див. акс≥оми алгебри ∆егалк≥на), то розкривши дужки ≥ зв≥вши под≥бн≥ члени, одержимо функц≥ю у вигл€д≥ суперпозиц≥њ функц≥й з набору або канон≥чного пол≥нома ∆егалк≥на.

ѕриклад 9. ƒл€ розгл€нутих вище функц≥й (табл. 10) побуду≠вати канон≥чний пол≥ном ∆егалк≥на.

–озвТ€занн€. ћаЇмо:

ѕри спрощен≥ функц≥й використана властив≥сть функц≥њ додаванн€ за модулем 2, що .





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


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


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

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

—воим успехом € об€зана тому, что никогда не оправдывалась и не принимала оправданий от других. © ‘лоренс Ќайтингейл
==> читать все изречени€...

2182 - | 2003 -


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

√ен: 0.034 с.