Algebra di Boole e
Funzioni Binarie
Lezione Prima
Sommario
•
•
•
•
•
•
•
Variabili Binarie
Negazione
Somma Logica
Prodotto Logico
Relazioni- proprietà
Funzioni
Minterm
•
•
•
•
•
Teoremi
Maxterm
Forme Canoniche
Mappe di Karnaugh
Fine lezione
Prof. Abramo Carmelo
2
Variabili Binarie
• Variabile binaria: grandezza matematica
che può assumere due soli valori: 0 o 1.
• Sulle variabili binarie definiamo tre
operatori: negazione, somma e prodotto.
• La negazione di una variabile binaria x si
indica con x° (“non x” o “x negato”)
Prof. Abramo Carmelo
3
Negazione
• Possiamo rappresentare il valore di x°
tramite tabella di verità:
x
x°
0
1
1
0
Prof. Abramo Carmelo
4
Somma logica
• La somma di n variabili binarie x1, x2, x3, --- xn vale 0
solo se tutte le xi (1≤i≤n) valgono contemporaneamente
0, vale 1 in ogni altro caso.
x1
x2
x1 + x2
0
0
0
0
1
1
1
0
1
1
1
1
esempio di somma logica di due variabili x1 e x2 mediante tabella di verità
Prof. Abramo Carmelo
5
Prodotto logico
• Il prodotto di n variabili binarie x1, x2, x3, --- xn vale
1 solo se tutte le xi (1≤i≤n) sono contemporaneamente 1,
vale 0 in ogni altro caso
x1
x2
x1 . x2
0
0
0
0
1
0
1
0
0
1
1
1
esempio di prodotto logico di due variabili x1 e x2 mediante tabella di verità
Prof. Abramo Carmelo
6
Relazioni e proprietà
• Le relazioni e proprietà degli operatori somma e
prodotto logico sono riportate nella tabella
Somma
Prodotto
x+1=1
x·0=0
x+0=x
x·1=x
x1 + x2 = x2 + x1
x1 · x2 = x2· x1
x1 + x2 + x3 = (x1 + x2) + x3 x1 · x2· x3= (x1 · x2) · x3
x1· x2+ x1· x3= x1· (x2 + x3)
(x1 + x2) · (x1 + x3) = x1+ x2 · x3
Prof. Abramo Carmelo
7
Relazioni e proprietà
• Per la negazione valgono le seguenti relazioni
e proprietà:
Negazione
0°° = 0
1°° = 1
x°° = x
x + x ° = 1
x · x° = 0
x°°  x due volte negato
Prof. Abramo Carmelo
8
Funzioni
• Con n variabili binarie (x1, x2, … xn) si possono formare 2n
configurazioni diverse.
• Se prendiamo, ad esempio, 2 variabili: x1, x2 dato che ognuna di
loro può valere 0 od 1, si possono creano le seguenti quattro (22)
configurazioni diverse: 00, 01, 10, 11.
• Così con 3 variabili binarie si potranno formare al massimo 23=8
configurazioni diverse che sono:
000, 001, 010, 011, 100, 101, 110, 111.
Prof. Abramo Carmelo
9
Funzioni
• Diremo che una variabile y è funzione di n
variabili indipendenti x1, x2, … xn e si scrive:
y = F (x1, x2, … xn)
• quando esiste un criterio che fa corrispondere in
modo univoco ad ognuna delle 2n configurazioni di
x un determinato valore y (ovviamente 0 o 1).
Prof. Abramo Carmelo
10
Funzioni
• Tutte le diverse funzioni di n variabili
(x1,x2,…xn) che si possono costruire sono
pari a
(22)n
• Ad esempio tutte le diverse funzioni che
si possono formare con 3 variabili sono
pari a
(22)3= 28 = 256
Prof. Abramo Carmelo
11
Funzioni
• Una funzione può essere rappresentata
sotto forma di tabella di verità, scrivendo
accanto ad ognuna delle 2n diverse
configurazioni di x1, x2, … xn il valore
assunto dalla y.
• Ad esempio la seguente tabella
rappresenta la tabella di verità di una
delle 256 funzioni possibili di tre variabili
binarie
Cliccare sull’immagine
Prof. Abramo Carmelo
12
Minterm
•
Se consideriamo 3 variabili, la scrittura x1x2x3 = 011 indica
tra le 23=8 configurazioni possibili, quella in cui x1 vale 0, x2
vale 1 e x3 vale 1.
•
Questa configurazione si scrive semplicemente con il prodotto
x°1x2x3
•
Se in una configurazione una variabile compare con 1 si assume il
valore diretto se invece compare con uno 0 si assume il valore
negato.
•
Consideriamo la funzione di 3 variabili rappresentata sotto forma
di tabella di verità in fig.1 e le 3 configurazioni in cui la stessa
vale 1
•
Avremo che la funzione vale 1 per le seguenti configurazioni:
x°1x2x°3
x°1x2x3
x1x°2x3
Ciascuno di questi prodotti si chiama minterm
Prof. Abramo Carmelo
13
Minterm
• La funzione conoscendo la sua tabella di verità, potrà
essere espressa sotto forma di somme di prodotti dei
termini minimi.
• Nel caso della funzione in esempio scriveremo
y = x°1x2x°3 + x°1x2x3 + x1x°2x3
• Se una funzione è direttamente espressa sotto forma di
somme di minterm sarà possibile costruire la sua tabella di
verità, mettendo 1 nelle configurazioni relative ai minterm,
e 0 negli altri casi.
Prof. Abramo Carmelo
14
Minterm
• Ad esempio data la funzione di 3 variabili
F(x,y,z) = xy°z + xyz° + x°yz
la sua tabella di verità sarà:
x
y
z
F(x,y,z)
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
1
1
0
0
0
xy°z
1
0
1
1
xyz°
1
1
0
1
1
1
1
0
x°yz
Prof. Abramo Carmelo
15
Teoremi
TEOREMI
Idempotenza
Diretto
Duale
x + x + x + --- x = x
x · x · x · --- x = x
x + xy = x
x · (x +y) = x
Assorbimento x + x°y = x + y
De Morgan
x · (x° + y) = x · y
xy +yz + x°z = xy + x°z
(x +y)·(y+z)·(x°+z) = (x+y) · (x°+z)
(x+y)° = x° · y°
(x · y)° = x° + y°
Prof. Abramo Carmelo
16
Maxtem
• Il teorema di De Morgan applicato alla funzione
della fig.1 ci consente di scrivere la funzione in
questo modo:
• y = (x1+x2+x3)· (x1+x2+x°3)· (x1+x°2+x°3)·
.(x°1+x°2+x3)· (x°1+x°2+x°3)
• ossia sotto forma di prodotto di somme.
• Ciascuna delle somme chiama maxterm (termine
massimo).
Prof. Abramo Carmelo
17
Maxtem
• L’espressione della y come prodotto di maxterm
si può ottenere dalla tabella di verità della
funzione;
•
ci sono tanti maxterm quanto sono i valori 0
della funzione;
• ogni maxterm è la somma di tutte le variabili
dirette
o
negate
a
seconda
che
la
configurazione contenga 1 o 0.
Prof. Abramo Carmelo
18
Forma Canonica
• Entrambe le espressioni della funzione sotto
forma di:
– somme di prodotti (minterm)
– prodotti di somme (maxterm)
• si chiamano forme canoniche di una funzione
binaria.
Prof. Abramo Carmelo
19
Mappe di KARNAUGH
• Le mappe di Karnaugh sono delle tabelle che permettono
in
modo
immediato
la
rappresentazione
e
la
semplificazione di funzioni booleane fino 6 variabili.
• Mappa di K. per funzione ad 1 variabile x
• Mappa di K. per funzione a 2 variabili
x,y con all’interno rappresentati i
relativi minterm
Prof. Abramo Carmelo
x
y
0
1
x°
x
0
1
0
x°y° xy°
1
x°y
xy
20
Mappe di KARNAUGH
• La mappa di K. per una funzione a 3 variabili x,y,z è un
rettangolo diviso in 8 celle come nell’esempio.
• Al solito dentro le celle
minterm.
xy
00
z
sono stati scritti i relativi
01
11
10
0
x°y°z° x°yz° xyz° xy°z°
1
x°y°z
x°yz
xyz
xy°z
Le coordinate della tabella vanno sistemate in modo che
nel passaggio da una cella all’altra ci sia un sola variazione.
Infatti le coordinate per la xy saranno 00 01 11 10.
Prof. Abramo Carmelo
21
Mappe di KARNAUGH
• Una mappa di K. per 4 variabili x,y,v,z è un rettangolo
diviso in 16 celle.
• All’interno indichiamo al solito i relativi minterm.
xy
vz
00
01
11
10
00
x°y°v°z
x°yv°z° xyv°z° xy°v°z°
°
01
x°y°v°z x°yv°z
xyv°z
xy°v°z
11
x°y°vz
x°yvz
xyvz
xy°vz
10
x°y°vz° x°yvz°
xyvz°
xy°vz°
Si omette di parlare delle mappe di K. a 5 e 6 variabili
Prof. Abramo Carmelo
22
Mappe di KARNAUGH
• Le Mappe di K. costituiscono un altro metodo per
rappresentare una funzione booleana;
• basta scrivere 1 in quelle caselle che hanno le coordinate
della tabella di verità in cui la funzione vale 1.
x
y
z
F(x,y,
z)
0
0
0
1
0
0
1
0
0
1
0
1
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
1
xy
z
0
1
00
01
1
1
1
11
10
1
1
Rappresentazione con Mappa di K.
della funzione a lato.
Prof. Abramo Carmelo
23
Prossima Lezione:
Semplificazioni di funzioni binarie
Arrivederci!