Questi due teoremi sono fondamentali per un semplice fatto. Essi ci permettono di trasformare AND in OR e viceversa. Ma non solo! Siccome possiamo trasformare un AND in un OR, attraverso i teoremi di De Morgan, definiamo le cosiddette algebre universali. Ossia delle algebre in cui abbiamo ad esempio solo gli operatori AND e NOT (perchè l'OR è espresso da un'AND ecc...). I due teoremi (sono duali) quindi, come detto più volte, ne basta conoscere uno solo, l'altro lo ricavate per dualità. $$ \diamond $$

Teoremi di De Morgan $$ \overline{x\cdot y} = \overline{x} + \overline{y} \hspace{2cm} \overline{x + y} = \overline{x} \cdot \overline{y} $$

$$ \diamond\diamond $$
Dimostrazione

La dimostrazione ve la riporto in due versioni. Nella prima versione utilizzerò le tavole di verità, nella seconda versione i diagrammi di Venn. Del resto in algebra booleana, siamo in un certo senso avvantaggiati, rispetto all'algebra tradizionale perchè i domini delle nostre funzioni sono finiti e quindi possiamo elencare tutti i casi. Per dimostrare il teorema di De-Morgan, costruiamoci la tabella di verità di una delle due espressioni, basta dimostrarne una sola, l'altra sarà valida per dualità. Consideriamo ad esempio la prima versione.

$$ \begin{array}{rrrrrrr} x & y & \overline{x} & \overline{y} & x\cdot y & \overline{x\cdot y} & \overline{x} + \overline{y} \\ \hline 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 \end{array} $$ La dimostrazione che la formula è valida si evince dalle ultime due colonne della tavola di verità che sono uguali per ogni \( x\) ed \( y\), quindi per tutti i casi in input (che sono \( 4\)). Naturalmente il fatto che valga la dualità, corrisponde a invertire nella tabella gli zeri con gli uni e veceversa, è ovvio che si ottengono relazioni equivalenti.

Ma vediamo come dimostrare il teorema in versione grafica. L'oggetto che abbiamo a disposizione sono i diagrammi di venn, che esprimono le relazioni con dei diagrammi rappresentati da cerchi.

$$ \diamond $$