DeMorgan's stellingen

Een wiskundige genaamd DeMorgan ontwikkelde een paar belangrijke regels met betrekking tot groepscomplementatie in Booleaanse algebra.

Door groep complementatie, ik verwijs naar het complement van een groep termen, weergegeven door een lange balk over meer dan één variabele.

U moet zich uit het hoofdstuk over logische poorten herinneren dat het omkeren van alle ingangen naar een poort de essentiële functie van die poort omkeert van EN naar OF, of vice versa, en ook de uitvoer omkeert.

Dus een OF-poort met alle ingangen omgekeerd (een negatieve-OF-poort) gedraagt ​​zich hetzelfde als een NIET-EN-poort, en een EN-poort met alle ingangen omgekeerd (een negatieve-EN-poort) gedraagt ​​zich hetzelfde als een NOR-poort.

De stellingen van DeMorgan stellen dezelfde equivalentie in "achterwaartse" vorm:dat het inverteren van de output van een poort resulteert in dezelfde functie als het tegenovergestelde type poort (AND vs. OR) met geïnverteerde inputs:

Een lange balk die zich over de term AB uitstrekt, fungeert als een groeperingssymbool en is als zodanig totaal verschillend van het product van A en B onafhankelijk omgekeerd.

Met andere woorden, (AB)' is niet gelijk aan A'B'. Omdat het "prime"-symbool (') niet over twee variabelen kan worden uitgerekt zoals een staaf, zijn we genoodzaakt haakjes te gebruiken om het van toepassing te laten zijn op de hele term AB in de vorige zin.

Een balk fungeert echter als zijn eigen groeperingssymbool wanneer deze over meer dan één variabele wordt uitgerekt.

Dit heeft grote invloed op hoe Booleaanse uitdrukkingen worden geëvalueerd en gereduceerd, zoals we zullen zien.

Theorema van DeMorgan

De stelling van DeMorgan kan worden gezien in termen van breken een lang balksymbool.

Wanneer een lange staaf wordt gebroken, verandert de bewerking direct onder de breuk van optellen naar vermenigvuldigen, of omgekeerd, en blijven de gebroken staafstukken over de afzonderlijke variabelen. Ter illustratie:

Als er meerdere "lagen" met staven in een uitdrukking voorkomen, mag u slechts één staaf tegelijk afbreken , en het is over het algemeen gemakkelijker om met vereenvoudiging te beginnen door eerst de langste (bovenste) maat te breken.

Laten we ter illustratie de uitdrukking (A + (BC)')' nemen en deze verkleinen met behulp van de stellingen van DeMorgan:

Na het advies om eerst de langste (bovenste) maat te breken, zal ik als eerste stap beginnen met het breken van de maat die de hele uitdrukking omvat:

Als gevolg hiervan wordt het oorspronkelijke circuit gereduceerd tot een EN-poort met drie ingangen met de A-ingang omgekeerd:

Je moet nooit breek meer dan één maat in één stap, zoals hier geïllustreerd:

Hoe verleidelijk het ook is om stappen te besparen en meer dan één maat per keer te breken, het leidt vaak tot een onjuist resultaat, dus doe het niet!

Het is mogelijk om deze uitdrukking op de juiste manier te verminderen door eerst de korte balk te breken, in plaats van eerst de lange balk:

Het eindresultaat is hetzelfde, maar er zijn meer stappen nodig in vergelijking met het gebruik van de eerste methode, waarbij de langste balk het eerst werd gebroken.

Merk op hoe we in de derde stap de lange balk op twee plaatsen hebben gebroken.

Dit is een legitieme wiskundige bewerking en niet hetzelfde als het breken van twee maten in één stap!

Het verbod om meer dan één maat in één stap te breken is niet een verbod op het breken van een balk op meer dan één plaats.

Inbreken op meer dan één plaats in een enkele stap is oke; het breken van meer dan één balk in een enkele stap niet.

Je vraagt ​​je misschien af ​​waarom er haakjes om de subexpressie B' + C' zijn geplaatst, aangezien ik ze zojuist in de volgende stap heb verwijderd.

Ik deed dit om een ​​belangrijk maar gemakkelijk te verwaarlozen aspect van de stelling van DeMorgan te benadrukken.

Aangezien een lange balk fungeert als een groeperingssymbool, moeten de variabelen die voorheen werden gegroepeerd door een onderbroken balk, gegroepeerd blijven om te voorkomen dat de juiste prioriteit (volgorde van bewerking) verloren gaat.

In dit voorbeeld zou het echt niet uitmaken als ik haakjes vergat te plaatsen na het breken van de korte balk, maar in andere gevallen zou het kunnen.

Beschouw dit voorbeeld, beginnend met een andere uitdrukking:

Zoals je kunt zien, is het van cruciaal belang om de groepering die wordt geïmpliceerd door de complementatiebalken voor deze uitdrukking te behouden om het juiste antwoord te krijgen.

Laten we de principes van de stellingen van DeMorgan toepassen op de vereenvoudiging van een poortcircuit:

Zoals altijd moet onze eerste stap bij het vereenvoudigen van dit circuit zijn om een ​​equivalente Booleaanse uitdrukking te genereren.

We kunnen dit doen door een sub-expressielabel aan de uitgang van elke poort te plaatsen, naarmate de ingangen bekend worden. Dit is de eerste stap in dit proces:

Vervolgens kunnen we de uitgangen van de eerste NOR-poort en de NAND-poort labelen.

Als ik te maken heb met poorten met omgekeerde uitvoer, vind ik het gemakkelijker om een ​​uitdrukking voor de uitvoer van de poort te schrijven zonder de laatste inversie, met een pijl die wijst naar net voor de inversiebel.

Dan, bij de draad die uit de poort leidt (na de bel), schrijf ik de volledige, aangevulde uitdrukking.

Dit helpt ervoor te zorgen dat ik een complementaire balk in de subuitdrukking niet vergeet, door mezelf te dwingen de taak voor het schrijven van uitdrukkingen in twee stappen te splitsen:

Ten slotte schrijven we een uitdrukking (of een paar uitdrukkingen) voor de laatste NOR-poort:

Nu reduceren we deze uitdrukking met behulp van de identiteiten, eigenschappen, regels en stellingen (DeMorgan's) van Booleaanse algebra:

Het equivalente poortcircuit voor deze veel vereenvoudigde uitdrukking is als volgt:

BEOORDELING:

• De stellingen van DeMorgan beschrijven de gelijkwaardigheid tussen poorten met geïnverteerde ingangen en poorten met geïnverteerde uitgangen. Simpel gezegd, een NAND-poort is gelijk aan een negatief-OF-poort en een NOR-poort is gelijk aan een negatief-EN-poort.
• Bij het "breken" van een complementatiebalk in een Booleaanse uitdrukking, wordt de bewerking direct onder de breuk (optellen of vermenigvuldigen) omgekeerd en blijven de gebroken balkdelen boven de respectieve termen staan.
• Het is vaak gemakkelijker om een ​​probleem te benaderen door de langste (bovenste) staaf te breken voordat de staven eronder worden afgebroken. Je moet nooit probeer twee maten in één stap te breken!
• Complementatiebalken fungeren als groeperingssymbolen. Daarom moeten de termen eronder gegroepeerd blijven wanneer een balk wordt verbroken. Er kunnen haakjes rond deze gegroepeerde termen worden geplaatst om te voorkomen dat de prioriteit verandert.

GERELATEERDE WERKBLAD:

• Booleaanse algebra-werkblad