Post on 18-Feb-2019
transcript
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)