Le Pierangiolate n.1Le Pierangiolate n.1

Dipartimento di Ingegneria della Informazione e Scienze Matematiche

La vera storiaLa vera storia

del barbiere di Russell del barbiere di Russell

introduzione agli enigmi logici

Luca Chiantini presenta

Giochi di Archimede - 2006

PROBLEMA : Gli abitanti di un'isola si dividono in due categorie: quelli sempre sinceri e quelli che mentono sempre.

progetto olimpiadi

UMI - Unione Matematica ItalianaSNS - Scuola Normale Superiore

Fra tre abitanti avviene la seguente conversazione:Andrea dice "Barbara è sincera".Ciro dice "Andrea è bugiardo".Barbara dice "Andrea e Ciro sono sinceri".

Chi dei tre è sincero?

PROBLEMA : Gli abitanti di un'isola si dividono in due categorie: quelli sempre sinceri e quelli che mentono sempre.

Fra tre abitanti avviene la seguente conversazione:Andrea dice "Barbara è sincera".Ciro dice "Andrea è bugiardo".Barbara dice "Andrea e Ciro sono sinceri".

Chi dei tre è sincero?

BarbaraAndrea Ciro

sincero bugiardo sincero bugiardo sincero bugiardo

01 01 01

BarbaraAndrea Ciro

000

100

010

110

001

101

011

11

Andrea dice "Barbara è sincera".

Ciro dice "Andrea è bugiardo".

Barbara dice "Andrea e Ciro sono sinceri".

A = B

A = C

1

Matrici Logiche

PROBLEMA :

Ad una festa in maschera, durante il Carnevale di Venezia, partecipano i quattro famosi personaggi:Arlecchino, Brighella, Colombina e Pantalone.

Come è vestita Colombina?

Ciascuno è travestito da uno degli altri personaggi.

E non ci sono due travestimenti uguali.

Brighella non è vestito da Arlecchino.

Pantalone non porta i pantaloni.

rlecchino

righella

olombina

antalone

A

B

P

C

A

B

P

C

il personaggio il personaggio

è vestito da

A B C P

A

B

C

P

1 = è vestito da

0 = non è vestito da

Ciascuno è travestito da uno degli altri personaggi.

0

0

0

0E non ci sono due travestimenti uguali.

Brighella non è vestito da Arlecchino.

Pantalone non porta i pantaloni

0

0

1

10

0 0 1

00

1 0

Colombina è vestita da Arlecchino.

A B C P

A

B

C

P

0

0

0

0

0

0

1

10

0 0 1

00

1 0 matrice di verità

AB

PC

AB

PC

"è vestito da"

f:

I GATTI

Ci sono tre gatti, Foffo, Gigio e Laila, che appartengono a Aldo, Berto e Carlo (ma non nell'ordine). Uno dei gatti ha 4 anni, uno ne ha 2 e uno ne ha 1.

La gatta di Aldo ha più di tre anni.

Foffo, che non è il gatto più giovane, non è di Berto.

Trovare i padroni e l'età di ciascun gatto.

A

B

C

padroni

F

GL

1

2

4

gatti età

F G L

A

B

C

12

4

F G L

A

B

C

12

4

relazione ternaria database ternario

matrice tridimensionale (TENSORE) database

F G L

A

B

C

12

4

Joseph Sylvester

La gatta di Aldo ha più di tre anni.

Tensore Logico

Foffo, che non è il gatto più giovane, non è di Berto.

http://www.studiogiochi.com/puzzle/griglie-logiche.html

Al negozio “Piccoli Passi” in questo momento ci sono 5 mamme in fila alla cassa che stanno acquistando scarpine. Sono tutti diversi i nomi delle mamme, dei bambini, i colori delle scarpine e i loro numeri.1. Elide non ha preso le scarpine nere.ecc.....

mammebimbi

colori

numeri

TENSORI di dimensione 4

Arthur Clarke

2001: Odissea nello spazio

...

Come era ovvio, come era necessario il rapporto dei lati del monolito, la sequenza 1 : 4 : 9!

ESEMPIO: database sul DNA

... A C C T A G T G T T A G C A ...

100 posizioni di DNA

tensori di DIMENSIONE 1004 x 4 x 4 x 4 x 4 ........

E quale ingenuità avere immaginato che la sequenza terminasse a quel punto, con appena 3 dimensioni!

...

relazione fran insiemi

database n-ario:ogni record ha n campi

tensore di dimensione n

ESEMPIO:database sul Palio

Palio Contrada Cavallo Fantino

Luglio 11 Bruco Lampante Gingillo

Agosto 11 Lupa Moedi Vittorio

...

Tensore di dimensione 4

http://www.studiogiochi.com/puzzle/griglie-logiche.html

TENSORE 5 x 5 x 5 x 5 SPARSO

54 caselle = 625

2 opzioni per ogni casella

2625 possibilità

2625 = 2 x 10208 circa

PROBLEMA : Gli abitanti di un'isola si dividono in due categorie: quelli

sempre sinceri e quelli che mentono sempre.

Fra tre abitanti avviene la seguente conversazione:Andrea dice "Barbara è sincera".Ciro dice "Andrea è bugiardo".Barbara dice "Andrea e Ciro sono sinceri".

Chi dei tre è sincero?

AUTOREFERENZIALITA'

AUTOREFERENZIALITA'

Questa frase è falsa

AUTOREFERENZIALITA'

La frase qui sotto è falsa

La frase qui sopra è falsa

La frase qui sotto è falsa

La frase qui sopra è falsa Ciro dice

"Andrea è bugiardo"

A

C

in entrambi i casi A = C

un'applicazione della autoreferenzialità

In una Università italiana, alcuni professori, esasperati dai continui tagli al finanziamento, decidono di scioperare.

Come forma di protesta, gli scioperanti sarebbero andati in aula a raccontare solo ENUNCIATI FALSI.

Naturalmente, in quella Università, accanto ad ottimi professori bravi, c'erano anche diversi professori

"asini" .....

Pertanto, in quella Università, si sono formati quattro tipi di docenti

i professori bravi e non-scioperanti (BN)Costoro, ben sapendo quali enunciati sono veri, ligi al loro compito, proclamano in aula soloENUNCIATI VERI

i professori bravi e scioperanti (BS)Costoro, pur sapendo quali enunciati sono veri, per protesta, proclamano in aula soloENUNCIATI FALSI

i professori asini e non-scioperanti (AN)Costoro vorrebbero raccontare enunciati veri, ma siccome sono asini, finiscono per proclamareENUNCIATI FALSI

i professori asini e scioperanti (AS)Costoro vorrebbero raccontare enunciati falsi, ma siccome sono asini, si confondono e proclamanoENUNCIATI VERI

La protesta giunge alle orecchie di qualche impiegato ministerialeche avverte subito i suoi superiori.

Si riuniscono immediatamente al Ministero

e decidono che

- tutti i professori dovrebbero essere bravi e non scioperare.

- tuttavia, è ammissibile la presenza di professori asini, purchè non si mettano a fare proteste.

- per evitare di apparire troppo autoritari, si può accettare la presenza di qualche professore che sciopera, purchè sia bravo.

- ma la presenza di professori che, oltre ad essere asini, protestano anche, è assolutamente INTOLLERABILE!

Detto questo, la Ministra prende carta e penna,poi accende il computer e manda una e-mailal Rettore:

"Smascherare immediatamente i professori non bravi, che stanno facendo sciopero!"

Il Rettore, molto preoccupato, manda subito un questionario con una domanda, a tutti i docenti, per operare lo smascheramento.

Quale domanda deve porre, nel questionario,il povero Rettore della piccola Università,per scoprire i professori asini che scioperanoed evitare il commissariamento?

e

e

enunciati veri

enunciati falsi

come distinguere dentro le due coppie?

SOLUZIONE

AUTOREFERENZIALITA'

problema

SOLUZIONE:Diresti, in aula, che sei un professore bravo che non sciopera?

i professori bravi e non-scioperanti (BN)Se lo dico loro, la frase è vera. Siccome raccontano enunciati veri, la risposta è SI'.

i professori asini e non-scioperanti (AN)Se lo dico loro, la frase è falsa. Siccome raccontano enunciati falsi, la risposta è SI'.

i professori asini e scioperanti (AS)Se lo dico loro, la frase è falsa. Siccome raccontano enunciati veri, la risposta è NO.

i professori bravi e scioperanti (BS)Se lo dico loro, la frase è falsa. Siccome raccontano enunciati falsi, la risposta è SI'.

Ma l'autoreferenzialitàpuò produrre anche veri

paradossi!Bertrand Russell

X = insieme di tutti gli insiemi

X X xxx ...R = {insieme che contiene gli insiemi

che non contengono se stessi}

R R ?

"... il BARBIERE è coluiche fa la barba a chi non se la fa da sè ..." Bertrand Russell

R = {insieme che contiene gli insiemiche non contengono se stessi}

R R ?

insieme --------> tizio

contenere ----> fare la barba

chi fa la barba al barbiere?

La vera storiaLa vera storia

del barbiere di Russell del barbiere di Russell

In un posto lontano lontano c'era una volta un ridente paesino che si chiamava RUSSELL.

Nel paese c'era un solo barbiere,che era anche molto bravo.

Il barbiere faceva la barba a tutti quelliche non si facevano la barba da sè.

I paesani, gente istruita, sapevano che si trattava di un paradosso.Ma se ne infischiavano allegramente,e tutto anda va bene.

finchè un giorno ...

... arrivarono nel paesino i tremendi AGENTI DEL FISCO.

Questi si aggirarono per tutte

le case, cercando di stanare gli

evasori

Alla fine, andarono dal barbieree gli dissero: "Lei è in contravvenzione."

"Perchè?" chiese il barbiere "Io ho versato un tallero di tasse per ogni barba che ho fatto!"

"Ah, ah!" dissero gli agenti del fisco "è qui che si sbaglia. Lei non ha versato il tallero per tutte le volte che si è fatto la barba da sè!

"Poche storie" tagliarono corto gli agenti "lei è un barbiere, un professionista. E come tale, è tenuto a pagare un tallero di tasse per ogni volta che fa la barba a qualcuno."

"Ma chi si fa la barba da sè, non deve pagare tasse" replicò il barbiere.

La gente partecipava appassionatamente al dibattito. Si erano anche formati due partiti ( quello pro-tasse e quello pro-barbiere) con liti continue e furibonde fra le due fazioni.

Alla fine, decisero di interpellare il grande giurista

PASQUALE CICCILLO

La faccenda si trascinò in tribunale.

La soluzione è semplice

sentenziò il grande Ciccillo.

se il barbiere si fa la barba in negozio, con tutta la sua attrezzatura, allora se la fa da professionista, e deve pagare le tasse.

ma se il barbiere si fa la barba in casa, con una attrezzatura artigianale, allora se la fa da privato e non paga.

Tutti rimasero felici e contenti. E la pace tornò a regnarenel ridente paesino di Russell.

Spiegazione matematica

TIZIO

CAIO

SEMPRONIO

TITO

MACCIO

BARBIERE

BARBIERE

TIZIO

CAIO

SEMPRONIO

TITO

MACCIO

1

1 1

1

1

0

0

0

0 0

RELAZIONE:fa la barba a ...

0 = falso

1 = vero

ogni colonna se ha 0 nella casella diagonale, allora ha 1 nella prima casella.E viceversa

?REGOLA:

TIZIO

CAIO

SEMPRONIO

TITO

MACCIO

BARB. CASA

BARBIERE

TIZIO

CAIO

SEMPRONIO

TITO

MACCIO

1

1 1

1

1

0

0

0

0 0

soluzione di Pasquale Ciccillo

sdoppiamento del concetto di "barbiere"

0BARB. NEGOZIO

1

BARB. CASA

0BARB. NEGOZIO

1

John F. Nashn. 1928

Logica temporale

Protagora

Evatlo

Protagora

Evatlo

Se vinco io, Evatlo mi deve pagare, in forza della sentenza.Se vince lui, mi deve pagare, perchè ha vinto la prima causa

Se vinco io, non devo pagare Protagora, in forza della sentenza.Se vince lui, non devo pagare, perchè non ho ancora vinto la prima causa

I giurati rimasero a lungo preplessi.

Alla fine decisero di chiedere consiglioal grande giurista PASQUALE CICCILLO

E' chiaro che, prima della sentenza,Evatlo non ha vinto alcuna causa,quindi ha ragione lui.

Dopo la sentenza, però, avrà vinto unacausa, e dovrà pagare Protagora.

Protagora Evatlo

ProtagoraProtagora Evatloprima della sentenza dopo la sentenza

Evatlo

Paradosso del cretese

Epimenide

Tutti i cretesi sono bugiardi

Tutti i cretesi sono bugiardi

vera falsa

anche Epimenide, essendo cretese, sarebbe bugiardo

un bugiardo avrebbe detto una cosa vera

contraddizione

non è vero che tuttii cretesi sono bugiardi

c'è almeno uncretese non bugiardo

ok

(ma non è Epimenide)

Tutti i cretesi sono bugiardi

c'è almeno uncretese non bugiiardo

vera falsa?

verafalsa ?

0 1

valore di verità

mucchio di fagioli

?

frasi indecidibili

fuzzy sets

probabilità ...

Questa frase èindecidibile

Kurt Godel

Lofti Zadeh

Son intrà in sto impegno senza pensarghe: m'ho volesto provar.

Ho fatto una gran fadiga!

Ho fatto anca dei mancamenti,ma spero che, per rason della stravaganza,

tutti sti siori me perdonerà.

Grazie

La vera storia del barbiere di RussellLa vera storia del barbiere di Russell