Wikibooks

Logica matematica/Calcolo delle proposizioni/Dimostrazione di completezza di insiemi di connettivi: differenze tra le versioni

Naviga nella cronologia in modo interattivo
← Differenza precedenteDifferenza successiva →
Contenuto cancellato Contenuto aggiunto
VisualeWikitesto
Nessun oggetto della modifica
m Correggo sintassi in formula matematica secondo mw:Extension:Math/Roadmap
Riga 1:
Ci occuperemo qui di dimostrare che i connettivi NOR e NAND, così come gli insiemi <math>\{\neg,\andland\}</math>, <math>\{\neg,\orlor\}</math> e <math>\{\neg,\andland,\orlor\}</math> sono funzionalmente completi.
 
== Definizione dei connettivi NOR e NAND ==
Riga 30:
 
=== Dimostrazione della completezza di NOR e NAND ===
Per provare la completezza di NOR e NAND, dimostriamo innanzitutto che i connettivi <math>\neg,\andland,\orlor</math> possono essere definiti attraverso formule che contengono solo connettivi NOR o solo NAND:
 
==== NOT ====
Riga 56:
Dunque:
 
<math>A \andland B \equiv (\neg A) \downarrow (\neg B) \equiv (A \downarrow A) \downarrow (B \downarrow B)</math>;
 
<math>A \andland B \equiv \neg(A \uparrow B) \equiv (A \uparrow B) \uparrow (A \uparrow B)</math>.
 
==== OR ====
Riga 75:
Dunque:
 
<math>A \orlor B \equiv \neg(A \downarrow B) \equiv (A \downarrow B) \downarrow (A \downarrow B)</math>;
 
<math>A \orlor B \equiv (\neg A) \uparrow (\neg B) \equiv (A \uparrow A) \uparrow (B \uparrow B)</math>.
 
Avendo dimostrato che i connettivi <math>\neg,\andland,\orlor</math> 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 <math>\{\neg,\andland,\orlor\}</math>.
 
=== Dimostrazione della completezza di <math>\{\neg,\andland,\orlor\}</math> ===
In base alla definizione di insieme funzionalmente completo, si deve dimostrare che, per ogni funzione booleana <math>f: \mathcal{B}^n \mapsto \mathcal{B}</math>, esiste una formula proposizionale <math>P</math>, costruita mediante i connettivi dell'insieme <math>\{\neg,\andland,\orlor\}</math>, tale che <math>f \equiv f_P</math>.
 
Supponiamo che <math>P</math> esista. Per ogni assegnazione booleana <math>\mathcal{V}_i</math> tale che <math>I_{\mathcal{V}_i}(P)=\mathrm{T}</math>, con <math>i=0,...,n</math>, siano:
Riga 90:
<math>P</math> è soddisfatta da una qualsiasi delle assegnazioni booleane <math>\mathcal{V}_i</math>; dunque, per rendere vera <math>P</math>, basta verificare se effettivamente le è stata assegnata una delle <math>\mathcal{V}_i</math>. Per fare ciò, per ogni <math>\mathcal{V}_i</math> si controlla se tutti i simboli proposizionali <math>A_{i,j}</math> sono effettivamente veri, e se tutti i simboli proposizionali <math>B_{i,k}</math> sono effettivamente falsi, negandoli. Formalmente, ciò è tradotto in una disgiunzione di congiunzioni che esegue il processo appena descritto, detta ''forma normale disgiunta''.
 
Estendiamo <math>\andland</math> e <math>\orlor</math> al caso più generale di <math>n</math> argomenti, definendo i connettivi <math>\bigvee</math> e <math>\bigwedge</math>:
 
* <math>\bigvee_i^N P_i =
\begin{cases}
\bot, & \text{se }i>N \\
P_i \orlor \bigvee_{k=i+1}^N P_k, & \text{altrimenti}
\end{cases}</math>;
 
Riga 101:
\begin{cases}
\top, & \text{se }i>N \\
P_i \andland \bigwedge_{k=i+1}^N P_k, & \text{altrimenti}
\end{cases}</math>.
 
Riga 107:
 
<math>P = \bigvee_{i=0}^n \left(
\bigwedge_{j=0}^m A_{i,j} \andland
\bigwedge_{k=0}^p (\neg B_{i,k})
\right)</math>.
 
Quindi, abbiamo dimostrato che effettivamente <math>P</math> esiste, dunque la tesi è dimostrata: <math>\{\neg,\andland,\orlor\}</math> è funzionalmente completo. Da ciò deriva che anche i connettivi NOR e NAND e, di conseguenza, anche gli insiemi <math>\{\neg,\andland\}</math> e <math>\{\neg,\orlor\}</math> sono funzionalmente completi.{{Avanzamento|100%}}
[[Categoria:Logica matematica|Calcolo delle proposizioni]]
Estratto da "https://it.wikibooks.org/wiki/Logica_matematica/Calcolo_delle_proposizioni/Dimostrazione_di_completezza_di_insiemi_di_connettivi"