Vai al contenuto

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

Wikibooks, manuali e libri di testo liberi.
Indice del libro

Ci occuperemo qui di dimostrare che i connettivi NOR e NAND, così come gli insiemi , e sono funzionalmente completi.

Definizione dei connettivi NOR e NAND

[modifica | modifica sorgente]

Definizione

Il connettivo NOR (), negazione del connettivo OR, restituisce sse entrambi gli operandi sono , mentre restituisce in tutti gli altri casi.

Definizione

Il connettivo NAND (), negazione del connettivo AND, restituisce sse entrambi gli operandi sono , mentre restituisce in tutti gli altri casi.

Dimostrazione

[modifica | modifica sorgente]

Dimostrazione della completezza di NOR e NAND

[modifica | modifica sorgente]

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

Dunque, .

Dunque:

;

.

Dunque:

;

.

Avendo dimostrato che i connettivi 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 .

Dimostrazione della completezza di

[modifica | modifica sorgente]

In base alla definizione di insieme funzionalmente completo, si deve dimostrare che, per ogni funzione booleana , esiste una formula proposizionale , costruita mediante i connettivi dell'insieme , tale che .

Per ogni assegnazione booleana tale che , con , siano:

  • , per ogni , i simboli proposizionali tali che ;
  • , per ogni , i simboli proposizionali tali che .

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

Estendiamo e al caso più generale di argomenti, definendo i connettivi e :

  • ;
  • .

Possiamo ora esprimere in forma normale disgiunta come:

.

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