Gioco di logica

Sono stato indeciso per qualche giorno se mettere questa discussione in relax o in informatica, ma poi, visto che è mia intenzione evolvere questa discussione in qualcosa che c'entra molto con l'informatica e con l'elettronica, ho finito per inserirla qui.

Sarà poi il buon Law a decidere eventualmente di spostarla, magara fra le paperogate, oppure no

Questo è un gioco di logica che risale alla fine degli anni '70. All'epoca stavano uscendo i primi computer per il grande pubblico. Uno dei miei migliori amici, non ricordo in quale occasione, si trovò davanti un computer in cui stava girando un gioco di logica, simile alla storia del lupo, della pecora e del cavolo.

Il quesito è questo:


Da una parte del fiume ci sono 3 missionari e 3 cannibali. Questi 6 personaggi devono attraversare il fiume, ma è disponibile solo una barca a remi in grado di portare 2 persone per volta.

Considerando che:

1)In qualsiasi momento e in qualsiasi lato del fiume i cannibali devono essere sempre in numero inferiore ai missionari (altrimenti ci sono ottime possibilità che i missionari vengano trasformati in un lauto pranzo).

2)La barca è a remi e deve sempre essere riportata indietro da qualcuno per potere caricare le persone successive (pur essendo in un forum di tecnologie non esistono telecomandi e neppure corde per trascinare la barca.......solo la buona, vecchia ed efficiente forza di braccia sui remi).

...trovare la sequenza dei movimenti per trasferire tutte le 6 persone dalla parte opposta del fiume.

Chi indovinerà la sequenza corretta verrà premiato con un pranzo a base di missionario scampato al cannibale (visto che era già stato dato per perso alla 2° mossa).

Buon divertimento

Bene, complimenti a Frak® perchè ha scoperto la soluzione del gioco.

In realtà questo gioco mi serviva per introdurre un'applicazione dell'elettronica digitale: la cosiddetta logica combinatoria.

Un circuito in logica combinatoria è un circuito digitale (quindi in grado di elaborare solo i livelli logici 0 e 1) in cui le uscite dipendono direttamente dallo stato degli ingressi, indipendentemente da altre condizioni particolari.
Ebbene consideriamo di volere progettare un circuito in grado di fornire un allarme (accendendo, ad esempio, una spia luminosa) quando nel gioco precedente c'è almeno un missionario che rischia di venire mangiato dai cannibali.

Consideriamo quindi di avere un circuito con 6 ingressi; 3 li chiamiamo M1, M2 e M3 (M sta per missionario) e i restanti C1, C2 e C3 (C sta per cannibale).
Ora consideriamo inoltre che l'ingresso sia a 1 in caso di presenza del relativo personaggio (cannibale o missionario); lo 0 indica, ovviamente, che il personaggio corrispondente non è presente (quindi si trova sulla barca o sull'altra sponda del fiume).

Per gestire correttamente l'allarme occorreranno 2 circuiti identici, uno per la sponda sinistra e l'altro per quella destra del fiume.

Per progettare questo circuito occorrerà innanzi tutto scrivere la cosiddetta tabella della verità, ovvero la tabella che lega gli ingressi alle uscite:



Questa tabella della verità sembra particolarmente complessa, invece è in realtà semplice. Per ogni riga vengono contati i 3 bit più a sinistra (colonne M1, M2 e M3) e confrontati in numero con quello corrispondenti alle colonne C1, C2 e C3.
Se i bit a 1 di C1,C2 e C3 sono in quantità maggiore rispetto a quelli delle colonne M1, M2 e M2, l'uscita di allarme ALM va a 1. In tutti gli altri casi (quelli in cui C1,C2, e C3 sono in quantità inferiore o uguale a quelli delle colonne M1, M2 e M3) l'uscita ALM è a 0.

Per maggiore chiarezza ho messo delle frecce in corrispondenza delle condizioni con ALM = 1.

Nella prossima puntata spiegherò come fare a progettare la rete logica necessaria. Nel frattempo verificate anche voi che la tabella della verità non sia concettualmente sbagliata.

SEGUE....

Forse sì, ma al posto dei cannibali e i missionari c'erano le ammoniti e i T-rex....
Chiamatemi Celacanto , visto che praticamente sono diventato un fossile vivente.

Beh, la logica combinatoria ha una sua.......logica (che brutta questa ). Se la si capisce le cose sono semplici da risolvere, altrimenti.....no.

Innanzi tutto il modo digitale, al contrario di quello analogico dove una tensione/corrente può variare con continuità da un minimo ad un massimo, lavora con solo 2 tensioni (o, per essere più precisi, con 2 fasce di tensioni) che vengono chiamate 0 quando la tensione è al di sotto di un certo valore o 1 se la tensione è al di sopra di un altro valore (talvolta i 2 valori di 0 e 1 coincidono). Se il valore della tensione è compreso fra la soglia dello 0 e dell'1 si entra nella fascia di incertezza che può creare malfunzionamenti.
Generalmente si considera 1 quando un ingresso è collegato alla tensione positiva che alimenta la rete logica, mentre 0 quando è collegata alla massa (0V) dell'alimentazione (oppure anche quando è scollegata, operazione non sempre praticabile perchè potrebbe generare malfunzionamenti causati da disturbi elettrici, ma questo è un altro discorso che eventualmente affronteremo più avanti).

Le reti logiche sono sostanzialmente di 2 tipi: combinatorie o sequenziali.

Le combinatorie sono quelle in cui le uscite sono direttamente dipendenti dallo stato degli ingressi, indipendentemente da ciò che è successo in precedenza.
Pensando all'impianto d'illuminazione di una casa una possibile rete logica potrebbe essere quella che accende una lampadina quando 2 interruttori sono entrambi accesi (lo so, ci sarebbe da lapidare l'elettricista che l'ha fatto, ma è per fare un esempio).
Praticamente ogni volta che i 2 interruttori sono entrambi a 1 (posizione di acceso) l'uscita (lampadina) va a 1 e si accende.
Le reti combinatorie sono composte di sole porte logiche (NOT, OR, AND, ecc.)

Le sequenziali sono quelle in cui le uscite sono dipendenti non solo dallo stato degli ingressi, ma anche dallo stato precedente di una o più uscite/nodi (sono uscite se possono essere usate dall'esterno della rete logica oppure nodi se sono utilizzabili solo dalla stessa rete logica, ma che non fanno capo a vere e proprie uscite).
Sempre per fare un esempio di un impianto di illuminazione potremmo pensare ad una stanza in cui le luci possono essere comandate da N pulsanti posti su varie pareti. In questo caso si usa un relè passo-passo che, ad ogni impulso ricevuto da uno dei pulsanti, inverte lo stato della lampada, da acceso a spento e viceversa.
In questo caso si tratta di una logica sequenziale perchè ogni pulsante (ingresso) non ha una funzione ben specifica, ma provoca un risultato dipendente dallo stato precedente.
Queste reti sono composte sia da porte logiche sia da blocchi che memorizzano i segnali digitali (Flip-flop)

Prima di passare alla ormai famigerata rete logica combinatoria di cui ho parlato in precedenza occorre parlare delle cosiddette porte logiche.
Le porte logiche sono dei circuiti dotati di N ingressi e un'uscita che sono legati da una certa funzione logico-matematica che provoca quella che prima ho chiamato (perchè così si chiama) tabella della verità.

La tabella della verità rappresenta ciò che accade ad una porta (oppure ad una rete dotata di più uscite) logica quando gli ingressi assumono gli stati logici. E' praticamente una tabella in cui sono riportati gli ingressi e le uscite e i relativi stati logici.

Potrei a questo punto sostituirmi a Wikipedia, disegnandomi le porte logiche e le relative tabelle della verità, ma mi sembrerebbe di fare una trattazione sull'acqua calda, per questo vi consiglio di leggere QUI

Per indicare le funzioni delle porte logiche non esistono standard riconosciuti da tutti, ma spesso si usano i seguenti simboli:
NOT = ! esempio: B = !A è uguale a scrivere B = NOT A, quindi se A = 0 -> B=1 e viceversa
AND = & esempio: C = A & B è uguale a scrivere C = A AND B, quindi se A=B=1 -> C=1, in tutti gli altri casi C=0
OR = # esempio: C = A # B è uguale a scrivere C = A OR B, quindi C=1 se A, B o entrambi sono uguali a 1. Se A e B sono entrambi = 0 anche C=0
XOR = $ esempio: C = A $ B è uguale a scrivere C = A XOR B, quindi se A e B sono diversi C=1, se sono uguali C=0

Tornando alla tabella della verità precedente e considerando che non abbia sbagliato a compilarla sorge una domanda? "Come faccio a trasformare quella tabella in una rete logica che mi generi il famoso allarme di missionario in pericolo?"

I metodi normalmente utilizzati sono 2 (non so se ce ne siano altri, ma io ho sempre usato solo questi): metodo dei mintermini e metodo delle mappe di Karnaugh.
Il secondo è quello che uso più spesso perchè generalmente porta a reti logiche più semplici a parità di tabella della verità, ma ha il limite di diventare decisamente complesso quando si superano i 4 ingressi.
In questo caso userò quindi il sistema dei mintermini, ripromettendomi di fare qualche esempio più avanti anche di uso delle mappe di Karnaugh.
Potrebbe essere interessante se a qualcuno venisse in mente un qualche problema che possa essere gestito con una logica combinatoria, così potremmo fare qualche altro esercizio.

I mintermini, se si vuole andare a leggere su Wikipedia, sono praticamente delle combinazioni di N ingressi della tabella della verità che portano come risultato sull'uscita 1. Non sono quindi mintermini quelli corrispondenti allo stato dell'uscita 0.
Quando l'altro giorno ho inserito delle frecce per evidenziare le condizioni di uscita (ALM) = 1 non solo mi serviva per sottolineare la condizione di allarme, ma anche la riga in cui sono contenuti i mintermini.

Il metodo dei mintermini è più difficile da descrivere a parole che da calcolare, ma ci provo lo stesso.
Per ogni mintermine occorre considerare una porta logica AND con tanti ingressi quanti sono quelli della tabella della verità. Nel nostro caso serve quindi una porta AND a 6 ingressi per ogni mintermine.
Bene, ora sugli ingressi della porta AND andranno portati i livelli logici di C1-C3 e M1-M3, considerando che gli ingressi saranno portati direttamente se sono a 1 e negati (quindi invertite di livello perchè passanti attraverso un NOT) se sono a 0.

Prendendo, ad esempio, il mintermine della riga Num.8, in cui gli ingressi sono 0 0 0 1 0 0 l'AND sarà composto dalla seguente formula:
ALM Num8 = !M1 & !M2 & !M3 & C1 & !C2 & !C3

Analogamente andrà scritta la formula per i restanti mintermini:
ALM Num16 = !M1 & !M2 & !M3 & !C1 & C2 & !C3
ALM Num24 = !M1 & !M2 & !M3 & C1 & C2 & !C3
ALM Num25 = M1 & !M2 & !M3 & C1 & C2 & !C3
ALM Num26 = !M1 & M2 & !M3 & C1 & C2 & !C3
ALM Num28 = !M1 & !M2 & M3 & C1 & C2 & !C3
ALM Num32 = !M1 & !M2 & !M3 & !C1 & !C2 & C3
ALM Num40 = !M1 & !M2 & !M3 & C1 & !C2 & C3
ALM Num41 = M1 & !M2 & !M3 & C1 & !C2 & C3
ALM Num42 = !M1 & M2 & !M3 & C1 & !C2 & C3
ALM Num44 = !M1 & !M2 & M3 & C1 & !C2 & C3
ALM Num48 = !M1 & !M2 & !M3 & !C1 & C2 & C3
ALM Num49 = M1 & !M2 & !M3 & !C1 & C2 & C3
ALM Num50 = !M1 & M2 & !M3 & !C1 & C2 & C3
ALM Num52 = !M1 & !M2 & M3 & !C1 & C2 & C3
ALM Num56 = !M1 & !M2 & !M3 & C1 & C2 & C3
ALM Num57 = M1 & !M2 & !M3 & C1 & C2 & C3
ALM Num58 = !M1 & M2 & !M3 & C1 & C2 & C3
ALM Num59 = M1 & M2 & !M3 & C1 & C2 & C3
ALM Num60 = !M1 & !M2 & M3 & C1 & C2 & C3
ALM Num61 = M1 & !M2 & M3 & C1 & C2 & C3
ALM Num62 = !M1 & M2 & M3 & C1 & C2 & C3

Bene, in totale ho 23 porte AND a 6 ingressi che mi danno ognuna l'uscita di un mintermine. Cosa ne faccio di queste 23 uscite?
Dato che una qualsiasi di esse, quando è a 1, mi deve fornire 1 sull'uscita ALM, le colleghiamo ad una porta OR a 23 ingressi.
L'uscita della porta OR darà finalmente la nostra uscita di ALM, tanto desiderata.
In totale, per fare questa rete logica, avremo usato 6 porte NOT, 23 porte AND a 6 ingressi e 1 porta OR a 23 ingressi.

Certo, il discorso è tutt'altro che comodo, soprattutto se si usano dei normali circuiti integrati contenenti porte logiche, ma usando questo sistema con le cosiddette logiche programmabili (PAL, GAL, ecc.) il discorso diventa facile da gestire.

Per il momento vi lascio digerire quanto ho scritto, ma il discorso non è finito. Se volete fare domande sono a vostra disposizione.

SEGUE......

Hai ragione, Ele, effettivamente sarebbe più "logico" (troppa logica che si sovrappone) usare gli operatori come hai detto tu, che rappresenterebbero poi la versione matematica dell'algebra di Bool;.
Per gli esempi ho preso come convenzioni un programma di Atmel (ormai Microchip), chiamato WinCupl che serve per creare i programmi interni alle PAL/GAL partendo da un testo che esprime le funzioni logiche da implementare al suo interno.
WinCupl avrebbe anche il simulatore, ma non è un granchè.

A proposito di circuiti logici: c'è un sito dove puoi simulare dei circuiti con porte logiche, flip-flop ed altro, a scopo didattico. Ci sono vari esempi, come quello de contatore (un classico) ed altri che ancora non ho guardato. Il link è questo

Comunque ero quasi certo che saresti intervenuto, visto che questo è il tuo pane e sicuramente hai più esperienza di me su questo argomento