Appunti di (test di) logica
Luca Mari, [email protected] - maggio 2010
Questi Appunti sono stati redatti per un ciclo di quattro seminari tenuti nei mesi di febbraio e marzo 2009, e ripetuti nei
mesi di aprile e maggio 2010, per gli studenti del Liceo C.Rebora, di Rho, con l’obiettivo di presentare ai partecipanti,
alcune decine di studenti degli ultimi anni di scuola superiore, elementi di logica utili come strumenti per affrontare in
modo appropriato i “test di logica” tipicamente proposti nelle prove di ammissione ai corsi di laurea.
Sommario
0. Premessa......................................................................................................................................................................................1
1. Introduzione.................................................................................................................................................................................2
2. Cenni di (test di) logica proposizionale........................................................................................................................................4
3. Cenni di (test di) logica predicativa..............................................................................................................................................8
4. Cenni di (test di) logica “in senso lato”......................................................................................................................................10
0. Premessa
(dal sito: http://testammissione.ilsole24ore.com – enfatizzazioni mie)
Sui test in generale
I test sono generalmente composti da una sezione verbale, che misura la comprensione linguistica e
concettuale, e da una sezione matematica, che verifica la capacità di risolvere problemi che richiedano il
ragionamento logico-matematico e una conoscenza di base dell’algebra e della geometria. Il test, dunque,
sebbene prenda in esame quanto appreso nel corso dell’istruzione, soprattutto, secondaria, tenta di evitare di
porre quesiti che dipendano dalla conoscenza di argomenti specifici, per mettere invece l’accento sulla
capacità di utilizzare abilità acquisite per risolvere problemi nuovi.
Di fronte alla crescente diffusione dei test di selezione molti studenti chiedono se valga la pena di svolgere
una specifica preparazione. In questo senso una certa familiarità con i test è fondamentale: chi ha già avuto
esperienze di test, e sa quindi cosa aspettarsi, è più sicuro di sé rispetto a chi non ne ha avute. Per esempio, si
può essere avvantaggiati dalla familiarità con le schede di risposta e con il modo corretto di compilarle, dalla
capacità di esaminare attentamente tutte le risposte di un test a scelta multipla anziché scegliere la prima
soluzione che sembra corretta, dal sapere di non dovere perdere troppo tempo per le domande che non si
riescono a risolvere, dal capire se e quando vale la pena di rischiare una risposta casuale (se non vi sono
penalizzazioni per le risposte errate, vale la pena di tentare comunque a caso; se la risposta errata comporta
una penalizzazione è più opportuno cercare di ridurre le alternative eliminando le risposte che sembrano più
improbabili).
Sulla parte dei test relativa alla cultura generale e capacità logica
Per queste prove non esiste un programma specifico. I test mirano a saggiare il livello culturale degli
studenti oppure la loro capacità di comprendere e di interpretare un testo (comprensione verbale). I test di
capacità logica consistono prevalentemente in problemi la cui soluzione richiede facoltà di concentrazione,
di analisi e di sintesi; non si richiedono nozioni specifiche, ma di volta in volta nell’enunciato dei test
vengono forniti tutti gli elementi necessari per risolverli correttamente.
Le domande di capacità logica valutano:
1. la capacità di comprendere il significato preciso dei termini, di cogliere termini simili e analogie
etimologiche; di capire quale categoria mentale (causa-effetto, contrapposizione, identità, ...) stabilisce un
rapporto tra coppie di parole; di scegliere tra varie parole quelle che possono essere inserite opportunamente
in un discorso dato o di riconoscere quelle che non rispondono alla logica del discorso stesso;
2. la capacità di distinguere, tra le diverse interpretazioni di grafici, quelle ammissibili da quelle errate o
arbitrarie;
3. la capacità di ritenere le informazioni che si sono appena lette, di interpretarle, di trarre delle conclusioni
conseguenti e di scartare conclusioni errate, arbitrarie o non rigorosamente giustificate.
I test di capacità logica presentano domande di carattere molto diversificato sia nella lunghezza
1
dell’enunciato, sia nel contenuto. Alcuni contengono testi di attualità comparsi su quotidiani o su riviste di
ampia tiratura, altri di autori del passato o contemporanei che presentano riflessioni di carattere sociale o
morale, o passi significativi di recenti testi di narrativa. Tra questi quesiti possono comparire anche problemi
in cui si delinea una situazione puramente teorica, alla quale vengono proposte soluzioni da vagliare sulla
base dei dati forniti; è richiesta quindi molta attenzione alla definizione della situazione e alla distinzione tra
ciò che in essa è possibile, necessario o logicamente inammissibile. I quesiti di logica non richiedono
comunque una specifica preparazione culturale in definiti ambiti disciplinari.
1. Introduzione
Per superare un test occorre essere allenati a sufficienza, per gestire il (generalmente non tanto) tempo in
modo efficiente, applicando sia il ragionamento “in avanti” / forward chaining (l’unico in generale possibile
se la domanda non fosse a risposte chiuse) ma anche “all’indietro” / backward chaining (dato il fatto che le
risposte possibili sono pre-identificate, operare per esclusione, eliminando progressivamente i “distrattori”).
Di fronte a un problema, il primo passo da compiere generalmente consiste nell’individuarne la struttura,
separando “forma” da “contenuto”, con un processo di astrazione (nota che generalmente l’enfasi è al
contrario...) che porta a mantenere appunto solo la struttura del problema.
Per esempio:
PROBLEMA 1
Il beffardo mago Atlante ha rinchiuso in un castello fatato Angelica, l’intelligente principessa cinese.
Angelica è confinata in una stanza con cinque porte contrassegnate UNO, DUE, TRE, QUATTRO, CINQUE
davanti a ciascuna delle quali sta un aiutante di Atlante, con il contrassegno della porta ricamato sul cappello.
Lei sa che quattro di essi mentono sempre e uno sempre dice la verità. Dietro alle porte dei mentitori c’è un
disgustoso e vorace drago, ma dietro alla porta dell’aiutante che dice la verità c’è il corridoio che porta fuori
dal castello. Angelica rivolge alcune domande agli aiutanti del mago, ricevendo queste informazioni:
- UNO dice che TRE, QUATTRO e CINQUE mentono
- TRE dice che UNO o DUE dicono il vero
- QUATTRO dice che TRE dice il vero
Da quale porta deve uscire Angelica?
A) CINQUE
B) UNO
C) QUATTRO
D) TRE
E) DUE
Individuando la struttura del problema, si tralasciano tutti i dettagli a proposito di beffardi maghi, intelligenti
principesse, ... Ciò che rimane è che ci sono cinque proposizioni, una vera e quattro false, e che occorre
individuare quella vera.
Ciò è tipico della logica, che infatti assume la verità delle asserzioni di partenza e si accontenta di trarne le
conclusioni, come per il sillogismo:
((Socrate è un uomo) e (ogni uomo è mortale)) implica (Socrate è mortale)
e assume solo poche, e generalmente non particolarmente significative (significative, appunto...) “verità
logiche” (chiamate “tautologie”), come A=A, dove A è il simbolo per una proposizione qualsiasi. Questa è
poi la ragione per cui si possono proporre test di logica: non si deve essere esperti di beffardi maghi e
intelligenti principesse, ma solo di ragionamento, acquisendo familiarità con alcune strutture logiche di base
(connettivi proposizionali, quantificatori, condizioni necessarie e sufficienti, …).
Al proposito, due considerazioni:
1. l’uso di simboli, che avvicina la logica alla matematica, presenta vari benefici (elimina, o almeno riduce,
le ambiguità delle espressioni nei linguaggi storico-naturali; è sintetico; consente di “calcolare la verità” di
proposizioni composte a partire dalla verità delle proposizioni componenti: vedremo in che senso e come),
ma comporta una, per qualcuno innaturale, attenzione alle questioni specificamente notazionali.
Per esempio:
2
PROBLEMA 2
Se x è il numero mancante nella seguente successione:
1, 1; 9, 3; 25, 5; 49, 7; x, 9; . . .
dire quante tra le seguenti conclusioni sono corrette:
•x>9
• x > 98
• x < 100
• x < 50
A) 2
B) 4
C) 3
D) 1
E) 0
un problema davvero semplice non appena ci si accorga dell’uso – specificamente notazionale, appunto –
della virgola e del punto e virgola nella successione, eseguendo quindi con cura i due passi:
- trovare il valore di x: x=81;
- contare il numero di conclusioni corrette.
2. Il punto di partenza dei test è generalmente un’affermazione, cioè una proposizione che viene dichiarata
vera (per cui per esempio A=A si può scrivere anche A↔A, a significare “A è vero se e solo se A è vero”). Se
dunque scrivere “A” corrisponde in effetti a scrivere “A è (considerata) vero”, ci occorre una notazione per
asserire invece che A non è vero: ¬A, che si legge anche “A è falso” a causa dei principi di bivalenza,
¬¬A↔A (non-non-A è vero se e solo se A è vero) e del terzo escluso, “A o non-A”, in simboli A∨¬A (è
sempre vero, cioè è una tautologia, che A o non-A).
Applicando poi le leggi di De Morgan, ¬(A∨B)↔(¬A∧¬B) (il simbolo ‘∧’ rappresenta la congiunzione ‘e’) e
¬(A∧B)↔(¬A∨¬B), si mostra facilmente che i principi del terzo escluso e di non contraddizione sono
equivalenti: (A∨¬A)↔¬(A∧¬A)).
Dal principio di bivalenza segue tra l’altro che nella logica che stiamo considerando – che si rifa a quella che
può essere chiamata “logica classica” – sono previsti solo due “valori di verità”, vero e falso. Quando si
vuole mettere in evidenza la presenza di tali valori di verità, l’asserzione della verità di una proposizione A
può essere essere scritta v(A)=V, oppure v(A)=F per indicare la falsità di A, dunque mediante una funzione v,
“verità di”, che attribuisce un valore di verità, V o F, a una proposizione A.
Tornando a questioni più generali, quando ci si trova di fronte a un test è utile identificare il tipo di problema
che pone.
Si possono forse identificare tre categorie generali di test generalmente considerati “di logica”:
1. test di logica “in senso stretto” (come il PROBLEMA 1);
2. test di ragionamento matematico ipotetico (o ipotetico-deduttivo) (come il PROBLEMA 2);
3. test di ragionamento matematico deduttivo.
Un esempio di questa terza categoria è il seguente:
PROBLEMA 3
Del numero intero n sappiamo che è compreso tra 2 e 6 (precisamente 2 ≤ n ≤ 6) e che rende vera
una e una sola delle seguenti affermazioni:
n è divisibile per 4
n è divisibile per 6
n è divisibile per 2
n è un divisore proprio di 6
Qual è il valore di n?
A) 3
B) 6
C) 5
D) 4
E) 2
3
non particolarmente complesso non appena ci si ricordi il significato dei concetti di divisibilità e di divisore
proprio. In questo caso non sembra possibile se non andare per tentativi, considerando via via tutti i numeri
2, 3, …, 6.
2: verifica due affermazioni;
3: verifica un’affermazione;
4: verifica due affermazioni;
5: non verifica alcuna affermazione;
6: verifica due affermazioni.
Le tre categorie di problemi citate sono sufficientemente diverse tra loro non tanto per la forma con cui si
presentano, ma per le condizioni di soluzione che prospettano:
1. i test di logica in senso stretto sono generalmente risolubili con un ragionamento formale (cioè: un po’ di
intuizione può essere utile, ma non è necessaria);
2. i test di ragionamento matematico ipotetico richiedono alcune competenze di base ma anche intuizione;
3. i test di ragionamento matematico deduttivo richiedono generalmente solo alcune competenze di base.
Torniamo ora a considerare il PROBLEMA 1. Abbiamo già individuato la struttura del problema,
tralasciando dunque tutti i dettagli a proposito di beffardi maghi, intelligenti principesse, ...: ci sono cinque
proposizioni, indichiamole semplicemente 1, ..., 5, una vera e quattro false. Occorre individuare quale è vera.
Conosciamo in modo diretto solo tre di esse:
1 = ¬3∧¬4∧¬5: ?
3 = 1∨2: ?
4 = 3: ?
La verità di 4 implicherebbe che anche 3 sia vera, cosa non possibile. Dunque ¬4 e perciò ¬3.
Da ¬3 segue ¬(1∨2), che per la legge di De Morgan è equivalente a ¬1∧¬2.
Ciò è già sufficiente per concludere che 5. Verifichiamo comunque questa conclusione analizzando anche 1.
Poiché ¬1, allora ¬(¬3∧¬4∧¬5), che ancora per la legge di De Morgan è equivalente a 3∨4∨5, compatibile
con l’asserzione di verità di 5.
2. Cenni di (test di) logica proposizionale
[esistono numerosi testi di introduzione alla logica; un buon riferimento sugli argomenti di questo e del prossimo
capitolo è in particolare: W. Hodges, Logica, Garzanti, 1986]
Lavoriamo un po’ sulla prima categoria di problemi, i test di logica “in senso stretto”.
Un semplice esempio è il seguente:
PROBLEMA 4
L’affermazione “quando bevo troppo, mi si gonfia lo stomaco” implica che:
A) se non mi si gonfia lo stomaco allora non ho bevuto troppo
B) non mi si gonfia lo stomaco pur avendo bevuto troppo
C) a volte capita che non mi si gonfi lo stomaco pur avendo bevuto troppo
D) se mi si gonfia lo stomaco vuol dire che ho bevuto troppo
E) o bevo troppo o mi si gonfia lo stomaco
Si può certamente cercare di “vedere intuitivamente” la soluzione, e in casi semplici come questo, per chi ne
è in grado, è forse perfino la tecnica più efficiente. Ma esiste anche una tecnica “semi-algoritmica”, che è
sufficientemente generale e ha tra il vantaggio di limitare il ruolo dell’intuizione, e quindi di essere
impiegabile anche “dai non intuitivi”. Tale tecnica si basa sui seguenti passi, applicabili a ogni affermazione
A da considerare, per esempio A=“quando bevo troppo, mi si gonfia lo stomaco”.
1. Si analizza la struttura di A e si stabilisce se sia una proposizione elementare, cioè non costituita da due o
più proposizioni, o sia una proposizione composta. Un criterio empirico per stabilire se un’espressione
candidata x sia o meno una proposizione è il seguente: se “è vero che x” è grammaticalmente corretto,
naturalmente sostituendo a x l’espressione candidata, allora tale espressione è una proposizione. Le
4
proposizioni elementari sono allora proposizioni non scomponibili. Nell’esempio, A è chiaramente una
proposizione composta, le proposizioni elementari componenti essendo “bevo troppo” e “mi si gonfia lo
stomaco”. E’ immediato constatare che anche le proposizioni A)-E) sono composte.
2. Nel caso in cui la proposizione considerata sia composta, la si riscrive isolando i connettivi dalle
proposizioni elementari e, per sintesi, sostituendo queste ultime con dei simboli; A potrebbe diventare perciò:
“quando B, S”, avendo sostituito B=“bevo troppo” e S=“mi si gonfia lo stomaco”. In questa riscrittura, modi
e tempi dei verbi tendono a perdere di importanza. Per esempio B=“bevo troppo”, ma anche B=“ho bevuto
troppo”, come nella proposizione A).
3. Il problema che si pone ora è di ricondurre il valore di verità della proposizione composta al valore di
verità delle proposizioni elementari; nell’esempio, la domanda da porsi è: come dipende il valore di verità di
“quando B, S” dal valore di verità di B e di S? Ancora più concretamente, se per esempio ¬B (cioè è falso che
abbia bevuto troppo) e S (mi si è comunque gonfiato lo stomaco), diremmo che “quando B, S” è vera o falsa?
Data la ricchezza espressiva di una lingua come l’italiano, una soluzione generale a problemi di questo
genere è difficile da trovare. E’ anche per questo che i logici, anche al costo di perdere alcuni dettagli e
sfumature semantiche, hanno individuato alcune “forme standard”, a cui le proposizioni che ci vengono
proposte dovrebbero essere ricondotte, per parafrasi.
Tali forme standard sono, in particolare:
- “non A” (in simboli ¬A): negazione;
- “A o B” (in simboli A∨B): disgiunzione;
- “o A o B” (in simboli A▽B): disgiunzione esclusiva;
- “A e B” (in simboli A∧B): congiunzione;
- “A implica B” (o: “se A allora B”) (in simboli A→B): implicazione;
- “A se e solo B” (in simboli A↔B): bi-implicazione o equivalenza.
Parafrasiamo dunque l’affermazione iniziale del problema e le proposizioni A)-E) in modo da ricondurle a
forme standard (si noti ancora che nelle parafrasi modi e tempi verbali tendono a non essere importanti):
“quando B, S” diventa “se B allora S”: B→S
A) “se non S allora non B” non richiede parafrasi: ¬S→¬B
B) “non S pur B” diventa “non S e B”: ¬S∧B
C) “a volte non S pur B” contiene il problematico “a volte”, che non sappiamo come trattare; per il resto è
identico a B
D) “se S vuol dire che B” diventa “se S allora B”: S→B
E) “o B o S” non richiede parafrasi: B▽S
4. I connettivi che caratterizzano le forme standard sono tali che il valore di verità di una proposizione
composta mediante ognuno di essi dipende esclusivamente dal valore di verità delle proposizioni componenti
(e perciò in logica sono chiamati “vero-funzionali”). Tali relazioni di dipendenza sono presentate in modo
efficace mediante le cosiddette “tavole della verità”:
A
¬A
V
F
F
V
(da leggere: se A è vero allora ¬A è falso, e se A è falso allora ¬A è vero)
A B A∨B
A B A▽B
A B A∧B
A B A↔B
V V
V
V V
F
V V
V
V V
V
V F
V
V F
V
V F
F
V F
F
F V
V
F V
V
F V
F
F V
F
F F
F
F F
F
F F
F
F F
V
5
tutti non solo ragionevoli ma anche semplici da comprendere (ma si noti la differenza tra disgiunzione e
disgiunzione esclusiva).
Per ultima, perché particolarmente importante e perché non così intuitivamente semplice, la tavola della
verità dell’implicazione:
A
B
A→B
V
V
V
V
F
F
F
V
V
F
F
V
che si può leggere così: “A implica B” è sempre vero salvo quando da una premessa, A, vera si ottiene una
conseguenza, B, falsa; oppure anche: mentre da una premessa vera si può dedurre solo una conseguenza vera,
da una premessa falsa si può dedurre qualsiasi conclusione.
Il problema che ci siamo posti è dunque: (B→S)→?
Non bisogna però lasciarsi trarre in inganno dalla condizione di implicazione: dato che affermare una
proposizione significa asserirne la verità, la situazione corrisponde in effetti alla sola prima riga della tavola
di verità, e quindi il problema è in effetti (B→S)↔?
Si tratta, in pratica, di verificare se:
A) (B→S)↔(¬S→¬B) ?
B) (B→S)↔(¬S∧B) ?
e così via.
Applicando passo passo le tavole della verità, controlliamo la prima (tra parentesi l’ordine di calcolo):
B (0)
S (0)
→ (1)
↔ (4)
→ (3)
¬S (2)
¬B (2)
V
V
F
F
V
F
V
V
V
F
V
F
V
V
V
V
F
V
F
V
V
F
V
V
F
F
V
V
che ne dimostra la correttezza: (B→S)↔(¬S→¬B) è una tautologia, e quindi A) è la risposta esatta.
Per completezza, controlliamo anche la seconda:
B (0)
S (0)
B (2)
→ (1)
↔ (4)
∧ (3)
¬S (2)
V
V
F
F
V
F
V
V
V
F
V
F
F
V
F
F
F
V
F
V
F
V
F
F
V
V
F
F
che invece nella colonna (4) contiene dei valori F, cosa che indica che l’ipotesi B) è sbagliata.
Un altro problema:
PROBLEMA 5
Da “Chi dorme non piglia pesci” segue logicamente:
A) chi piglia pesci non dorme
B) chi non piglia pesci non dorme
C) chi non piglia pesci dorme
D) chi piglia pesci dorme
E) Nessuna delle altre alternative proposte
Riscriviamo l’affermazione iniziale in forma standard: “se uno dorme, allora non piglia pesci”.
La simbolizzazione di questa affermazione secondo le modalità introdotte finora, dunque D→¬P, nasconde
un problema, dato che non consente di distinguere “se uno dorme, allora non piglia pesci” da “se uno dorme,
allora un altro non piglia pesci”, proposizioni la cui verità non è evidentemente la stessa. Vedremo nel
seguito come affrontare questo genere di problemi; per ora manteniamo la forma proposizionale: D→¬P.
6
Trasformiamo corrispondentemente anche le risposte:
A) P→¬D
B) ¬P→¬D
C) ¬P→D
D) P→D
A questo punto si può operare con le tavole della verità per trovare a quale tra le proposizioni A)-E)
l’affermazione di partenza è equivalente.
Ancora un problema:
PROBLEMA 6
Nel diario del giovane Telesforo è scritto:
“Nonno Ubaldo dice che quando era giovane ha traversato l’oceano Atlantico a nuoto e che riusciva a battere
in velocità le balene. Secondo me questa è una bugia.”
Si dica cosa si può correttamente dedurre dalla convinzione di Telesforo.
A) Se Nonno Ubaldo riusciva a battere in velocità le balene allora non ha traversato l’oceano
Atlantico a nuoto
B) A Nonno Ubaldo non piacciono le balene
C) Nonno Ubaldo ha traversato l’oceano Atlantico a nuoto ma non riusciva a battere in velocità le
balene
D) Nonno Ubaldo non ha traversato l’oceano Atlantico a nuoto ma riusciva comunque a battere in
velocità le balene
E) Nonno Ubaldo non ha traversato l’oceano Atlantico a nuoto e non riusciva a battere in velocità
le balene
Indichiamo T=“Nonno Ubaldo quando era giovane ha traversato l’oceano Atlantico a nuoto” e B=“Nonno
Ubaldo riusciva a battere in velocità le balene”.
Dunque la convinzione di Telesforo è che ¬(T∧B). Per De Morgan, ciò è equivalente a ¬T∨¬B.
Riscriviamo ora anche le proposizioni A)-E):
A) B→¬T
B) ...
C) T∧¬B
D) ¬T∧B
E) ¬T∧¬B
Nuovamente, si può ora operare con le tavole della verità.
Come si vede, le leggi di De Morgan:
¬(A∨B)↔(¬A∧¬B)
¬(A∧B)↔(¬A∨¬B)
sono spesso utili per trasformare le proposizioni, mantenendone le condizioni di verità.
Analogamente, è utile imparare le seguenti due equivalenze, relative all’implicazione:
(A→B)↔(¬A∨B)
(A→B)↔(¬B→¬A)
Dimostriamo, a titolo di esempio, la seconda:
A (0)
B (0)
→ (1)
↔ (4)
→ (3)
¬Β (2)
¬A (2)
V
V
F
F
V
F
V
V
V
F
V
F
V
V
V
V
F
V
F
V
V
F
V
V
F
F
V
V
E’ plausibile che con queste poche, e semplici, regole la gran parte dei test di logica delle proposizioni
possano essere interpretati e risolti.
Facciamo qualche esercizio di parafrasi, in particolare per trovare esempi di proposizioni equivalenti,
compatibili e incompatibili a quella di partenza:
7
“Sarai bocciato, a meno che tu non ti metta a studiare”
Tale affermazione è parafrasabile in “se non S allora B”, equivalente a “S o B”: “studi o sarai bocciato”
(attenzione: non si tratta della disgiunzione esclusiva, “o studi o sarai bocciato”, che nega la possibilità che
pur studiando si sia bocciati).
Per analizzare le condizioni di verità dell’affermazione, è particolarmente efficace sfruttare la corrispondenza
tra logica e insiemistica, e quindi rappresentare A→B in un diagramma di Venn come:
A
B
così che ¬S→B si rappresenta:
¬S
B
Grazie a tale rappresentazione possiamo posizionare nel diagramma i casi seguenti:
.1
¬S
.2
B
.3
I punti 1, 2 e 3 corrispondono rispettivamente a ¬S∧B (“non studi e sei bocciato”), S∧B (“studi e sei
bocciato”) e S∧¬B (“studi e sei non bocciato”), tutte compatibili con l’affermazione iniziale, cioè tali da
essere equivalenti a ¬S→B almeno in qualche caso. Viceversa, il caso rimanente, ¬S∧¬B (“pur non studiando
non sarai bocciato”), non può essere rappresentato nel diagramma, cosa che ne mostra l’incompatibilità con
l’affermazione iniziale. In termini, (¬S→B)↔(¬S∧¬B) è sempre falso, cioè è una contraddizione, e quindi
¬((¬S→B)↔(¬S∧¬B)) è una tautologia.
Un secondo esercizio:
“Andrò al mare solo se c’è bel tempo”
Tale affermazione è equivalente (un po’ controintuitivamente) a “se M allora B”, e quindi “non M o B”, e
quindi l’unica proposizione incompatibile è “M e non B”: “andrò al mare e non c’è bel tempo”.
3. Cenni di (test di) logica predicativa
[a differenza della logica delle proposizioni, la logica dei predicati porta a risultati – espressi nella forma di teoremi –
profondi e complessi: quanto segue è dunque solo preliminare a un discorso di logica dei predicati vero e proprio]
Un nuovo problema:
PROBLEMA 7
Negare che “ogni gatto miagola” equivale a dire che:
A) c’è un gatto che non miagola
B) se non miagola non è un gatto
C) c’è un gatto che miagola
8
D) ogni gatto non miagola
E) nessun gatto miagola
Siamo qui di fronte a una difficoltà, dovuta alla non riducibilità dell’affermazione di partenza a una
proposizione, a causa del fatto che il problema si gioca sulla presenza dei termini “ogni”, “c’è”,
“nessuno”, ...
E’ questo il primo esempio di un problema per la cui soluzione la logica delle proposizioni con cui abbiamo
operato finora non è sufficiente: occorre passare a una logica più generale, e più complessa, chiamata “dei
predicati”.
Per lo scopo di affrontare efficacemente test come il PROBLEMA 7, è generalmente sufficiente imparare una
versione delle leggi di De Morgan generalizzata alla logica dei predicati. Ripartiamo da:
¬(A∧B)↔(¬A∨¬B)
(A e B è falso se e solo se sono falsi A o B; detto altrimenti: A e B è una bugia se e solo A è una bugia, oppure
B è una bugia, oppure lo sono entrambi).
Ciò è generalizzabile a tre o più proposizioni:
¬(A∧B∧C)↔(¬A∨¬B∨¬C)
e quindi:
¬(A1∧...∧An)↔(¬A1∨...∨¬An)
Supponiamo ora che le n proposizioni Ai abbiano tutte la stessa forma: dato un insieme di n individui,
l’individuo i-esimo ha la proprietà A. Per esempio, A1=“il gatto 1 miagola”; A2=“il gatto 2 miagola”; ...
Allora in particolare (A1∧...∧An) e (A1∨...∨An) significano “tutti i gatti (dell’insieme considerato) miagolano”,
e “almeno un gatto miagola”, rispettivamente. Per denotare in modo sintetico situazioni di questo genere si
introducono il quantificatore universale:
∀x, A(x): per ogni elemento x dell’insieme considerato, x ha la proprietà A
e il quantificatore esistenziale:
∃x, A(x): esiste almeno un elemento x nell’insieme considerato tale che x ha la proprietà A
Le leggi di De Morgan generalizzate sono allora:
¬∀x, A(x) ↔ ∃x, ¬A(x) (“non tutti i gatti miagolano” è equivalente a “esiste un gatto che non miagola”, cioè
“almeno un gatto non miagola”)
¬∃x, A(x) ↔ ∀x, ¬A(x) (“non esiste un gatto che miagola”, cioè “nessun gatto miagola”, è equivalente a
“tutti i gatti non miagolano”)
Tornando allora al problema, l’affermazione iniziale, negare che “ogni gatto miagola”, si scrive ¬∀x, M(x), e
altrettanto facilmente si possono scrivere le asserzioni A)-E):
A) c’è un gatto che non miagola: ∃x, ¬M(x)
B) se non miagola non è un gatto: ∀x, ¬M(x)→¬G(x)
C) c’è un gatto che miagola: ∃x, M(x)
D) ogni gatto non miagola: ∀x, ¬M(x)
E) nessun gatto miagola: ¬∃x, M(x)
Applicando le leggi di De Morgan a ¬∀x, M(x) si ottiene ∃x, ¬M(x).
Un problema analogo:
PROBLEMA 8
Un grande teorico dei numeri ha scoperto i numeri troppobelli, e, avendo osservato che tutti quelli che ha
scoperto sono pari, congettura che esistano solo numeri troppobelli pari.
Un suo allievo, studiando con cura questi numeri, afferma che la congettura del maestro è falsa.
Dunque l’allievo sostiene che:
A) c’è almeno un numero troppobello dispari
B) nessun numero pari è troppobello
C) c’è almeno un numero pari che non è troppobello
D) esiste solo un numero finito di troppobelli pari
E) tutti i numeri troppobelli sono dispari
9
La congettura è ∀x, T(x)→P(x). Poiché si assume che sia falsa: ¬(∀x, T(x)→P(x)), che per De Morgan è
equivalente a ∃x, ¬(T(x)→P(x)) e quindi ∃x, ¬(¬T(x)∨P(x)) e ancora per De Morgan ∃x, T(x)∧¬P(x).
Infine, un problema ancora analogo ma un poco più complesso:
PROBLEMA 9
C’è una casa con almeno due porte; si consideri l’affermazione:
Esiste una chiave che apre tutte le porte di casa, ma non la porta della cantina.
Indicare quale tra le seguenti frasi costituisce la negazione dell’affermazione riportata sopra.
A) Per ogni chiave, o esiste una porta che non è quella della cantina che non viene aperta da
quella chiave, oppure quella chiave apre la porta della cantina
B) Esiste una chiave che apre tutte le porte di casa, compresa quella della cantina
C) Esiste una chiave che non apre nessuna porta, se non quella della cantina
D) Nessuna chiave apre tutte le porte
E) Per ogni chiave, esiste una porta che non è quella della cantina che viene aperta da quella
chiave
Riscriviamo l’affermazione iniziale in forma standard e cercando di semplificarla, in particolare assumendo
che oggetto di base del discorso siano implicitamente sempre chiavi: “esiste un elemento tale da essere onniaprente e non cantina-aprente”. Dunque: ∃x, O(x)∧¬C(x).
Poiché dobbiamo analizzare la negazione dell’affermazione, applichiamo la versione generalizzata della
legge di De Morgan: ¬∃x, A(x) ↔ ∀x, ¬A(x).
Dunque la negazione dell’affermazione precedente è equivalente a ∀x, ¬(O(x)∧¬C(x)).
Applicando la legge di De Morgan: ∀x, ¬O(x)∨C(x)).
4. Cenni di (test di) logica “in senso lato”
[non è facile trovare testi di introduzione alla logica “in senso lato”; un interessante riferimento al proposito è: G. Polya,
Come risolvere i problemi di matematica, Feltrinelli, 1976]
Infine, lavoriamo per esempi su alcuni problemi di tipo matematico, o comunque di logica “in senso lato”,
per i quali la procedura introdotta e adottata finora non è generalmente applicabile, e quindi, oltre ad alcune
competenze matematiche di base, occorre disporre di un metodo di “approccio ai problemi”.
Cominciamo con un tipico problema “continua la successione”:
PROBLEMA 10
Indicare quale numero prosegue la successione: 7, 20, 46, 98, 202, 410, ...
A) 826
B) 820
C) 612
D) 814
E) 938
Il problema è dunque: dati i termini x1=7, x2=20, x3=46, x4=98, x5=202, x6=410 di una successione, qual è il
valore di x7?
Si vede che x2−x1=13 e x3−x2=26. Potremmo allora formulare l’ipotesi che la differenza tra ogni coppia di
termini della successione sia un multiplo crescente di 13, cioè che xi+1−xi=13i. In questo caso, sarebbe che x4−
x3=39, e quindi x4=39+46=85. L’ipotesi è errata, dunque.
Guardiamo le differenze successive: x4−x3=52; x5−x4=104; x6−x5=208. Ogni differenza è il doppio della
precedente. Partendo dai suoi primi due termini:
x1=7
x2=20
la successione è dunque definita dalla regola:
xi+1-xi=2(xi−xi−1)
e quindi, con un po’ di algebra:
xi+1=3xi−2xi−1
10
Perciò x7=3x6−2x5.
Spesso i test chiedono di analizzare la relazione tra due gruppi di individui, come in questo semplicissimo
caso:
PROBLEMA 11
A una conferenza, 8 persone prendono appunti, 5 hanno un registratore. Con questi dati si può concludere
con certezza che il numero totale N degli ascoltatori a quella conferenza è:
A) N >= 8
B) N = 13
C) N > 8
D) N < 8
E) N > 13
in cui è sufficiente riconoscere che si considerano due proprietà indipendenti.
Più complesso è invece quest’altro problema.
PROBLEMA 12
Nell’harem del sultano Alì Babà i 4/5 delle odalische hanno i capelli neri e i 3/4 hanno gli occhi neri. Si può
concludere che:
A) almeno 11/20 delle odalische hanno sia capelli sia occhi neri
B) 3/5 delle odalische hanno sia capelli sia occhi neri
C) al più 11/20 delle odalische hanno sia capelli sia occhi neri
D) 4/5 delle odalische hanno sia capelli sia occhi neri
E) 3/4 delle odalische hanno sia capelli sia occhi neri
Tutte le risposte possibili si riferiscono al problema di determinare la frazione di individui (odalische, in
questo caso) che hanno sia la proprietà A (capelli neri) sia la proprietà B (occhi neri), indichiamola fA∧B, a
partire dalle frazioni fA e fB. Se il problema fosse: la frazione fA=4/5 di individui ha la proprietà A e la frazione
fB=3/4 di questi ha la proprietà B, allora la frazione fA∧B sarebbe semplicemente 4/5 x 3/4 = 12/20 = 3/5. Ma le
due frazioni sono invece espresse senza relazione l’una con l’altra.
Proviamo ad analizzare il problema generale in questo caso.
Date le frazioni fA e fB, la richiesta tipicamente potrebbe riguardare la frazione fA∧B (come appunto nel nostro
problema) ma anche la frazione fA∨B degli individui che hanno la proprietà A o la proprietà B (chiamiamoli
per brevità “individui-A” e “individui-B”).
Consideriamo prima di tutto la situazione particolare in cui una delle due frazioni, supponiamo fA, è uguale a
0 o 1. La soluzione è evidentemente:
fA∧B
fA∨B
fA=0
0
fB
fA=1
fB
1
Per esempio – quanto è indicato nella prima riga della tabella –, se non ci sono individui-A allora non ci
possono essere individui-AeB, mentre la frazione di individui-AoB coincide con la frazione di individui-B.
Assumiamo ora invece che 0<fA<1 e 0<fB<1, e ipotizziamo per esempio che fA≤fB.
Come si vede anche dalle risposte A)-E), in questo caso si può dover stabilire non solo il valore di fA∧B (o
fA∨B), ma anche il suo valore minimo (“almeno ...”, come nella risposta A)) o il suo valore massimo (“al più”,
come nella risposta C)).
Cominciamo a prendere in considerazione il caso, più semplice, fA∨B. Il valore massimo di fA∨B si presenta nel
caso in cui c’è intersezione minima tra individui-A e individui-B, quindi per fA+fB. D’altra parte, occorre
garantire che fA∨B abbia al massimo il valore 1, corrispondente alla situazione in cui tutti gli individui sono
individui-A o individui-B, cosa che richiede di calcolare il massimo di fA∨B come il minimo tra 1 e fA+fB:
11
dunque max(fA∨B)=min(1, fA+fB). Il valore minimo di fA∨B si presenta nel caso in cui c’è intersezione massima
tra individui-A e individui-B, e quindi, data l’ipotesi che fA≤fB, quando tutti gli individui-A sono anche
individui-B. Dunque min(fA∨B)=max(fA, fB).
Consideriamo ora il caso fA∧B. Il valore massimo di fA∧B si presenta quando c’è intersezione massima tra
individui-A e individui-B, e perciò, sempre con l’ipotesi che fA≤fB, quando tutti gli individui-A sono anche
individui-B. In tal caso, max(fA∧B)=min(fA, fB). Rimane da prendere in esame il valore minimo di fA∧B, che si
presenta nel caso in cui, evidentemente, c’è intersezione minima tra individui-A e individui-B, cioè quando
tutti gli individui che non sono individui-B sono individui-A. Poiché questi sono pari alla frazione 1−fB, la
frazione degli individui-AeB è pari alla frazione degli individui-A, fA, a cui è stata sottratta la frazione 1−fB.
Dato infine che il valore ottenuto potrebbe risultare negativo, calcoliamo il min(fA∨B) come max(0, fA−(1−fB))
A∧B
A∨B
max(f)
intersezione massima tra individui-A e individui-B
(tutti gli individui-A sono anche individui-B)
min(fA, fB)
intersezione minima tra individui-A e individui-B
min(1, fA+fB)
min(f)
intersezione minima tra individui-A e individui-B
max(0, fA−(1−fB))
intersezione massima tra individui-A e individui-B
(tutti gli individui-A sono anche individui-B)
max(fA, fB)
(come semplice esercizio, si può verificare che le conclusioni ottenute sopra per i casi fA=0 e fA=1 rientrano
come casi particolari di questi stessi risultati).
Tornando finalmente al nostro problema, in cui fA=4/5 e fB=3/4, da questa tabella si ottiene che:
1. al più min(4/5, 3/4)=3/4 delle odalische hanno sia capelli sia occhi neri;
2. almeno max(0, 4/5−(1−3/4)=11/20 delle odalische hanno sia capelli sia occhi neri;
3. poiché min(1, 4/5+3/4)=1, tutte le odalische potrebbero avere capelli o occhi neri;
4. almeno max(4/5, 3/4)=4/5 delle odalische hanno capelli o occhi neri,
e naturalmente il punto 2 ci dà la risposta cercata.
In effetti, date le risposte possibili A)-E), allo stesso risultato in questo caso si sarebbe potuto arrivare per
esclusione: le risposte B), D) ed E) indicano un valore definito per la frazione fA∧B, invece che un valore
minimo o massimo, e quindi possono essere escluse a priori. Rimane, oltre alla risposta giusta, C), che si può
forse intuitivamente (soprattutto dopo l’analisi appena compiuta...) riconoscere anch’essa come sbagliata.
Il prossimo problema non richiede invece alcuna intuizione, ma solo precisione nel seguire, passo passo, un
semplice procedimento.
PROBLEMA 13
Gianni ha trovato un vecchio giornale enigmistico che riportava uno schema triangolare in cui ogni numero,
dalla seconda riga in giù, era uguale alla somma dei due numeri situati sopra al numero stesso, esattamente
come succede nella seguente figura:
Lo schema di Gianni era in gran parte illeggibile. Si sono potuti riconoscere solo i 4 numeri indicati in
quest’altra figura:
12
Sapreste aiutare Gianni a ricostruire lo schema originario? Indicate in particolare quale numero deve stare
nella casella indicata con “?”.
A) 25
B) 35
C) 30
D) 20
E) 15
Assegniamo dei simboli:
x4
x1
x3
x5
x2
Allora:
x1=5+10=15
x2=105−65=40
x3=40−15=25
x4=25−10=15
x5=65−25=40
?=40−15=25
Infine, due problemi che sollecitano l’uso di un poco di intuizione spaziale.
PROBLEMA 14
Abbiamo 60 contenitori uguali di forma cubica disposti in modo da formare un parallelepipedo le cui
dimensioni misurano 5x4x3. Alla fine dell’inverno scopriamo che si sono rovinati i contenitori che avevano
almeno una faccia verso l'esterno o sul fondo del parallelepipedo. Quanti sono i contenitori rimasti integri?
A) 6
B) 30
C) 24
D) 12
E) nessuno
Il volume del parallelepipedo è 5x4x3=60. Poiché i contenitori sono 60, il volume di ognuno è 1 cioè sono
cubi 1x1x1. Dato il fatto che una dimensione è 3, per trovare il numero di contenitori “interni” possiamo
eliminare i contenitori sulle due facce 4x5, dunque 40 e quindi quelli sul profilo, dunque 5x2+2x2.
PROBLEMA 15
Voglio costruire una ‘piramide’ alta 4 livelli con pietre a forma di cubi, come indicato nella figura seguente:
al livello più alto c'è un solo cubo, al livello immediatamente inferiore ne abbiamo 3 e così via. Quanti cubi
devo utilizzare in totale?
13
A) 20
B) 22
C) 16
D) 19
E) 18
Possiamo risolvere il problema individuando la successione il cui termine xi corrisponde al numero di
elementi della ‘piramide’ con i livelli, e dunque tale che x1=1, x2=4, ... e quindi cercando x4.
xi = xi-1 + (1+...+i-1) + i = xi-1 + Σj=1,...,i j = xi-1 + si.
A questo punto è sufficiente calcolare le somme si per i primi 4 interi:
s1=1
s2=1+2=3
s3=1+2+3=6
s4=1+2+3+4=10
e quindi:
x1=1
x2=x1+s2=4
x3=x2+s3=10
x4=x3+s4=20
14
Esempi di altri problemi
Cinquanta famosi matematici sono riuniti a congresso. Non tutti sono distratti. Però, presi a caso due
matematici, almeno uno dei due è distratto.
Dunque necessariamente i congressisti distratti sono:
A) 49
B) almeno 2, ma possono essere meno di 25
C) più di 25, ma non si può dire quanti
D) 50
E) 25
Nel paese di Belpoggio tutti i ragazzi praticano qualche sport.
Se:
• chi gioca a calcio fa anche nuoto
• chi gioca a tennis non fa nuoto
• chi gioca a pallavolo gioca anche a calcio
si può concludere che:
A) chi gioca a pallavolo fa anche nuoto
B) chi fa nuoto gioca anche a calcio
C) chi fa nuoto e gioca a pallavolo, gioca anche a tennis
D) chi gioca a tennis gioca anche a calcio
E) chi non gioca a calcio non fa nuoto
Questo problema può essere facilmente risolto mediante diagrammi di Venn.
L’affermazione:
“A nessuno studente sono antipatici tutti i professori”
equivale a dire che:
A. Scelto un qualsiasi studente, c’è almeno un professore che gli è simpatico
B. Tutti i professori sono simpatici agli studenti
C. Esiste uno studente a cui sono antipatici tutti i professori
D. C’è un professore che è simpatico a tutti gli studenti
E. A qualche studente sono simpatici tutti i professori
L’affermazione iniziale è ¬∃s, ∀p, A(p,s) (“non esiste uno studente tale che per ogni professore il professore
è antipatico allo studente”; si noti la presenza di un predicato a due argomenti, A(p,s), “p è antipatico a s”);
per De Morgan: ∀s, ¬∀p, A(p,s) (“per ogni studente, non per ogni professore il professore è antipatico allo
studente”); ancora per De Morgan, infine: ∀s, ∃p, ¬A(p,s) (“per ogni studente, esiste un professore tale che il
professore non è antipatico allo studente”).
(...)
15