Algebra di Boole, elementi di logica e Mappe di...

DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE

Algebra di Boole, elementi di logica e Mappe di Karnaugh

Marco D. Santambrogio – marco.santambrogio@polimi.itVer.aggiornataal18Marzo2016

Progetti

•  Meeting§ Quando: 22 Marzo @2pm§ Dove: Sala Conferenze @DEIB

Progetti

•  Problemi email§  stephen.bono@email.polimi.it§  elena.balzan@polimi.it§  gianluca.drappo@polimi.it§  giulia.crocioni@polimi.it

Progetti

•  Problemi email§  stephen.bono@mail.polimi.it§  elena.balzan@mail.polimi.it§  gianluca.drappo@mail.polimi.it§  giulia.crocioni@mail.polimi.it

Problema: caratteri MaIuScOli

Si scriva un programma che, preso un carattere minuscolo da tastiera, ne riporta a video l’equivalente maiuscolo

HELP: errori sull’input

Problema: errori sull’input

•  Problema§  Preso un dato inserito da tastiera§  Per potervi applicare la trasformazione di

nostro interesse§  Dobbiamo prima verificare che il dato sia

coerente con quanto ci aspettiamo

•  Soluzione§  Definire l’insieme dei caratteri validi§  Verificare l’appartenenza del carattere

inserito, all’insieme dei caratterei validi

Pseudocodice

•  Dati§  L’insieme dei caratteri ammissibili

{a, b, c, …, z}

1.  Richiedere l’inserimento di un carattere

2.  Se carattere inserito corretto3.  Allora stampa a video carattere-324.  Altrimenti stampa a video un

messaggio di errore

Condizione da verificare

{a, b, c, …, z}

•  Il carattere inserito deve essere§ =>a§ <= z

Obiettivi

•  Algebra di Boole§  Algebra di boole a due valori: algebra

di commutazione§ Operazioni logiche§  Espressioni logiche

•  Funzioni booleane•  Forme canoniche•  Karnaugh e Mappe di Karnaugh

•  L’algebra di Boole (inventata da G. Boole, britannico, seconda metà ’800), o algebra della logica, si basa su operazioni logiche

•  Le operazioni logiche sono applicabili a operandi logici, cioè a operandi in grado di assumere solo i valori vero e falso

•  Si può rappresentare vero con il bit 1 e falso con il bit 0 (convenzione di logica positiva)

Cenni all’algebra di Boole

- 12 -

Algebra Booleana: definizione

•  Algebra Booleana B è un sistema algebrico identificato dalla sestupla (B,+,*,’,0,1) dove:

§ B è l'insieme su cui vengono definite le operazioni (supporto)

§ +,*,’ sono le operazioni binarie OR e AND e l’operazione unaria NOT

§  0,1 sono elementi speciali di B.•  0 è l’elemento neutro rispetto a +•  1 è l’elemento neutro rispetto a *

§ Assiomi

Algebra Booleana a due valori: Algebra di Commutazione

“Tra tutte le algebre booleane, l'algebra booleana a due valori........è la più utile. Essa è la base matematica della analisi e progetto di circuiti di commutazione che realizzano i sistemi digitali.”

[Lee, S.C., Digital Circuit And Logic Design. Englewood Cliffs, NJ: Prentice-Hall, 1976]

- 13 -

•  Operatori logici binari (con 2 operandi logici)§  Operatore OR, o somma logica§  Operatore AND, o prodotto logico

•  Operatore logico unario (con 1 operando)§  Operatore NOT, o negazione, o inversione

•  Poiché gli operandi logici ammettono due soli valori, si può definire compiutamente ogni operatore logico tramite una tabella di associazione operandi-risultato

Operazioni logiche fondamentali

•  Le variabili dell’algebra booleana a due valori possono assumere solo i due valori 0 e 1§  precisamente, se x indica una variabile, è

•  x = 0 se e solo se x ≠ 1 •  x = 1 se e solo se x ≠ 0

•  Algebra Booleana a due valori: ({0,1},+,*,’,0,1) dove + (OR) e * (AND) sono definiti come

•  Mentre l’operazione a un solo elemento (unary operation) detta complementazione o negazione (NOT) è definita come

§  Nota: il simbolo associato al NOT è spesso indicato come ’(esempio x’), !(esempio !x) o sopra segnando la variabile.

0 1 1 0

+ 0 1 0 0 1 1 1 1

* 0 1 0 0 0 1 0 1

Operazioni logiche fondamentali

Operatori logici di base e loro tabelle di verità

A B A and B0 0 00 1 01 0 01  1 1(prodotto logico)

A B A or B0 0 00 1 11 0 11  1 1(somma logica)

A not A

(negazione)

Le tabelle elencano tutte le possibili combinazioni in ingresso e il risultato associato a ciascuna combinazione

•  Come le espressioni algebriche, costruite con:§  Variabili logiche (letterali): p. es. A, B, C = 0 oppure 1§  Operatori logici: and, or, not

•  Esempi:A or (B and C)(A and (not B)) or (B and C)

•  Precedenza: l’operatore “not” precede l’operatore “and”, che a sua volta precede l’operatore “or”

A and not B or B and C = (A and (not B)) or (B and C)•  Per ricordarlo, si pensi OR come “+” (più), AND

come “×” (per) e NOT come “-” (cambia segno)

Espressioni logiche (o Booleane)

A and B or not C

A B C X = A and B Y = not C X or Y

0 0 0 0 and 0 = 0 not 0 = 1 0 or 1 = 1

0 0 1 0 and 0 = 0 not 1 = 0 0 or 0 = 0

0 1 0 0 and 1 = 0 not 0 = 1 0 or 1 = 1

0 1 1 0 and 1 = 0 not 1 = 0 0 or 0 = 0

1 0 0 1 and 0 = 0 not 0 = 1 0 or 1 = 1

1 0 1 1 and 0 = 0 not 1 = 0 0 or 0 = 0

1 1 0 1 and 1 = 1 not 0 = 1 1 or 1 = 1

1 1 1 1 and 1 = 1 not 1 = 0 1 or 0 = 1

Tabella di verità di un’espressione logica

A B NOT ((A OR B) AND (NOT A)) 0 0 0 1 1 0 1 1

A B C ( B OR NOT C) AND (A OR NOT C) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

00110011

01010101

10101011

00001111

10101010

10111011

10101111

Due esercizi

•  A modellare alcune (non tutte) forme di ragionamento§  A = è vero che 1 è maggiore di 2 ? (sì o no, qui è no) = 0§  B = è vero che 2 più 2 fa 4 ? (sì o no, qui è sì) = 1§  A and B = è vero che 1 sia maggiore di 2 e che 2 più 2 faccia 4 ?

Si ha che A and B = 0 and 1 = 0, dunque no§  A or B = è vero che 1 sia maggiore di 2 o che 2 più 2 faccia 4 ?

Si ha che A or B = 0 and 1 = 1, dunque sì•  OR, AND e NOT vengono anche chiamati connettivi

logici, perché funzionano come le congiunzioni coordinanti “o” ed “e”, e come la negazione “non”, del linguaggio naturale

•  Si modellano ragionamenti (o deduzioni) basati solo sull’uso di “o”, “e” e “non” (non è molto, ma è utile)

A che cosa servono le espressioni logiche?

•  Le espressioni logiche (booleane) non modellano:§  Domande esistenziali: “c’è almeno un numero reale x tale

che il suo quadrato valga -1 ?” (si sa bene che non c’è) ∃x | x2 = -1 è falso

§  Domande universali: “ogni numero naturale è la somma di quattro quadrati di numeri naturali ?” (si è dimostrato di sì) ∀x | x = a2+b2+c2+d2 è vero (“teorema dei 4

quadrati”)Più esattamente andrebbe scritto: ∀x ∃a,b,c,d | x = a2+b2+c2+d2

•  ∃ e ∀ sono chiamati “operatori di quantificazione”, e sono ben diversi da or, and e not

•  La parte della logica che tratta solo degli operatori or, and e not si chiama calcolo proposizionale

•  Aggiungendo gli operatori di quantificazione, si ha il calcolo dei predicati (che è molto più complesso)

Che cosa non si può modellare tramite espressioni logiche?

Problema: caratteri MaIuScOli

Si scriva un programma che, preso un carattere minuscolo da tastiera, ne riporta a video l’equivalente maiuscolo

Pseudocodice

{a, b, c, …, z}

1.  Richiedere linserimento di un carattere

2.  Se carattere inserito corretto3.  Allora stampa a video carattere-324.  Altrimenti stampa a video un

messaggio di errore

{a, b, c, …, z}

•  Il carattere inserito deve essere§ =>a§ <= z

Maiuscolo: solo if

Maiuscolo: esecuzione

•  Il carattere inserito deve essere§  X: =>a§  Y: <= z

•  Come vogliamo che si comporti il nostro modello rispetto a X e Y?

•  Come vogliamo che si comporti il nostro modello rispetto a X e Y?§  Se X = 0?

•  Come vogliamo che si comporti il nostro modello rispetto a X e Y?§  Se X = 0? Vogliamo una uscita FALSA

•  Come vogliamo che si comporti il nostro modello rispetto a X e Y?§  Se X = 0? Vogliamo una uscita FALSA§  Se Y = 0?

•  Come vogliamo che si comporti il nostro modello rispetto a X e Y?§  Se X = 0? Vogliamo una uscita FALSA§  Se Y = 0? Vogliamo una uscita FALSA

•  Come vogliamo che si comporti il nostro modello rispetto a X e Y?§  Se X = 0? Vogliamo una uscita FALSA§  Se Y = 0? Vogliamo una uscita FALSA§  Se X = 1 e Y = 1? Uscita VERA!

X Y USCITA0 0 00 1 01 0 01  1 1

Vi ricorda

qualche cosa?

X Y USCITA0 0 00 1 01 0 01  1 1

Vi ricorda

qualche cosa?

AND!!!

Vi ricorda

qualche cosa?

AND!!!

X Y X AND Y0 0 00 1 01 0 01  1 1

(prodotto logico)

Maiuscolo: AND

Maiuscolo: codice ottimizzato

Maiuscolo: esecuzione

Qualche cosa di più complesso…

•  Si accettano soltanto numeri dispari, primi, oppure maggiori di tre§  a: dispari§  b: primi§  c: maggiori di 3

a b c f(a,b,c) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

a b c f(a,b,c) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1

Per farlo…

Qualche definizione

Letterale

•  Un letterale è una coppia (Variabile,Valore)§  (x,1) è indicato come x (variabile in

forma naturale); §  (x,0) rappresenta la variabile x in forma

negata (complementata) ed è indicato come x’ (oppure !x).

Termine prodotto

•  Un termine prodotto è il prodotto logico o congiunzione (AND) di più letterali.

•  Un termine prodotto in cui compaiono letterali corrispondenti a tutte le variabili della funzione e tale per cui la configurazione di valori delle variabili definite dai letterali genera un valore 1 della funzione stessa nella tabella delle verità, costituisce un mintermine della funzione§  Ad esempio, a’b’c e ab’c rappresentano due

mintermini della funzione di cui si è prima data la tabella delle verità

•  Un termine prodotto in cui compaiono solo alcuni dei letterali e che corrisponda a un insieme di 1 della funzione è denominato implicante.

Termine somma (duale)

•  Un termine somma è la somma logica o disgiunzione (OR) di più letterali.

•  Un termine somma in cui compaiono letterali corrispondenti a tutte le variabili della funzione e tale per cui la configurazione di valori delle variabili definite dai letterali genera un valore 0 della funzione stessa nella tabella delle verità, costituisce un maxtermine della funzione§  Ad esempio, a+b+c e a+b’+c rappresentano due

maxtermini della funzione data

•  Un termine somma in cui compaiono solo alcuni dei letterali e che corrisponda a un insieme di 0 della funzione è denominato implicato.

Funzioni

•  Una funzione booleana di n variabili può essere espressa attraverso una espressione booleana di n variabili costituita da letterali, costanti, operatori AND, OR e NOT.

Funzioni

•  Una funzione booleana di n variabili può essere espressa attraverso una espressione booleana di n variabili costituita da letterali, costanti, operatori AND, OR e NOT.

•  Esempio di espressione booleana: f(a,b,c)=ab+a’c’

•  Il numero di espressioni booleane di n variabili definite su una algebra booleana B è infinito. §  La relazione tra espressioni booleane e

funzioni booleane non è 1 a 1

a b c f(a,b,c) 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1

f(a,b,c)= (a’*b’)’*a

f(a,b,c)= a

f(a,b,c)= ...

Ma quindi…

a b c f(a,b,c) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1

Ma quindi…

•  Data una funzione booleana§  ad esempio, mediante la tabella delle verità§  il problema è identificare almeno una

espressione booleana ad essa corrispondente

a b c f(a,b,c) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1

Ma quindi… diventa...

•  Data una funzione booleana§  ad esempio, mediante la tabella delle verità§  il problema è identificare almeno una

espressione booleana ad essa corrispondente

a b c f(a,b,c) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1

Come calcolare l’espressione booleana

•  Data una funzione booleana, la soluzione iniziale al problema di determinare una sua espressione consiste nel ricorso alle forme canoniche

•  Le forme canoniche sono:§  la forma somma di prodotti (SoP)§  quella prodotto di somme (PoS)

Prima forma canonica

•  Mettendo in OR i mintermini della funzione si ottiene l’espressione booleana della funzione stessa (SoP)

a b f(a,b) 0 0 0 0 1 1 1 0 0 1 1 1

f(a,b) =

a b f(a,b) 0 0 0 0 1 1 1 0 0 1 1 1

a b f2(a,b) 0 0 0 0 1 0 1 0 0 1 1 1

a b f1(a,b) 0 0 0 0 1 1 1 0 0 1 1 0

f(a,b) =

a b f(a,b) 0 0 0 0 1 1 1 0 0 1 1 1

a b f2(a,b) 0 0 0 0 1 0 1 0 0 1 1 1

a b f1(a,b) 0 0 0 0 1 1 1 0 0 1 1 0

a’b ab f(a,b) + =

Seconda forma canonica

•  Mettendo in AND i maxtermini della funzione si ottiene l’espressione booleana della funzione stessa (PoS)

a b f(a,b) 0 0 0 0 1 1 1 0 0 1 1 1

f(a,b) =

a b f(a,b) 0 0 0 0 1 1 1 0 0 1 1 1

a b f2(a,b) 0 0 1 0 1 1 1 0 0 1 1 1

a b f1(a,b) 0 0 0 0 1 1 1 0 1 1 1 1

f(a,b) =

a b f(a,b) 0 0 0 0 1 1 1 0 0 1 1 1

a b f2(a,b) 0 0 1 0 1 1 1 0 0 1 1 1

a b f1(a,b) 0 0 0 0 1 1 1 0 1 1 1 1

a+b a’+b f(a,b) = *

Il problema di partenza

a b c f(a,b,c) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1

!a!bc + !abc

a b c f(a,b,c) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1

!a!bc + !abc + a!bc

a b c f(a,b,c) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1

!a!bc + !abc + a!bc + ab!c

a b c f(a,b,c) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1

!a!bc + !abc + a!bc + ab!c + abc

a b c f(a,b,c) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1

!a!bc + !abc + a!bc + ab!c + abc

a b c f(a,b,c) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1

Il problema

•  Ridurre la complessità di una (o più) funzione(i) booleana(e) espressa(e) in forma di Prodotto di Somme o di Somma di Prodotti (SOP).

•  Si considerano le forme canoniche come soluzioni iniziali

Il problema

•  Ridurre la complessità di una (o più) funzione(i) booleana(e) espressa(e) in forma di Prodotto di Somme o di Somma di Prodotti (SOP).

•  Si considerano le forme canoniche come soluzioni iniziali

•  Obiettivi§  Riduzione del numero dei termini

prodotto (principale)§  Riduzione del numero di letterali

(secondario)

•  Si propone di identificare forme minime a due livelli applicando la regola di riduzione a Z + a' Z = (a+a') Z = Z con Z termine prodotto di n-1 variabili.§  Esempio: abcd’ + ab’cd’ = acd’

- 74 -

Karnaugh

•  La riduzione può essere applicata iterativamente§  Esempio: abc’d’+abc’d+abcd’+abcd= abc’(d’+d)

+abc(d’+d) = abc’+abc = ab(c’+c) = ab

- 75 -

Karnaugh

•  La riduzione può essere applicata iterativamente§  Esempio: abc’d’+abc’d+abcd’+abcd= abc’(d’+d)

+abc(d’+d) = abc’+abc = ab(c’+c) = ab

Nota: si osservi che la applicazione della relazione identificata è applicata ad un numero di termini pari a 2n quindi 2, 4, 8, ...

- 76 -

Karnaugh

Karnaugh sul nostro esempio

f(a,b,c)=!a!bc + !abc + a!bc + ab!c + abc

f(a,b,c)=!a!bc + !abc + a!bc + ab!c + abc!ac (!b + b) + a!bc + ab!c + abc

!ac + a!bc + ab!c + abc

!ac + a!bc + ab!c + abc!ac + a!bc + ab (!c + c)

!ac + a!bc + ab

•  Una mappa di Karnaugh è uno schema deducibile dalla rappresentazione geometrica delle configurazioni binarie.

•  Definizione utili:§  Distanza di Hamming: numero di bit che cambia nel

passare da una configurazione binaria ad un’altra•  Esempio: la distanza di Hamming tra le configurazioni 01001

e 10101 è 3 poiché cambiano 3 bit.

•  L’applicazione della regola di riduzione consiste nell’identificare le configurazioni binarie associate ai termini prodotto che sono a distanza di Hamming unitaria.§  Esempio: i termini prodotto abcd’ e ab’cd’

corrispondono a 1110 e 1010 e sono a distanza di Hamming pari ad 1.

- 83 -

Mappe di Karnaugh

•  Una funzione booleana a n variabili f: {0,1}n → {0,1} può essere rappresenta in modo comodo utilizzando una tabella della funzione o tabella della verità.

•  In modo assolutamente equivalente una funzione a n variabili può essere associata ad una rappresentazione cartesiana in uno spazio a n dimensioni

f(a,b,c)=ONset(001,011,101,110,111)

- 84 -

Funzione in uno spazio n-D

ONset= insieme di 1 della funzione

Punti a distanza di Hamming 1 in n-D

•  Nella rappresentazione cartesiana di una funzione in uno spazio a n dimensioni, collegando i vertici le cui configurazioni sono a distanza di Hamming unitaria si ottiene un n-cubo. §  Spazio a 1 dimensione (1 variabile)

•  È una linea, e l’1-cubo è un segmento: i due vertici sono associati alle configurazioni 0 e 1

§  Spazio a 2 dimensioni (2 variabili):•  È il piano, il 2-cubo è un quadrato che si ottiene dall’1-cubo per

proiezione. Si premette 0 alle configurazioni dei vertici originali, 1 a quelle dei vertici proiettati

- 85 -

§  Spazio a 3 dimensioni (3 variabili)•  Il 3-cubo è un solido, che si ottiene dal 2-cubo per proiezione, premettendo 0 alle configurazioni dei vertici originali, 1 a quelle dei vertici proiettati

- 86 -

101 100

111 110

001 000

011 010

Punti a distanza di Hamming 1 in n-D

f(a,b,c)=ONset(001,011,101,110,111)

- 87 -

f(a,b,c)=ONset(001,011,101,110,111)

- 88 -

101 100

111 110

001 000

011 010 a

0 dove

•  Di fatto, la rappresentazione in uno spazio a n dimensioni non è maneggevole §  Quindi, si passa allo sviluppo nel piano dei cubi§  Lo sviluppo nel piano di un 3-cubo implica il taglio del

cubo§  Il taglio deve mantenere intatta, concettualmente, la

adiacenza fra vertici. Si presti molta attenzione all’ordinamento delle coordinate•  Ordinamento delle coordinate mantiene le distanze di

Hamming e non coincide con la numerazione consecutiva

- 89 -

Sviluppo nel piano dei cubi

•  Di fatto, la rappresentazione in uno spazio a n dimensioni non è maneggevole §  Quindi, si passa allo sviluppo nel piano dei cubi§  Lo sviluppo nel piano di un 3-cubo implica il taglio del

cubo§  Il taglio deve mantenere intatta, concettualmente, la

adiacenza fra vertici. Si presti molta attenzione all’ordinamento delle coordinate•  Ordinamento delle coordinate mantiene le distanze di

Hamming e non coincide con la numerazione consecutiva

- 90 -

101 100

111 110

001 000

011 010 a

0 dove

00 01 11 10 0 1

0 0 1 0 1 1 1 1

Sviluppo nel piano dei cubi

•  Si ricorda che: un implicante è un termine prodotto in cui compaiono solo alcuni dei letterali.

- 91 -

00 01 11 10 00 01 11 10

1 1 0 0 0 0 0 1 0 0 0 1 1 0 0 1

a,b c,d

F(a,b,c,d)=a’b’c’d’+a’b’cd’+a’bc’d’+ab’c’d+ ab’cd+ab’cd’

F(a,b,c,d)=a’b’d’+a’c’d’+...

raggruppamento 1

raggruppamento2

Implicante 1

Implicante 2

raggruppamento 1

raggruppamento 2

Caratteristiche delle mappe

1.  Individuare gli implicanti primi e primi essenziali;§  Implicante primo

•  Termine prodotto associato ad un raggruppamento di dimensione massima.

§  implicante primo essenziale•  Implicante primo che copre uno o più 1 non coperti

da nessun altro implicante primo.2. Copertura:

§  Scelta del minor numero di implicanti primi e primi essenziali

- 92 -

implicanti implicanti primi implicanti primi essenziali

Metodo

•  Identificare una forma SoP che includa il numero minimo di implicanti e – a parità di numero di prodotti – gli implicanti col minimo numero di letterali (definita come forma minima) garantendo la copertura di tutti gli 1 della funzione.

•  Teorema:§  Esiste sicuramente una forma minima costituita da soli

implicanti primi •  sulla mappa di Karnaugh si identificano tutti gli implicanti primi.

–  Nota: la somma di tutti gli implicanti primi è spesso ridondante. §  Implicanti primi essenziali devono essere inclusi nella forma

minima.§  Una forma minima costituita da soli implicanti primi

essenziali è unica•  Condizione sufficiente.

- 93 -

Scopo delle mappe

Esempio

- 94 -

00 01 11 10 00 01 11 10

1 1 0 0 1 1 1 1 0 0 1 1 1 0 0 1

a,b c,d

1 1 0 0 1 1 1 1 0 0 1 1 1 0 0 1

raccoglimento

Raccoglimento di dimensione massima

ERRORE: valido raccoglimento solo di 2,4,...

- 95 -

00 01 11 10 00 01 11 10

1 1 0 0 1 1 1 1 0 0 1 1 1 0 0 1

a,b c,d

1 1 0 0 1 1 1 1 0 0 1 1 1 0 0 1

Raccoglimento di dimensione massima essenziale

1 appartenente ad un solo implicante primo

Raccoglimento di dimensione massima

Esempio: continua

•  Ad ogni raccoglimento è associato un termine prodotto.

•  Il termine prodotto (implicante) è ottenuto:§  identificando le variabili che non

cambiano mai di valore §  riportando ogni variabile in modo

naturale •  (esempio: a) se il valore che essa assume è 1 •  in modo complementato (esempio: a’) se il

valore da essa assunto è 0

- 96 -

Definizione del termine prodotto

- 97 -

00 01 11 10 00 01 11 10

1 1 0 0 1 1 1 1 0 0 1 1 1 0 0 1

a,b c,d

1 1 0 0 1 1 1 1 0 0 1 1 1 0 0 1

c,d 11 10

b e d cambiano valore: non compaiono nel termine prodotto. a e c compaiono come 0 quindi a’ e c’ . Il termine prodotto è a’c’.

d cambia valore

b cambia valore !

Identificazione del termine prodotto

•  Sotto insieme degli implicanti identificati tale per cui nessun 1 della funzione rimane scoperto.§  Poiché ogni implicante scelto aumenta il

costo della realizzazione della funzione, il numero di implicanti da scegliere deve essere il minore possibile.

§  L’obiettivo è la riduzione del costo; questo si traduce nella identificazione della copertura di minima cardinalità: •  sotto insieme degli implicanti primi e primi ed

essenziali identificati che realizza una copertura della funzione che è di cardinalità minima.

- 98 -

Copertura

1. Si scelgono tutti gli implicanti primi essenziali.§  Gli implicanti primi essenziali devono essere

parte della copertura poiché “sono essenziali” e, quindi, non è possibile fare a meno di loro.

2. Si eliminano tutti gli implicanti primi che sono coperti da quelli essenziali (eliminazione implicanti completamente ridondanti)§  gli implicanti eliminati, detti completamente

ridondanti, coprono degli 1 che sono già ricoperti da quelli essenziali e, quindi, non servono ed aumentano il costo.

3. Si seleziona il numero minore degli implicanti primi che sono rimasti.§  gli implicanti residui sono detti parzialmente

ridondanti.

- 99 -

Copertura: scelta implicanti

- 100 -

E quindi, il nostro esempio…

a b c f(a,b,c) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1

f (a,b,c) = 001,011,101,110,111( )∑

00 01 11 10 0 1

0 0 1 0 1 1 1 1

- 101 -

a b c f(a,b,c) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1

f (a,b,c) = 001,011,101,110,111( )∑Implicanti primi essenziali

00 01 11 10 0 1

0 0 1 0 1 1 1 1

- 102 -

a b c f(a,b,c) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1

f (a,b,c) = 001,011,101,110,111( )∑

Implicanti primi essenziali

00 01 11 10 0 1

0 0 1 0 1 1 1 1

- 103 -

a b c f(a,b,c) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1

f (a,b,c) = 001,011,101,110,111( )∑

Implicanti primi essenziali

00 01 11 10 0 1

0 0 1 0 1 1 1 1

f(a,b,c)= ab + c Forma minima

Osservazione

•  Ma se la forma minima èf(a,b,c) = ab + c

00 01 11 10 0 1

0 0 1 0 1 1 1 1

Osservazione

•  La soluzione (S78)f(a,b,c) = !ac + a!bc + ab ?

00 01 11 10 0 1

0 0 1 0 1 1 1 1

Osservazione

•  La soluzione (S78)f(a,b,c) = !ac + a!bc + ab ?

00 01 11 10 0 1

0 0 1 0 1 1 1 1

00 01 11 10 0 1

0 0 1 0 1 1 1 1

Problemi di fine giornata…

•  Si scriva un programma in C che richiede l’inserimento di un numero intero positivo, se l’inserimento e’ errato ritorna un messaggio di errore

•  Si scriva un programma in C che, dati due caratteri, li ordina in ordine alfabetico “inverso”

Appendice (utile per la prox exe)

•  Tautologia§  Una espressione logica che è sempre vera, per

qualunque combinazione di valori delle variabili•  Esempio: principio del “terzo escluso”: A or not A

(tertium non datur, non si dà un terzo caso tra l’evento A e la sua negazione)

•  Contraddizione§  Una espressione logica che è sempre falsa, per

qualunque combinazione di valori delle variabili•  Esempio: principio di “non contraddizione”: A and not

A (l’evento A e la sua negazione non possono essere entrambi veri)

Tautologie e Contraddizioni

•  Due espressioni logiche si dicono equivalenti (e si indica con ⇔) se hanno la medesima tabella di verità. La verifica è algoritmica. Per esempio:

A B not A and not B ⇔ not (A or B)

0 0 1 and 1 = 1 not 0 = 1

0 1 1 and 0 = 0 not 1 = 0

1 0 0 and 1 = 0 not 1 = 0

1 1 0 and 0 = 0 not 1 = 0

•  Espressioni logiche equivalenti modellano gli stessi stati di verità a fronte delle medesime variabili

Equivalenza tra espressioni

Proprietà dell’algebra di Boole

•  L’algebra di Boole gode di svariate proprietà, formulabili sotto specie di identità§  cioè formulabili come equivalenze tra espressioni

logiche, valide per qualunque combinazione di valori delle variabili

Algebra Booleana a due valori: Assiomi

•  Gli operatori descritti godono delle proprietà definite dai seguenti assiomi (postulati di Huntington):

§  Le operazioni di disgiunzione (+) e congiunzione (·) sono commutative, cioè per ogni elemento a,b ∈ B

a+b = b+a a·b = b·a §  Esiste un elemento neutro (o identità) rispetto a +

(indicato con 0) e un elemento neutro rispetto a · (indicato con 1), cioè:

a+0=a a·1=a §  Le due operazioni sono distributive rispetto all’altra,

cioè per ogni a,b,c ∈ B, risulta: a+(b·c)=(a+b)·(a+c) a·(b+c)=(a·b)+(a·c)

§  Per ogni a ∈ B esiste l’elemento a’∈ B, detto negazione logica o complemento di a, tale che:

a+a’=1 a·a’=0

” in

un’o

Algebra di Commutazione: Proprietà 1

1: associativaa+(b+c)=(a+b)+c a*(b*c)=(a*b)*c

2: idempotenzaa+a=a a*a=a

3: elemento nulloa+1=1 a*0=0

4: unicità elemento inverso: il complemento di a, a’, è unico

5: assorbimentoa+(a*b)=a a*(a+b)=a

- 114 -

6: Semplificazionea+a’b = a+b a*(a’+b) = a*b

7: involuzione ((a)’)’ = a

8: Leggi di De Morgan(a+b)’ = a’*b’ (a*b)’ = a’+b’

9: consensoa*b+a’*c+b*c = a*b + a’*c (a+b)*(a’+c)*(b+c)=(a+b)*(a’+c)

Algebra di Commutazione: Proprietà 2

•  Trasformare un’espressione logica in un’altra, differente per aspetto ma equivalente:

not A and B or A = (assorbimento)=  not A and B or (A or A and B) = (togli le parentesi)=  not A and B or A or A and B = (commutativa)=  not A and B or A and B or A = (distributiva)=  (not A or A) and B or A = (legge dell’elemento 1)=  true and B or A = (vero and B à B)=  B or Aè più semplice dell’espressione originale

•  Si può verificare l’equivalenza con le tabelle di verità•  Occorre conoscere un’ampia lista di proprietà e si

deve riuscire a “vederle” nell’espressione (talvolta è difficile)

Uso delle proprietà

Fonti per lo studio + Credits

•  Fonti per lo studio§  Introduzione ai sistemi informatici, D.

Sciuto, G. Buonanno, L. Mari, 4a Ed, McGrawHill•  Capitolo 2

•  Credits§  Daniele Braga

•  http://home.dei.polimi.it/braga/§  Cristiana Bolchini

•  http://home.dei.polimi.it/bolchini/didattica/retilogichea/index.htm

Algebra di Boole, elementi di logica e Mappe di...

Documents

Transcript of Algebra di Boole, elementi di logica e Mappe di...

L'algebra di Boole e la minimizzazione di funzioni booleanewpage.unina.it/edoardo.fusella/ei/downloads/Algebra di Boole.pdf · L'algebra di Boole e la minimizzazione di funzioni booleane

Algebra di Boole - DIMES Unicalsi.deis.unical.it/~talia/aa0304/fond/lezione5x2.pdf · Algebra di Boole: Concetti di base Fondamenti di Informatica - D. Talia - UNICAL 2 10110 01100

L’ algebra di Boole

Fondamenti dell’Informatica Algebra di Boole

Settembre 2002IFTS2002 Acq. Dati Remoti: INFORMATICA1 Lalgebra di Boole.

Algebra di Boole - na.icar.cnr.itdepietro.g/DePietro/L04Boole.pdf · • Un reticolo distributivo, dotato di minimo e massimo assoluti e complementato, si dice un'algebra di Boole

Esercizio - Algebra di Boole, Aritmetica Binaria, Codifica ... · Esercizio - Algebra di Boole, Aritmetica Binaria, Codifica delle Informazioni ( 2,5 punti ) (a) Si costruisca la

L’algebra di Boole AD

Algebra di Boole ed elementi di logicahome.deib.polimi.it/santambr/dida/infob/1516/doc/PDF/3...Algebra Booleana a due valori: Algebra di Commutazione “Tra tutte le algebre booleane,

Proposizioni logiche e algebra di Boolewpage.unina.it/edoardo.fusella/ei/downloads/02_boole.pdf · Algebre di Boole 19 La definizione di Algebra di Boole non specifica quale sia K

Algebra di Boole. George Boole (1815-1864) (1815-1864)

ALGEBRA DI BOOLE Lalgebra di Boole è un sistema algebrico sviluppato a metà dell800 dal matematico e logico inglese George Boole, per formalizzare la sillogistica.

Algebra di Boole - Unicalsi.deis.unical.it/~talia/aa0304/fond/lezione5.pdfFondamenti di Informatica - D. Talia - UNICAL 2 10110 01100 01011 Algebra di Boole E’ un’algebra basata

Algebra di Boole - Intranet DEIBhome.deib.polimi.it/ferrandi/reti_logiche_A/lezione2.pdf · Teorema di espansione di Shannon Versione del 19/09/03 Algebra di Boole - 2 - Algebra Booleana:

Lab 0: 23 Marzo 2015 - Intranet DEIBhome.deib.polimi.it/santambr/dida/ieim/2015/labs/IEIM_Lab0_V0.pdf · quindi lanciando Geany 14 DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE Desktop

IEIM 0 INTRO 2011 - Intranet DEIBhome.deib.polimi.it/gpalermo/doc/IEIM/IEIM_0_6PP.pdf · INFORMATICA E ELEMENTI DI ... "Informaca. arte e mesere", Terza Edizione, McGraw‐Hill Libri

Struttura Programmi Algebra di Boole

Algebra di Boole - polimi.it

Algebra di Boole. Chi era Boole? George Boole, è stato un matematico e logico britannico, ed è considerato il fondatore della logica matematica. Nel 1854,

Logica e Algebra de Boole