I due teoremi sono duali:
-
-
Con riferimento a termini insiemistici, il primo si enuncia affermando che se un elemento non appartiene ad per , allora o non appartiene ad o non appartiene a o non appartiene ad entrambi. Il secondo teorema si enuncia affermando che se un elemento non appartiene ad , allora non appartiene ad e non appartiene a .
È immediata la generalizzazione a un numero di variabili:
-
-
Nella logica proposizionale possono essere formulate in vario modo:
-
oppure
-
oppure
-
e nella teoria degli insiemi:
-
oppure
-
e
-
oppure
-
In pratica esse descrivono il comportamento dei connettivi logici (AND e OR) quando una negazione viene tolta da o inserita in una formula in parentesi. Se si raccoglie la negazione fuori parentesi o la si distribuisce tra i termini in parentesi, il connettivo si trasforma nel suo opposto.
Espresse in forma tabellare:
¬(W+Y) = (¬W) * (¬Y)
|
¬(W*Y) = (¬W) + (¬Y)
|
1 + W = 1
|
0 * W = 0
|
0 + W = W
|
1 * W = W
|
I teoremi si possono dimostrare sia algebricamente che con l'ausilio della tabella della verità, essendo i casi da provare in numero finito:
|
|
|
|
|
|
|
V |
V |
F |
F |
V |
F |
F
|
V |
F |
F |
V |
V |
F |
F
|
F |
V |
V |
F |
V |
F |
F
|
F |
F |
V |
V |
F |
V |
V
|
Prima di passare alla dimostrazione è utile annotare alcune proprietà e definizioni dell'algebra booleana; si considerino , e tre variabili booleane:
- e, viceversa,
- è la negazione logica di
- (due negazioni logiche si elidono così che una variabile negata due volte equivale alla variabile stessa non negata)
-
-
-
-
-
-
-
- (notare come questa proprietà sia valida solamente nell'algebra booleana, non nella comune algebra)
DIMOSTRAZIONE:
I)
(Si applica la proprietà 11)
(Si applica la proprietà 8)
(Si applica la proprietà 6)
(Si applica la proprietà 4)
II)
(Si applica la proprietà 10)
(Si applica la proprietà 9)
(Si applica la proprietà 7)
(Si applica la proprietà 5)
Sia ora ; otteniamo da I) e II) rispettivamente le equazioni:
I-bis)
II-bis)
Unendo le proprietà 6) e 7) rispettivamente alle equazioni I-bis) e II-bis) si possono impostare i due sistemi equivalenti:
s1)
s2)
Adoperando nuovamente la sostituzione e, successivamente, la proprietà 3), si ottiene infine:
c.v.d.
|
|
|
|
|
|
|
V |
V |
F |
F |
V |
F |
F
|
V |
F |
F |
V |
F |
V |
V
|
F |
V |
V |
F |
F |
V |
V
|
F |
F |
V |
V |
F |
V |
V
|