ДеМорганов теорем

Лекция 67. Теорема де Моргана (Јули 2019).

$config[ads_text] not found
Anonim

ДеМорганов теорем

Поглавље 7 - Боолеан алгебра


Математичар по имену ДеМорган је развио пар важних правила везаних за групно комплементирање у Боолеан алгебри. Групним комплементирањем, мислим на комплемент групе групе, представљене дугом бар преко више од једне променљиве.

Морате се сетити из поглавља о логичким вратима да обртање свих улаза на капију преиначује основну функцију тог гатеа од АНД-ОР или обратно, а такође обрће излаз. Дакле, ОР гате са свим улазним инверзима (Негатив-ОР гате) понаша се исто као НАНД гате, а АНД гате са свим улазима обрнутим (Негатив-АНД гате) понаша се исто као НОР гате. Теорема ДеМорган-а истичу исту еквиваленцију у "заосталом" облику: претварање излаза било којег врата резултира у истој функцији као супротни тип капије (АНД вс. ОР) са инверзним улазима:

Дуга трака која пролази кроз термин АБ делује као симбол групације, и као таква потпуно се разликује од производа А и Б независно преокренутих. Другим речима, (АБ) 'није једнако А'Б'. Зато што се "приме" симбол (') не може проширити преко две варијабле као што је шипка, присиљени смо да користимо заграде да би се примијенило на цијели израз АБ у претходној реченици. Бар, међутим, делује као свој симбол за груписање када се истегне преко више варијабли. Ово има дубок утицај на то како се Боолеан изрази оцењују и смањују, као што ћемо видети.

ДеМорганов теорем се може сматрати у смислу разбијања дугачког симбола. Када је дугачак трака прекинута, операција која се директно налази испод паузе се мења од додатка до множења или обрнуто, а сломљени комади остају над појединачним варијаблама. Илустровати:

Када у изразу постоји више "слојева" шипки, можете само да прекинете један бар једном, а најчешће је лакше започети поједностављивање тако што ћете најраније најраније бар прво прекинути. Да бисмо илустровали, узмимо израз (А + (БЦ) ')' и смањимо га користећи ДеМорганове Теореме:

После савета да најпре доспијемо најдужи (највиши) бар, почињем тако што ћу прекинути шипку који покрива цео израз као први корак:

Као резултат тога, изворно коло је сведено на три улазна И улазна врата са инвертираним улазом А:

Никада не би требало да прекинете више од једне бар у једном кораку, као што је илустровано овде:

Као што је запањујуће као што може бити очување корака и прекидање више од једног бара у исто време, то често доводи до погрешног резултата, зато немојте то радити!

Могуће је правилно редуцирати овај израз тако што прво разбије кратку шипку, а не прво дугу шипку:

Крајњи резултат је исти, али потребно је више корака у поређењу са применом првог метода, где је најстарији трака први прекршен. Имајте на уму како смо у трећем кораку разбили дугачак бар на два места. Ово је легитимна математичка операција, а не исто што и разбијање два бара у једном кораку! Забрана кршења више од једне бар у једном кораку није забрана од рушења бар на више места. Прекидање на више места у једном кораку је у реду; кршење више од једне бар у једном кораку није.

Можда се питате зашто су заграде биле постављене око под-израза Б '+ Ц', с обзиром на чињеницу да сам их само уклонио у наредном кораку. Урадио сам ово да нагласим важан али лако запостављен аспект Деорегове теореме. Пошто дуга бар функционира као симбол групације, варијабиле које су раније биле груписане сломљеном траком морају остати груписане да не би дошло до погрешног приоритета (реда рада). У овом примјеру, стварно не би било важно да ли сам заборавио ставити заграде након разбијања кратке траке, али у другим случајевима то може. Размотрите овај пример, почевши од другачијег израза:

Као што можете видети, одржавање груписања подразумеване од комплементарних шипки за овај израз је кључно за добијање тачног одговора.

Хајде да применимо принципе ДеМорганових теорема о поједностављењу кола:

Као и увек, наш први корак у поједностављивању овог кола мора бити генерисање еквивалентног Боолеан израза. Ово можемо учинити постављањем ознаке подизразнице на излаз сваке капије, пошто улазни подаци постану познати. Ево првог корака у овом процесу:

Затим можемо означити излазе прве НОР гате и НАНД гате. Када се бавим инвертираним излазима, сматрам да је лакше написати израз за излаз врата без коначне инверзије, са стрелицом која показује непосредно пред инверзни мехур. Затим, на жици која води из капије (после мехурића), пишем пун, допуњени израз. Ово помаже да не заборавим комплементарну траку у под-изразу, присиљавајући себе да поделите задатак из писања израза у два корака:

Коначно, напишемо израз (или пар израза) за последњу НОР капију:

Сада смањимо овај израз користећи идентитете, својства, правила и теореме (ДеМорганове) Боолове алгебре:

Еквивалентни гате круг за овај изразито поједностављен израз је следећи:

  • ПРЕГЛЕД
  • ДеМорганове теореме описују еквиваленцију између врата са инверзним улазима и капијама са инверзним излазима. Једноставно речено, НАНД гате је еквивалентан вратима Негатив-ОР, а НОР гате је еквивалентан негативној АНД капији.
  • Када "преломне" комплементарну траку у Боолеан изразу, операција која се директно налази испод паузе (додатак или множење) се обнавља, а сломљени комади остају изнад одговарајућих термина.
  • Често је лакше приступити проблем тако што се разбија најдужи (највиши) шипак пре него што се разбије било који барови испод њега. Никада не покушавајте да сломите две шипке у једном кораку!
  • Комплеменационе траке функционишу као групни симболи. Због тога, када је пруга сломљена, изрази испод њега морају остати груписани. Опртке могу бити постављене око ових груписаних термина као помоћ да се избегне промјена приоритета.