En berømt matematiker DeMorgan opfandt de to vigtigste sætninger i boolsk algebra. DeMorgans sætninger bruges til matematisk verifikation af ækvivalensen af NOR- og negative-AND-portene og negative-ELLER- og NAND-portene. Disse teoremer spiller en vigtig rolle i løsningen af forskellige booleske algebraudtryk. I nedenstående tabel er den logiske operation for hver kombination af inputvariablen defineret.
Inputvariabler | Udgangstilstand | ||||
---|---|---|---|---|---|
EN | B | OG | NAND | ELLER | HELLER IKKE |
0 | 0 | 0 | 1 | 0 | 1 |
0 | 1 | 0 | 1 | 1 | 0 |
1 | 0 | 0 | 1 | 1 | 0 |
1 | 1 | 1 | 0 | 1 | 0 |
Reglerne i De-Morgans sætning er fremstillet ud fra de boolske udtryk for OR , AND og IKKE ved at bruge to inputvariable x og y. Den første sætning i Demorgan siger, at hvis vi udfører AND-operationen af to inputvariable og derefter udfører NOT-operationen af resultatet, vil resultatet være det samme som ELLER-operationen af komplementet til den variabel. Den anden sætning i DeMorgan siger, at hvis vi udfører ELLER-operationen af to inputvariabler og derefter udfører IKKE drift af resultatet, vil resultatet være det samme som OG-operationen af komplementet af den variabel.
De-Morgans første sætning
Ifølge den første sætning er komplementresultatet af AND-operationen lig med OR-operationen af komplementet af den variabel. Det svarer således til NAND-funktionen og er en negativ-ELLER-funktion, der beviser, at (A.B)' = A'+B', og vi kan vise dette ved hjælp af følgende tabel.
Indgange | Output 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 anden sætning
Ifølge den anden sætning er komplementresultatet af OR-operationen lig med OG-operationen af komplementet af den variabel. Det svarer således til NOR-funktionen og er en negativ-AND-funktion, der beviser, at (A+B)' = A'.B', og vi kan vise dette ved hjælp af følgende sandhedstabel.
Indgange | Output 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 |
Lad os tage nogle eksempler, hvor vi tager nogle udtryk og anvender DeMorgans sætninger.
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 at anvende DeMorgans sætning på dette udtryk, skal vi følge følgende udtryk:
1) I komplet udtryk finder vi først de termer, som vi kan anvende DeMorgans sætning på og behandle hvert led som en enkelt variabel.
Så,
2) Dernæst anvender vi DeMorgans første sætning. Så,
3) Dernæst bruger vi regel nummer 9, dvs. (A=(A')') til at annullere de dobbelte takter.
4) Dernæst anvender vi DeMorgans anden sætning. Så,
5) Anvend igen regel nummer 9 for at annullere dobbeltbjælken
Nu har dette udtryk ikke noget udtryk, hvor vi kan anvende nogen regel eller sætning. Så dette er det endelige udtryk.
Eksempel 3: (AB'.(A + C))'+ A'B.(A + B + C')'
leksikografisk orden