Logica matematica/Calcolo delle proposizioni/Dimostrazione di completezza di insiemi di connettivi

Template:Logica matematica Ci occuperemo qui di dimostrare che i connettivi NOR e NAND, così come gli insiemi $\{\mathrm{\neg },\wedge \}$, $\{\mathrm{\neg },\vee \}$ e $\{\mathrm{\neg },\wedge ,\vee \}$ sono funzionalmente completi.

Dimostrazione

Dimostrazione della completezza di NOR e NAND

Per provare la completezza di NOR e NAND, dimostriamo innanzitutto che i connettivi $\mathrm{\neg },\wedge ,\vee$ possono essere definiti attraverso formule che contengono solo connettivi NOR o solo NAND:

NOT

$\begin{array}{ccc}A& A\downarrow A& A\uparrow A\\ \mathrm{F}& \mathrm{T}& \mathrm{T}\\ \mathrm{T}& \mathrm{F}& \mathrm{F}\end{array}$

Dunque, $\mathrm{\neg }A\equiv A\downarrow A\equiv A\uparrow A$.

AND

$\begin{array}{ccccc}A& B& \mathrm{\neg }A& \mathrm{\neg }B& (\mathrm{\neg }A)\downarrow (\mathrm{\neg }B)\\ \mathrm{F}& \mathrm{F}& \mathrm{T}& \mathrm{T}& \mathrm{F}\\ \mathrm{F}& \mathrm{T}& \mathrm{T}& \mathrm{F}& \mathrm{F}\\ \mathrm{T}& \mathrm{F}& \mathrm{F}& \mathrm{T}& \mathrm{F}\\ \mathrm{T}& \mathrm{T}& \mathrm{F}& \mathrm{F}& \mathrm{T}\end{array}$$\begin{array}{cccc}A& B& A\uparrow B& \mathrm{\neg }(A\uparrow B)\\ \mathrm{F}& \mathrm{F}& \mathrm{T}& \mathrm{F}\\ \mathrm{F}& \mathrm{T}& \mathrm{T}& \mathrm{F}\\ \mathrm{T}& \mathrm{F}& \mathrm{T}& \mathrm{F}\\ \mathrm{T}& \mathrm{T}& \mathrm{F}& \mathrm{T}\end{array}$

Dunque:

$A\wedge B\equiv (\mathrm{\neg }A)\downarrow (\mathrm{\neg }B)\equiv (A\downarrow A)\downarrow (B\downarrow B)$;

$A\wedge B\equiv \mathrm{\neg }(A\uparrow B)\equiv (A\uparrow B)\uparrow (A\uparrow B)$.

OR

$\begin{array}{cccc}A& B& A\downarrow B& \mathrm{\neg }(A\downarrow B)\\ \mathrm{F}& \mathrm{F}& \mathrm{T}& \mathrm{F}\\ \mathrm{F}& \mathrm{T}& \mathrm{F}& \mathrm{T}\\ \mathrm{T}& \mathrm{F}& \mathrm{F}& \mathrm{T}\\ \mathrm{T}& \mathrm{T}& \mathrm{F}& \mathrm{T}\end{array}$$\begin{array}{ccccc}A& B& \mathrm{\neg }A& \mathrm{\neg }B& (\mathrm{\neg }A)\uparrow (\mathrm{\neg }B)\\ \mathrm{F}& \mathrm{F}& \mathrm{T}& \mathrm{T}& \mathrm{F}\\ \mathrm{F}& \mathrm{T}& \mathrm{T}& \mathrm{F}& \mathrm{T}\\ \mathrm{T}& \mathrm{F}& \mathrm{F}& \mathrm{T}& \mathrm{T}\\ \mathrm{T}& \mathrm{T}& \mathrm{F}& \mathrm{F}& \mathrm{T}\end{array}$

Dunque:

$A\vee B\equiv \mathrm{\neg }(A\downarrow B)\equiv (A\downarrow B)\downarrow (A\downarrow B)$;

$A\vee B\equiv (\mathrm{\neg }A)\uparrow (\mathrm{\neg }B)\equiv (A\uparrow A)\uparrow (B\uparrow B)$.

Avendo dimostrato che i connettivi $\mathrm{\neg },\wedge ,\vee$ possono essere definiti attraverso formule che contengono solo NOR o solo NAND, possiamo ora ridurre la dimostrazione della completezza di NOR e NAND alla completezza dell'insieme $\{\mathrm{\neg },\wedge ,\vee \}$.

Dimostrazione della completezza di $\{\mathrm{\neg },\wedge ,\vee \}$

In base alla definizione di insieme funzionalmente completo, si deve dimostrare che, per ogni funzione booleana $f:{ℬ}^n\mapsto ℬ$, esiste una formula proposizionale $P$, costruita mediante i connettivi dell'insieme $\{\mathrm{\neg },\wedge ,\vee \}$, tale che $f\equiv f_P$.

Per ogni assegnazione booleana ${𝒱}_i$ tale che $I_{{𝒱}_i}(P)=\mathrm{T}$, con $i=0,\mathrm{...},n$, siano:

• $A_{i,j}$, per ogni $j=0,\mathrm{...},m$, i simboli proposizionali tali che ${𝒱}_i(A_{i,j})=\mathrm{T}$;

• $B_{i,k}$, per ogni $k=0,\mathrm{...},p$, i simboli proposizionali tali che ${𝒱}_i(B_{i,k})=\mathrm{F}$.

$P$ è soddisfatta da una qualsiasi delle assegnazioni booleane ${𝒱}_i$; dunque, per rendere vera $P$, basta verificare se effettivamente le è stata assegnata una delle ${𝒱}_i$. Per fare ciò, per ogni ${𝒱}_i$ si controlla se tutti i simboli proposizionali $A_{i,j}$ sono effettivamente veri, e se tutti i simboli proposizionali $B_{i,k}$ sono effettivamente falsi, negandoli. Formalmente, ciò è tradotto in una disgiunzione di congiunzioni che rappresenta il processo appena descritto, detta forma normale disgiunta.

Estendiamo $\wedge$ e $\vee$ al caso più generale di $n$ argomenti, definendo i connettivi $\bigvee$ e $\bigwedge$:

• $\underset{i}{\overset{N}{\bigvee }}{P}_i=P_0\vee \mathrm{...}\vee P_N$;

• $\underset{i}{\overset{N}{\bigwedge }}{P}_i=P_0\wedge \mathrm{...}\wedge P_N$.

Possiamo ora esprimere $P$ in forma normale disgiunta come:

$P=\underset{i=0}{\overset{n}{\bigvee }}(\underset{j=0}{\overset{m}{\bigwedge }}{A}_{i,j}\wedge \underset{k=0}{\overset{p}{\bigwedge }}(\mathrm{\neg }{B}_{i,k}))$.

Quindi, abbiamo dimostrato che effettivamente $P$ esiste, dunque la tesi è dimostrata: $\{\mathrm{\neg },\wedge ,\vee \}$ è funzionalmente completo. Da ciò deriva che anche i connettivi NOR e NAND e, di conseguenza, anche gli insiemi $\{\mathrm{\neg },\wedge \}$ e $\{\mathrm{\neg },\vee \}$ sono funzionalmente completi.Template:Avanzamento