Informatica - algebra boleana 1

ALGEBRA BOOLEANA

Logica delle Proposizioni

Proposizione: frase alla quale può essere

attribuito un valore di verità: vero o falso

Logica: In filosofia, lo studio delle funzioni

proprie della struttura e dell’attività del pensiero in

sè (l.formale), oppure dei procedimenti seguiti dal

pensiero in riferimento ai diversi contenuti cui può

applicarsi (l.materiale). L.matematica (o

simbolica), lo studio delle operazioni logiche, che

le formalizza in linguaggio matematico.

(Devoto-Oli, “Il Dizionario della Lingua Italiana”, Le

Monnier, 2002-03) 1

ALGEBRA BOOLEANA

Calcolo Proposizionale

George Boole 1815 – 1864

In matematica, informatica ed elettronica,

l'algebra di Boole è un ramo dell'algebra

astratta che comprende tutte le algebre che

operano con i soli valori di verità 0 o 1,

detti variabili booleane o logiche.

L'algebra booleana è finalizzata al calcolo

proposizionale ALGEBRA BOOLEANA

Calcolo Proposizionale Vero = 1

→

Proposizioni atomiche Valori di verità Falso = 0

+

Connettivi Proposizioni composte

∧ • ∩

AND , , , A AND B

∨ ∪

OR , , + , A OR B

∨ ⊕ A XOR B

XOR , ,

¬ NOT A

NOT , , - 2

Operatore AND (congiunzione)

A B A and B

Tavola di verità 1 1 1

0 1 0

1 0 0

0 0 0

•

Esempio è martedì è marzo è martedì è marzo

1 1 1

0 1 0

1 0 0

0 0 0

Oggi è martedì Siamo in marzo È un martedì di marzo

Operatore OR (disgiunzione)

Tavola di verità A B A or B

1 1 1

0 1 1

1 0 1

0 0 0

≥ ≥

Esempio n pari n 9 +

( n pari) ( n 9)

1 1 1

0 1 1

1 0 1

0 0 0 3

Operatore NOT (negazione)

A not A

Tavola di verità 1 0

0 1 ≡ ≠

a = b -

Esempio - (a = b) a b

a = b)

( ≡ ≠

not (a = b) a b

1 0

0 1

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

4

Funzioni logiche in Excel

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)

5

Esercizi

A or F = A A Falso A or Vero

V F V

F F F

A Vero A and Vero

A and V = ? V V

F V

Esercizi

A not A not not A

V

F

A B A or B not(A or B)

V V

V F

F V

F F 6

Proprietà

Gli operatori introdotti godono di numerose proprietà:

Commutativa ed associativa

Distributiva

– A and ( B or C ) = ( A and B ) or ( A and C )

– A or ( B and C ) = ( A or B ) and (A or C)

not not A = A

A and A = A A or A = A

A or (notA) = Vero A and (notA) = Falso

….

Leggi di De Morgan

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

• •

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

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

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 7

Osservazioni

Le leggi di De Morgan sono utili per negare espressioni complesse:

– not(X>5 or N<1000) = not(X>5) and not(N<1000)

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

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))

. . .

Operatore XOR (disgiunzione esclusiva)

Tavola di verità A B A xor B

1 1 0

XOR 1

0 1

A è diverso da B 1

1 0 0

0 0 ⊕

Esempio n pari n > 9 n pari n > 9

1 1 0

0 1 1

1 0 1

0 0 0 8

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 B

not (A xor B)

Operatori: IF THEN ed IFF

Implicazione logica A B A B

⇒

1 1 1

A implica B 0 1 1

A è condizione sufficiente per B

notA or B 1 0 0

0 0 1

≡

Equivalenza logica A B A B

1

1 1 0

• 0 1

(A B)•

(B A)

⇒ ⇒ 0

1 0 1

0 0 9

≡

A NAND B not ( A and B) A B A nand B

V V F

Con il solo NAND

si possono esprimere V F V

AND, OR e NOT F V V

F F V

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 B) + (A (-B ) )

• • • • ≡

⊕

A B -A -B A

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

0 0 0 0

1 1 0 0 1 0 1 1

0 1 1 0 0 1 1 1

1 0 0 1 0 0 0 0

0 0 1 1 10