Invito alla Indovinelli InvitoallaLogicaMatematica ...liceoalberti.it/~deleo/indovinelli.pdf ·...

Invito allaLogica

Matematicaattraverso gliIndovinelli

R. De [email protected] Invito alla Logica Matematica

attraverso gli Indovinelli

R. De [email protected]

Liceo Scientifico “L.B. Alberti”

9 Febbraio 2010

1 / 40

Invito allaLogica

Outline

2 / 40

Invito allaLogica

La Matematica come “gioco da tavolo”

Quali sono gli elementi fondamentali di un gioco da tavolo?

I Pezzi

3 / 40

Invito allaLogica

I Pezzi

Il Setup

3 / 40

Invito allaLogica

I Pezzi

Il Setup

Le Regole

3 / 40

Invito allaLogica

I Pezzi

Il Setup

Le Regole

La Matematica funziona allo stesso modo!

3 / 40

Invito allaLogica

I Pezzi

Il Setup

Le Regole

Definizioni/Assiomi di esistenza

3 / 40

Invito allaLogica

I Pezzi

Il Setup

Le Regole

Postulati

3 / 40

Invito allaLogica

I Pezzi

Il Setup

Le Regole

Postulati Logica

3 / 40

Invito allaLogica

Durante una partita i giocatori utilizzano le regole muovere ipezzi sulla scacchiera ottenendo così nuove posizioni a partireda quella di partenza (setup).

Allo stesso modo in Matematica si utilizza la Logica (cioè ilragionamento) per ottenere nuovi risultati a partire daipostulati. Le “nuove posizioni sulla scacchiera” in Matematicasi chiamano Teoremi.

4 / 40

Invito allaLogica

Durante una partita i giocatori utilizzano le regole muovere ipezzi sulla scacchiera ottenendo così nuove posizioni a partireda quella di partenza (setup).

Allo stesso modo in Matematica si utilizza la Logica (cioè ilragionamento) per ottenere nuovi risultati a partire daipostulati. Le “nuove posizioni sulla scacchiera” in Matematicasi chiamano Teoremi.

4 / 40

Invito allaLogica

Brevissima Storia della Logica

• Aristotele (∼ 350AC) è il primo a formalizzare le leggi delragionamento con i sillogismi.Esempio:

1 Tutti i gatti sono mammiferi;2 Tutti i mammiferi sono a sangue caldo;3 Perciò tutti i gatti sono a sangue caldo.

• Nel Medioevo lo studio della logica continua nelladirezione indicata da Aristotele.

• Nel Seicento G.W. Leibniz (1646− 1716) introduce laLogica Simbolica mostrando che la logica può esseretrattata con strumenti algebrici così come si fa con inumeri.

5 / 40

Invito allaLogica

5 / 40

Invito allaLogica

5 / 40

Invito allaLogica

5 / 40

Invito allaLogica

5 / 40

Invito allaLogica

5 / 40

Invito allaLogica

• Nel Settecento L. Euler (1707− 1783) introduce un mododi rappresentare graficamente i sillogismi, poi sfociato neidiagrammi di Venn della teoria degli insiemi.

CTutti gli A sono B.

Tutti i B sono C.Tutti gli A sono C.

• Nell’Ottocento G. Boole (1815− 1864) chiarifica icollegamenti tra logica e teoria degli insiemi. Ad esempio:A∪ B = {x|(x ∈ A) ∨ (x ∈ B)}A∩ B = {x|(x ∈ A) ∧ (x ∈ B)}

6 / 40

Invito allaLogica

• Nel Settecento L. Euler (1707− 1783) introduce un mododi rappresentare graficamente i sillogismi, poi sfociato neidiagrammi di Venn della teoria degli insiemi.

CTutti gli A sono B.

Tutti i B sono C.Tutti gli A sono C.

• Nell’Ottocento G. Boole (1815− 1864) chiarifica icollegamenti tra logica e teoria degli insiemi. Ad esempio:A∪ B = {x|(x ∈ A) ∨ (x ∈ B)}A∩ B = {x|(x ∈ A) ∧ (x ∈ B)}

6 / 40

Invito allaLogica

• Giuseppe Peano (1858− 1932) pubblica il Formulario incui, tra le altre cose, introduce le notazioni che da allora inpoi saranno usate in logica e matematica. In particolaresono suoi i simboli ∩, ∪, ∃, ∈, 3, ∼ (negazione logica), pper indicare le proposizioni.

• Bertrand Russel (1872− 1970) pubblica i PrincipiaMathematica mettendo la logica proposizionale alla basedei fondamenti della matematica.

• Kurt Gödel (1906− 1978) dimostra il famoso teorema diincompletezza.

7 / 40

Invito allaLogica

7 / 40

Invito allaLogica

7 / 40

Invito allaLogica

La Logica Proposizionale

Come si procede in Fisica quando si studia un nuovo fenomeno,il primo passo è quello di determinarne il modello più semplicepossibile. In Logica il ’livello zero’ è quello in cui gli ’atomi’sono le proposizioni, cioè frasi di senso compiuto delle quali siapossibile determinare il valore di verità (vero/falso).Da ora in poi indicheremo le proposizioni con lettere latineminuscole (p,q, · · · ).Ogni ragionamento consiste nella combinazione di diverseproposizioni in modo da dar luogo alla fine alla combinazionedesiderata; se il ragionamente è corretto dalla verità degliassunti discende necessariamente la verità delle conclusioni.La logica proposizionale dunque studia il modo in cui varieproposizioni possono combinarsi mantenendo il loro valore diverità.

8 / 40

Invito allaLogica

La Logica Proposizionale

Come si procede in Fisica quando si studia un nuovo fenomeno,il primo passo è quello di determinarne il modello più semplicepossibile. In Logica il ’livello zero’ è quello in cui gli ’atomi’sono le proposizioni, cioè frasi di senso compiuto delle quali siapossibile determinare il valore di verità (vero/falso).Da ora in poi indicheremo le proposizioni con lettere latineminuscole (p,q, · · · ).Ogni ragionamento consiste nella combinazione di diverseproposizioni in modo da dar luogo alla fine alla combinazionedesiderata; se il ragionamente è corretto dalla verità degliassunti discende necessariamente la verità delle conclusioni.La logica proposizionale dunque studia il modo in cui varieproposizioni possono combinarsi mantenendo il loro valore diverità.

8 / 40

Invito allaLogica

I connettivi Logici

Esaminando il modo in cui ragioniamo sono stati individuatistoricamente cinque operatori fondamentali: quattro connettivibinari (congiunzione, disgiunzione, implicazione ecoimplicazione) ed uno unario (negazione).

9 / 40

Invito allaLogica

La Negazione

Data una proposizione p si puó generare una nuovaproposizione “non p”, che risulta vera quando p è falsa eviceversa.

In logica si indica con

Tavola di verità:

p ∼ pV FF V

10 / 40

Invito allaLogica

La Negazione

Tavola di verità:

p ∼ pV FF V

10 / 40

Invito allaLogica

La Negazione

Tavola di verità:

p ∼ pV FF V

10 / 40

Invito allaLogica

Il connettivo ’o’

Date p e q possiamo affermare “o p o q”, vera quando almenouna delle due proposizioni è vera (disgiunzione inclusiva).

In logica si indica con p∨ qTavola di verità:

p q p∨ qV V VV F VF V VF F F

L’operatore ∨ corrisponde in insiemistica a ∪:A∪ B = {x|(x ∈ A) ∨ (x ∈ B)}.

Esempio: sarò promosso o bocciato? si!

11 / 40

Invito allaLogica

11 / 40

Invito allaLogica

11 / 40

Invito allaLogica

11 / 40

Invito allaLogica

11 / 40

Invito allaLogica

Il connettivo ’xor’

Date p e q si puó affermare “p o q ma non entrambe”, che èvera quando solo una delle due proposizioni componenti è vera

(disgiunzione esclusiva).In logica si indica con p Y q

Tavola di verità:

p q p Y qV V FV F VF V VF F F

Esempio: o la borsa o la vita!

12 / 40

Invito allaLogica

Tavola di verità:

12 / 40

Invito allaLogica

Tavola di verità:

12 / 40

Invito allaLogica

Tavola di verità:

12 / 40

Invito allaLogica

Il connettivo ’e’

Date p e q si puó affermare “sia p che q”, vera quandoentrambe sono vere.

In logica si indica con p∧ qTavola di verità:

p q p∧ qV V VV F FF V FF F F

∧ corrisponde in insiemistica a ∩:A∩ B = {x|(x ∈ A) ∧ (x ∈ B)}.

13 / 40

Invito allaLogica

13 / 40

Invito allaLogica

13 / 40

Invito allaLogica

13 / 40

Invito allaLogica

Il connettivo ’implica’

Questo connettivo cerca di rappresentare il concetto diimplicazione, ad esempio “x = 2⇒ x2 = 4”. Si dovrebbe

interpretare come “non è possibile che sia vero q quando p èfalso”.

In logica si indica con p→ qTavola di verità:

p q p→ qV V VV F FF V VF F V

→ corrisponde in insiemistica a ⊆: A ⊆ B sse x ∈ A → x ∈ B.

14 / 40

Invito allaLogica

14 / 40

Invito allaLogica

14 / 40

Invito allaLogica

14 / 40

Invito allaLogica

Il connettivo ’equivale a’

Questo connettivo cerca di rappresentare il concetto diimplicazione nei due sensi, cioè sia p→ q che q→ p; ad es.

“x = 2,−2⇔ x2 = 4”.In logica si indica con p↔ q

Tavola di verità:

p q p↔ qV V VV F FF V FF F V

L’operatore ↔ corrisponde in insiemistica a =:A = B se e solo se x ∈ A ↔ x ∈ B.

15 / 40

Invito allaLogica

Tavola di verità:

15 / 40

Invito allaLogica

Tavola di verità:

15 / 40

Invito allaLogica

Tavola di verità:

15 / 40

Invito allaLogica

Traduzione dal linguaggio naturale

Il linguaggio naturale è molto complesso, per tradurre una frasenella logica proposizionale bisogna semplificarla al massimo.Il primo passo è di “riscrivere” la frase eliminando tutte le“ellissi” che si fanno nel linguaggio comune. Ad es. “Pula è unpaese ed una parola di quattro lettere” si deve rifrasare come“Pula è un paese e Pula è una parola di quattro lettere”.Poi bisogna identificare le proposizioni “atomiche” ed indicarlecon una lettera.Infine bisogna capire quale connettivo corrisponde ai connettividella lingua comune.

16 / 40

Invito allaLogica

16 / 40

Invito allaLogica

16 / 40

Invito allaLogica

16 / 40

Invito allaLogica

Esempi

Mario è uno studente ed un lavoratoreMario, che è uno studente, è anche un lavoratoreMario non solo è uno studente ma è anche un lavoratoresono del tutto equivalenti e vanno tradotte usando il connettivo∧.

17 / 40

Invito allaLogica

Esempi

Una frase del tipo “hanno la laurea in filosofia o matematica”rivolta ad un insieme di concorrenti per un posto di ricercatorein logica sicuramente va tradotta con ∨ perché qualcunopotrebbe avere la laurea in entrambe, ma la frase “o si vince osi perde” dev’essere senz’altro tradotta con Y.

18 / 40

Invito allaLogica

Esempi

Frasi come “Sarete promossi se studierete” e “Sarete promossisolo se studierete” si traducono come p→ q e ∼ p→∼ q.In particolare la equivalenza logica p↔ q corrisponde a “Saretepromossi se e solo se studierete”.

19 / 40

Invito allaLogica

Tautologie e contraddizioni

Una tautologia è una proposizione che è sempre vera,indipendentemente dai valori di verità delle proposizioni che lacompongono.Una contraddizione è esattamente l’opposto di una tautologia,cioè rimane falsa qualunque siano i valori di verità delleproposizioni che la compongono.Esempi:

• p∨ ∼ p (Terzo escluso)

• ∼ (p∧ ∼ p) (Legge di non contraddizione)

• ∼ (∼ p)↔ p (Legge della doppia negazione)

• (p∧ ∼ p)→ q (Ex falso sequitur quodlibet)

• ((p↔ q)↔ r)↔ (p↔ (q↔ r))

20 / 40

Invito allaLogica

• ((p↔ q)↔ r)↔ (p↔ (q↔ r))

20 / 40

Invito allaLogica

• ((p↔ q)↔ r)↔ (p↔ (q↔ r))

20 / 40

Invito allaLogica

• ((p↔ q)↔ r)↔ (p↔ (q↔ r))

20 / 40

Invito allaLogica

• ((p↔ q)↔ r)↔ (p↔ (q↔ r))

20 / 40

Invito allaLogica

• ((p↔ q)↔ r)↔ (p↔ (q↔ r))

20 / 40

Invito allaLogica

• ((p↔ q)↔ r)↔ (p↔ (q↔ r))

20 / 40

Invito allaLogica

Il Sistema di deduzione naturale

1 Se p→ q e p→∼ q allora ∼ p (Introduzione dellanegazione)

2 Se ∼ (∼ p) allora p (Eliminazione della doppia negazione)3 Se p e q allora p∧ q (Introduzione della congiunzione)4 Se p∧ q allora sia p che q (Eliminazione della

congiunzione)5 Se p (o q) allora p∨ q (Introduzione della disgiunzione)6 Se p∨ q, p→ r e q→ r allora r (Elim. della disg.)7 Se p→ q e q→ p allora p↔ q (Introduzione di ↔)8 Se p↔ q allora sia p→ q che q→ p (Elim. di ↔)9 Se p e p→ q allora q (Eliminazione del condizionale)10 Se dall’assunzione di p riusciamo a dim. q allora p→ q

(Dim. cond. – intr. del condiz.)21 / 40

Invito allaLogica

Gli Indovinelli

22 / 40

Invito allaLogica

Chi è Matto?

23 / 40

Invito allaLogica

Il Bruco e la Lucertola

24 / 40

Invito allaLogica

Soluzione

Traduzione in Formule:b = “Il Bruco è savio”, l = “La Lucertola è savia”

b↔ (∼ b∧ ∼ l)Soluzione:

Eliminando l’equivalenza logica (8) otteniamob→ (∼ b∧ ∼ l)

Eliminando la congiunzione (3), b→∼ b.Dato che anche b→ b, usiamo (1) e deduciamo ∼ b,

cioé il Bruco è matto!Allora ∼ (∼ b∧ ∼ l)

cioè b∨ lMa dato che b è falsa allora l dev’esser vera,

cioè la Lucertola è savia!

25 / 40

Invito allaLogica

Soluzione

25 / 40

Invito allaLogica

Soluzione

25 / 40

Invito allaLogica

Soluzione

25 / 40

Invito allaLogica

Soluzione

25 / 40

Invito allaLogica

Soluzione

25 / 40

Invito allaLogica

Soluzione

25 / 40

Invito allaLogica

Soluzione

25 / 40

Invito allaLogica

La Cuoca e il Gatto

26 / 40

Invito allaLogica

Soluzione

Traduzione in Formule:c = “La Cuoca è savia”, g = “Il Gatto del Cheshire è savio”

c↔ (∼ c∨ ∼ g)Soluzione:

Ovviamente p↔ q equivale a ∼ p↔∼ q, per cui∼ c↔∼ (∼ c∨ ∼ g)↔ c∧ g

Esattamente come prima dunque succede che ∼ c→ c,cioè ∼ c dev’essere falsa!

Dunque la cuoca è savia e quindi è vero che ∼ c∨ ∼ gda cui necessariamente ∼ g, cioè il Gatto dev’essere matto!

27 / 40

Invito allaLogica

Soluzione

27 / 40

Invito allaLogica

Soluzione

27 / 40

Invito allaLogica

Soluzione

27 / 40

Invito allaLogica

Soluzione

27 / 40

Invito allaLogica

Soluzione

27 / 40

Invito allaLogica

Domestico-Pesce e Domestico-Rana

28 / 40

Invito allaLogica

Soluzione

Traduzione in Formule:p = “Il Dom.-Pesce è savio”, r = “Il Dom.-Rana è savio”

p↔ (p↔ r)

Soluzione:L’equivalenza logica è associativa:

(p↔ q)↔ r è equivalente a p↔ (q↔ r)

Dunque p↔ (p↔ r) equivale a (p↔ p)↔ rma p↔ p è una tautologia per cui r è vera,

cioè il Domestico-Rana è savio!

Del Domestico-Pesce non si puó concludere nulla.

29 / 40

Invito allaLogica

Soluzione

p↔ (p↔ r)

29 / 40

Invito allaLogica

Soluzione

p↔ (p↔ r)

29 / 40

Invito allaLogica

Soluzione

p↔ (p↔ r)

29 / 40

Invito allaLogica

Soluzione

p↔ (p↔ r)

29 / 40

Invito allaLogica

Soluzione

p↔ (p↔ r)

29 / 40

Invito allaLogica

Un indovinello delle Olimpiadi (Febbraio 2009)

30 / 40

Invito allaLogica

SoluzioneTraduzione in Formule:, x = “X dice la verità”

1 l↔ (m∧ p)2 m↔ (∼ l∧ ∼ n)3 n↔ (m↔∼ p)4 p↔ (l↔∼ n)

Soluzione:Da (3) e (4) troviamo che p↔ (l↔ (m↔ p))

Dunque p↔ ((l↔ m) ∧ p)e p↔ (p↔ (l↔ m))e (p↔ p)↔ (l↔ m)

Ma a sinistra c’è una tautologia, per cui l↔ mcioè Luca e Maria o mentono o dicono entrambi la verità!

Da (2) allora m↔ (∼ m∧ ∼ n) per cui ∼ m e quindi ∼ l!Da (1) e (2) quindi p e n. Quindi due mentono e due no.

31 / 40

Invito allaLogica

1 l↔ (m∧ p)2 m↔ (∼ l∧ ∼ n)3 n↔ (m↔∼ p)4 p↔ (l↔∼ n)

31 / 40

Invito allaLogica

1 l↔ (m∧ p)2 m↔ (∼ l∧ ∼ n)3 n↔ (m↔∼ p)4 p↔ (l↔∼ n)

31 / 40

Invito allaLogica

1 l↔ (m∧ p)2 m↔ (∼ l∧ ∼ n)3 n↔ (m↔∼ p)4 p↔ (l↔∼ n)

31 / 40

Invito allaLogica

1 l↔ (m∧ p)2 m↔ (∼ l∧ ∼ n)3 n↔ (m↔∼ p)4 p↔ (l↔∼ n)

31 / 40

Invito allaLogica

1 l↔ (m∧ p)2 m↔ (∼ l∧ ∼ n)3 n↔ (m↔∼ p)4 p↔ (l↔∼ n)

31 / 40

Invito allaLogica

1 l↔ (m∧ p)2 m↔ (∼ l∧ ∼ n)3 n↔ (m↔∼ p)4 p↔ (l↔∼ n)

31 / 40

Invito allaLogica

1 l↔ (m∧ p)2 m↔ (∼ l∧ ∼ n)3 n↔ (m↔∼ p)4 p↔ (l↔∼ n)

31 / 40

Invito allaLogica

1 l↔ (m∧ p)2 m↔ (∼ l∧ ∼ n)3 n↔ (m↔∼ p)4 p↔ (l↔∼ n)

31 / 40

Invito allaLogica

1 l↔ (m∧ p)2 m↔ (∼ l∧ ∼ n)3 n↔ (m↔∼ p)4 p↔ (l↔∼ n)

31 / 40

Invito allaLogica

Il Re e la Regina di Cuori

32 / 40

Invito allaLogica

Soluzione

Traduzione in Formule:k = “Il Re è savio”, q = “La Regina è savia”,

q↔ (k↔ (q↔ (k↔∼ q)))

Soluzione:Usiamo a ripetizione assoc. e comm. dell’equiv. logica:

q↔ (k↔∼ q) è equivalente a q↔ (∼ q↔ k)

e quindi a (q↔∼ q)↔ k

Dunque dire k↔ (q↔ (k↔∼ q))

è come dire k↔ ((q↔∼ q)↔ k)

o anche k↔ (k↔ (q↔∼ q))

33 / 40

Invito allaLogica

Soluzione

q↔ (k↔ (q↔ (k↔∼ q)))

33 / 40

Invito allaLogica

Soluzione

q↔ (k↔ (q↔ (k↔∼ q)))

33 / 40

Invito allaLogica

Soluzione

q↔ (k↔ (q↔ (k↔∼ q)))

33 / 40

Invito allaLogica

Soluzione

q↔ (k↔ (q↔ (k↔∼ q)))

33 / 40

Invito allaLogica

Soluzione

q↔ (k↔ (q↔ (k↔∼ q)))

33 / 40

Invito allaLogica

Soluzione

A sua volta k↔ (k↔ (q↔∼ q)) equivale a(k↔ k)↔ (q↔∼ q)

In conclusione quindi la formula inizialeq↔ (k↔ (q↔ (k↔∼ q)))

si puó riscrivere comeq↔ ((k↔ k)↔ (q↔∼ q))

Ma k↔ k è una tautologiamentre q↔∼ q è una contraddizione

Non sono equivalenti!

Dunque q è equivalente ad una proposizione falsae quindi ∼ q è vera, cioè la Regina è matta!

Del Re invece non si può dire nulla.

34 / 40

Invito allaLogica

Soluzione

34 / 40

Invito allaLogica

Soluzione

34 / 40

Invito allaLogica

Soluzione

34 / 40

Invito allaLogica

Soluzione

34 / 40

Invito allaLogica

Il Fante di Cuori

35 / 40

Invito allaLogica

Il Fante di Cuori

36 / 40

Invito allaLogica

Il Fante di Cuori

Traduzione in Formule:3↔∼ 1

36 / 40

Invito allaLogica

Il Fante di Cuori

4↔∼ (∼ 3∧ ∼ 2)

36 / 40

Invito allaLogica

Il Fante di Cuori

4↔∼ (∼ 3∧ ∼ 2)

5↔ (1↔ 4)

36 / 40

Invito allaLogica

Il Fante di Cuori

4↔∼ (∼ 3∧ ∼ 2)

5↔ (1↔ 4)

6↔ (1∧ 2)

36 / 40

Invito allaLogica

Il Fante di Cuori

4↔∼ (∼ 3∧ ∼ 2)

5↔ (1↔ 4)

6↔ (1∧ 2)

7↔∼ 5

36 / 40

Invito allaLogica

Il Fante di Cuori

4↔∼ (∼ 3∧ ∼ 2)

5↔ (1↔ 4)

6↔ (1∧ 2)

7↔∼ 5

F↔∼ (∼ 6∧ ∼ 7)

36 / 40

Invito allaLogica

Soluzione

4↔∼ (∼ 3∧ ∼ 2)

5↔ (1↔ 4)

6↔ (1∧ 2)

7↔∼ 5

F↔∼ (∼ 6∧ ∼ 7)

37 / 40

Invito allaLogica

Soluzione

4↔∼ (∼ 3∧ ∼ 2)

5↔ (1↔ 4)

6↔ (1∧ 2)

7↔∼ 5

F↔∼ (∼ 6∧ ∼ 7)

4↔ (3∨ 2)

F↔ (6∨ 7)

37 / 40

Invito allaLogica

Soluzione

4↔∼ (∼ 3∧ ∼ 2)

5↔ (1↔ 4)

6↔ (1∧ 2)

7↔∼ 5

F↔∼ (∼ 6∧ ∼ 7)

4↔ (3∨ 2)

F↔ (6∨ 7)

Soluzione:F↔ (6∨ 7)

37 / 40

Invito allaLogica

Soluzione

4↔∼ (∼ 3∧ ∼ 2)

5↔ (1↔ 4)

6↔ (1∧ 2)

7↔∼ 5

F↔∼ (∼ 6∧ ∼ 7)

4↔ (3∨ 2)

F↔ (6∨ 7)

F↔ ((1∧ 2)∨ ∼ 5)

37 / 40

Invito allaLogica

Soluzione

4↔∼ (∼ 3∧ ∼ 2)

5↔ (1↔ 4)

6↔ (1∧ 2)

7↔∼ 5

F↔∼ (∼ 6∧ ∼ 7)

4↔ (3∨ 2)

F↔ (6∨ 7)

F↔ ((1∧ 2)∨ ∼ 5)

F↔ ((1∧ 2)∨ ∼ (1↔ 4))

37 / 40

Invito allaLogica

Soluzione

4↔∼ (∼ 3∧ ∼ 2)

5↔ (1↔ 4)

6↔ (1∧ 2)

7↔∼ 5

F↔∼ (∼ 6∧ ∼ 7)

4↔ (3∨ 2)

F↔ (6∨ 7)

F↔ ((1∧ 2)∨ ∼ 5)

F↔ ((1∧ 2)∨ ∼ (1↔ 4))

F↔ ((1∧ 2) ∨ (∼ 1↔ 4))

37 / 40

Invito allaLogica

Soluzione

4↔∼ (∼ 3∧ ∼ 2)

5↔ (1↔ 4)

6↔ (1∧ 2)

7↔∼ 5

F↔∼ (∼ 6∧ ∼ 7)

4↔ (3∨ 2)

F↔ (6∨ 7)

F↔ ((1∧ 2)∨ ∼ 5)

F↔ ((1∧ 2)∨ ∼ (1↔ 4))

F↔ ((1∧ 2) ∨ (∼ 1↔ 4))

F↔ ((1∧ 2) ∨ (∼ 1↔ (3∨ 2)))

37 / 40

Invito allaLogica

Soluzione

4↔∼ (∼ 3∧ ∼ 2)

5↔ (1↔ 4)

6↔ (1∧ 2)

7↔∼ 5

F↔∼ (∼ 6∧ ∼ 7)

4↔ (3∨ 2)

F↔ (6∨ 7)

F↔ ((1∧ 2)∨ ∼ 5)

F↔ ((1∧ 2)∨ ∼ (1↔ 4))

F↔ ((1∧ 2) ∨ (∼ 1↔ 4))

F↔ ((1∧ 2) ∨ (∼ 1↔ (3∨ 2)))

F↔ ((1∧ 2) ∨ (∼ 1↔ (∼ 1∨ 2)))

37 / 40

Invito allaLogica

Soluzione

4↔∼ (∼ 3∧ ∼ 2)

5↔ (1↔ 4)

6↔ (1∧ 2)

7↔∼ 5

F↔∼ (∼ 6∧ ∼ 7)

4↔ (3∨ 2)

F↔ (6∨ 7)

F↔ ((1∧ 2)∨ ∼ 5)

F↔ ((1∧ 2)∨ ∼ (1↔ 4))

F↔ ((1∧ 2) ∨ (∼ 1↔ 4))

F↔ ((1∧ 2) ∨ (∼ 1↔ (3∨ 2)))

F↔ ((1∧ 2) ∨ (∼ 1↔ (∼ 1∨ 2)))

Se ci pensate, p↔ (p∨ q) equivale a ∼ (∼ p∧ q).

37 / 40

Invito allaLogica

Soluzione

4↔∼ (∼ 3∧ ∼ 2)

5↔ (1↔ 4)

6↔ (1∧ 2)

7↔∼ 5

F↔∼ (∼ 6∧ ∼ 7)

4↔ (3∨ 2)

F↔ (6∨ 7)

F↔ ((1∧ 2)∨ ∼ 5)

F↔ ((1∧ 2)∨ ∼ (1↔ 4))

F↔ ((1∧ 2) ∨ (∼ 1↔ 4))

F↔ ((1∧ 2) ∨ (∼ 1↔ (3∨ 2)))

F↔ ((1∧ 2) ∨ (∼ 1↔ (∼ 1∨ 2)))

Se ci pensate, p↔ (p∨ q) equivale a ∼ (∼ p∧ q).

Dunque F↔ ((1∧ 2)∨ ∼ (1∧ 2))

cioé il Fante è savio indipendentemente da 1 e 2!

37 / 40

Invito allaLogica

Chi ha rubato le torte?

38 / 40

Invito allaLogica

Traduzione in Formule:X = “X dice la verità”x = “X ha rubato la torta”

38 / 40

Invito allaLogica

gri Y tar

38 / 40

Invito allaLogica

gri Y tarDuc↔∼ gri

38 / 40

Invito allaLogica

gri Y tarDuc↔∼ griCuo↔ α

38 / 40

Invito allaLogica

Gat↔ β

38 / 40

Invito allaLogica

Gat↔ β

Bru↔ γ

38 / 40

Invito allaLogica

Gat↔ β

Bru↔ γ

Lep↔ (Cuo∧Gat)

38 / 40

Invito allaLogica

Gat↔ β

Bru↔ γ

Lep↔ (Cuo∧Gat)Ghi↔ (Cuo∧ Bru)

38 / 40

Invito allaLogica

Gat↔ β

Bru↔ γ

Lep↔ (Cuo∧Gat)Ghi↔ (Cuo∧ Bru)Cap↔ (Gat∨ Bru)

38 / 40

Invito allaLogica

Gat↔ β

Bru↔ γ

Lep↔ (Cuo∧Gat)Ghi↔ (Cuo∧ Bru)Cap↔ (Gat∨ Bru)Luc↔ (Lep∨Ghi)

38 / 40

Invito allaLogica

Gat↔ β

Bru↔ γ

Lep↔ (Cuo∧Gat)Ghi↔ (Cuo∧ Bru)Cap↔ (Gat∨ Bru)Luc↔ (Lep∨Ghi)Fan↔ (Cuo∧ Cap)

38 / 40

Invito allaLogica

Gat↔ β

Bru↔ γ

Lep↔ (Cuo∧Gat)Ghi↔ (Cuo∧ Bru)Cap↔ (Gat∨ Bru)Luc↔ (Lep∨Ghi)Fan↔ (Cuo∧ Cap)Con↔ (Luc∧ ∼ Fan)

38 / 40

Invito allaLogica

Gat↔ β

Bru↔ γ

Lep↔ (Cuo∧Gat)Ghi↔ (Cuo∧ Bru)Cap↔ (Gat∨ Bru)Luc↔ (Lep∨Ghi)Fan↔ (Cuo∧ Cap)Con↔ (Luc∧ ∼ Fan)Con↔ Duc

38 / 40

Invito allaLogica

Soluzione

1. gri Y tar2. Duc↔∼ gri3. Cuo↔ α

4. Gat↔ β

5. Bru↔ γ

6. Lep↔ (Cuo∧Gat)7. Ghi↔ (Cuo∧ Bru)8. Cap↔ (Gat∨ Bru)9. Luc↔ (Lep∨Ghi)

10. Fan↔ (Cuo∧ Cap)11. Con↔ (Luc∧ ∼ Fan)12. Con↔ Duc

39 / 40

Invito allaLogica

Soluzione

4. Gat↔ β

5. Bru↔ γ

Soluzione:Basta capire se la Duchessa mente o no (2)

39 / 40

Invito allaLogica

Soluzione

4. Gat↔ β

5. Bru↔ γ

Soluzione:Basta capire se la Duchessa mente o no (2)Da (11) e (12), Duc↔ (Luc∧ ∼ Fan)

39 / 40

Invito allaLogica

Soluzione

4. Gat↔ β

5. Bru↔ γ

e, a cascata,Duc↔ ((Lep∨Ghi)∧ ∼ (Cuo∧ Cap))

39 / 40

Invito allaLogica

Soluzione

4. Gat↔ β

5. Bru↔ γ

Duc↔ (((Cuo∧Gat) ∨ (Cuo∧ Bru))∧ ∼ (Cuo∧ (Gat∨ Bru)))

39 / 40

Invito allaLogica

Soluzione

4. Gat↔ β

5. Bru↔ γ

Duc↔ {[(α ∧ β) ∨ (α ∧ γ)]∧ ∼ [α ∧ (β ∨ γ)]}

39 / 40

Invito allaLogica

Soluzione

4. Gat↔ β

5. Bru↔ γ

Duc↔ {[(α ∧ β) ∨ (α ∧ γ)]∧ ∼ [α ∧ (β ∨ γ)]}Ma (α ∧ β) ∨ (α ∧ γ)

39 / 40

Invito allaLogica

Soluzione

4. Gat↔ β

5. Bru↔ γ

Duc↔ {[(α ∧ β) ∨ (α ∧ γ)]∧ ∼ [α ∧ (β ∨ γ)]}Ma (α ∧ β) ∨ (α ∧ γ)equivale a α ∧ (β ∨ γ)

39 / 40

Invito allaLogica

Soluzione

4. Gat↔ β

5. Bru↔ γ

Per cuiDuc↔ {[α ∧ (β ∨ γ)]∧ ∼ [α ∧ (β ∨ γ)]}

39 / 40

Invito allaLogica

Soluzione

4. Gat↔ β

5. Bru↔ γ

Quella a destra è una tautologia!

39 / 40

Invito allaLogica

Soluzione

4. Gat↔ β

5. Bru↔ γ

Quella a destra è una tautologia!Dunque la Duchessa dice la verità

39 / 40

Invito allaLogica

Soluzione

4. Gat↔ β

5. Bru↔ γ

Quella a destra è una tautologia!Dunque la Duchessa dice la verità

e il Grifone è innocente.

39 / 40

Invito allaLogica

Letture Consigliate

http://utenti.quipo.it/base5/idxcollez.htm#logicahttp://www2.polito.it/didattica/polymath/htmlS/info/CapitoloPrimo/CapitoloPrimo.htm

E. Bencivenga: Il mio primo libro di LogicaD. Hofstadter: Gödel, Escher, Bach.R. Smullyan: tutti quelli che potete trovare!M. Gardner: idem!

40 / 40

Invito alla Indovinelli InvitoallaLogicaMatematica ...liceoalberti.it/~deleo/indovinelli.pdf ·...

Documents

Transcript of Invito alla Indovinelli InvitoallaLogicaMatematica ...liceoalberti.it/~deleo/indovinelli.pdf ·...