Applicazioni della Logica Booleana (2)
Per non trascinarci sempre una trentina di posts, apro un
secondo ciclo di esempi applicativi della logica booleana.
Per comodita’, ricordo i principali riferimenti dati nel ciclo
precedente, ed in particolare l’articolo in Internet su:
Impiego del calcolatore per la soluzione di problemi logici
(http:www.schgor.com/artic/ICSPL.htm)
In tale articolo sono citati (e pure disponibili in Internet):
- Corso di logica booleana (in Java)
(http://www.schgor.com/logicabool/CLB.htm)
- Programma SPL (eseguibile di Visual Basic3)
(http://www.schgor.com/eseg/SPL.exe)
Tutto questo materiale ha come scopo una piu’ rapida
applicazione dei metodi booleani ai problemi pratici.
Una delle fonti piu’ note di problemi di questo tipo e’
il libro di Raymond. Smullyan dallo strano titolo
“Qual’e’ il titolo di questo libro?”,
scritto una trentina di anni fa, e che raccoglie ben 270
rompicapo logici.
Mentre Smullyan da’ la soluzione di ogni problema
con complicati ragionamenti deduttivi, si vuole qui
dimostrare che l’applicazione dell’algebra booleana
consente di ottenere le soluzioni in modo semplice e
rapido (soprattutto se facilitato dall’uso del calcolatore).
Se l’argomento interessa i frequentatori del Forum,
incominceremo dunque presto questa rassegna.
G.Schgör
secondo ciclo di esempi applicativi della logica booleana.
Per comodita’, ricordo i principali riferimenti dati nel ciclo
precedente, ed in particolare l’articolo in Internet su:
Impiego del calcolatore per la soluzione di problemi logici
(http:www.schgor.com/artic/ICSPL.htm)
In tale articolo sono citati (e pure disponibili in Internet):
- Corso di logica booleana (in Java)
(http://www.schgor.com/logicabool/CLB.htm)
- Programma SPL (eseguibile di Visual Basic3)
(http://www.schgor.com/eseg/SPL.exe)
Tutto questo materiale ha come scopo una piu’ rapida
applicazione dei metodi booleani ai problemi pratici.
Una delle fonti piu’ note di problemi di questo tipo e’
il libro di Raymond. Smullyan dallo strano titolo
“Qual’e’ il titolo di questo libro?”,
scritto una trentina di anni fa, e che raccoglie ben 270
rompicapo logici.
Mentre Smullyan da’ la soluzione di ogni problema
con complicati ragionamenti deduttivi, si vuole qui
dimostrare che l’applicazione dell’algebra booleana
consente di ottenere le soluzioni in modo semplice e
rapido (soprattutto se facilitato dall’uso del calcolatore).
Se l’argomento interessa i frequentatori del Forum,
incominceremo dunque presto questa rassegna.
G.Schgör
Risposte
quote:
Originally posted by g.schgor
Siete ormai dei maghi
beh, non esgeriamo...comunque a presto...
Complimenti a jack ed Alice. Siete ormai dei maghi.
Comunque riporto la soluzione completa:
La risposta di A (“siamo tutti furfanti”)
e’ facilmente convertibile in abc .
La risposta di B (“solo uno di noi è un cavaliere”)
si può invece esprimere come somma logica delle
possibili combinazioni: Abc+aBc+abC
(solo il primo e’ un cavaliere e gli altri 2 sono
furfanti, oppure solo il secondo e’ un cavaliere… ecc.).
Essendo due le risposte, la struttura dell’espressione
risolvente sarà il prodotto logico delle due condizioni
(devono essere ‘vere’ entrambe):
R1 = A(abc)+a[abc]
R2 = B(Abc+aBc+abC)+b[Abc+aBc+abC]
Come si vede, la soluzione ‘algebrica’ del prodotto delle due,
pur essendo fattibile, risulta piuttosto noiosa da svolgere
(ma soprattutto c’è il pericolo di commettere errori banali).
Per questo si consiglia l’uso del programma SPL.,che da’
immediatamente la soluzione,: aBc
(solo il secondo è un cavaliere, gli altri 2 sono furfanti).
Credo che a questo punto sia superfluo continuare con
esempi di questo tipo, rimandando al libro di Smullyan chi
trovasse interessante proseguire.
Del resto chiunque potrebbe ‘inventare’ casi con più abitanti
e più risposte, constatando che con un approccio tradizionale
di deduzione logica diventerebbe sempre più arduo arrivare
a soluzioni certe e, soprattutto, complete.
Chiudo pertanto questo ’ciclo’ , per riprendere prossimamente
con problemi logici di altro tipo.
G.Schgör
Comunque riporto la soluzione completa:
La risposta di A (“siamo tutti furfanti”)
e’ facilmente convertibile in abc .
La risposta di B (“solo uno di noi è un cavaliere”)
si può invece esprimere come somma logica delle
possibili combinazioni: Abc+aBc+abC
(solo il primo e’ un cavaliere e gli altri 2 sono
furfanti, oppure solo il secondo e’ un cavaliere… ecc.).
Essendo due le risposte, la struttura dell’espressione
risolvente sarà il prodotto logico delle due condizioni
(devono essere ‘vere’ entrambe):
R1 = A(abc)+a[abc]
R2 = B(Abc+aBc+abC)+b[Abc+aBc+abC]
Come si vede, la soluzione ‘algebrica’ del prodotto delle due,
pur essendo fattibile, risulta piuttosto noiosa da svolgere
(ma soprattutto c’è il pericolo di commettere errori banali).
Per questo si consiglia l’uso del programma SPL.,che da’
immediatamente la soluzione,: aBc
(solo il secondo è un cavaliere, gli altri 2 sono furfanti).
Credo che a questo punto sia superfluo continuare con
esempi di questo tipo, rimandando al libro di Smullyan chi
trovasse interessante proseguire.
Del resto chiunque potrebbe ‘inventare’ casi con più abitanti
e più risposte, constatando che con un approccio tradizionale
di deduzione logica diventerebbe sempre più arduo arrivare
a soluzioni certe e, soprattutto, complete.
Chiudo pertanto questo ’ciclo’ , per riprendere prossimamente
con problemi logici di altro tipo.
G.Schgör
non ti preoccupare...basta che vai al primo post di questo topic, dove ci sono tutti i collegamenti...e il terzo è proprio il programma SPL..ah, SPL vuol dire Solutore Problemi Logici, io all' inizio avevo qualche difficoltà ad usarlo, ma dopo un po' riesci a destreggiarti...comunque sia trovi all' interno del programma una guida, che ti indica come usare il calcolatore...
a presto
jack
a presto
jack
Per jack:
io in realtà ho compilato una semplice tavola di verità, ma con le tue formule mi ritrovo. Poi però per il calcolo come fai? Cosa si intende per programma SPL? Vi chiedo scusa, ma non ho letto tutti i post precedenti.
Grazie e ciao
io in realtà ho compilato una semplice tavola di verità, ma con le tue formule mi ritrovo. Poi però per il calcolo come fai? Cosa si intende per programma SPL? Vi chiedo scusa, ma non ho letto tutti i post precedenti.
Grazie e ciao
@alice
la soluzione è corretta...io ho proceduto usando il metodo algebrico, e ho impostato così le due formule:
A(abc)+a[abc]
B(Abc+aBc+abC)+b[Abc+aBc+abC]
da cui
aBc...beh, perlomeno se abbiamo sbagliato abbiamo commesso lo stesso errore [:D][:D]
la soluzione è corretta...io ho proceduto usando il metodo algebrico, e ho impostato così le due formule:
A(abc)+a[abc]
B(Abc+aBc+abC)+b[Abc+aBc+abC]
da cui
aBc...beh, perlomeno se abbiamo sbagliato abbiamo commesso lo stesso errore [:D][:D]
Va bene:aBc?
Dopo la risposta del primo si ha: abC oppure aBc oppure aBC
dopo la risposta del secondo: abc oppure aBc oppure AbC
dopo tutte e due...
Ciao
Dopo la risposta del primo si ha: abC oppure aBc oppure aBC
dopo la risposta del secondo: abc oppure aBc oppure AbC
dopo tutte e due...
Ciao
Per chi non avesse seguito le soluzioni
date da jack del problema del 17/12 , le riassumo.
La risposta dell’ abitante e’ un “or-esclusivo” (a xor B),
equivalente all’espressione (ab+AB).
Messa nella solita struttura, comune a tutti questi problemi,
si ottiene: A(ab+AB)+a[ab+AB]
che risolta da’: AB (entrambi gli abitanti sono cavalieri),
ma anche aB (il primo e’ un furfante, il secondo un cavaliere).
Ma quest’ultima situazione corrisponde alle due
affermazioni che fa il primo (“io sono un furfante”
“lui e’ un cavaliere”), quindi come puo’ essere
un furfante se dice cose vere?
In realta’ la risposta e’ falsa nel suo complesso
poiche’, dando le due situazioni in alternativa,
esclude proprio che possano essere vere entrambe,
quindi chi la da’ e’ un furfante.
Piu’ propriamente la soluzione algebrica si riduce alla
sola B (cioe’ il secondo e’ certamente un cavaliere),
mentre il primo non puo’ essere identificato.
La possibilita’ di soluzioni multiple ovviamente
si riduce se vi sono piu’ risposte da parte degli abitanti,
ma e’ evidente che l’analisi si complica, facendo risaltare
i vantaggi di seguire il metodo algebrico, rispetto ad
un’analisi deduttiva diretta.
Ecco un problema con 3 abitanti e con 2 risposte (n.31, pag.21).
Per maggior chiarezza, chiamiamo A il primo abitante,
B il secondo, C il terzo, con la convenzione che A=1
se cavaliere (quindi A=0, ovvero a=(not A)=1, se furfante),
e cosi’ per gli altri.
Allora, stessa domanda da parte dell’esploratore
(“siete cavalieri o furfanti?”), e in questo caso
A risponde: “siamo tutti furfanti”, mentre
B risponde: “solo uno di noi e’ un cavaliere”
Chi e’ cavaliere e chi furfante?.
Ovviamente attendo che qualcuno provi a rispondere.
date da jack del problema del 17/12 , le riassumo.
La risposta dell’ abitante e’ un “or-esclusivo” (a xor B),
equivalente all’espressione (ab+AB).
Messa nella solita struttura, comune a tutti questi problemi,
si ottiene: A(ab+AB)+a[ab+AB]
che risolta da’: AB (entrambi gli abitanti sono cavalieri),
ma anche aB (il primo e’ un furfante, il secondo un cavaliere).
Ma quest’ultima situazione corrisponde alle due
affermazioni che fa il primo (“io sono un furfante”
“lui e’ un cavaliere”), quindi come puo’ essere
un furfante se dice cose vere?
In realta’ la risposta e’ falsa nel suo complesso
poiche’, dando le due situazioni in alternativa,
esclude proprio che possano essere vere entrambe,
quindi chi la da’ e’ un furfante.
Piu’ propriamente la soluzione algebrica si riduce alla
sola B (cioe’ il secondo e’ certamente un cavaliere),
mentre il primo non puo’ essere identificato.
La possibilita’ di soluzioni multiple ovviamente
si riduce se vi sono piu’ risposte da parte degli abitanti,
ma e’ evidente che l’analisi si complica, facendo risaltare
i vantaggi di seguire il metodo algebrico, rispetto ad
un’analisi deduttiva diretta.
Ecco un problema con 3 abitanti e con 2 risposte (n.31, pag.21).
Per maggior chiarezza, chiamiamo A il primo abitante,
B il secondo, C il terzo, con la convenzione che A=1
se cavaliere (quindi A=0, ovvero a=(not A)=1, se furfante),
e cosi’ per gli altri.
Allora, stessa domanda da parte dell’esploratore
(“siete cavalieri o furfanti?”), e in questo caso
A risponde: “siamo tutti furfanti”, mentre
B risponde: “solo uno di noi e’ un cavaliere”
Chi e’ cavaliere e chi furfante?.
Ovviamente attendo che qualcuno provi a rispondere.
OK jack.
Hai capito perfettamente.
Mi auguro che tu segua anche i prossimi problemi
(che saranno piu' difficili)
Hai capito perfettamente.
Mi auguro che tu segua anche i prossimi problemi
(che saranno piu' difficili)
beh, diciamo che aB è accettabile perchè la condizione iniziale è quella dell' or esclusivo; mi spiego meglio: chi parla ha detto "io sono un furfante o, in alternativa, lui è un cavaliere", e questa frase si traduce logicamente con un "xor", il che vuol dire che le due condizioni (cioè che il primo è furfante e il secondo è cavaliere),non possono accadere contemporaneamente....ma qua arriva la svolta: se chi parla è un mentitore, allora la condizione sopra detta non vale, o perlomeno è possibile che il primo sia furfante e contemporaneamente il secondo sia cavaliere, cosa che infatti accade...
spero che questa sia una buona giustificazione....comunque trovare empiricamente questa soluzione era piuttosto difficile(da quello che ho capito nemmeno smullyan l' aveva scritta...), e immagino che qua si veda la potenza del metodo algebrico...
spero che questa sia una buona giustificazione....comunque trovare empiricamente questa soluzione era piuttosto difficile(da quello che ho capito nemmeno smullyan l' aveva scritta...), e immagino che qua si veda la potenza del metodo algebrico...
Giusto.
Ma vorrei anche un commento sulle soluzioni.
Che possano essere 2 cavalieri (AB) va bene
(e' la soluzione di Smullyan), ma (aB)?
Prova a confrontarla con l'effettiva risposta
data dal 'furfante a': “io sono un furfante o,
in alternativa, lui e’ un cavaliere”.
Non trovi niente di strano? Come si giustifica?
Ma vorrei anche un commento sulle soluzioni.
Che possano essere 2 cavalieri (AB) va bene
(e' la soluzione di Smullyan), ma (aB)?
Prova a confrontarla con l'effettiva risposta
data dal 'furfante a': “io sono un furfante o,
in alternativa, lui e’ un cavaliere”.
Non trovi niente di strano? Come si giustifica?
quindi le soluzioni sarebbero aB e AB...cioè quelle ottenute da
A(ab+AB)+a[ab+AB]...
A(ab+AB)+a[ab+AB]...
Andiamo con ordine.
Giustamente dici che la risposta e' un or esclusivo (a xor B),
ma l'equivalente di questo, in soli termini di operazioni primarie
(not,and,or), e' (ab+AB), quindi questa e' l'espressione
corrispondente alla risposta (bastava sviluppare algebricamente
il prodotto dell'ultimo tuo post).
Giustamente dici che la risposta e' un or esclusivo (a xor B),
ma l'equivalente di questo, in soli termini di operazioni primarie
(not,and,or), e' (ab+AB), quindi questa e' l'espressione
corrispondente alla risposta (bastava sviluppare algebricamente
il prodotto dell'ultimo tuo post).
forse ci sono: posso scrivere la condizione sopra detta come
(a+B)(A+b), e facendo al calcolatore questo prodotto ottengo come soluzioni
ab
AB
Adesso sostituisco ognuna di queste due soluzioni nella soluzione generale del probelma, ottenende
A(ab)+a[ab]
A(AB)+a[AB]
da cui otteniamo per la prima aB, per la seconda ab AB aB...quindi in pratica le soluzioni possibili sono tre: ab Ab aB.
eh sì, c'è qualcosa che non quadra...le soluzioni non dovevano essere due?...
(a+B)(A+b), e facendo al calcolatore questo prodotto ottengo come soluzioni
ab
AB
Adesso sostituisco ognuna di queste due soluzioni nella soluzione generale del probelma, ottenende
A(ab)+a[ab]
A(AB)+a[AB]
da cui otteniamo per la prima aB, per la seconda ab AB aB...quindi in pratica le soluzioni possibili sono tre: ab Ab aB.
eh sì, c'è qualcosa che non quadra...le soluzioni non dovevano essere due?...
dunque...a giudicare dalla affermazione, mi pare che la disgiunzione "o" sia esclusiva, per cui penso potremmo tradurre algebricamente la condizione come (a+B)and[aB];
a questo punto basta mettere questa risposta nella soluzione genrale e otteniamo i valori di verità....l' unico problemino è che con l'SPL si può mettere solo un livello di parentesi e non è ammesso l' and fra parentesi....però so che questi problemi si possono evitare...devo solo prendere più prstica col programma...spero di riuscire a dare le soluzioni...
a questo punto basta mettere questa risposta nella soluzione genrale e otteniamo i valori di verità....l' unico problemino è che con l'SPL si può mettere solo un livello di parentesi e non è ammesso l' and fra parentesi....però so che questi problemi si possono evitare...devo solo prendere più prstica col programma...spero di riuscire a dare le soluzioni...
Le soluzioni dei problemi del 7/12 sono facilmente
ottenibili seguendo la struttura dell’espressione
logica indicata, e ponendo le singole risposte in
termini booleani.
Risp.1: “Almeno uno di noi e’ un furfante”...........-> a+b
Risp.2: “Siamo due furfanti”........................ -> ab
Risp.3: “Io sono un furfante o lui e’ un cavaliere”..-> a+B
Quindi le espressioni risolventi sono rispettivamente:
R1 = A(a+b)+a[a+b]
R2 = A(ab)+a[ab]
R3 = A(a+B)+a[a+B]
Con il programma SPL si ottengono poi le soluzioni:
A...B.....R1..R2..R3
0...0.....0...0...0
1...0.....1...0...0
0...1.....0...1...0
1...1.....0...0...1
che si interpretano:
R1 = Ab (il primo e’ un cavaliere, l’altro un furfante)
R2 = aB (il primo e’ un furfante, l’altro un cavaliere)
R3 = AB (sono entrambi cavalieri)
Mentre questi casi danno per ciascuno una sola soluzione,
e’ evidente che ci possono essere risposte che ammettono
piu’ alternative.
Fra queste c’e’ il problema di Smullyan n.29 (pag.21), in
cui la risposta del primo e’: “io sono un furfante o,
in alternativa, lui e’ un cavaliere”.
A dire il vero, Smullyan da’ una sola soluzione (lunga
un’intera pagina), ed io mi sono alquanto sorpreso quando,
applicando l’SPL, ho ottenuto una seconda possibile soluzione.
Ma mi sono reso conto che il calcolatore....aveva ragione!
C’e’ qualcuno che trova (e giustifica) le due soluzioni?
ottenibili seguendo la struttura dell’espressione
logica indicata, e ponendo le singole risposte in
termini booleani.
Risp.1: “Almeno uno di noi e’ un furfante”...........-> a+b
Risp.2: “Siamo due furfanti”........................ -> ab
Risp.3: “Io sono un furfante o lui e’ un cavaliere”..-> a+B
Quindi le espressioni risolventi sono rispettivamente:
R1 = A(a+b)+a[a+b]
R2 = A(ab)+a[ab]
R3 = A(a+B)+a[a+B]
Con il programma SPL si ottengono poi le soluzioni:
A...B.....R1..R2..R3
0...0.....0...0...0
1...0.....1...0...0
0...1.....0...1...0
1...1.....0...0...1
che si interpretano:
R1 = Ab (il primo e’ un cavaliere, l’altro un furfante)
R2 = aB (il primo e’ un furfante, l’altro un cavaliere)
R3 = AB (sono entrambi cavalieri)
Mentre questi casi danno per ciascuno una sola soluzione,
e’ evidente che ci possono essere risposte che ammettono
piu’ alternative.
Fra queste c’e’ il problema di Smullyan n.29 (pag.21), in
cui la risposta del primo e’: “io sono un furfante o,
in alternativa, lui e’ un cavaliere”.
A dire il vero, Smullyan da’ una sola soluzione (lunga
un’intera pagina), ed io mi sono alquanto sorpreso quando,
applicando l’SPL, ho ottenuto una seconda possibile soluzione.
Ma mi sono reso conto che il calcolatore....aveva ragione!
C’e’ qualcuno che trova (e giustifica) le due soluzioni?
correggo subito...ecco fatto...
(risposta a jack)
La procedura algebrica comincia a funzionare.
Dobbiamo pero' essere d'accordo sulle convenzioni.
Io ho proposto di indicare i cavalieri con le lettere
maiuscole (e ovviamente i furfanti con le corrispondenti
minuscole).
Questa convenzione deve valere anche nelle risposte...
(mentre tu l'hai scambiata per il secondo)
Comunque complimenti per i progressi.
La procedura algebrica comincia a funzionare.
Dobbiamo pero' essere d'accordo sulle convenzioni.
Io ho proposto di indicare i cavalieri con le lettere
maiuscole (e ovviamente i furfanti con le corrispondenti
minuscole).
Questa convenzione deve valere anche nelle risposte...
(mentre tu l'hai scambiata per il secondo)
Comunque complimenti per i progressi.
ora che ci penso...per il secondo, la risposta è ab,da cui otteniamo
A(ab)+a[ab], e sempre usando il calcolatore booleano, ottengo aB, cioè chi parla è un mentitore e l' altro è un cavaliere...
caspita, era così facile che mi pareva difficile....coincidentia oppositorum...
A(ab)+a[ab], e sempre usando il calcolatore booleano, ottengo aB, cioè chi parla è un mentitore e l' altro è un cavaliere...
caspita, era così facile che mi pareva difficile....coincidentia oppositorum...
dunque, vediamo se ho capito...per esempio la terza condizione la possiamo tradurre con a+B, e quindi la soluzione diventa A(a+B)+a[a+B], che ha come risultato AB, cioè tutti e due sono cavalieri...ci ho messo un po' ma spero il ragionameno sia giusto...ah, per il calcolo squisitamente booleano ho ovviamente usato il programma SPL...
(risposta a jack e JvloIvk)
Vedo che l'approccio algebrico sembra risultare piu'
faticoso di quanto esso sia in realta'.
Quindi cerco di fare un ragionamento elementare per
convincervi che in realta' e' semplice da applicare,
piu' semplice che fare deduzioni dirette dagli enunciati.
Consideriamo il primo problema:
La risposta e' "almeno uno di noi e' un furfante"
quindi vuol dire che indica 3 possibilita', cioe'
aB (il primo furfante, il secondo cavaliere)
Ab (il primo cavaliere, il secondo furfante)
ab (entrambi furfanti).
Ma aB+Ab+ab = a+b, quindi questa e' la conversione
della risposta in termini booleani.
Pero' non e' finita. Il contesto del problema dice
che questa risposta e' valida solo se chi la da' e'
un cavaliere (A), altrimenti (cioe' se fosse un
furfante, quindi a) varrebbe il suo contrario.
Abbiamo gia' visto che questo comporta l'espressione
(A and (risposta)) or (a and not(risposta))
quindi e' elementare scrivere A(a+b)+ a[a+b]
(la parentesi quadra rappresenta la negazione del contenuto,
quindi, applicando DeMorgan, e' [a+b]=AB ).
In definitiva la soluzione 'algebrica' risulta
A(a+b)+a(AB) che chiaramente da' come risultato Ab
Tutti gli altri termini sono 'nulli' (=0, quindi 'falsi')
La soluzione e' quindi che il primo e' un cavaliere, il secondo
un furfante.
Su questa traccia, vi chiedo di risolvere gli altri 2 problemi
Vedo che l'approccio algebrico sembra risultare piu'
faticoso di quanto esso sia in realta'.
Quindi cerco di fare un ragionamento elementare per
convincervi che in realta' e' semplice da applicare,
piu' semplice che fare deduzioni dirette dagli enunciati.
Consideriamo il primo problema:
La risposta e' "almeno uno di noi e' un furfante"
quindi vuol dire che indica 3 possibilita', cioe'
aB (il primo furfante, il secondo cavaliere)
Ab (il primo cavaliere, il secondo furfante)
ab (entrambi furfanti).
Ma aB+Ab+ab = a+b, quindi questa e' la conversione
della risposta in termini booleani.
Pero' non e' finita. Il contesto del problema dice
che questa risposta e' valida solo se chi la da' e'
un cavaliere (A), altrimenti (cioe' se fosse un
furfante, quindi a) varrebbe il suo contrario.
Abbiamo gia' visto che questo comporta l'espressione
(A and (risposta)) or (a and not(risposta))
quindi e' elementare scrivere A(a+b)+ a[a+b]
(la parentesi quadra rappresenta la negazione del contenuto,
quindi, applicando DeMorgan, e' [a+b]=AB ).
In definitiva la soluzione 'algebrica' risulta
A(a+b)+a(AB) che chiaramente da' come risultato Ab
Tutti gli altri termini sono 'nulli' (=0, quindi 'falsi')
La soluzione e' quindi che il primo e' un cavaliere, il secondo
un furfante.
Su questa traccia, vi chiedo di risolvere gli altri 2 problemi
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo