Algebra Booleana

Transcript

ALGEBRA BOOLEANA Insieme K con elementi che assumono i valori {0,1) con operatori (AND , OR, NOT) Notazione: Se x e y sono due variabili booleane: L’AND di x e y si indica con x · y (oppure xy) L’OR di x e y si indica con x + y Il NOT di x si indica con x ( oppure con x’ , ~x, (not x) ,x ) In generale, con n variabili si possono ottenere 2 ( 2n ) funzioni. PORTE LOGICHE ELEMENTARI GENERALIZZAZIONE DELLE REGOLE DI DE MORGAN ORDINE DI PRECEDENZA DEGLI OPERATORI LOGICI Se in una espressione logica simbolica vengono utilizzati più operatori logici, viene valutato prima NOT, quindi AND e infine OR. Per alterare tale priorità si usano le parentesi : Esempio : f(a,b,c) = a  b  c deve essere valutata , una volta assegnati i valori booleani di a,b,c , eseguendo : 1) il not di a 2) la congiunzione and (•) tra a e b 3) la disgiunzione or (+) tra a  b e c Esempio : f(a,b,c) = a  (b  c) deve essere valutata , una volta assegnati i valori booleani di a,b,c , eseguendo : 1) il not di a 2) la disgiunzione OR (+) tra b e c 3) la congiunzione and (•) FUNZIONE DI MAGGIORANZA La risposta del circuito è 1 quando ci sono più “ uni “ di “zeri” PORTE XOR LA PORTA XOR A PIU’ INGRESSI CALCOLA LA FUNZIONE “DISPARI” Per esempio la funzione xor tra tre variabili: restituisce il valore vero solo se una sola variabile è vera (=1) o lo sono tutte e tre. CIRCUITO EQUIVALENTE ALLA FUNZIONE LOGICA EXOR TABELLA di verita’ della funzione EXOR C = A xor B LEGGI PRINCIPALI DELL’ALGEBRA BOOLEANA --- - - - - - -- - - - - - - - - - - - - - - -- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ADDIZIONATORE A n BIT ( in questo caso n= 4) Verificare che se C = 0 il circuito effettua uno shift (scivolamento )a sinistra dei valori D0……D7 ed S7 risulta = 0 ( caso della moltiplicazione per 2). Se invece C = 1 il circuito effettua uno shift a destra dei valori D0……D7 S0 risulta = 0 ( caso della divisione per 2). e MULTIPLEXER Circuito che seleziona in base ai valori A B e C ( 3 segnali di controllo) quale degli 8 segnali d’ingresso sara’ presente all’uscita Y. Notare che i 3 segnali A,B,C possono controllare 23 = 8 segnali di ingresso (D0,D1, ………,D7) In generale con n segnali di controllo si possono selezionare 2n segnali d’ingresso. Applicazioni pratiche : trasformazione parallelo-seriale. DEMULTIPLEXER Il demultiplexer è un circuito che compie una funzione inversa rispetto al multiplexer; il demultiplexer è in grado di trasferire a ciascuna delle sue uscite un dato presente in ingresso in tempi successivi; l'uscita a cui inviare il dato è scelta mediante un apposito selettore; il demultiplexer ha quindi un solo ingresso e più uscite; Nell’esempio in figura: le linee A,B,C controllano le entrate in serie (D0,D1, ………,D7) in 8 uscite in parallelo . Applicazione pratica : Trasformazione serie-parallelo. Notiamo, infine, che il bit in ingresso deve essere presente per tutto il tempo in cui i selettori (A,B,C) comandano il passaggio dall'ingresso all'uscita di un certo bit. Esempio Duale a + ab = a + b a*( a+b) = ab Regola del controduale Data una funzione booleana f(x1,x2,x3,…xn) si ottiene la sua controduale fcd: 1) negando ogni variabile; 2) scambiando + e * 3) scambiando 0 con 1 La funzione fcd ha la seguente proprieta’: - per ogni x1,x2,x3,…xn  {0,1) fcd (x1,x2,x3,…xn) = f(x1,x2,x3,…xn) Questo significa che a parita’ di valori x1,x2,x3,…xn il valore che assume f e’ l’opposto del valore che assume fcd Esempio-1 F ( x, y , z )  x * ( y  z ) Fcd  x  y * z  x * ( y  z ) Verificate, per esercizio, le tabelle di verita’ di f e di fcd per tutti i valori di x,y,z. Esempio-2 F ( x, y )  x  y Fcd  x * y  x  y e abbiamo ottenuto una delle proprieta’ di De Morgan. Esempio-3 F ( x, y )  x * y Fcd  x  y  x * y e abbiamo ottenuto l’altra proprieta’ di De Morgan!! PROPRIETA’ DI ASSORBIMENTO - dimostrazione: a + ab = a + ab a = a *(b+b) + a*b = ab + ab + ab distributività = ab + ab + ab commutativita’ = ab + ab idempotenza = a( b + b ) distributività = a*1 inverso =a a + ab a + ab = elemento neutro del * identità a+b = a + ab + ab per l’assorbimernto = a +b(a + a) distributività = a +b*1 inverso =a+b identità da (a + ab = a+b) discende anche a + ab = a+b Il teorema del consensus permette di semplificare una espressione Booleana nel seguente modo : XY + XZ + YZ = XY + XZ Come si vede salta il terzo termine,YZ, questo è ridondante e può essere eliminato. Si noti che Y e Z sono associati a X e X nei primi due termini e appaiono insieme nel termine che è eliminato. Dimostrazione: X*Y + X *Z + Y*Z = X*Y + X*Z + Y*Z*( X + X ) per l’elemento neutro di * = X*Y + X*Z + X*Y*Z + X*Y*Z = X*Y + X*Y*Z + X*Z + X*Y*Z per assorbimento = X*Y(1 + Z) + X*Z *(1 + Y ) = X*Y + X*Z CVD Duale: (X + Y)( X + Z)(Y + Z) = (X + Y)( X + Z) . COMPLETEZZA DELLE PORTE NAND e NOR Le porte NAND e NOR posso implementare qualsiasi funzione logica (per questo sono chiamate porte universali) CIRCUITI INTEGRATI I circuiti digitali sono costruiti come circuiti integrati (IC) cristalli di semiconduttori al silicio, detti informalmente chip, contenenti i componenti elettronici per i gate digitali. I gate sono interconnessi sul chip per formare il circuito integrato. A seconda del numero di gate (porta logiche) che possono essere messi su un chip variano da pochi a migliaia di milioni. A seconda del numero parleremo di: o o o o Small-scale integrated (SSI): diversi gate; Medium-scale integrated (MSI): 10-100; Large-scale integrated (LSI) : da 100 a poche migliaia; Very large-scale integrated (VLSI): da parecchie migliaia a molti milioni. ESERCIZI: VERIFICARE tramite le regole di Boole oppure tramite le tabelle di verità quale delle seguenti uguaglianze sono corrette: AB + AC + BC = AB + BC AB + AC + BC = AB + AC --------------------------Semplificare la seguente funzione a 3 variabili: F(A,B,C)= A B  BC F(A,B,C)= A*B*C + B*C + A*B + A*B*C ---------------------------Applicando i teoremi dell’algebra di Boole, verificare la seguente equivalenza tra espressioni: ELEMENTI DI RAGIONAMENTO LOGICO. CONCETTI FONDAMENTALI, IMPLICAZIONE E REGOLE DI INFERENZA Per prima cosa il termine “ragionamento logico” nel senso da noi usato va inteso come il processo seguito nella deduzione di nuove proposizioni o nuovi asserti da una o più proposizioni date. Praticamente useremo, nello stesso senso, anche i termini “inferenza logica” o “inferenza deduttiva”. Osserviamo che è possibile anche studiare la logica in senso “induttivo”; tal caso si parlerà di “inferenza statistica” o inferenza sperimentale”. Una definizione appropriata di inferenza logica risale al 1943 da parte di J.C. Cooley: DEFINIZIONE: Ogniqualvolta una o più proposizioni portano a nuove proposizioni che – se sono state accettate quelle originali – le nuove devono essere accettate puramente in virtù della forma e non del contenuto . Questa definizione sottolinea, ponendo l’accento sulla forma, il moderno punto di vista della logica. La maggior parte delle ricerche logiche contemporanee appartengono al campo noto sotto i vari nomi di “logica simbolica”, “logica formale”, “logica matematica”, che consiste nello studio dei principii del ragionamento e di numerosi argomenti ad essi connessi, con l’ausilio di un simbolismo altamente astratto e complesso. La “logica classica” (termine con cui abitualmente s’intende lo studio della logica basato sull’opera del grande filosofo e logico greco Aristotele) è invece una logica essenzialmente “verbale”. PROPOSIZIONI GENERALI E PROPOSIZIONI PARTICOLARI La logica formale si occupa di asserti o dichiarazioni che possono venire classificati, sia effettivamente che ipoteticamente come “veri” oppure “falsi” ma non “veri e falsi” contemporaneamente”. A questi asserti daremo il nome di proposizioni. Assioma 1 (Principio di non contraddizione) E' impossibile che una proposizione sia contemporaneamente vera e falsa. Assioma2 (Principio del terzo escluso) Non esistono altri valori di verità oltre a "VERO" e "FALSO". Così come nel linguaggio corrente possiamo incontrare frasi semplici (costituite cioè da un soggetto, un predicato e da uno o più complementi) e frasi più complesse, così anche in logica possiamo distinguere le proposizioni atomiche, cioè quelle più semplici delle quali abbiamo parlato fin qui, delle quali si possa dire subito se sono vere o false, dalle proposizioni composte o molecolari. Chiameremo “proposizioni generali” quelle in cui compaiono termini generali o indefiniti come “tutti”, “alcuni”, “ogni”, “ciascuno” ; le proposizioni in cui non compaiono termini di questo tipo saranno chiamate “particolari”. In base a quanto detto, quindi, nella logica possono considerarsi proposizioni le frasi: 1) 2) 3) 4) 5) La zebra è un mammifero; (prop. atomica) 3 è un numero primo. Milano è in Sardegna. ( una proposizione può essere vera o falsa) Bruxelles è in Belgio o in Olanda. (prop. composta) La neve è di colore rosso. Non possono considerarsi proposizioni, invece, le frasi: 6) 7) 8) 9) Firenze è la città più bella d’Italia; ( è soggettiva) Chi è l’autore de “L’uomo senza qualità”? (è una domanda) Per favore non chiamare dopo le 11 di sera. (è una richiesta) Avanti! (è un comando) NEGAZIONE di una proposizione Per esempio se p sta per “sta piovendo” ~ stia piovendo”. p sta per “non sta piovendo” oppure “è falso che DISGIUNZIONE La disgiunzione tra due proposizioni poq p , q è la proposizione o p o q oppure p⋁q oppure p+q oppure che va intesa vera quando almeno una delle proposizioni sia vera, falsa nel caso opposto. Se p indica come prima “sta piovendo” e q indica “spende il sole” la proposizione composta: “o sta piovendo o splende il sole “ è vera quando: 1) sta piovendo 2) spende il sole 3) sta piovendo e splende il sole Invece è falsa quando - non sta piovendo e non splende il sole CONGIUNZIONE La congiunzione tra due proposizioni p,q è la proposizione p⋀q oppure p*q oppure p q che va intesa vera quando entrambe le proposizioni sono vere , falsa nel caso opposto. Usando le precedenti proposizioni p * q significa “ sta piovendo e splende il sole” I simboli introdotti per la negazione, disgiunzione e congiunzione possono essere combinati in molti modi per dar luogo a diverse proposizioni composte . Ricordiamo che gli operatori ~, * e + hanno priorità differenti . Prima il NOT(~) poi l’AND (*) e poi l’OR (+). Per alterare tale priorità si possono usare le parentesi [( )]. Es: a) p(q+r) : p è vera e q o r è vera b) pq + r : p e q è vera oppure r è vera c) p(~q)+( ~p)q : abbiamo (p e non-q ) è vera oppure (non-q e p) è vera. Questa è la disgiunzione completa o anche elusive or. d) ~[(~p)+ (~q)] : è falsa che non-p o non-q sia vera. Alcune proposizioni composte possono risultare sempre vere , in tal caso si parla di tautologie. Esempio: la proposizione p + (~p) è sempre vera ( è una tautologia). Alcune proposizioni composte possono risultare sempre false , in tal caso si parla di contraddizioni. Esempio: la proposizione q *(~q) è sempre falsa ( è una contraddizione). Implicazione logica L’ implicazione logica è un connettivo logico attraverso il quale, a partire da due proposizioni p e q , si forma una nuova proposizione ,chiamata p implica q e si scrive p  q, la quale è falsa solo se p è vera e q è falsa Questa definizione si può riassumere mediante la seguente tabella di verità: p falsa falsa vera vera q falsa vera falsa vera p q vera vera falsa vera Si dice anche che   p è condizione sufficiente per q; q è condizione necessaria per p; NOTARE CHE LA TABELLA DI VERITA’ DELL’IMPLICAZIONE p E’ EQUIVALENTE ALL’ESPESSIONE pq Esempio p è la proposizione “piove” q è la proposizione “Giulia resta a casa” “se piove allora Giulia resta a casa“ pq Usando l’equivalenza con O non piove o Giulia resta a casa possiamo affermare : MA Se non piove Giulia può restare a casa oppure no! q CONTRARIA-INVERSA-CONTRONOMINALE Data l'implicazione p→q (implicazione diretta), l'implicazione p  q si dice contraria di ; l'implicazione q  p si dice inversa di ; l'implicazione q  p si dice contronominale di . L’Implicazione diretta e contronominale sono logicamente equivalenti, come si può facilmente controllare costruendo le relative tavole di verità. Sempre utilizzando le tavole di verità si può dimostrare che una implicazione non equivale logicamente alla sua inversa né alla sua contraria. Tavole di verità p q falsa falsa vera vera falsa vera falsa vera vera vera falsa falsa vera falsa vera falsa vera vera falsa vera vera falsa vera vera vera falsa vera vera vera vera falsa vera Osserviamo che implicazione diretta e contronominale hanno lo stesso valore di verità , mentre l'inversa ha lo stesso valore di verità della contraria. ESEMPI Sia N un numero intero p è la proposizione “N ha lo zero come ultima cifra” q è la proposizione “ N è pari” Consideriamo l'implicazione p  q "Se N ha lo zero come ultima cifra allora è pari"; VERA La sua contraria è: "Se N non ha lo zero come ultima cifra allora non è pari"; FALSA La sua inversa è: " Se N è pari allora ha lo zero come ultima cifra "; FALSA La sua contronominale è " Se N non è pari allora non ha lo zero come ultima cifra Possiamo allora affermare: VERA  Condizione sufficiente , ma non necessaria, affinché N sia pari è che la sua ultima cifra sia lo zero  Condizione necessaria, ma non sufficiente, affinché N abbia come ultima cifra lo zero, è che N sia pari. LA DOPPIA IMPLICAZIONE Sia T un triangolo; Consideriamo le due proposizioni: p = “T è rettangolo” q = “ Le misure dei lati di T verificano la relazione pitagorica In questo caso pq: "Se T è rettangolo allora le misure dei lati di T verificano la relazione pitagorica” VERA La sua contraria è: " Se T non è rettangolo allora le misure dei lati di T non verificano la relazione pitagorica” VERA La sua inversa è: "Se le misure dei lati di T verificano la relazione pitagorica allora T è rettangolo ” VERA La sua contronominale è "Se le misure dei lati di T non verificano la relazione pitagorica allora T non è rettangolo ” VERA Le implicazioni sono tutte e quattro vere. Si parla allora di Implicazione doppia (pq )che si può esprimere nelle forme seguenti:    p se e solo se q. p è condizione necessaria e sufficiente per q. p è equivalente a q. pq è vera quando p e q hanno lo stesso valore di verità p q falsa falsa vera vera falsa vera falsa vera pq vera falsa falsa vera Possiamo allora affermare Se e solo se T è rettangolo allora le misure dei lati di T verificano la relazione pitagorica”  Condizione necessaria e sufficiente affinché i lati di T verifichino la relazione pitagorica è che T sia rettangolo Le due proposizioni: p “T è rettangolo” q “Le misure dei lati di T verificano la relazione pitagorica” sono logicamente equivalenti REGOLE DI INFERENZA Regola di inferenza deduttiva o Modus ponens Se p q è vera e p è vera allora q è vera Tavole di verità p q falsa falsa vera falsa vera falsa vera vera falsa vera vera falsa falsa falsa vera vera vera vera vera vera Regola di inferenza della contronominale o Modus tollens Se p  q è vera e q è vera allora Tavole di verità p q falsa falsa vera vera falsa vera falsa vera vera vera falsa vera vera falsa falsa falsa vera vera vera vera ESEMPI ” “se piove allora Giulia resta a casa“ A) PIOVE! allora Giulia resta a casa B) Giulia non resta a casa! allora Non piove p è vera ESERCIZI (01) Dire quali delle seguenti coppie di forme proposizionali sono logicamente equivalenti ( il simbolo ¬ = NOT) : (a) A (A∨B)∧(A∨¬B) (b) ¬(A∧¬B) ¬A∨B (c) A→B ¬B→A (d) A∨B (¬A∧B)∨(A∧¬B) (e) A∧(B→C) B ∧ (A→C) (f) (A∨B)→C (A→C)∧(B→C) risp: (a) (b) (d) (f) Risp: sotto la casella (02) Posto: A = “Carlo è ligure” e B = “Diego è piemontese”, scrivere le proposizioni che formalizzano i seguenti enunciati: (a) “Carlo non è ligure” risp(¬A) (b) “Carlo è ligure e Diego è piemontese” (c) “Carlo è ligure sebbene Diego sia piemontese” (d) “Non è vero che Carlo sia ligure e Diego piemontese” (e) “Se Carlo non è ligure, allora Diego non è piemontese” (f) “È falso che se Carlo è ligure, allora Diego è piemontese” (g) “Carlo è ligure solo se Diego non è piemontese” (h) “Carlo è ligure se e solo se Diego è piemontese” (i) “O Carlo è ligure o, se Carlo non è ligure, allora Diego è piemontese” (l) “O Carlo è ligure e Diego è piemontese, o né Carlo è ligure, né Diego è piemontese” (m) “Carlo è ligure se Diego è piemontese” RISPOSTE ¬A (b) A∧B Risp sotto la(a)casella (e) ¬A→¬B (f) ¬(A→B) (c) A∧B (g) A  ¬B (i) A∨(¬A→B) (l) (A∧B)∨(¬A∧¬B) (d) ¬(A∧B) (h) AB (m) B→A FINE da finire IMPLICAZIONI Una delle più importanti e abituali relazioni tra due proposizioni è formata dai due termini “se…. allora “ . Nel caso di un teorema matematico il “se” regge l’ipotesi e l’”allora” regge la tesi . La dimostrazione del teorema mostra che vi è una connessione logica tra ipotesi e tesi che impone di accettare la seconda qualora sia stata accettata la prima, con l’ipotesi addizionale che i postulati ( del ramo della matematica in esame) siano veri. Spesso, nel linguaggio comune , una frase che contiene il “se…..allora” viene usata in modo molto più casuale, senza che sia richiesta un’effettiva connessione logica tra le due preposizioni componenti ( spesso le due proposizioni sono legate da una forma di causa ed effetto). Per esempio: 1) Se piove, allora l’aria si rinfrescherà. 2) Se il tempo è buono allora esco in bicicletta. 3) Se vai tu, allora vengo anch’io. Invece di “se…..allora” si usa spesso un unico termine “implica” e qualsiasi proposizione composta del tipo “se p, allora q”, “se p è vera , allora q è vera” oppure “ p implica q” saraà chiamata un’implicazione e sarà simboleggiata in questo modo: pq . Come fare per definire l’implicazione con gli operatori and, or, not , già precedentemente conosciuti e usati? A questo scopo consideriamo la seguente proposizione: Se il tempo sarà buono allora si giocherà la partita In questo caso vi sono due possibilità corrispondenti alla proposizione condizionale, vale a dire che il tempo potrà essere buono o cattivo. Nel primo caso, accettando che la proposizione sia vera OR , ⋁ , ⋀ ,+ xor , ⊕ not , ~ , ∊ appartenenza ∉ non appartenenza ∃ esistenza ∄ non esistenza ⇒ ⊥(falso- assurdo) n = 2 variabili simboli matematici 16 funzioni possibili