En kjent matematiker DeMorgan oppfant de to viktigste teoremene i boolsk algebra. DeMorgans teoremer brukes til matematisk verifisering av ekvivalensen til NOR- og negative-AND-portene og negative-ELLER- og NAND-portene. Disse teoremene spiller en viktig rolle i å løse ulike boolske algebrauttrykk. I tabellen nedenfor er den logiske operasjonen for hver kombinasjon av inngangsvariabelen definert.
Inndatavariabler | Utgangstilstand | ||||
---|---|---|---|---|---|
EN | B | OG | NAND | ELLER | ELLER |
0 | 0 | 0 | 1 | 0 | 1 |
0 | 1 | 0 | 1 | 1 | 0 |
1 | 0 | 0 | 1 | 1 | 0 |
1 | 1 | 1 | 0 | 1 | 0 |
Reglene i De-Morgans teorem er produsert fra de boolske uttrykkene for OR , AND , og IKKE ved å bruke to inngangsvariabler x og y. Den første teoremet til Demorgan sier at hvis vi utfører OG-operasjonen av to inngangsvariabler og deretter utfører NOT-operasjonen av resultatet, vil resultatet være det samme som OR-operasjonen til komplementet til den variabelen. Den andre teoremet til DeMorgan sier at hvis vi utfører OR-operasjonen av to inngangsvariabler og deretter utfører IKKE operasjon av resultatet, vil resultatet være det samme som OG-operasjonen av komplementet til den variabelen.
De-Morgans første teorem
I følge det første teoremet er komplementresultatet av OG-operasjonen lik OR-operasjonen til komplementet til den variabelen. Dermed er den ekvivalent med NAND-funksjonen og er en negativ-ELLER-funksjon som beviser at (A.B)' = A'+B' og vi kan vise dette ved å bruke følgende tabell.
Innganger | Utgang for hvert semester | |||||
---|---|---|---|---|---|---|
EN | B | A.B | (A.B)' | EN' | B' | A'A+B' |
0 | 0 | 0 | 1 | 1 | 1 | 1 |
0 | 1 | 0 | 1 | 1 | 0 | 1 |
1 | 0 | 0 | 1 | 0 | 1 | 1 |
1 | 1 | 1 | 0 | 0 | 0 | 0 |
De-Morgans andre teorem
I følge det andre teoremet er komplementresultatet av OR-operasjonen lik OG-operasjonen til komplementet til den variabelen. Dermed er den ekvivalent med NOR-funksjonen og er en negativ-AND-funksjon som beviser at (A+B)' = A'.B' og vi kan vise dette ved å bruke følgende sannhetstabell.
Innganger | Utgang for hvert semester | |||||
---|---|---|---|---|---|---|
EN | B | A+B | (A+B)' | EN' | B' | A'.B' |
0 | 0 | 0 | 1 | 1 | 1 | 1 |
0 | 1 | 1 | 0 | 1 | 0 | 0 |
1 | 0 | 1 | 0 | 0 | 1 | 0 |
1 | 1 | 1 | 0 | 0 | 0 | 0 |
La oss ta noen eksempler der vi tar noen uttrykk og anvender DeMorgans teoremer.
Eksempel 1: (A.B.C)'
(A.B.C)'=A'+B'+C'
Eksempel 2: (A+B+C)'
(A+B+C)'=A'.B'.C
Eksempel 3: ((A+BC')'+D(E+F')')'
For å bruke DeMorgans teorem på dette uttrykket, må vi følge følgende uttrykk:
1) I fullstendig uttrykk finner vi først de begrepene vi kan bruke DeMorgans teorem på og behandle hvert begrep som en enkelt variabel.
Så,
2) Deretter bruker vi DeMorgans første teorem. Så,
3) Deretter bruker vi regel nummer 9, dvs. (A=(A')') for å kansellere de doble strekene.
4) Deretter bruker vi DeMorgans andre teorem. Så,
5) Bruk regel nummer 9 igjen for å avbryte dobbeltstreken
Nå har dette uttrykket ingen term der vi kan bruke noen regel eller teorem. Så dette er det endelige uttrykket.
Eksempel 3: (AB'.(A + C))'+ A'B.(A + B + C')'
leksikografisk rekkefølge