Wikibooks

Logica matematica/Calcolo delle proposizioni: differenze tra le versioni

Naviga nella cronologia in modo interattivo
← Differenza precedenteDifferenza successiva →
Contenuto cancellato Contenuto aggiunto
VisualeWikitesto
m Correggo sintassi in formula matematica secondo mw:Extension:Math/Roadmap
Riga 10:
=== Alfabeto ===
{{Definizione|Un ''alfabeto'' <math>\Sigma</math> è costituito da:
* i connettivi proposizionali <math>\neg</math> (unario) e <math>\andland, \orlor, \to, \leftrightarrow</math> (binari);
* le costanti proposizionali <math>\top, \bot</math> (per denotare il vero e il falso);
* un insieme non vuoto (finito o numerabile) di simboli proposizionali <math>\mathcal{P}=\{A,B,C,...\}</math>;
Riga 20:
# le costanti e i simboli proposizionali sono formule;
# se <math>A</math> è una formula, <math>(\neg A)</math> è una formula;
# se <math>\circ</math> è un connettivo binario (cioè <math>\circ \in \{\andland,\orlor,\to,\leftrightarrow\}</math>) e se <math>A</math> e <math>B</math> sono due formule, <math>(A \circ B)</math> è una formula.
Le costanti e i simboli proposizionali sono anche detti ''atomi'', le loro negazioni sono dette ''atomi negati''. Gli atomi e gli atomi negati sono anche detti ''letterali''. Gli atomi negati sono talvolta detti ''letterali negativi''. Una formula del linguaggio proposizionale è anche detta ''proposizione'' o ''enunciato proposizionale''.
 
Riga 29:
# <math>A</math> stessa è una sottoformula di <math>A</math>;
# se <math>A</math> è una formula del tipo <math>(\neg B)</math>, allora le sottoformule di <math>B</math> sono anche sottoformule di <math>A</math>; <math>\neg</math> è detto ''connettivo principale'' e <math>B</math> ''sottoformula immediata'' di <math>A</math>;
# se <math>A</math> è una formula del tipo <math>B\circ C</math>, dove <math>\circ</math> è un connettivo binario (cioè <math>\circ \in \{\orlor,\andland,\rightarrow,\leftrightarrow\}</math>), e <math>B</math> e <math>C</math> due formule, le sottoformule di <math>B</math> e <math>C</math> sono anche sottoformule di <math>A</math>; <math>\circ</math> è detto ''connettivo principale''; <math>B</math> e <math>C</math> ''sottoformule immediate'' di <math>A</math>.}}
Per evitare un uso eccessivo delle parentesi, introduciamo anche delle regole di precedenza tra i connettivi. Per le formule proposizionali, si usa la seguente convenzione: la massima precedenza a <math>\neg</math>, poi, nell'ordine, ai connettivi <math>\andland, \orlor, \to</math> e infine a <math>\leftrightarrow</math>. Questo significa che, in assenza di parentesi, una formula ben formata va parentesizzata privilegiando le sottoformule i cui connettivi principali hanno precedenza più alta. A parità di precedenza, cioè se siamo in presenza di più occorrenze dello stesso connettivo, si assume che esso associ a destra, cioè la parentesizzazione va eseguita a partire dall'ultima occorrenza a destra del connettivo.
 
==== Simboli proposizionali occorrenti in una formula ====
Riga 42:
* <math>simb(\bot)=\emptyset</math>;
* <math>simb(\neg A)=simb(A)</math>;
* <math>simb(A \circ B)=simb(A)\cup simb(B)</math>, dove <math>\circ \in \{\andland,\orlor,\to,\leftrightarrow\}</math>.}}
La funzione <math>simb</math> restituisce l'insieme dei simboli proposizionali che occorrono in una formula. Essa è definita in <math>\wp\mathcal{P}</math>, cioè nell'inseme dei sottoinsiemi di <math>\mathcal{P}</math>, dato che restituisce sempre un sottoinsieme di <math>\mathcal{P}</math>.
 
Riga 58:
Esempi di frasi ben formate:
 
# <math>((A \to B) \andland (C \to D)) \to ((A \andland C) \to (B \andland D))</math>
# <math>\neg A \to \neg \neg \neg A</math>
# <math>A \leftrightarrow B \orlor C</math>
 
mentre frasi invalide sono:
Riga 66:
# <math>A(B)</math>
# <math>\to A \to B</math>
# <math>A \to \andland B</math>
 
[[Logica matematica/Calcolo delle proposizioni/Connettivi|I vari connettivi]]
Riga 86:
# <math>{\displaystyle {\mathcal {B}}=\{\mathrm {T} ,\mathrm {F} \}} </math>
# <math>\mathcal{T}=\{\mathrm {T}\}</math>;
# <math>\mathcal{Op}=\{\mathcal{Op}_\neg, \mathcal{Op}_\andland, \mathcal{Op}_\orlor, \mathcal{Op}_\to, \mathcal{Op}_\leftrightarrow\}</math>, uno per ognuno dei connettivi del linguaggio <math>\{\neg,\andland,\orlor,\rightarrow,\leftrightarrow\}</math>, con:
#* <math>\mathcal{Op}_\neg : \mathcal{B} \mapsto \mathcal{B} </math>;
#* <math>\mathcal{Op}_\circ : \mathcal{B} \times \mathcal{B} \mapsto \mathcal{B} </math>, <math>\circ \in \{\andland,\orlor,\to,\leftrightarrow\}</math>.}}
 
==== Negazione ====
Riga 111:
==== Congiunzione ====
{{Definizione|
<math>\begin{array}{|c|c|c|} A & B & A \andland B \\
\hline \mathrm{F} & \mathrm{F} & \mathrm{F} \\
\mathrm{F} & \mathrm{T} & \mathrm{F} \\
Riga 119:
</math>
 
Il connettivo di ''congiunzione'' <math>\andland</math> viene definito in modo che <math>A \andland B</math> è vero sse sia <math>A
</math> che <math>B
</math> (i due ''congiunti'') sono veri, quindi <math>\mathcal{Op}_\andland = min </math>.
}}
 
==== Disgiunzione ====
{{Definizione|
<math>\begin{array}{|c|c|c|} A & B & A \orlor B \\
\hline \mathrm{F} & \mathrm{F} & \mathrm{F} \\
\mathrm{F} & \mathrm{T} & \mathrm{T} \\
Riga 134:
</math>
 
Il connettivo di ''disgiunzione'' <math>\orlor</math> viene definito in modo che <math>A \orlor B</math> è vero sse <math>A
</math> oppure <math>B
</math> (uno dei due ''disgiunti'') sono veri, quindi <math>\mathcal{Op}_\orlor = max </math>. Si noti che, con questa definizione, <math>\orlor</math> è la disgiunzione inclusiva, cioè corrisponde al "vel" latino e non all'"aut".
}}
 
Riga 197:
* <math>I_\mathcal{V}(A \circ B)=
\mathcal{Op}_\circ(I_\mathcal{V}(A),I_\mathcal{V}(B))</math>.
dove <math>\circ \in \{\andland,\orlor,\to,\leftrightarrow\}</math>. Data un'assegnazione booleana <math>\mathcal{V}</math>, l'esistenza e l'unicità dell'estensione <math>I_\mathcal{V}</math> sono garantite dal [[teorema di ricorsione]].
}}
 
Riga 217:
 
* (''Passo Induttivo'') Sia <math>A=(\neg B)</math>. Abbiamo per <math>I_\mathcal{V_1}</math> e <math>I_\mathcal{V_2}</math> che <math>I_\mathcal{V_1}(\neg B)=\mathcal{Op}_\neg(I_\mathcal{V_1}(B))</math> e <math>I_\mathcal{V_2}(\neg B)=
\mathcal{Op}_\neg(I_\mathcal{V_2}(B))</math> e dunque, poiché per ipotesi induttiva <math>I_\mathcal{V_1}(B)=I_\mathcal{V_2}(B)</math>, segue che <math>I_\mathcal{V_1}(A)=I_\mathcal{V_2}(A)</math>. Analogamente, sia <math>A=B \circ C</math> con <math>\circ \in \{\andland,\orlor,\to,\leftrightarrow\}</math>; abbiamo <math>I_\mathcal{V_1}(B \circ C)=
\mathcal{Op}_\circ
(I_\mathcal{V_1}(B),I_\mathcal{V_1}(C))</math> e <math>I_\mathcal{V_2}(B \circ C)=
Riga 328:
Diamo qui di seguito una lista di formule tautologicamente equivalenti. L'equivalenza può essere facilmente verificata tramite tavole di verità.
{|
|<math>A \andland A </math>
|<math>\equiv </math>
|<math>A</math>
|idempotenza della congiunzione
|-
|<math>A \orlor A </math>
|<math>\equiv </math>
|<math>A</math>
|idempotenza della disgiunzione
|-
|<math>A \andland (B \andland C) </math>
|<math>\equiv </math>
|<math>(A \andland B) \andland C</math>
| associatività della congiunzione
|-
|<math>A \orlor (B \orlor C) </math>
|<math>\equiv </math>
|<math>(A \orlor B) \orlor C</math>
| associatività della disgiunzione
|-
Riga 353:
|associatività della doppia implicazione
|-
|<math>A \andland B </math>
|<math>\equiv </math>
|<math>B \andland A </math>
|commutatività della congiunzione
|-
|<math>A \orlor B </math>
|<math>\equiv </math>
|<math>B \orlor A </math>
|commutatività della disgiunzione
|-
Riga 368:
|commutatività della doppia implicazione
|-
|<math>A \andland (B \orlor C) </math>
|<math>\equiv </math>
|<math>(A \andland B) \orlor (A \andland C)</math>
| distributività della congiunzione sulla disgiunzione
|-
|<math>A \orlor (B \andland C) </math>
|<math>\equiv </math>
|<math>(A \orlor B) \andland (A \orlor C)</math>
| distributività della disgiunzione sulla congiunzione
|-
|<math>A \andland (A \orlor B) </math>
|<math>\equiv </math>
|<math>A</math>
|assorbimento della congiunzione sulla disgiunzione
|-
|<math>A \orlor (A \andland B) </math>
|<math>\equiv </math>
|<math>A</math>
|assorbimento della disgiunzione sulla congiunzione
|-
|<math>A \andland \top </math>
|<math>\equiv </math>
|<math>A</math>
| neutralità del vero nella congiunzione
|-
|<math>A \orlor \top </math>
|<math>\equiv </math>
|<math>\top</math>
| assorbimento del vero nella disgiunzione
|-
|<math>A \orlor \bot </math>
|<math>\equiv </math>
|<math>A</math>
|neutralità del falso nella disgiunzione
|-
|<math>A \andland \bot </math>
|<math>\equiv </math>
|<math>\bot </math>
Riga 413:
| doppia negazione
|-
|<math>\neg(A \andland B) </math>
|<math>\equiv </math>
|<math>\neg A \orlor \neg B</math>
| legge di De Morgan per la congiunzione
|-
|<math>\neg(A \orlor B) </math>
|<math>\equiv </math>
|<math>\neg A \andland \neg B</math>
| legge di De Morgan per la disgiunzione
|-
|<math>A \orlor \neg A </math>
|<math>\equiv </math>
|<math>\top</math>
|terzo escluso
|-
|<math>A \andland \neg A </math>
|<math>\equiv </math>
|<math>\bot</math>
Riga 440:
|<math>A \to B </math>
|<math>\equiv </math>
|<math>\neg A \orlor B </math>
| trasformazione dell'implicazione in disgiunzione
|-
Riga 448:
[[Logica matematica/Calcolo delle proposizioni/Esercizi su algebra delle proposizioni|Esercizi ed esempi]]
 
Relativamente alla legge del terzo escluso, il fatto che <math>A \orlor \neg A </math> sia sempre vero sembra del tutto intuitivo. In effetti, questa è una caratteristica della logica classica; in altre logiche, per esempio nella logica intuizionista, questo fatto non vale.
 
Intuitivamente ci si aspetta che, se una proposizione <math>A</math> è logicamente equivalente a una proposizione <math>B</math>, sostituendo <math>A</math> al posto di <math>B</math> in una formula <math>C</math>, il valore di verità di <math>C</math> non cambi.
Riga 479:
Dunque <math>I_\mathcal{V}(F[X/p])=I_\mathcal{V}(F[Y/p])</math>.
 
Analogamente, sia <math>F[p]=A[p] \circ B[p]</math>, con <math>\circ \in \{\andland,\orlor,\to,\leftrightarrow\}</math>. Osserviamo che, per definizione di valutazione booleana:
 
<math>I_\mathcal{V}(F[X/p])=\mathcal{Op}_\circ(I_\mathcal{V}(A[X/p]),I_\mathcal{V}(B[X/p]))</math>.
Riga 664:
 
== Completezza di insiemi di connettivi ==
I connettivi definiscono delle funzioni da <math>\mathcal{B}</math> (nel caso del connettivo unario <math>\neg</math>), oppure <math>\mathcal{B} \times \mathcal{B}</math> (nel caso dei connettivi binari) in <math>\mathcal{B}</math>. Ciascuna di queste funzioni, dette ''funzioni booleane'', è definita attraverso la relativa tavola dei valori di verità, oppure, equivalentemente, attraverso le funzioni <math>\mathcal{Op}_\neg</math> e <math>\mathcal{Op}_\circ</math>, con <math>\circ \in \{\andland,\orlor,\to,\leftrightarrow\}</math>.
 
Più in generale, ogni formula proposizionale <math>A</math> contenente simboli proposizionali distinti <math>A_1,...,A_n</math> definisce una funzione booleana da <math>\mathcal{B}^n</math> in <math>\mathcal{B}</math>.
Riga 684:
|<math>A \to B </math>
|<math>\equiv </math>
|<math>\neg A \orlor B</math>
|-
|<math>A \orlor B </math>
|<math>\equiv </math>
|<math>\neg A \to B</math>
|-
|<math>A \orlor B </math>
|<math>\equiv </math>
|<math>\neg(\neg A \andland \neg B)</math>
|-
|<math>A \andland B </math>
|<math>\equiv </math>
|<math>\neg(\neg A \orlor \neg B)</math>
|-
|<math>A \andland B </math>
|<math>\equiv </math>
|<math>(((A \to \bot) \to \bot) \to (B \to \bot)) \to \bot </math>
Riga 708:
|<math>\bot </math>
|<math>\equiv </math>
|<math>A \andland \neg A </math>
|-
|<math>A \leftrightarrow B </math>
|<math>\equiv </math>
|<math>(A \to B) \andland (B \to A) </math>
|}
Si noti che la costante proposizionale <math>\bot </math> (così come la costante proposizionale <math>\top </math>) può essere considerata come un connettivo <math>0</math>-ario.
Riga 726:
In particolare, un insieme di connettivi logici è completo se mediante i suoi connettivi si può esprimere qualunque altro connettivo.
 
È facile [[Logica matematica/Calcolo delle proposizioni/Dimostrazione di completezza di insiemi di connettivi|verificare]] che l'insieme dei connettivi <math>\{\neg,\andland,\orlor\}</math> è completo, così come lo sono <math>\{\neg,\andland\}</math> e anche <math>\{\neg,\orlor\}</math>.
 
Questo ci porta a concludere che nella trattazione della logica potremmo ridurci a considerare due soli connettivi. Si può in effetti anche dimostrare che un solo connettivo binario può bastare per definire tutti gli altri; in particolare, un connettivo a scelta tra il "nand" o il "nor" costituisce un insieme completo. Si può anche dimostrare che nand e nor sono gli unici due connettivi binari completi.
Estratto da "https://it.wikibooks.org/wiki/Logica_matematica/Calcolo_delle_proposizioni"