ALGEBRA BOOLEANA

Prof. Pagani Corrado

INTRODUZIONE

L'algebra di Boole è definita da G. Boole, britannico, seconda metà ’800

E’ un modello matematico che rappresenta le leggi della logica utilizzando variabili binarie che possono cioè assumere solo due valori (che si escludono a cioè assumere solo due valori (che si escludono a vicenda):

� il valore falso

� il valore vero

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

IL SISTEMA NUMERICO BINARIO

� Anche i moderni calcolatori utilizzano il sistema

numerico binario (1 e 0), messo a punto dallo

stesso Boole, per poter rappresentare

un’informazione.un’informazione.

� Questi valori, all'interno dell'architettura dei

calcolatori, sono abbinati a due tensioni

differenti denominate livello logico alto e livello

logico basso.

LE OPERAZIONI FONDAMENTALI

Le operazioni fondamentali dell'algebra di Boolesono tre:

� Operatori logici binari (con 2 operandi logici) 1. Operatore OR, o somma logica

2. Operatore AND, o prodotto logico 2. Operatore AND, o prodotto logico

� Operatore logico unario (con 1 operando) 3. Operatore NOT, o negazione

Attraverso queste operazioni è possibile realizzare tutte le altre operazioni più complesse che un calcolatore è in grado di compiere.

TABELLE DI VERITA’

� Poiché gli operandi logici ammettono due soli

valori, si può definire compiutamente ogni

operatore logico tramite una tabella di

associazione operandi-risultato detta tabella di associazione operandi-risultato detta tabella di

verità.

� Le tabelle elencano tutte le possibili

combinazioni in ingresso e il risultato associato

a ciascuna combinazione.

SOMMA LOGICA – OR

A B A or B

0 0 0

1 0 1

0 1 1

1 1 1

PRODOTTO LOGICO – AND

A B A and B

0 0 0

1 0 0

0 1 0

1 1 1

SOMMA LOGICA ESCLUSIVA – XOR

A B A xor B

0 0 0

1 0 1

0 1 1

1 1 0

NEGAZIONE LOGICA – NOT

A Not A

0 1

1 0

ESPRESSIONI LOGICHE

� Sono costruite analogamente alle espressioni algebriche, costruite con:� Costanti logiche: valori 0 o 1

� Variabili logiche (letterali)

� Operatori logici: and, or, not� Operatori logici: and, or, not

� Es � A or (B and C) or (A and (not B)) or (B and C)

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

� Per ricordarlo, si pensi OR come “+” (più), AND come “×” (per) e NOT come “−” (cambia segno)

TABELLE DI VERITÀ DELLE ESPRESSIONI

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

0 0 ?

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

0 0 ?

1 0 ?

0 1 ?

1 1 ?

TABELLE DI VERITÀ DELLE ESPRESSIONI

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

0 0 1

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

0 0 1

1 0 1

0 1 0

1 1 1

ESPRESSIONI CON 3 OPERANDI

A B C A and B or not C

0 0 0 ?

0 0 1 ?

A and B or not C

0 0 1 ?

0 1 0 ?

0 1 1 ?

1 0 0 ?

1 0 1 ?

1 1 0 ?

1 1 1 ?

ESPRESSIONI CON 3 OPERANDI

A B C A and B or not C

0 0 0 1

0 0 1 0

A and B or not C

0 0 1 0

0 1 0 1

0 1 1 0

1 0 0 1

1 0 1 0

1 1 0 1

1 1 1 1

MODELLARE FORME DI RAGIONAMENTO

� A = è vero che ci troviamo all’aperto?

(supponiamo di no) �A = 0

� B = è vero che oggi piove ? (supponiamo di sì)

� B = 1 � B = 1

� A and B � espressione che ci indica se la

pioggia ci bagna = risulta falsa

� Se usciamo dalla scuola diventa vera

TAUTOLOGIE E CONTRADDIZIONI

� Tautologia � Una espressione logica che è

sempre vera, per qualunque combinazione di

valori delle variabili

� A or not A � A or not A

� Contraddizione � Una espressione logica che

è sempre falsa, per qualunque combinazione di

valori delle variabili

� A and not A

PROPRIETA’

� L’algebra di Boole gode di svariate proprietà,

formulabili sotto specie di identità (cioè

equivalenze tra espressioni logiche, valide per

qualunque combinazione di valori delle qualunque combinazione di valori delle

variabili)

� Esempio celebre: le Leggi di De Morgan

� not (A and B) = not A or not B (1a legge)

� not (A or B) = not A and not B (2a legge)

INDOVINELLI LOGICI

� Un'ampia classe di indovinelli logici elementari

può essere risolta usando le leggi dell'algebra

booleana e le tavole di verità.

� Indovinelli dell’isola dei cavalieri e dei furfanti� Indovinelli dell’isola dei cavalieri e dei furfanti

� Su questa isola di fantasia, tutti gli abitanti

sono o cavalieri, che dicono sempre la verità, o

furfanti, che mentono sempre

ENIGMA 1

� Arturo e Bernardo sono abitanti dell'isola dei

cavalieri e dei furfanti.

� Arturo dice: “Siamo entrambi furfanti”.

� Di che tipo sono?� Di che tipo sono?

� Possiamo usare l'algebra booleana: sia A vera

se Arturo è un cavaliere e B vera se Bernardo è

un cavaliere.

SOLUZIONE ENIGMA 1

� O Arturo è un cavaliere e quello che dice è vero o

Arturo non è un cavaliere e quello che dice è

falso

(A and (not A and not b)) or (not A and not(not A and not b))(A and (not A and not b)) or (not A and not(not A and not b))

Contraddizione � sempre

falsa � posso ignorare la

parte prima dell’OR

per la legge di de Morgan

Not A and ( A or B )

A deve essere FALSO

Di conseguenza B deve essere VERO

Soluzione � Arturo è un furfante mentre Bernardo è un cavaliere

SOLUZIONE ENIGMA 1 CON EXCEL

Traduzione dell’espressione booleana…

(A and (not A and not b)) or (not A and not(not A and not b))

…con la sintassi di excel (elenco tutte le combinazioni possibili svolgendo la tabella di verità)…

O(E(A1;(E(NON(A1);NON(B1))));(E(NON(A1);NON(E(NON(A1);NON(B1))))))

ESERCIZI

� Valutare il risultato delle seguenti espressioni� VERO and (FALSO or (not (FALSO and VERO)))

� A OR (not ((B or not B)) and A)

� Determinare la tabella di verità delle seguenti espressioni (verificare poi con excel)espressioni (verificare poi con excel)� Not A and B or not B and C OR A and B

� A or (B and C) or not (C and A)

� Verificare l’equivalenza delle seguenti espressioni: � R = A and not B or not a and b

� S = not (not a and not b or a and b)