Híres matematikus DeMorgan feltalálta a logikai algebra két legfontosabb tételét. A DeMorgan-tételek a NOR és a negatív ÉS kapuk, valamint a negatív VAGY és NAND kapuk ekvivalenciájának matematikai ellenőrzésére szolgálnak. Ezek a tételek fontos szerepet játszanak a különféle logikai algebrai kifejezések megoldásában. Az alábbi táblázat a logikai műveleteket a bemeneti változó egyes kombinációihoz határozza meg.
Bemeneti változók | Kimeneti állapot | ||||
---|---|---|---|---|---|
A | B | ÉS | NAND | VAGY | SEM |
0 | 0 | 0 | 1 | 0 | 1 |
0 | 1 | 0 | 1 | 1 | 0 |
1 | 0 | 0 | 1 | 1 | 0 |
1 | 1 | 1 | 0 | 1 | 0 |
A De-Morgan tétel szabályait az OR , AND , és NOT logikai kifejezéseiből állítjuk elő két x és y bemeneti változó használatával. Demorgan első tétele azt mondja, hogy ha végrehajtjuk két bemeneti változó ÉS műveletét, majd végrehajtjuk az eredmény NEM műveletét, akkor az eredmény ugyanaz lesz, mint az adott változó kiegészítésének VAGY művelete. DeMorgan második tétele azt mondja, hogy ha végrehajtjuk két bemeneti változó VAGY műveletét, majd végrehajtjuk a NEM az eredmény művelete, az eredmény ugyanaz lesz, mint az adott változó kiegészítésének ÉS művelete.
De-Morgan első tétele
Az első tétel szerint az ÉS művelet komplementereje egyenlő az adott változó komplementerének VAGY műveletével. Így ekvivalens a NAND függvénnyel, és egy negatív VAGY függvény, amely bizonyítja, hogy (A.B)' = A'+B', és ezt a következő táblázat segítségével tudjuk megmutatni.
Bemenetek | Kimenet minden kifejezéshez | |||||
---|---|---|---|---|---|---|
A | B | A.B | (A.B)” | A' | 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-Morgan második tétele
A második tétel szerint a VAGY művelet komplementereje egyenlő az adott változó komplementerének ÉS műveletével. Így ez a NOR függvény megfelelője, és egy negatív ÉS függvény, amely bizonyítja, hogy (A+B)' = A'.B', és ezt a következő igazságtáblázat segítségével tudjuk megmutatni.
Bemenetek | Kimenet minden kifejezéshez | |||||
---|---|---|---|---|---|---|
A | B | A+B | (A+B)' | A' | 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 |
Vegyünk néhány példát, amelyekben néhány kifejezést alkalmazunk, és alkalmazzuk DeMorgan tételeit.
1. példa: (A.B.C)'
(A.B.C)'=A'+B'+C'
2. példa: (A+B+C)'
(A+B+C)'=A'.B'.C
3. példa: ((A+BC')'+D(E+F')')'
Ahhoz, hogy a DeMorgan-tételt alkalmazzuk erre a kifejezésre, a következő kifejezéseket kell követnünk:
1) A teljes kifejezésben először megkeressük azokat a kifejezéseket, amelyekre alkalmazhatjuk a DeMorgan-tételt, és minden tagot egyetlen változóként kezelünk.
Így,
2) Ezt követően alkalmazzuk DeMorgan első tételét. Így,
3) Ezután a 9-es szabályt használjuk, azaz (A=(A')') a kettős sávok törlésére.
4) Ezután alkalmazzuk DeMorgan második tételét. Így,
5) Ismét alkalmazza a 9-es szabályt a dupla sáv törléséhez
Ennek a kifejezésnek nincs olyan kifejezése, amelyben bármilyen szabályt vagy tételt alkalmazhatnánk. Tehát ez a végső kifejezés.
3. példa: (AB'.(A + C))'+ A'B.(A + B + C')'
interfész vs absztrakt osztály