Teoria

Problemi di deduzione e tabelle

Come si risolvono i quesiti in cui da un elenco di indizi si ricava chi fa che cosa, con le griglie di deduzione, le disposizioni in fila e attorno a un tavolo, i turni di lavoro, i problemi di veri e bugiardi e quelli in cui un numero fissato di affermazioni è vero.

In questa pagina

Che cos’è un problema di deduzione
Griglie di deduzione

Che cos’è un problema di deduzione

Problema di deduzione

Un problema di deduzione presenta alcune persone, alcune caratteristiche da attribuire loro (un lavoro, una città, un posto in fila, un giorno di turno) e un elenco di indizi, detti anche vincoli. Risolverlo significa trovare tutte le attribuzioni che rispettano ogni indizio. Quasi sempre il testo dichiara che le caratteristiche sono tutte diverse, cioè che a ogni persona ne corrisponde una e una sola e che nessuna caratteristica è condivisa da due persone.

Se Anna, Bruno e Carla lavorano in tre uffici diversi, che sono anagrafe, protocollo e tributi, ogni ufficio ha esattamente una delle tre persone. L’indizio “Carla non lavora né all’anagrafe né ai tributi” lascia a Carla un solo ufficio possibile, quindi Carla lavora al protocollo.

Una soluzione o più soluzioni

Gli indizi di un quesito ben costruito possono lasciare una sola attribuzione possibile oppure più di una. Nel primo caso la domanda è diretta (“Chi lavora ai tributi?”). Nel secondo la domanda chiede che cosa vale in tutte le soluzioni, oppure quale informazione in più basterebbe a fissarne una. Può anche accadere che gli indizi lascino due soluzioni che differiscono soltanto per dettagli non richiesti: se Luca e Nicola possono scambiarsi il succo e l’acqua, la domanda “chi prende il caffè?” ha comunque una sola risposta.

Griglie di deduzione

1. Griglia di deduzione

Una griglia di deduzione è una tabella a doppia entrata con le persone sulle righe e i valori di una caratteristica sulle colonne. In ogni casella si scrive ✗ quando l’abbinamento è escluso dagli indizi e ✓ quando è certo. La griglia serve a tenere traccia di ciò che si è già dedotto, senza doverlo tenere a mente.

Tre amici, Davide, Elisa e Fabio, hanno ciascuno un animale diverso, cioè un gatto, un cane e un pappagallo. Davide non ha il gatto, e Fabio non ha né il gatto né il cane. Dopo aver letto gli indizi la griglia si presenta così.

	gatto	cane
Davide	✗
Elisa
Fabio	✗	✗

2. Regola delle righe e delle colonne

Se ogni persona ha esattamente un valore e ogni valore appartiene a esattamente una persona, in una griglia di deduzione valgono due regole.

Se in una riga, o in una colonna, tutte le caselle tranne una sono ✗, nella casella rimasta va ✓.
Se una casella è ✓, tutte le altre caselle della sua riga e della sua colonna sono ✗.

Nella griglia degli animali la riga di Fabio ha due ✗, quindi Fabio ha il pappagallo. Di conseguenza la colonna del pappagallo riceve ✗ nelle righe di Davide e di Elisa.

Dimostrazione

Ogni riga contiene esattamente un ✓, perché ogni persona ha un solo valore; se tutti gli altri valori sono esclusi, resta quello. Allo stesso modo ogni colonna contiene un solo ✓, perché ogni valore appartiene a una sola persona, perciò un ✓ esclude gli altri nella sua colonna e nella sua riga.

Propagazione dei vincoli

Applicare una regola produce un nuovo ✓ o un nuovo ✗, che a sua volta permette di applicarne un’altra. Questo procedimento si chiama propagazione dei vincoli. Nel problema degli animali, dopo il ✓ di Fabio sul pappagallo, la riga di Davide ha ✗ sul gatto e sul pappagallo, quindi Davide ha il cane. La colonna del gatto ha ora ✗ nelle righe di Davide e di Fabio, perciò il gatto è di Elisa.

	gatto	cane	pappagallo
Davide	✗	✓	✗
Elisa	✓	✗	✗
Fabio	✗	✗	✓

Ogni passaggio usa un solo indizio o una sola regola. La griglia è completa quando ogni riga contiene un ✓.

3. Griglie con due caratteristiche

Quando le caratteristiche sono due, per esempio la professione e la città, si usa una tabella con una riga per persona e una colonna per caratteristica, e accanto si annotano i valori esclusi. Gli indizi che legano due caratteristiche, come “l’insegnante vive a Roma”, si usano in entrambi i versi. Se l’insegnante vive a Roma e Giulia vive a Napoli, allora Giulia non è l’insegnante. Questo passaggio è la contronominale dell’indizio: “se una persona è l’insegnante, allora vive a Roma” equivale a “se una persona non vive a Roma, allora non è l’insegnante”. Per l’equivalenza tra un’implicazione e la sua contronominale si rimanda all’argomento sui connettivi, le negazioni e le implicazioni.

Attenzione

L’indizio “l’insegnante vive a Roma” non dice che chi vive a Roma è l’insegnante, a meno che il testo dichiari che in ogni città vive una sola persona. Con tre persone e tre città diverse le due frasi sono equivalenti; con quattro persone e due sole città, una delle quali è Roma, a Roma può vivere anche qualcuno che non insegna.

La teoria continua con 7 altri paragrafi (disposizioni in fila, disposizioni attorno a un tavolo, turni e calendari di lavoro…), oltre a tutte le schede svolte, le soluzioni e il PDF.

Sblocca ora