Come abbiamo visto in precedenza, l’algebra booleana utilizza un insieme di leggi e regole per definire il funzionamento di un circuito logico digitale con “0” e “1” utilizzati per rappresentare una condizione di ingresso o uscita digitale. L’algebra booleana usa questi zeri e uno per creare tabelle di verità ed espressioni matematiche per definire il funzionamento digitale di un circuito logico AND, OR e NOT (o inversione) così come i modi di esprimere altre operazioni logiche come la funzione XOR (Exclusive-OR).
Mentre l’insieme di leggi e regole di George Boole ci permette di analizzare e semplificare un circuito digitale, ci sono due leggi all’interno del suo insieme che sono attribuite ad Augustus DeMorgan (un matematico inglese del XIX secolo) che vede le operazioni logiche NAND e NOR come funzioni separate NOT AND e NOT OR rispettivamente.
Ma prima di esaminare la teoria di DeMorgan in modo più dettagliato, ricordiamoci delle operazioni logiche di base dove A e B sono variabili binarie logiche (o booleane) di input, e i cui valori possono essere solo “0” o “1” producendo quattro possibili combinazioni di input, 00, 01, 10 e 11.
Tabella della verità per ogni operazione logica
| Variabile di ingresso | Condizioni di uscita | ||||||
| A | B | AND | NAND | OR | NOR | ||
| 0 | 0 | 0 | 1 | 0 | 1 | ||
| 0 | 1 | 0 | 1 | 1 | 1 | 0 | |
| 1 | 0 | 0 | 1 | 1 | 0 | ||
| 1 | 1 | 1 | 0 | 1 | 0 | ||
La seguente tabella fornisce un elenco delle funzioni logiche comuni e la loro notazione booleana equivalente dove un “.” (un punto) indica un’operazione AND (prodotto), un “+” (segno più) indica un’operazione OR (somma), e il complemento o l’inverso di una variabile è indicato da una barra sopra la variabile.
| Funzione logica | Notazione booleana | |
| AND | A.B | |
| OR | A+B | |
| NOT | A | |
| NAND | A .B | |
| NOR | A+B |
Teoria di DeMorgan
I teoremi di DeMorgan sono fondamentalmente due serie di regole o leggi sviluppate dalle espressioni booleane per AND, OR e NOT usando due variabili di input, A e B. Queste due regole o teoremi permettono alle variabili di input di essere negate e convertite da una forma di funzione booleana in una forma opposta.
Il primo teorema di DeMorgan afferma che due (o più) variabili NOR´ed insieme sono uguali alle due variabili invertite (Complemento) e AND’ed, mentre il secondo teorema afferma che due (o più) variabili NAND’ed insieme sono uguali ai due termini invertiti (Complemento) e OR´ed. Cioè sostituire tutti gli operatori OR con operatori AND, o tutti gli operatori AND con un operatore OR.
Primo teorema di DeMorgan
Il primo teorema di DeMorgan dimostra che quando due (o più) variabili di input sono AND’ed e negate, sono equivalenti agli OR dei complementi delle singole variabili. Così l’equivalente della funzione NAND sarà una funzione negativa-OR, dimostrando che A.B = A+B. Possiamo mostrare questa operazione usando la seguente tabella.
Verifica del primo teorema di DeMorgan usando la tabella della verità
| Ingressi | Uscite della tabella della verità per ogni termine | |||||||
| B | A | A.B | A.B | A | B | A + B | ||
| 0 | 0 | 0 | 1 | 1 | 1 | |||
| 0 | 1 | 0 | 1 | 0 | 1 | 1 | ||
| 1 | 0 | 0 | 1 | 1 | 0 | 1 | ||
| 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
Si può anche dimostrare che A.B = A+B usando porte logiche come mostrato.
Implementazione della prima legge di DeMorgan usando porte logiche
La disposizione superiore delle porte logiche di: A.B può essere implementato utilizzando un gate NAND standard con ingressi A e B. La disposizione del gate logico inferiore inverte prima i due ingressi che producono A e B. Questi diventano poi gli ingressi del gate OR. Quindi l’uscita dal gate OR diventa: A+B
Allora possiamo vedere che una funzione standard di OR gate con invertitori (NOT gate) su ogni suo ingresso è equivalente a una funzione NAND gate. Quindi un singolo gate NAND può essere rappresentato in questo modo come l’equivalenza di un gate NAND è un negativo-OR.
Secondo teorema di DeMorgan
Il secondo teorema di DeMorgan dimostra che quando due (o più) variabili di ingresso sono OR e negate, sono equivalenti all’AND dei complementi delle singole variabili. Così l’equivalente della funzione NOR è una funzione negativa-AND che dimostra che A+B = A.B, e ancora una volta possiamo mostrare l’operazione usando la seguente tabella di verità.
Verifica del secondo teorema di DeMorgan usando la tabella della verità
| Ingressi | Esiti della tabella della verità per ogni termine | ||||||
| B | A | A+B | A+B | A | B | A . B | |
| 0 | 0 | 0 | 1 | 1 | 1 | 1 | |
| 0 | 1 | 1 | 0 | 0 | 1 | 0 | |
| 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | |
Si può anche dimostrare che A+B = A.B utilizzando il seguente esempio di porte logiche.
Implementazione della seconda legge di DeMorgan utilizzando porte logiche
La disposizione superiore della porta logica di: A+B può essere implementato utilizzando una funzione standard di gate NOR utilizzando gli ingressi A e B. La disposizione inferiore del gate logico inverte prima i due ingressi, producendo così A e B. Questi diventano quindi gli ingressi del gate AND. Quindi l’uscita dal gate AND diventa: A.B
Allora possiamo vedere che una funzione standard di AND gate con invertitori (NOT gates) su ciascuno dei suoi ingressi produce una condizione di uscita equivalente ad una funzione standard di NOR gate, e un NOR gate individuale può essere rappresentato in questo modo poiché l’equivalenza di un NOR gate è un negative-AND.
Anche se abbiamo usato i teoremi di DeMorgan con solo due variabili di ingresso A e B, essi sono ugualmente validi per l’uso con espressioni di tre, quattro o più variabili di ingresso, per esempio:
Per un ingresso di 3 variabili
A.B.C = A+B+C
e anche
A+B+C = A.B.C
Per un input di 4 variabili
A.B.C.D = A+B+C+D
e anche
A+B+C+D = A.B.C.D
e così via.
Gate Equivalenti di DeMorgan
Abbiamo visto qui che usando i Teoremi di DeMorgan possiamo sostituire tutti gli operatori AND (.) con un OR (+) e viceversa, e poi completa ognuno dei termini o variabili nell’espressione invertendolo, cioè da 0 a 1 e da 1 a 0 prima di invertire l’intera funzione.
Quindi, per ottenere l’equivalente DeMorgan di una porta AND, NAND, OR o NOR, dobbiamo semplicemente aggiungere degli invertitori (NOT-gates) a tutti gli ingressi e le uscite e cambiare un simbolo AND in un simbolo OR o cambiare un simbolo OR in un simbolo AND come mostrato nella tabella seguente.
Gate equivalenti di DeMorgan
| Standard Logic Gate | DeMorgan’s Equivalent Gate |
 |
 |
 |
 |
 |
 |
 |
 |
Abbiamo visto in questo tutorial sul Thereom di DeMorgan che il complemento di due (o più) variabili di ingresso AND è equivalente all’OR dei complementi di queste variabili, e che il complemento di due (o più) variabili OR è equivalente all’AND dei complementi delle variabili come definito da DeMorgan.
