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

Ci occuperemo qui di dimostrare che i connettivi NOR e NAND, così come gli insiemi $\{\neg ,\land \}$, $\{\neg ,\lor \}$ e $\{\neg ,\land ,\lor \}$ sono funzionalmente completi.

Definizione dei connettivi NOR e NAND

NOR

Definizione

Il connettivo NOR ($\downarrow$), negazione del connettivo OR, restituisce $\mathrm {T}$ sse entrambi gli operandi sono $\mathrm {F}$, mentre restituisce $\mathrm {F}$ in tutti gli altri casi.

${\begin{array}{|c|c|c|}A&B&A\downarrow B\\\hline \mathrm {F} &\mathrm {F} &\mathrm {T} \\\mathrm {F} &\mathrm {T} &\mathrm {F} \\\mathrm {T} &\mathrm {F} &\mathrm {F} \\\mathrm {T} &\mathrm {T} &\mathrm {F} \\\end{array}}$

NAND

Definizione

Il connettivo NAND ($\uparrow$), negazione del connettivo AND, restituisce $\mathrm {F}$ sse entrambi gli operandi sono $\mathrm {T}$, mentre restituisce $\mathrm {T}$ in tutti gli altri casi.

${\begin{array}{|c|c|c|}A&B&A\uparrow B\\\hline \mathrm {F} &\mathrm {F} &\mathrm {T} \\\mathrm {F} &\mathrm {T} &\mathrm {T} \\\mathrm {T} &\mathrm {F} &\mathrm {T} \\\mathrm {T} &\mathrm {T} &\mathrm {F} \\\end{array}}$

Dimostrazione

Dimostrazione della completezza di NOR e NAND

Per provare la completezza di NOR e NAND, dimostriamo innanzitutto che i connettivi $\neg ,\land ,\lor$ possono essere definiti attraverso formule che contengono solo connettivi NOR o solo NAND:

NOT

${\begin{array}{|c|c|c|}A&A\downarrow A&A\uparrow A\\\hline \mathrm {F} &\mathrm {T} &\mathrm {T} \\\mathrm {T} &\mathrm {F} &\mathrm {F} \end{array}}$

Dunque, $\neg A\equiv A\downarrow A\equiv A\uparrow A$.

AND

${\begin{array}{|c|c|c|c|}A&B&\neg A&\neg B&(\neg A)\downarrow (\neg B)\\\hline \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}{|c|c|c|c|}A&B&A\uparrow B&\neg (A\uparrow B)\\\hline \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\land B\equiv (\neg A)\downarrow (\neg B)\equiv (A\downarrow A)\downarrow (B\downarrow B)$;

$A\land B\equiv \neg (A\uparrow B)\equiv (A\uparrow B)\uparrow (A\uparrow B)$.

OR

${\begin{array}{|c|c|c|c|}A&B&A\downarrow B&\neg (A\downarrow B)\\\hline \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}{|c|c|c|c|}A&B&\neg A&\neg B&(\neg A)\uparrow (\neg B)\\\hline \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\lor B\equiv \neg (A\downarrow B)\equiv (A\downarrow B)\downarrow (A\downarrow B)$;

$A\lor B\equiv (\neg A)\uparrow (\neg B)\equiv (A\uparrow A)\uparrow (B\uparrow B)$.

Avendo dimostrato che i connettivi $\neg ,\land ,\lor$ 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 $\{\neg ,\land ,\lor \}$.

Dimostrazione della completezza di $\{\neg ,\land ,\lor \}$

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

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

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

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

$P$ è soddisfatta da una qualsiasi delle assegnazioni booleane ${\mathcal {V}}_{i}$; dunque, per rendere vera $P$, basta verificare se effettivamente le è stata assegnata una delle ${\mathcal {V}}_{i}$. Per fare ciò, per ogni ${\mathcal {V}}_{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 $\land$ e $\lor$ al caso più generale di $n$ argomenti, definendo i connettivi $\bigvee$ e $\bigwedge$:

• $\bigvee _{i}^{N}P_{i}=P_{0}\lor ...\lor P_{N}$;

• $\bigwedge _{i}^{N}P_{i}=P_{0}\land ...\land P_{N}$.

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

$P=\bigvee _{i=0}^{n}\left(\bigwedge _{j=0}^{m}A_{i,j}\land \bigwedge _{k=0}^{p}(\neg B_{i,k})\right)$.

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