3.1 Logica[1YS]

[23H]Nelle prossime sezioni daremo alcune definizioni; queste sono semplificate, ma sufficienti per affrontare gli esercizi. I lettori interessati a un approfondimento possono consultare un libro di logica quale ad esempio [ 13 ] .

Proposizioni

Una proposizione può dipendere da alcune variabili. Esempi:

• “la persona x di mestiere fa il panettiere”,

• “il numero x è maggiore di 9”.

Scriveremo

per dire che \(P(x)\) è il simbolo che riassume la proposizione scritta a destra.

Logica proposizionale

 foo = 3 ;
 bar = 7;
 pippo = foo + bar;

sarà anch’essa una “formula ben formata”.

Per comodità, in questa Sezione, aggiungiamo al linguaggio anche le costanti \(V\) e \(F\) che sono rispettivamente sempre vere e sempre false, in ogni valutazione.  ⁵ Nella costruzione delle formule ben formate vengono trattate come le variabili. Notate che non abbiamo introdotto il connettivo di uguaglianza “\(=\)”. Quando tutte le variabili possono assumere solo i valori vero/falso, l’uguaglianza \(a=b\) può essere interpretata come \(a\iff b\). In contesti più generali (come nel caso della teoria degli insiemi) invece “l’uguaglianza” necessita di una precisa definizione.

E9

[1VY] Completate la seguente tabella di verità

P	Q	¬ P	\(P ∧ Q\)	\(P ∨ Q\)	\(P ⇒ Q\)	\(P⇐ Q\)	\(P ⇔ Q\)
V	V
V	F
F	V
F	F

Soluzione nascosta: [UNACCESSIBLE UUID ’1VZ’]

E9

[00K] Dite quali formule sono ben formate, e aggiungete le parentesi per evidenziare l’ordine di precedenza.

\begin{eqnarray*} a \land \neg b \land c \land d\\ \neg a \lor b \land c \Rightarrow d\\ a \Rightarrow \neg b \land c \lor d \\ a \land b \lor c \Leftrightarrow \neg c \Rightarrow d\\ a \lor b \neg c \lor d \end{eqnarray*}

Soluzione nascosta: [UNACCESSIBLE UUID ’00M’]

E9

[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.  ⁶

\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}

[UNACCESSIBLE UUID ’00P’]

indi usate l’esercizio 6 per trasformarla in un diagramma di Venn con tre insiemi. Soluzione nascosta: [UNACCESSIBLE UUID ’22D’] [2G8]Mostrate che il connettivo \(\Rightarrow \) di implicazione non è né commutativo né associativo. ⁸ Soluzione nascosta: [UNACCESSIBLE UUID ’2G9’]

Logica del primo ordine

Nella logica del primo ordine si aggiungono i connettivi \(∀\), che si legge “per ogni” e \(∃\), che si legge “esiste”. Dobbiamo dunque allargare la famiglia delle formule ben formate.

Notate che, in molti esempi, si suppone che le variabili quantificate siano elementi di un “insieme”.

Un esempio di proposizione logica potrebbe essere: “\(n\) è un numero pari”. Possiamo usare le proposizioni logiche come atomi nella costruzione delle formule ben formate.

E27

[00V]Siano \(X,Y\) insiemi. Siano \(𝜙,𝜓\) proposizioni logiche; \(x,a\) sono variabili libere in \(𝜙\), e \(y,b\) sono libere in \(𝜓\). Assumiamo inoltre che \(a,b\) possano essere solo vere o false, mentre \(x∈ X, y∈ Y\). Considerate le seguenti formule. Quali sono ben formate? Quali variabili sono libere in esse?

\begin{eqnarray*} b ∧ (∀ x,𝜙) \\ (∃ y, 𝜓) ∨ (∀ x,𝜙)\\ ∀ x,∀ b, \bigl(𝜙∧ (𝜓∨ b)\bigr) \\ a ∨ (∀ x,∀ a, 𝜙) \\ (∃ x, 𝜓) ∧ (∀ x,𝜙) \end{eqnarray*}

Soluzione nascosta: [UNACCESSIBLE UUID ’00W’]

E27

[00X]Consideriamo una proposizione \(P(u,ℓ)\) dipendente da due variabili libere \(u\) (che prende valori nell’insieme delle persone), e \(ℓ\) (nell’insieme dei lavori), e che è così formulata: ‘La persona \(u\) sa fare il lavoro \(ℓ\)‘.

Esprimete in Italiano le seguenti formule

\begin{align*} ∃ u∃ ℓ P(u,ℓ)~ ~ , ∀ u ∃ ℓ P(u,ℓ)~ ~ , ∃ ℓ ∀ u P(u,ℓ)~ ~ , \\ ∀ ℓ ∃ u P(u,ℓ)~ ~ , ∃ u ∀ ℓ P(u,ℓ)~ ~ , ∀ u ∀ ℓ P(u,ℓ)~ ~ . \end{align*}

Soluzione nascosta: [UNACCESSIBLE UUID ’00Y’]

E27

[00Z](Svolto il 2022-10-11) Quali implicazioni vi sono fra le precedenti formule?

Soluzione nascosta: [UNACCESSIBLE UUID ’010’]

E27

[011]Si verifichi che

\[ \Big((∀ x,\, 𝜑(x))∧ (∀ y,\, 𝜓(y))\Big) \iff \Big(∀ x\, (𝜑(x) ∧ 𝜓(x)) \Big) \]

[UNACCESSIBLE UUID ’012’]

però

laddove le versioni “estese” sono formule ben formate.

Usando questa scrittura estesa dimostrate che le due proposizioni

sono equivalenti, nel senso che da una è possibile dimostrare l’altra (e viceversa). Nella dimostrazione usate solo le tautologie (elencate in 3) e in particolare l’equivalenza della formula “\(P⇒ Q\)” con “\((¬ P)∨ Q\)”  ⁹  , e infine l’equivalenza fra “\(¬ ∃ x, Q\)” e “\(∀ x, ¬ Q\)”  ¹⁰ . 

Sostituendo poi \(P(x)\) con \(¬ P(x)\) e usando la tautologia della doppia negazione si ottiene infine che

sono equivalenti.

Soluzione nascosta: [UNACCESSIBLE UUID ’017’] [013] Dato \(A\) un insieme, e \(P(x)\) una proposizione dipendente da una variabile libera \(x\), usa scrivere

quando vi è uno e un solo elemento \(x\) di \(A\) per cui \(P(x)\) è vera. Definite questa notazione con una formula ben formata. (Notate che avrete bisogno di usare il connettivo di uguaglianza, perché dovete poter esprimere l’idea di “unico”, che necessita di un metodo per poter dire quando due oggetti sono distinguibili e quando non lo sono).

Soluzione nascosta: [UNACCESSIBLE UUID ’015’]