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

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

  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

Dimostrazione della completezza di NOR e NAND

modifica

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

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.