Algebra Booleana

George Boole

1815 – 1864

Wikipedia, the Free Encyclopedia

www.wikipedia.org

http://en.wikipedia.org/wiki/George_Boole

1

Logica delle Proposizioni

LogicaIn filosofia, lo studio delle leggi e delle funzioni che caratterizzano la struttura del pensiero in sé (logica formale), oppure dei procedimenti seguiti dal pensiero in riferimento ai diversi contenuti cui può applicarsi (logica materiale).Logica matematica (o simbolica), lo studio della formalizzazione dei procedimenti e delle operazioni logiche in linguaggio matematico (Devoto-Oli, “Il Vocabolario della Lingua Italiana”, Le Monnier, 2008).

ProposizioneEspressione del linguaggio alla quale può essere attribuito un valore di verità: vero o falso.

2

Proposizioni atomiche Valori di verità

+Proposizioni composte

NOT A

A AND B

A OR B

A XOR B

IF A THEN B

A IFF B

Vero = 1

Falso = 0

Calcolo Proposizionale

Bergamo è una città e i Caniana erano intarsiatori, scultori e

architetti tra i più celebri nell'Italia settentrionale.

NOT , NON , , -

AND , E , , ,

OR , O , , + ,

XOR , ,

IF..THEN , SE..ALLORA ,

IFF, SSE ,

Connettivi

3

Calcolo Proposizionale

“Partecipate al corso!” è una proposizione?

I connettivi che utilizziamo sono delle operazioni vero-funzionali, ciò significa che l’applicazione delle operazioni modifica la falsità o la verità delle proposizioni coinvolte.

Ogni operazione è una funzione che può essere rappresentata mediante una tabella.

Una formula composta che viene interpretata sempre come vera viene detta tautologia (dal greco, che dice lo stesso). Ad esempio: A A ,(A B) ( B A).

4

Obiettivi

Capacità di estrarre (tutte e sole) le informazioni utili a risolvere un dato problema

Essere in grado di formalizzare e risolvere un problema analizzando tutti i casi possibili in modo esaustivo

Saper ricavare il valore di verità delle formule (atomiche e molecolari) a partire da valori di verità noti

5

Tavola di verità

esempio - (a = b) a b

A NOT A

0 1

1 0

a = b - (a = b)

0 1

1 0

Operatore NOT (negazione)

6

Tavola di verità

esempio

A B A AND B

0 0 0

0 1 0

1 0 0

1 1 1

x -2 x < 1 (x -2)(x < 1)

0 0 00 1 01 0 01 1 1

Operatore AND (congiunzione)

7

A B A OR B

0 0 0

0 1 1

1 0 1

1 1 1

n pari n 9 ( n pari) + ( n 9)

0 0 0

0 1 1

1 0 1

1 1 1

Operatore OR (disgiunzione)

Tavola di verità

esempio

8

Esercizi “on the fly”

Se A = Vero, B = Falso, C = Vero,qual è il valore di verità delle seguenti espressioni?

A or (not B and C)

A and Falso

B or Vero

A and B and C

9

Esercizi

Costruire la tavola di verità di:

A or Vero (A or Falso)

A and Vero (A and Falso)

not (not (A))

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

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

10

Priorità

Imponiamo le seguenti priorità ai connettivi dalla più alta alla più bassa:

1. not

2. and

3. or

4. if..then, iff

Un esempio di cancellazione delle parentesi è dato dalla seguente formula((if (A or (not B)) then C) iff A)che può essere scritta senza parentesi.

13

A B -A -B A B - (A B) (-A) + (-B)

1 1 0 0 1 0 0

0 1 1 0 0 1 1

1 0 0 1 0 1 1

0 0 1 1 0 1 1

A B -A -B A+B - (A+B) (-A) (-B)

1 1 0 0 1 0 0

0 1 1 0 1 0 0

1 0 0 1 1 0 0

0 0 1 1 0 1 1

NOT (A AND B) = (NOT A) OR (NOT B)

NOT (A OR B) = (NOT A) AND (NOT B)

Leggi di De Morgan

14

Osservazioni

Le leggi di De Morgan sono utili per negare espressioni

complesse:

not ( x>5 or y<3 ) = not (x>5) and not (y<3)

Le leggi di De Morgan mostrano che i tre operatori AND OR

NOT non sono indipendenti

E’ possibile esprimere AND tramite OR e NOT:

A and B = not not ( A and B ) = not ((not A) or (not B))

E’ possibile esprimere OR tramite AND e NOT:

A or B = not not (A or B) = not ((not A) and (not B))

15

Costruire la tabella di verità delle espressioni logiche:

1) A (- B) + C

2) A + B (C (- C))

3) A B + (C (- C))

4) (A + (- A)) B

Applicare le leggi di De Morgan a:

5) -(A + (- B) + C)

6) -(-(A + (- B) (- C)))

7) -(-A (- B) (- C))

Esercizi

16

A B A XOR B

0 0 0110

0 1

1 0

1 1

n pari n > 9 n pari n > 9

0 0 0

1

1

0

0 1

1 0

1 1

Operatore XOR (disgiunzione esclusiva)

Tavola di verità

esempio

17

Esercizi

Se A = Vero, B = Vero, C = Falso,qual è il valore di verità di:

A xor (B or C)

A xor B xor C

(A and B) xor C

Costruire la tavola di verità di:

A xor B xor A

not (A xor B)

18

A B -A -B (-A) B A (-B) (-A B) + (A (-B)) A B

1 1

0 1

1 0

0 0

A B -A -B (-A) B A (-B) (-A B) + (A (-B)) A B

1 1 0 0

0 1 1 0

1 0 0 1

0 0 1 1

A B -A -B (-A) B A (-B) (-A B) + (A (-B)) A B

1 1 0 0 0 0 0

0 1 1 0 1 0 1

1 0 0 1 0 1 1

0 0 1 1 0 0 0

A B -A -B (-A) B A (-B) (-A B) + (A (-B)) A B

0 0 0 0 0 0

0 1 1 0 1 1

1 0 1 0 1 1 1

0 1 1 0 0 0 0

A B (-A B) + (A (-B ) )

19

Implicazione logica

Equivalenza logica

A B A B

0 0 1

0 1 11 0 0

1 1 1

A B A B

0 0

0 1

1 0

1 1

IF THEN e IFF

(AB) (BA)

A implica B

A è condizione sufficiente per B

B è condizione necessaria per A

NOT A OR B

1

0

0

120

Con il solo NAND

si possono esprimere

AND, OR e NOT

A NAND B not ( A and B )

not A = A nand A

A and B = not not(A and B)= not(A nand B)

=(A nand B)nand (A nand B)

A or B = not not(A or B)= not(not A and not B)

= (not A) nand (not B)

= (A nand A) nand (B nand B)

A B A nand B

V V F

V F V

F V V

F F V

21

Verificare la validità delle identità logiche:

1) (-A + B) (A B)

2) (A + (-A)) Vero

3) (A (-A)) Falso

4) (A xor B xor B) A

L’operatore NOR è definito da:

A NOR B -(A+B)

Verificare che:

- A A NOR A

A + B NOT (A NOR B)

A B (NOT A) NOR (NOT B)

Esercizi

22

Operatori booleani

Nelle formule di Excel

Nella riga dei criteri nelle query di Access

Nei motori di ricerca in Internet

Nei linguaggi di programmazione

Nella progettazione dei circuiti logici

Nella crittografia

23

Dalla tabella alla funzione booleana

A (- B)

(-A) (- B)

A B F(A,B)

1 1 0

1 0 1

0 1 0

0 0 1

F(A,B) = A(-B) + (-A)(-B)

= ( A + (- A)) (- B)

= Vero (- B)

= - B

24

Esercizio: correttezza di un voto universitario

Errore = not(Voto30) and Lode

OK = not Errore = (Voto30) or not Lode

Voto30 Lode Errore OK

V V F V

V F F V

F V V F

F F F V

25

Progettazione dei circuiti logici

Somma di due bit (S) con riporto (R)

Controllo di parità pari (P) e dispari (D)

A B S R

0 0 0 0

0 1 1 0

1 0 1 0

1 1 0 1

A B P D

0 0 0 1

0 1 1 0

1 0 1 0

1 1 0 1

_ _

S = A B + A B

R = A B

_ _

P = A B + A B_ _

D = A B + A B

26

Progettazione dei circuiti logici

Confronto fra due bit: A=B; A>B

A B U M

0 0 1 0

0 1 0 0

1 0 0 1

1 1 1 0

_ _

U = A B + A B_

M = A B

– Confronto fra due bit

A >= B: M or U

A <= B: not M

A < B: not(M or U)=(not M)and(not U)

A B: not U 27

Espressioni Motore di ricerca

AND Unisce due parole che devono essere

presenti entrambe nella ricerca

OR Si usa quando è sufficiente che nel risultato

compaia una sola parola

AND NOT Precede una parola che si vuole escludere

dalla ricerca

NEAR Trova i documenti che contengono

entrambe le parole indicate ad una distanza

max di altre 10

PARENTESI Attribuiscono una priorità ad

un’espressione booleana (espressione

algebrica)28

L'inglese vive nella casa rossa

Lo svedese ha un cane

Il danese beve tè

La casa verde è immediatamente a sinistra della casa bianca

Il proprietario della casa verde beve caffè

Il signore che fuma sigarette Pall Mall alleva uccelli

Il proprietario della casa gialla fuma sigari Dunhill

Il signore che abita nella casa al centro beve latte

Il norvegese vive nella prima casa

Il signore che fuma la pipa con tabacco Blends vive accanto a quello che ha un gatto

Il proprietario del cavallo vive accanto a quello che fuma sigari Dunhill

Il signore che fuma sigari Bluemasters beve birra

Il tedesco fuma sigarette Prince

Il norvegese vive accanto alla casa blu

Il signore che fuma tabacco Blends vive accanto a quello che beve acqua.

Chi possiede il pesce rosso?

Quiz famoso. In una strada ci sono 5 case affiancate di 5 colori diversi. In ogni casa vive una persona di nazionalità diversa. Ognuno di essi beve un diverso tipo di bibita, fuma una diversa marca di sigari ed ha un diverso animale domestico. Inoltre:

29