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
Per il secondo caso, basta ipotizzare che chi parla non può essere un cavaliere,perchè altrimetni mentirebbe su se stesso, e quindi necessariamente il secondo deve essere cavaliere,se no il primo direbbe una verità...per il terzo invece, per la regola di smisteru, la negazione di una delle due proposizioni implica la verità dell' altra:per esempio se scegliamo di negare "Lui è un cavaliere", vuol dire che chi parla è un furfante,che dicendo appunto "Io sono un furfante o lui è un cavaliere" dice però una verità, per cui questa ipotesi è da scartare;se invece neghiamo "io sono un furfante" allora rendiamo vera "lui è un cavaliere", e poichè abbiamo ipotizzato che chi parli dica la verità, allora non si creano contraddizioni nell' affermare che in questo caso entrambi i personaggi sono cavalieri...
il problema è che bisogna risolvere la questione con le operazioni dell' aritmetica booleana, anche se viene naturale andare a senso...
il problema è che bisogna risolvere la questione con le operazioni dell' aritmetica booleana, anche se viene naturale andare a senso...
Per la prima basta considerare tutto il ragionamento precedente e scartare il caso in cui sono tutti e due cavalieri
Non mi ero accorto delle varianti al problema...
Risolverli per via empirica è piuttosto facile, basta ipotizzare che il primo dica la verità, vedere se ciò che dice può essere conforme a ciò che è, e quindi valutare se il primo è mentitore o no, e dopo sappiamo anche ciò che è il secondo...
Ma a parte questo metodo, usare quello booleano, mi si è rivelato ostico, o quanto meno intricato...ad esempio, la prima risposta la possiamo tradurre con (A and B)xor(B and B)?
Risolverli per via empirica è piuttosto facile, basta ipotizzare che il primo dica la verità, vedere se ciò che dice può essere conforme a ciò che è, e quindi valutare se il primo è mentitore o no, e dopo sappiamo anche ciò che è il secondo...
Ma a parte questo metodo, usare quello booleano, mi si è rivelato ostico, o quanto meno intricato...ad esempio, la prima risposta la possiamo tradurre con (A and B)xor(B and B)?
Non ho ricevuto finora alcuna soluzione degli ultimi 3 problemi.
C'e' difficolta'?
Mi sembra che seguendo il metodo illustrato nell'ultimo post
(e conoscendo le regole dell'algebra booleana), non
dovrebbe essere poi cosi' difficile rispondere.
Attendo ancora qualche giorno prima di dare le soluzioni.
C'e' difficolta'?
Mi sembra che seguendo il metodo illustrato nell'ultimo post
(e conoscendo le regole dell'algebra booleana), non
dovrebbe essere poi cosi' difficile rispondere.
Attendo ancora qualche giorno prima di dare le soluzioni.
Scusatemi se sono noioso e riprendo osservazioni gia’ fatte.
I problemi finora trattati sono elementari quindi, bene o male,
con un po’ di ragionamento ed un po’ d’intuizione, si puo’
comunque arrivare alla soluzione.
Nelle soluzioni pervenute non trovo pero’ l’utilizzo dell’algebra
booleana, cosi' come (ne sono certo) fareste nella soluzione
algebrica di un problema numerico.
Questo e’ l’obbiettivo, che ci consentira’ di affrontare problemi
ben piu’ complessi. Ed ecco l’approccio suggerito:
Il ragionamento che l’esploratore deve fare, date
le premesse del problema, e’ che se chi da’ la risposta
e’ un cavaliere (quindi A), allora la sua risposta e’ vera ma,
in caso contrario (quindi a=notA, se cioe’ e’ un furfante),
la verita’ e’ esattamente il contrario della risposta.
L’espressione booleana corrispondente a questa situazione
e’ quindi : (A and (risposta)) or (a and not(risposta)).
Tale struttura di espressione vale per qualsiasi risposta
che l’interpellato da’ (ovviamente tradotta a sua volta
in termini booleani).
Nel caso proposto, la risposta “io sono un furfante ma lui no”
e’ facilmente ‘traducibile’ in : (a and B) .
L’intera espressione, adottando le convenzioni proposte,
risulta quindi: A(aB)+a[aB].
Procedendo algebricamente, si nota che il primo termine e’
nullo (Aa=0), mentre il secondo (con un Nand rappresentato
dalla parentesi quadra) deve essere sviluppato applicando
DeMorgan in: a(A+b), quindi = ab
L’interpretazione del risultato e’ che i due sono entrambi
furfanti.
Con il programma SPL, la soluzione e’ immediata dopo
aver scritto l’espressione nel campo R1: l’attivazione
del pulsante laterale (Cond1), mostra la tabella con una
sola condizione vera (=1) in corrispondenza di A=0 e
B=0, il che significa che sono veri sia a che b.
Per dimostrare che il procedimento illustrato non e’
una perdita di tempo, ma una reale facilitazione,
propongo la soluzione di 3 altre possibili risposte
che l’interpellato avrebbe potuto dare.
Quindi, medesime premesse, ma differenti situazioni
(sono 3 diversi problemi).
Risp.1 “Almeno uno di noi e’ un furfante”
Risp.2 “Siamo due furfanti”
Risp.3 “Io sono un furfante o lui e’ un cavaliere”
Attendo le soluzioni.
I problemi finora trattati sono elementari quindi, bene o male,
con un po’ di ragionamento ed un po’ d’intuizione, si puo’
comunque arrivare alla soluzione.
Nelle soluzioni pervenute non trovo pero’ l’utilizzo dell’algebra
booleana, cosi' come (ne sono certo) fareste nella soluzione
algebrica di un problema numerico.
Questo e’ l’obbiettivo, che ci consentira’ di affrontare problemi
ben piu’ complessi. Ed ecco l’approccio suggerito:
Il ragionamento che l’esploratore deve fare, date
le premesse del problema, e’ che se chi da’ la risposta
e’ un cavaliere (quindi A), allora la sua risposta e’ vera ma,
in caso contrario (quindi a=notA, se cioe’ e’ un furfante),
la verita’ e’ esattamente il contrario della risposta.
L’espressione booleana corrispondente a questa situazione
e’ quindi : (A and (risposta)) or (a and not(risposta)).
Tale struttura di espressione vale per qualsiasi risposta
che l’interpellato da’ (ovviamente tradotta a sua volta
in termini booleani).
Nel caso proposto, la risposta “io sono un furfante ma lui no”
e’ facilmente ‘traducibile’ in : (a and B) .
L’intera espressione, adottando le convenzioni proposte,
risulta quindi: A(aB)+a[aB].
Procedendo algebricamente, si nota che il primo termine e’
nullo (Aa=0), mentre il secondo (con un Nand rappresentato
dalla parentesi quadra) deve essere sviluppato applicando
DeMorgan in: a(A+b), quindi = ab
L’interpretazione del risultato e’ che i due sono entrambi
furfanti.
Con il programma SPL, la soluzione e’ immediata dopo
aver scritto l’espressione nel campo R1: l’attivazione
del pulsante laterale (Cond1), mostra la tabella con una
sola condizione vera (=1) in corrispondenza di A=0 e
B=0, il che significa che sono veri sia a che b.
Per dimostrare che il procedimento illustrato non e’
una perdita di tempo, ma una reale facilitazione,
propongo la soluzione di 3 altre possibili risposte
che l’interpellato avrebbe potuto dare.
Quindi, medesime premesse, ma differenti situazioni
(sono 3 diversi problemi).
Risp.1 “Almeno uno di noi e’ un furfante”
Risp.2 “Siamo due furfanti”
Risp.3 “Io sono un furfante o lui e’ un cavaliere”
Attendo le soluzioni.
L'intero periodo è formato da 2 proposizioni collegate dal connettore logico e.Ho fatto la tabella di verità A e B con A la proposizone"io sono furfante" e con B "lui non lo è".
L'intero periodo A e B per le leggi della logica è vero SE E SOLO SE le proposizioni A e B sono entrambe vere(come puoi vedere dalla tabella).Ma se è vero che AeB è vero ed A pure ,allora quello che ha risposto per primo è contemporaneamente furfante(in quanto A è vera)e cavaliere(in quanto AeB è vera).Quindi AeB è necessariamente falsa e il primo a rispondere è furfante.La proposizione A è quindi vera e dalla tabella si nota che anche B è un bugiardo
L'intero periodo A e B per le leggi della logica è vero SE E SOLO SE le proposizioni A e B sono entrambe vere(come puoi vedere dalla tabella).Ma se è vero che AeB è vero ed A pure ,allora quello che ha risposto per primo è contemporaneamente furfante(in quanto A è vera)e cavaliere(in quanto AeB è vera).Quindi AeB è necessariamente falsa e il primo a rispondere è furfante.La proposizione A è quindi vera e dalla tabella si nota che anche B è un bugiardo
(risposta n.3 a JvloIvk)
La soluzione e' ora corretta, ma francamente
non ho capito la procedura che hai seguito.
La soluzione e' ora corretta, ma francamente
non ho capito la procedura che hai seguito.
so che a prima vista sembra impossibile che tutti e due siano mentitori, però se ci pensi bene, devi considerare falsa una frase dove anche una sola proposizione di esse è falsa; nel nostro caso, avevi una frase formata da due proposizioni, ti basta verificare che una sia falsa per capire che l' intero periodo sia falso...insomma se una frase non è vera allora è....falsa
ps:io avrei indicato con 1 chi parla, con 2 il secondo uomo e con Valore, la verità dell' affermazione(non so se è una tavola di verità, però aiuta...):
1 2 Valore
A A F
A B F
B A F
B B V
ps:io avrei indicato con 1 chi parla, con 2 il secondo uomo e con Valore, la verità dell' affermazione(non so se è una tavola di verità, però aiuta...):
1 2 Valore
A A F
A B F
B A F
B B V
Quello che nn ho chiara è se i 2 possono essere entrambi furfanti o cavalieri.
La tavola della verità A e B è:
A B AeB
V V V
V F F
F V F
F F F
Se Ae B è vera significa che il primo a rispondere è cavaliere,ma anche che la preposizione A è vera e ciò è impossibile
Se Ae B è falsa significa che il primo a rispondere è furfante per cui A è necessariamente vera.
Morale:nella tabella la riga "giusta è la 2°"
A è furfante e B pure[:D].
La tavola della verità A e B è:
A B AeB
V V V
V F F
F V F
F F F
Se Ae B è vera significa che il primo a rispondere è cavaliere,ma anche che la preposizione A è vera e ciò è impossibile
Se Ae B è falsa significa che il primo a rispondere è furfante per cui A è necessariamente vera.
Morale:nella tabella la riga "giusta è la 2°"
A è furfante e B pure[:D].
(risposta a jack)
Bravo! Ma prova ad usare il metodo algebrico,
perche' i problemi diventeranno sempre piu' complicati.
Domani daro' la procedura consigliata.
Bravo! Ma prova ad usare il metodo algebrico,
perche' i problemi diventeranno sempre piu' complicati.
Domani daro' la procedura consigliata.
forse ci sono....se poniamo che chi parla dice il falso, allora potremmo scrivere la sua affermazione come not(a and b) si possa riscrivere, con la legge di de morgan, come not(not(A or B)), da cui (A or B), cioè o il primo è un cavaliere o il secondo è un mentitore(o tutte e due); adesso secondo me, anzi secondo smisteru, se si nega una delle due possibilità(A o B), allora si afferma l' altra, però se neghiamo B, allora chi parla deve essere veritiero, ma allora mentirebbe su se stesso,quindi dobbiamo negare A, cioè B è effettivamente un furfante, il che contrasta con la versione del primo, che automaticamente diventa un bugiardo anch' esso....
penso che in questo problema per essere bugiardi basta dire anche una sola falsità, e mi pare sia questa la cosa fondamentale da capire...o almeno spero che sia così...
penso che in questo problema per essere bugiardi basta dire anche una sola falsità, e mi pare sia questa la cosa fondamentale da capire...o almeno spero che sia così...
(risposta n.2 a IvloIvk)
Un consiglio: rileggi con calma il problema....
Gli abitanti incontrati dall'esploratore sono 2,
e ciascuno di loro puo' essere o un cavaliere o,
in alternativa, un furfante.
Si chiede 'la qualifica' sia del primo (quello
che risponde) che del secondo.
Un consiglio: rileggi con calma il problema....
Gli abitanti incontrati dall'esploratore sono 2,
e ciascuno di loro puo' essere o un cavaliere o,
in alternativa, un furfante.
Si chiede 'la qualifica' sia del primo (quello
che risponde) che del secondo.
io stavo pensando che entrambi gli uomini sono mentitori...ma dimostrarlo è un po' complicato...
Scusa ho sbagliato a scrivere l'ultimo topic...Cmq l'idea è sempre la stessa.La contraddizione è:
A e nonA
A e nonA
(risposta a IvloIvk)
No, non l'hai azzeccata.
Mi sembra che tu tratti la cosa con sufficienza
(i soliti problemi...) e, come Maverik, snobbi
l'argomento come troppo elementare.
Quello che constato e' che nessuno affronta i
problemi usando l'algebra booleana per arrivare
alle soluzioni (che e' il vero scopo di questo topic).
No, non l'hai azzeccata.
Mi sembra che tu tratti la cosa con sufficienza
(i soliti problemi...) e, come Maverik, snobbi
l'argomento come troppo elementare.
Quello che constato e' che nessuno affronta i
problemi usando l'algebra booleana per arrivare
alle soluzioni (che e' il vero scopo di questo topic).
In effetti è possibile dimostare a prescindere da questi esempi che date 2 preposizioni A e B
non(A e nonB) è una tautologia
e quindi A e nonB una contraddizione
non(A e nonB) è una tautologia
e quindi A e nonB una contraddizione
I soliti problemi che compaiono alle olimpiadi...
Consideriamo i 2 casi distiti:
A dice la verità
A non dice l verità
Se A dicesse la verità dovrebbero essere entrambe le proposizioni"io sn furfante" e "lui non lo è" vere.Ma il fatto che lui è furfante implica necessariamente che lui nn può dire la verità.
Ma se A dicesse il falso significherebbe che lui lui è cavaliere ,cosa che non può essere visto che ha detto una bugia.
Mi sa di impossibile
Consideriamo i 2 casi distiti:
A dice la verità
A non dice l verità
Se A dicesse la verità dovrebbero essere entrambe le proposizioni"io sn furfante" e "lui non lo è" vere.Ma il fatto che lui è furfante implica necessariamente che lui nn può dire la verità.
Ma se A dicesse il falso significherebbe che lui lui è cavaliere ,cosa che non può essere visto che ha detto una bugia.
Mi sa di impossibile
La fertile fantasia di Smullyan (professore di Logica
in Universita’ americane) ha immaginato l’esistenza
di un’isola su cui vivono solo due sole specie di abitanti,
indistinguibili fra loro, ma che hanno questa caratteristica:
gli uni (cavalieri) dicono sempre la verita’, mentre gli altri
(furfanti) mentono sempre.
Un esploratore che visita l’isola incontra degli abitanti e
pone loro delle domande per identificarli.
Dalle domande e soprattutto dalle loro risposte, nasce tutta
una serie di problemi logici di piu’ o meno difficile soluzione.
Cominciamo da uno dei piu’ semplici.
Supponiamo che l’esploratore incontri due abitanti e
chieda loro “siete cavalieri o furfanti?” e che il primo
risponda “io sono un furfante, ma lui non lo e’ ”
(problema n. 33, a pag. 22).
L’esploratore puo’ stabilire chi e’ cavaliere e chi furfante?
Per chiarezza, diciamo che in base alle premesse, un furfante
e’ (booleanamente parlando) un non-cavaliere e che le risposte
sono “vere” se le da’ un cavaliere, ma se a darle e’ un furfante
la verita’ e’ esattamente il contrario della risposta stessa.
Per convenzione, e’ opportuno poi indicare il primo abitante
(quello che in questo caso da’ la risposta) con A se cavaliere
(e quindi a = not A , se furfante), ed il secondo rispettivamente
con B, (se cavaliere ) oppure b (se furfante).
Attendo le vostre soluzioni.
in Universita’ americane) ha immaginato l’esistenza
di un’isola su cui vivono solo due sole specie di abitanti,
indistinguibili fra loro, ma che hanno questa caratteristica:
gli uni (cavalieri) dicono sempre la verita’, mentre gli altri
(furfanti) mentono sempre.
Un esploratore che visita l’isola incontra degli abitanti e
pone loro delle domande per identificarli.
Dalle domande e soprattutto dalle loro risposte, nasce tutta
una serie di problemi logici di piu’ o meno difficile soluzione.
Cominciamo da uno dei piu’ semplici.
Supponiamo che l’esploratore incontri due abitanti e
chieda loro “siete cavalieri o furfanti?” e che il primo
risponda “io sono un furfante, ma lui non lo e’ ”
(problema n. 33, a pag. 22).
L’esploratore puo’ stabilire chi e’ cavaliere e chi furfante?
Per chiarezza, diciamo che in base alle premesse, un furfante
e’ (booleanamente parlando) un non-cavaliere e che le risposte
sono “vere” se le da’ un cavaliere, ma se a darle e’ un furfante
la verita’ e’ esattamente il contrario della risposta stessa.
Per convenzione, e’ opportuno poi indicare il primo abitante
(quello che in questo caso da’ la risposta) con A se cavaliere
(e quindi a = not A , se furfante), ed il secondo rispettivamente
con B, (se cavaliere ) oppure b (se furfante).
Attendo le vostre soluzioni.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo