EDB — 00N

view in whole PDF view in whole HTML

Vista

Italiano

E10

[00N] Una formula ben formata nella logica proposizionale è una tautologia se per ogni valutazione la formula è sempre vera. Supponiamo che \(A,B,C\) siano formule ben formate. Mostrate che le seguenti proprietà dei connettivi sono tautologie.  1

\begin{eqnarray} {A⇒ A} & & \text{legge dell'identità} \nonumber \\ { ¬ (¬ A)⇔ A} & & \text{legge della doppia negazione} \nonumber \\ {A∨ A⇔ A}~ ~ ,~ ~ {A∧ A⇔ A} & & \text{leggi di idempotenza} \nonumber \\ {(A⇒ B) ⇔ (¬ B⇒ ¬ A)} & & \text{legge di contrapposizione,} \nonumber \\ & & \text{o della contronominale\footnotemark } \label{eqn:legge_ contrapposizione} \\ {(A⇒ B) ⇔ (¬ A∨ B)} ⇔ (¬ (A∧ ¬ B)) & & \text{equivalenza di implicazione,} \nonumber \\ & & \text{congiunzione e disgiunzione} \label{eq_ and_ or_ not_ 3r23n} \\ {A∧ B⇔ ¬ (¬ A∨ ¬ B)} & & \text{prima legge di De Morgan} \label{deMorgan_ 1} \\ {A∨ B⇔ ¬ (¬ A∧ ¬ B)} & & \text{seconda legge di De Morgan} \label{deMorgan_ 2} \\ {A∧ (B∨ C) ⇔ (A∧ B) ∨ (A∧ C)} & & \text{proprietà distributiva della congiunzione} \nonumber \\ & & \text{rispetto alla disgiunzione} \label{distrib_ and_ or} \\ {A∨ (B∧ C) ⇔ (A∨ B) ∧ (A∨ C)} & & \text{proprietà distributiva della disgiunzione } \nonumber \\ & & \text{rispetto alla congiunzione} \label{distrib_ or_ and} \\ {A∧ B⇔ B∧ A} & & \text{proprietà commutativa di } { ∧ } \nonumber \\ { A∨ B⇔ B∨ A} & & \text{proprietà commutativa di } { ∨ } \nonumber \\ { A∧ (B∧ C)⇔ (A∧ B)∧ C} & & \text{proprietà associativa di }{ ∧ } \nonumber \\ { A∨ (B∨ C)⇔ (A∨ B)∨ C} & & \text{proprietà associativa di} { ∨ } \label{assoc_ or} \end{eqnarray}

Queste due ultime proprietà permettono di omettere le parentesi in sequenze di congiunzioni oppure di disgiunzioni.

Le proprietà ??,??,?? dicono che potremmo fondare tutta la logica sui soli connettivi \(¬\) e \(∧\), (o su \(¬,∨ \)).

Altre tautologie importanti, spesso usate nel ragionamento logico.

\begin{eqnarray} {A∨ ¬ A} & & \text{{legge del terzo escluso}} \nonumber \\ {¬ (A∧ ¬ A)} & & \text{legge di non contraddizione} \nonumber \\ {(A∧ (A⇒ B)) ⇒ B} & & \text{modus ponens} \label{modus_ ponens} \\ { (¬ B∧ (A⇒ B))⇒ ¬ A} & & \text{modus tollens} \label{modus_ tollens} \\ {¬ A ⇒ (A⇒ B)} & & \text{negazione dell'antecedente } \nonumber \\ {B ⇒ (A⇒ B)} & & \text{affermazione del conseguente } \nonumber \\ {(A ⇒ (B⇒ C)) ⇒ ((A∧ B) ⇒ C)} & & \text{esportazione } \nonumber \\ {((A⇒ B) ∧ (A⇒ C)) ⇒ (A⇒ (B∧ C))} & & \text{dimostrazione per parti} \nonumber \\ {((A⇒ C) ∧ (B⇒ C)) ⇒ ((A∨ B) ⇒ C)} & & \text{dimostrazione per casi} \nonumber \\ {((A⇒ B) ∧ (B⇒ C)) ⇒ (A⇒ C)} & & \parbox{\RightWidth }{sillogismo ipotetico, o transitività dell'implicazione} \nonumber \\ {(A∨ (A∧ B)) ⇔} { A∧ (A∨ B) ⇔ } & & \nonumber \\ {(A∨ F)⇔ (A∧ V) ⇔ A} & & \text{leggi di assorbimento} \nonumber \\ {{F ⇒ B}} & & \parbox{\RightWidth }{prima legge di Pseudo Scoto, o \em ex falso sequitur quodlibet } \nonumber \\ { A⇒ (¬ A⇒ B)} & & \text{seconda legge di Pseudo Scoto} \nonumber \\ {(¬ A⇒ F)⇔ A} & & \text{dimostrazione per assurdo} \nonumber \\ {(( A∧ ¬ B)⇒ F)⇔ (A⇒ B)} & & \parbox{\RightWidth }{dimostrazione per assurdo, con ipotesi e tesi} \nonumber \\ {(¬ A⇒ A)⇒ A} & & \text{consequentia mirabilis} \end{eqnarray}

[[00P]]

  1. Queste liste sono tratte dalla Sezione 1.3 in [ 14 ] , oppure [ 32 ] .
  2. La proposizione \((¬ B⇒ ¬ A)\) è detta "contronominale" della \((A⇒ B)\).
Scarica PDF
Bibliografia
Indice analitico
  • tautologia
  • formula, ben formata, valutazione
  • valutazione, di formula ben formata
  • contronominale
Stai gestendo il blob in: Multiple languages
Questo contenuto è disponibile in: Italiano Inglese