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

Logica matematica
Copertina Tutti i moduli · Sviluppo
* InsiemiLogica matematica/Insiemi
* Sistemi formaliLogica matematica/Sistemi formali
* Calcolo delle proposizioniLogica matematica/Calcolo delle proposizioni
** Il sistema di Frege-HilbertLogica matematica/Calcolo delle proposizioni/Sistema di Hilbert
** La deduzione naturaleLogica matematica/Calcolo delle proposizioni/La deduzione naturale
** Il calcolo dei sequenti
** I tableaux semanticiLogica matematica/Calcolo delle proposizioni/I tableaux semantici
** La risoluzioneLogica matematica/Calcolo delle proposizioni/La risoluzione
** Esercizi su tavole di veritàLogica matematica/Calcolo delle proposizioni/Esercizi su tavole di verità
* Calcolo dei predicatiLogica matematica/Calcolo dei predicati
* Teoria dei modelliLogica matematica/Teoria dei modelli
* Computabilità
* IncompletezzaLogica matematica/Incompletezza
** Teoremi di incompletezza di GödelLogica matematica/Incompletezza/Teoremi di incompletezza di Gödel
* Intermezzo: EuclideLogica matematica/Intermezzo Euclide
* Intermezzo: i paradossiLogica matematica/Intermezzo paradossi
* Risorse internetLogica matematica/Risorse internet
Modifica il sommario
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.