Scuola Interuniversitaria Lombarda di Specializzazione

per l’Insegnamento Secondario – Sezione di Milano

Indirizzo Fisico-Informatico-Matematico

Classe di abilitazione A042 – INFORMATICA

Relazione Finale di Tirocinio

INTRODUZIONE ALLA LOGICA

Docente universitario: Prof. Silvio GHILARDI

Insegnante supervisore: Prof. Paolo BARAGGIA

Specializzanda: Giuseppa TRABACCA

Matricola Y02099

Anno Accademico 2004/2005

Indice

1. Introduzione..........................................................................................................................3

2. Tirocinio osservativo e tirocinio attivo.................................................................................3

Il tirocinio osservativo..........................................................................................................3

La lezione tenuta in classe: prerequisiti, obiettivi, tempi......................................................4

UD 1 : Situazione-stimolo e prime definizioni.....................................................................5

UD 2 : Espressioni logiche, proprietà, soluzione del gioco..................................................6

Verifica, correzione, risultati................................................................................................7

3. Approfondimenti. Obiettivi, prerequisiti, tempi...................................................................7

UD 1 : Calcolo proposizionale e complessità – Problemi NP..............................................8

UD 2 : Uno strumento software per il problema SAT: la procedura DPLL e zChaff..........9

UD 3 : Equivalenza di alcuni formalismi...........................................................................11

UD 4 : La logica proposizionale e i circuiti elettronici – Esercizi......................................13

UD 5 : Equivalenza di circuiti............................................................................................16

Verifica...............................................................................................................................19

Bibliografia...............................................................................................................................20

ALLEGATO I: Verifica in classe.............................................................................................21

2

1.

2. Introduzione

Questo lavoro vuole ripercorrere l’esperienza di tirocinio che ho svolto durante i due anni

della SILSIS presso un istituto tecnico industriale e proporre alcuni spunti per invitare i

ragazzi a studiare la Logica in un’ottica più ampia e con l’uso di uno strumento software.

L’obiettivo è quello di riflettere dapprima sul periodo osservativo vissuto nella prima

fase del tirocinio e di descrivere la parte in cui ho potuto avere un ruolo attivo con la

supervisione del docente accogliente; poi di proporre degli approfondimenti che potrei

utilizzare in una nuova occasione in cui si affronti la Logica. Rivisitando l’esperienza nel suo

insieme, desidero riassumere quegli insegnamenti che potranno aiutarmi a svolgere il mio

futuro ruolo di insegnante con maggiore consapevolezza e preparazione nell’affrontare le

classi e gli argomenti d’insegnamento.

3. Tirocinio osservativo e tirocinio attivo

Il tirocinio osservativo

Ho svolto i due tirocini di Matematica e di Informatica presso un ITIS, nel triennio a indirizzo

Informatica.

Sono entrata in una grande scuola che si è mostrata subito ricca di attività e ben

organizzata, come ho dedotto anche seguendo i Collegi dei Docenti; è dotata di un sito

Internet, utilizzato non solo come vetrina della scuola verso l’esterno, ma anche come utile

strumento di informazione e documentazione per alunni e genitori; molti docenti, inoltre, lo

utilizzano per mettere a disposizione degli studenti il materiale didattico.

Un buon numero di professori insegna in questa scuola da tanti anni, contribuendo a

darle un aspetto di stabilità e serietà.

Il professore accogliente insegna da pochi anni; si nota subito la sua provenienza

aziendale per l’impostazione pratica nella fase di spiegazione. Ho subito apprezzato la sua

ottima organizzazione riguardo alla programmazione e alla gestione delle ore di lezione, sia a

breve termine, sia a lungo termine. Da questo atteggiamento i ragazzi colgono sicurezza e

serietà, sentendosi costantemente motivati allo studio.

3

L’insegnante accogliente insegna nella III, nella IV e nella V classe di una delle

sezioni a indirizzo informatico. Io ho svolto la parte di tirocinio nella III classe, composta da

un buon numero di ragazzi interessati e da alcuni elementi di disturbo.

Il professore svolge durante la settimana tre ore in classe e tre ore in laboratorio.

Durante la maggior parte delle ore in classe, egli spiega quegli argomenti che vengono poi

applicati nelle ore di laboratorio. Per la valutazione dei ragazzi si basa sulle verifiche e

sull’osservazione del lavoro svolto in laboratorio.

Ho colto subito da lui quanto la passione per la materia che si insegna aiuti ad essere

più efficaci nel trasmettere le conoscenze ai ragazzi e ad essere più positivi e più disponibili:

la classe non può che beneficiare di un simile atteggiamento.

L’insegnante segue poco il libro di testo, se non per assegnare i compiti a casa.

Ritengo, invece, che nel mio futuro di insegnante potrei fare un più largo uso del libro di

testo, invitando i ragazzi alla sua lettura. Infatti, se da un lato gli appunti presi in classe

permettono ai ragazzi di focalizzare l’argomento e avere uno schema degli aspetti più

importanti del modulo, dall’altro il libro, oltre a fugare eventuali errori di copiatura, offre la

presentazione dell’argomento in modo più discorsivo, evidenziando con precisione formule,

grafici, algoritmi e offrendo sempre un punto di vista diverso da quello dell’insegnante,

fattore che favorisce una maggiore apertura mentale. Più in generale, reputo molto importante

trasmettere ai ragazzi l’abitudine alla lettura.

La sua impostazione pratica fa sì che le sue spiegazioni vertano sempre su parti di

codice da implementare, scritti in Java oppure in forma di diagrammi a blocchi. Raramente

accenna a concetti puramente teorici, aspetto che mi ha fatto riflettere sull’opportunità di

proporgli un argomento teorico come oggetto del mio tirocinio attivo.

Gli ho proposto quindi di trattare gli elementi fondamentali della logica, argomento

che io reputo importante per gli studenti al fine di contribuire allo sviluppo delle capacità di

analizzare e risolvere problemi di varia natura, indipendentemente dal linguaggio o dallo

strumento utilizzato per la loro formalizzazione.

La lezione tenuta in classe: prerequisiti, obiettivi, tempi

I prerequisiti necessari alla comprensione delle basi della logica sono molto semplici e

consistono nel conoscere il significato delle particelle grammaticali “e”, “o”, “non”, “se” nel

linguaggio comune.

4

Gli obiettivi che, insieme all’insegnante accogliente, mi sono posta sono stati quelli di

far conoscere ai ragazzi i simboli utilizzati nella logica e la definizione delle operazioni tra

proposizioni logiche, in modo da giungere alla capacità di determinare il risultato di

un’operazione tra proposizioni logiche e di compilare una tavola di verità.

La parte teorica, molto interattiva con i ragazzi e sempre ricca di esempi, è stata tenuta

in due lezioni di due ore ciascuna. La verifica di un’ora è stata poi seguita da un’altra ora per

la sua correzione in classe.

Essendo l’argomento completamente slegato dai temi stabiliti nella programmazione

modulare, ho potuto inserire il mio intervento in un qualsiasi momento dell’anno scolastico.

Riporto il contenuto del mio intervento in classe, suddiviso in unità didattiche.

UD 1 : Situazione-stimolo e prime definizioni

Tempo: 2 ore

Al fine di attirare l’attenzione sull’argomento e per prevenire possibili atteggiamenti di

disinteresse causati dalle notazioni formali utilizzate, ho iniziato la lezione ponendo il

seguente quesito-indovinello ai ragazzi.

“Al momento della sua morte, il nostro amico Pippo si trova davanti a due porte

esattamente uguali, una delle quali conduce al Paradiso, l’altra all’Inferno.

Davanti alle due porte ci sono due Angeli esattamente uguali, uno che dice

sempre il Vero, l’altro che dice sempre il Falso.

Il nostro amico Pippo ha la possibilità di porre una sola domanda a uno solo dei

due Angeli. Da tale domanda deve capire quale sia la porta del Paradiso, che

potrà così aprire e varcare.

Qual è la domanda che Pippo pone ad uno degli Angeli per ottenere il suo

scopo?”

I ragazzi si sono subito interessati alla questione, ponendomi delle domande al fine di

comprendere bene il quesito. Nel dare loro dei chiarimenti, ho spiegato che tale quesito è un

quesito di Logica e che “la Logica è la disciplina che si occupa di controllare la correttezza

di un ragionamento, costruito con proposizioni logiche e connettivi logici”. Ho aggiunto poi

le definizioni di proposizione logica, aiutandoli, con molti esempi, a imparare a distinguere tra

enunciati che sono proposizioni ed enunciati che non lo sono.

Sempre arricchendo le spiegazioni con esempi, ho dato le definizioni di variabile

logica, di valore di verità di una proposizione, di proposizione semplice e di proposizione

5

composta. Ho introdotto quindi i connettivi logici not, and, or, implicazione e doppia

implicazione; per ognuno di essi ho mostrato la tavola di verità, che ho introdotto facendo

notare che essa ha 2n righe, dove n è il numero di proposizioni semplici considerate. Ho

concluso così la prima lezione, assegnando alcuni esercizi per casa.

UD 2 : Espressioni logiche, proprietà, soluzione del gioco

Tempo: 2 ore

Dopo aver ripreso velocemente i concetti della lezione precedente, chiedendo e ottenendo dai

ragazzi una buona interazione, ho introdotto il concetto di espressione logica come

composizione di più proposizioni tramite i connettivi logici e, con un esempio, ho mostrato

come valutare il valore di verità delle espressioni logiche per mezzo delle tavole di verità. Ho

dato quindi la seguente definizione di equivalenza tra espressioni logiche: “Due espressioni

logiche nelle stesse variabili si dicono equivalenti quando hanno uguale la relativa colonna

della tavola di verità”.

Corredando sempre la spiegazione di numerosi esempi, ho dato le definizioni di

tautologia e di contraddizione ed elencato i principi fondamentali e le proprietà delle

operazioni logiche: principi di identità, non contraddizione, terzo escluso, leggi della doppia

negazione, di idempotenza, proprietà commutativa, associativa, distributiva, leggi di

assorbimento e di De Morgan.

Siamo passati quindi alla soluzione dell’indovinello proposto all’inizio. I ragazzi

hanno avanzato diverse risposte non corrette, finché due ragazzi, in due passi successivi, sono

giunti alla giusta soluzione, che recita così: “Cosa risponderebbe l’altro Angelo se gli

chiedessi qual è la porta del Paradiso?”.

Per convincerci che tale proposizione è quella corretta, li ho invitati a fare il seguente

ragionamento.

Chiamiamo A1 e A2 gli Angeli, p1 e p2 le porte. Supponiamo di porre la domanda ad

A1: per la simmetria del problema, lo stesso ragionamento varrà per la domanda posta ad A2.

A1 risponderà o “A2 direbbe p1”, o “A2 direbbe p2”.

Consideriamo il caso che risponda “A2 direbbe p1”. Allora se A1 dice il Vero, A2

dice il Falso e p1 è la porta dell’Inferno; se A1 dice il Falso, allora A2 dice il Vero e la

proposizione “A2 dice p1” è Falsa, cioè p1 è anche in questo caso la porta dell’Inferno.

Possiamo ripetere lo stesso ragionamento sulla risposta “A2 direbbe p2”, che ci

porterebbe ad affermare che p2 è la porta dell’Inferno.

La tavola di verità che riassume il ragionamento è la seguente.

6

A1 A2 “A2 direbbe p1” p1 = Paradiso

V F V F

F V F F

Verifica, correzione, risultati

Tempo: 1 ora + 1 ora

Ho voluto strutturare la verifica (riportata in allegato) con esercizi di difficoltà varia, al fine di

permettere a tutti i ragazzi di esprimere il loro livello di preparazione e le loro capacità.

Svolta senza che i ragazzi evidenziassero particolari difficoltà, la verifica ha dato

risultati positivi, poiché sono state ottenute dodici sufficienze contro nove insufficienze.

Dalla correzione sono emersi molti errori di cattiva interpretazione del testo

dell’esercizio, tanto che durante la correzione in classe ho voluto insistere con i ragazzi

sull’importanza in ogni disciplina di leggere ed analizzare i testi con attenzione.

Ho preferito distribuire i compiti corretti con i commenti, ma senza i voti, al fine di

ottenere maggiore attenzione durante la correzione alla lavagna, che io stessa ho svolto

(sempre con l’interazione dei ragazzi). Solo alla fine ho chiamato ogni ragazzo singolarmente

e ho assegnato il voto, invitando ognuno di essi a chiedermi eventuali chiarimenti.

4. Approfondimenti. Obiettivi, prerequisiti, tempi.

A partire dal problema, chiamato SAT, della soddisfacibilità delle proposizioni composte,

presentato durante il mio tirocinio attivo, riporto alcuni approfondimenti, ipotizzando di

poterli utilizzare in classe in una prossima occasione.

Il problema SAT permette infatti di presentare agli studenti di scuola superiore il

concetto di NP-completezza. Inoltre rende immediato il passaggio ad altri problemi analoghi,

quale quello dell’Algebra di Boole.

Tutti questi aspetti teorici possono quindi essere rivisitati in un’ottica più pratica,

utilizzando il programma zChaff, basato sulla procedura DPLL, che fornisce uno strumento

software per il calcolo della soddisfacibilità delle proposizioni alternativo alle tavole di verità.

Tali argomenti richiedono come prerequisito semplicemente la parte teorica già trattata

sulla logica. La conoscenza dei circuiti non è strettamente necessaria, perché può essere

introdotta in modo semplice nel corso della spiegazione. Si presuppone, invece, che gli

7

studenti siano già capaci di lanciare da un computer la finestra MS-DOS e da essa richiamare

e utilizzare un editor di linea.

Gli argomenti vengono qui proposti in forma di unità didattiche e per ognuna di esse

viene indicata la quantità di tempo necessaria per lo svolgimento della lezione. Inoltre si

possono prevedere almeno altre quattro ore in laboratorio per svolgere altri esercizi sui

modelli di quelli proposti.

UD 1 : Calcolo proposizionale e complessità – Problemi NP

Tempo: 2 ore in classe

Data una proposizione composta, i ragazzi sono in grado di costruire la corrispondente tavola

di verità. Come situazione stimolo per introdurre il problema della complessità

computazionale, si può proporre ai ragazzi di verificare tramite la tavola di verità la

soddisfacibilità di una proposizione composta costituita da sette proposizioni semplici. Essi

quindi imposteranno una tavola di verità le cui prime sette colonne conterranno tutte le

possibili combinazioni dei valori di verità delle sette proposizioni. Si accorgeranno subito di

dover preparare ben 27 = 128 righe per tale tavola di verità. Più in generale, essi

verificheranno che a una proposizione composta da n proposizioni semplici corrisponde una

tavola di verità di 2n righe.

I ragazzi vengono quindi invitati a considerare che nel momento in cui si giunge ad

una riga che verifica la soddisfacibilità della clausola, il lavoro è concluso e non è necessario

procedere con il calcolo delle righe rimanenti, poiché è stata trovata una combinazione di

valori di verità delle proposizioni semplici che soddisfa la proposizione composta. Tale riga

potrebbe trovarsi, per pura fortuna, tra le prime computate oppure, più sfortunatamente, più

avanti, e ottenuta dopo molto tempo di lavoro. Finché non viene trovata una riga che soddisfi

la proposizione, bisognerà andare avanti con la computazione e computare tutte le righe prima

di poter affermare che la proposizione composta non è soddisfacibile per nessuna

combinazione di valori di verità delle proposizioni semplici.

Inoltre si fa notare agli studenti che, se è nota una soluzione del problema, cioè una

sequenza ordinata di valori che soddisfa la proposizione composta, è facile e immediato

verificare la sua validità, semplicemente sostituendo tali valori nella proposizione di partenza.

Un esempio di tal genere può essere molto incisivo per far comprendere ai ragazzi

cosa sia un problema NP, in termini descrittivi: un problema appartiene alla classe di

problemi NP se è un problema la cui soluzione richiede molto tempo, ma tale che, nota una

8

soluzione, è facile mostrarne la validità.

Per allargare il discorso, si fa presente agli studenti che molti problemi sono

riconducibili alla soddisfacibilità delle proposizione composte, cioè sono rappresentabili in

tali termini.

Di conseguenza, se un giorno un bravo matematico o logico troverà un metodo, cioè

un algoritmo, per risolvere velocemente il problema SAT, allora esso potrà essere dichiarato

un problema della classe P (risolubile in poco tempo, in tempo Polinomiale) e tutti i problemi

ad esso riconducibili si troveranno anch’essi a far parte della classe P. Poiché non è ancora

dimostrata né l’esistenza, né la non esistenza di tale algoritmo, non possiamo neanche

affermare se il problema SAT appartenga o meno alla classe P.

UD 2 : Uno strumento software per il problema SAT: la procedura DPLL e zChaff

Tempo: 2 ore in classe + 2 ore in laboratorio

Vogliamo fornire agli studenti uno strumento per la risoluzione dei problemi di

soddisfacibilità delle proposizioni logiche che sia alternativo alle tavole di verità, delle quali

essi già conoscono la lunghezza di compilazione e come si prestino facilmente ad errori di

scrittura.

La procedura DPLL è stata sviluppata nel corso degli anni a partire dal 1960 da Davis,

Putnam, Logemann, Loveland, in fasi successive. Essa affronta il problema SAT tramite

alcune tecniche che, grazie alle sofisticate realizzazioni ingegneristiche attuali, rendono

efficacemente affrontabile tale problema anche quando esso contiene ben 10.000 variabili,

come ampi risultati sperimentali hanno dimostrato. Alcune strategie permettono infatti di

ridurre il numero dei casi da trattare o, per usare i termini noti ai ragazzi, permettono di non

effettuare il calcolo di alcune righe della tavola di verità corrispondente al problema in analisi,

che già si possono dire non soddisfacibili per qualche “somiglianza” con righe già trattate. La

procedura agisce ricercando un assegnamento che soddisfa la proposizione e cercando di

propagare ai passaggi successivi i risultati intermedi ottenuti.

La procedura DPLL è in grado di operare solo su proposizioni in forma normale

congiunta, cioè scritte come congiunzioni di altre proposizioni; queste ultime, che chiamiamo

clausole, possono essere costituite da proposizioni semplici, da proposizioni semplici negate,

da disgiunzioni di proposizioni semplici o semplici negate.

Per esempio, se indichiamo con le lettere maiuscole le proposizioni semplici, ecco un

esempio di proposizione composta in forma normale congiunta:

9

.

Lo strumento software che implementa la procedura DPLL si chiama zChaff ed è stato

sviluppato alla Princeton University nel 2001. Esso, quindi, è un risolutore di problemi SAT,

ma chiede che le proposizioni date in input siano in forma normale congiunta e che rispettino

una rigorosa sintassi.

Al fine di usare lo strumento zChaff, i ragazzi devono quindi imparare a manipolare

con facilità le proposizioni logiche, utilizzando le proprietà a loro già note, per poterle

trasformare in proposizioni equivalenti in forma normale congiunta, come richiesto in input

dallo stesso zChaff1; inoltre devono imparare ad usare un formalismo estremamente rigoroso,

ma semplice, per tradurre le proposizioni in forma normale congiunta nella sintassi richiesta

per la scrittura del file di input del programma. Tali regole sono le seguenti:

le righe di commento iniziano con la lettera c;

l’elenco delle clausole deve essere preceduto dalla seguente riga:

p cnf numero_lettere numero_clausole,

dove numero_lettere indica il numero di proposizioni semplici che compongono la

proposizione logica e numero_clausole indica il numero di clausole presenti;

ad ogni proposizione semplice viene associato un numero compreso tra 1 e

numero_lettere;

la proposizione semplice negata viene indicata con il numero assegnatole preceduto

dal segno meno;

ogni clausola viene indicata con i numeri delle proposizioni semplici che la

compongono separati da uno spazio e conclusa con uno 0.

Quindi, assegnando i valori da 1 a 5 alle lettere dalla A alla E, l’esempio riportato prima viene

tradotto nel seguente file di input:

c Esempio 1

p cnf 5 6

1 0

-2 0

3 4 01 Esiste in realtà uno strumento software che, data in input una qualsiasi proposizione logica, la trasforma in una equivalente in forma normale congiunta. Tale strumento è un modulo di SPASS, un dimostratore automatico di teoremi del Max-Plank-Institut in Germania. Può risultare, però, più formativo per i ragazzi imparare a manipolare in modo rigoroso le proposizioni, piuttosto che introdurre un nuovo strumento concettualmente impegnativo.

10

1 -4 0

-5 2 0

-3 -5 0

Gli studenti potranno quindi utilizzare lo strumento zChaff solo dopo aver effettuato le due

trasformazioni delle proposizioni dapprima in forma normale congiunta, poi nella sintassi

richiesta.

Per lanciare il programma, occorre dal PC richiamare una finestra MS-DOS; dopo

essersi spostati nel direttorio che contiene l’eseguibile, bisogna dare il comando “zChaff”

seguito dal nome del file che si vuole dare in input. È opzionale dare un secondo parametro

che indica un limite di tempo: se entro tale tempo il programma non avrà raggiunto una

conclusione, esso terminerà comunque.

Il risultato è formato da più righe, l’ultima delle quali indica se il problema dato in

input è o meno soddisfacibile. In caso affermativo, una delle righe precedenti riporta un

assegnamento che soddisfa il problema di partenza (facilmente riconoscibile perché seguito

dalla dicitura “Random Seed Used”). Ogni numero positivo corrisponde

all’assegnamento uguale a 1 alla proposizione semplice corrispondente a quel numero; se il

numero compare negativo, l’assegnamento è uguale a 0. Nel caso del nostro esempio,

otteniamo che il problema è soddisfacibile; troviamo infatti nell’output le seguenti

indicazioni:

1 -2 3 -4 -5 Random Seed Used

…

RESULT: SAT

che ci indica che l’assegnamento che soddisfa la proposizione è 1 -1 1 -1 -1 alle proposizioni

semplici A, B, C, D, E.

L’utilità di tale strumento sta anche nel permettere di far conoscere ai ragazzi

l’esistenza di strumenti software realmente utilizzati nell’industria per verificare la correttezza

dei circuiti logici, oppure per applicazioni su grafi che potrebbero riguardare, per esempio, i

percorsi delle ferrovie.

11

UD 3 : Equivalenza di alcuni formalismi

Tempo: 2 ore in classe

Nella scuola in cui ho svolto il tirocinio, un ITIS, gli studenti conoscevano già l’algebra di

Boole e i circuiti logici, perché studiati in Elettronica. Nel nostro contesto, questi due

argomenti possono essere ripresi (o introdotti completamente, nel caso di scuole di altro

genere) perché permettono di mostrare agli studenti in modo semplice ed immediato

l’equivalenza tra i due formalismi e la loro equivalenza con la logica proposizionale. Si può

riprendere anche l’algebra degli insiemi e mostrare che anch’essa è equivalente agli altri tre

formalismi. In questo contesto rimaniamo su un livello qualitativo, ma si può scegliere, anche

in base alla risposta della classe a tali argomenti, se mostrare le equivalenze usando degli

esempi o se enunciare e dimostrare i teoremi relativi. Tali ragionamenti permetterebbero agli

studenti di capire che uno stesso problema può essere scritto in quattro modi diversi, tutti

equivalenti tra loro; e che un problema studiato, per esempio, in Elettronica, può essere

opportunamente riscritto in modo da poterlo sottoporre allo strumento zChaff per ottenerne la

soluzione.

Per affrontare i quattro formalismi, occorre inizialmente riprenderne una semplice

definizione.

Nel caso dell’algebra degli insiemi, si possono introdurre i concetti di insieme, di

unione, di intersezione, di complemento per rapportarli poi ai concetti di proposizione

semplice, di congiunzione, di disgiunzione e di negazione. In generale, per rendere uniforme

la correlazione tra operazione insiemistica e proposizione composta, è opportuno esprimere

quest’ultima in termini dei soli connettivi logici , , , operazione che gli studenti sono

già in grado di fare, utilizzando le proprietà logiche viste nelle prime lezioni.

L’algebra di Boole può essere presentata parlando di un insieme B dotato di due

operazioni binarie e , dell’operazione unitaria ’ e di due elementi distinti 0 e 1 per i quali

valgono le leggi commutative, distributive e gli assiomi seguenti, per ogni x appartenente a B:

Anche in questo caso la corrispondenza biunivoca tra l’espressione booleana e la forma

proposizionale può essere mostrata sostituendo i simboli , e ’ dell’algebra booleana con i

simboli corrispondenti delle proposizioni logiche.

Infine si può parlare di circuito logico. Innanzitutto si introducono dei semplici circuiti

di commutazione, aventi un ingresso, un’uscita e più interruttori del tipo aperto/chiuso,

12

mostrando come si possano considerare gli interruttori analoghi alle proposizioni semplici; la

posizione reciproca degli interruttori, posti in serie o in parallelo, determina la rispettiva

corrispondenza con la congiunzione e la disgiunzione della logica proposizionale, mentre il

nome negato, per esempio , associato ad un interruttore permette la corrispondenza con la

negazione della logica. Come nella logica proposizionale ogni proposizione semplice può

assumere uno dei due valori di verità Vero – Falso, così ciascun interruttore può assumere lo

stato di aperto o chiuso, normalmente indicati con 0 = aperto, 1 = chiuso. Come nella logica

proposizionale vogliamo conoscere il valore della proposizione composta formata dalle

proposizioni semplici legate dai connettivi logici, così nel caso di un circuito che colleghi più

interruttori vogliamo sapere se la corrente passa da un estremo all’altro, in base allo stato di

ciascun interruttore. La figura che segue mostra un esempio di circuito logico e la

corrispondente formulazione in logica proposizionale.

UD 4 : La logica proposizionale e i circuiti elettronici – Esercizi

Tempo: 2 ore in laboratorio

La logica proposizionale afferma che qualsiasi proposizione può essere espressa servendosi di

proposizioni semplici e dei tre connettivi logici di negazione, congiunzione e disgiunzione.

Ciò significa che la realizzazione dei circuiti elettronici corrispondenti a questi tre operatori

permette di realizzare una qualsiasi rete elettronica, in grado di compiere operazioni logiche

su segnali binari, come una opportuna interconnessione dei circuiti fondamentali. Gli

equivalenti elettronici degli operatori logici sono chiamati porte logiche e gli schemi che si

usano per rappresentarle sono quelli in figura, che riportano nell’ordine, il circuito

C

A

¬B

CBA )(

)( BA

13

corrispondente alla negazione, quello della congiunzione e quello della disgiunzione.

Come esercizio per i ragazzi, partendo dal circuito logico del paragrafo precedente, la cui

proposizione logica è già espressa in forma normale congiunta, creiamo il file di input per

zChaff:

c Circuito1

p cnf 3 2

1 -2 0

3 0

Il risulato dell’elaborazione è il seguente:

1 -2 3 Random Seed Used

…

RESULT: SAT

Vediamo un altro esempio e consideriamo il seguente circuito:

Esso corrisponde alla proposizione logica

A ¬CB

¬C ¬A

14

che può essere trasformata in forma normale congiunta. Applicando infatti la proprietà

distributiva, si ottiene la proposizione equivalente:

Applichiamo ancora la proprietà distributiva:

Poi, per il principio del terzo escluso,

Infine, per la proprietà di Vero e Falso, otteniamo la seguente proposizione equivalente a

quella di partenza:

.

Quest’ultima proposizione corrisponde ad un circuito equivalente al primo, ma più semplice:

La proposizione ottenuta può quindi essere trascritta secondo la sintassi zChaff:

c Circuito2

p cnf 3 2

-3 0

-1 2 0

Il file viene dato in input al programma zChaff, che ritorna il seguente risultato

¬C

B

¬A

15

dell’elaborazione:

-1 2 -3 Random Seed Used

…

RESULT: SAT

UD 5 : Equivalenza di circuiti

Tempo: 2 ore in classe + 2 ore in laboratorio

Supponiamo ora di voler verificare l’equivalenza logica di due circuiti.

Si tratta di un problema concreto, che si presenta in aziende costruttrici di

microprocessori allorché devono verificare che il complesso circuito costruito equivalga al

problema logico per risolvere il quale tale circuito è stato concepito.

Proponiamo quindi il problema agli studenti sotto forma di verifica di equivalenza di

due circuiti.

A causa della formulazione più complicata che le proposizioni logiche possono

presentare per tali esercizi, introduciamo un metodo, detto metodo strutturale, che permette di

trasformare facilmente una proposizione nella sua forma normale congiunta.

Il metodo strutturale parte da formule che abbiano la negazione presente solo davanti

alle proposizioni semplici (condizione facilmente ottenibile applicando le proprietà già note).

All’interno della proposizione da trasformare, si individua una parte del tipo o

del tipo . Introduciamo una nuova proposizione semplice a e nella

proposizione sostituiamo ogni occorrenza di con a. Aggiungiamo inoltre alla

formula intera i due congiunti .

Per esempio, applicando il metodo strutturale alla formula

,

sostituiamo A1 ad ogni occorrenza di , A2 ad ogni occorrenza di , A3

ad ogni occorrenza di ; otteniamo la seguente forma normale congiunta,

equivalente a quella iniziale, ma contenente una proposizione semplice in più:

.

16

Con l’aiuto di questo strumento, possiamo ora affrontare il problema dell’equivalenza

di due circuiti indicando con e con le proposizioni logiche corrispondenti ai due circuiti.

Se i due circuiti, e quindi le due proposizioni, sono equivalenti, allora deve valere che

è una tautologia. Occorre quindi verificare che siano tautologie entrambe le formule

e .

Le due espressioni, per le note proprietà della logica proposizionale, si possono riscrivere

rispettivamente come

e .

Siccome zChaff agisce per refutazione, esso sa verificare non quando una formula è una

tautologia, ma quando una formula è insoddisfacibile. Tuttavia una formula è una tautologia

se e solo se la sua negazione è insoddisfacibile. Quindi neghiamo entrambe le espressioni e

otteniamo

e .

Se entrambe queste formule sono insoddisfacibili, i due circuiti sono equivalenti, altrimenti

no. Ognuna di queste due formule deve essere trasformata dagli studenti in forma normale

congiunta, riscritta in un file secondo la sintassi opportuna e data in input allo strumento

zChaff. Se zChaff risponde UNSAT per entrambe le elaborazioni, allora essi potranno

concludere che i due circuiti sono equivalenti (perché abbiamo sottoposto a zChaff il

problema negato); se zChaff da come risultato SAT in uno solo dei casi o in entrambi, i

circuiti non sono equivalenti.

Prendiamo come esempio i due circuiti delle pagine 14 e 15, che abbiamo già mostrato

essere equivalenti, e applichiamo il ragionamento. Abbiamo:

17

e ,

da cui

e quindi, negando entrambe,

La prima espressione, riscritta in forma normale congiunta utilizzando il metodo strutturale,

diventa:

La seconda, anch’essa riscritta in forma normale congiunta, diventa:

.

Scriviamo ora il primo file di input per zChaff:

c PrimaImplicazione

p cnf 4 7

-4 -3 0

-3 4 0

-1 4 0

-2 3 0

-4 1 0

-4 2 0

1 3 0

Il file che riporta la seconda espressione è il seguente:

18

c SecondaImplicazione

p cnf 3 4

-1 -2 3 0

-1 2 0

-3 0

1 3 0

Il risultato che zChaff ritorna, dando in input il primo file, è:

…

RESULT: UNSAT

Per il secondo file, il risultato è esattamente lo stesso:

…

RESULT: UNSAT

Per le argomentazioni precedenti, possiamo affermare che i due circuiti di partenza, e quindi

le loro proposizioni logiche, sono equivalenti.

Verifica

Tempo: 2 ore in laboratorio

In una possibile verifica da svolgere in laboratorio, si può proporre agli studenti di stabilire

l’equivalenza o meno di due circuiti, al fine di verificare che abbiano compreso le varie fasi

che portano al corretto completamento dell’esercizio. Gli studenti dovranno quindi mostrare

di conoscere i seguenti passi, che ripercorrono le unità didattiche proposte:

dato un circuito, ricavare la proposizione logica corrispondente;

mettere in relazione le due proposizioni logiche dei due circuiti, per sottoporle a

zChaff secondo la sua logica;

trasformare una proposizione logica in un’altra equivalente che sia in forma normale

congiunta;

trasformare una proposizione logica in un file, secondo la sintassi zChaff;

eseguire zChaff e saper leggere il risultato dell’elaborazione;

trarre le dovute conclusioni sull’equivalenza dei circuiti dati.

19

Bibliografia

Per le parti teoriche:

S. Ghilardi, E. Nicolini, D. Zucchelli, Introduzione alla procedura DPLL

M. Maiocchi, Teoria e applicazioni delle macchine calcolatrici, Casa Editrice

Ambrosiana, 1984

D. Mandrioli, C. Ghezzi, Theoretical foundations of computer sciences, John Wiley &

Sons, 1987

E. Mendelson, Algebra di Boole e circuiti di commutazione, Collana Schaum – ETAS

Libri, 1974

Per DPLL, zChaff, SPASS:

S. Ghilardi, E. Nicolini, D. Zucchelli, Introduzione alla procedura DPLL

http://www.dit.unitn.it/%7Erseba/DIDATTICA/Tutorials/Slides_tutorial_cade04.pdf

http://www.princeton.edu/~chaff/zchaff.html

http://spass.mpi-sb.mpg.de/

20

ALLEGATO I: Verifica in classe

1. Date le seguenti proposizioniA. “Roma è la capitale d’Italia”B. “Milano è in Veneto”C. “La Sardegna è un’isola”

scrivi in parole le seguenti proposizioni composte e assegna a ognuna il valore di verità:1.a 1.b 1.c

2. Costruisci la tavola di verità della proposizione .

3. Dopo aver attribuito il valore di verità alle proposizioni semplici che seguono, attribuisci il valore di verità alle proposizioni composte indicate:

A. “Il quadrato è un parallelogramma”B. “Il quadrato è un rettangolo”C. “Il quadrato è un trapezio”

3.a 3.b 3.c 3.d3.e 3.f 3.g 3.h

4. Utilizzando la tavola di verità, verifica che le due proposizioni seguenti sono equivalenti:

________

Dimostra la validità delle seguenti equivalenze senza l’aiuto delle tavole di verità:5.6.7.________

Date le seguenti proposizioni composte, indica ogni proposizione componente con una variabile e riscrivi la proposizione composta in forma simbolica.Esempio: “Se piove o nevica, allora non esco”.

A: “piove”; B: “nevica; C: “io esco”.

(Suggerimento: è utile scrivere ogni proposizione con il suo soggetto, anche se è sottinteso.)8. “Se non studi, non prenderai la sufficienza”.9. “Se un parallelogramma è un quadrato, allora è un rombo e un rettangolo”.10. “Se un numero è multiplo di 10, allora è pari ed è divisibile per 5”.11. Se il mare è calmo e Alessandro scrive romanzi, allora Giacomo scrive poesie”.________

12. Scrivi se ognuna delle seguenti proposizioni è una tautologia o una contraddizione (puoi verificarlo con le tavole di verità o con semplici ragionamenti):

13. Analogamente a come fatto in classe, disegna il circuito con lampadina e interruttori corrispondente alla proposizione .

21