L’algebra della logica delle proposizioni
 K={0,
1} è un’algebra di Boole
Infatti la struttura soddisfa i 14 postulati
Verità di P  1
Falsità di P  0
Operazioni
0+0=0 00=0
0+1=1 01=0
1+0=1 10=0
1+1=1 11=1
0=1 disgiunzione
1=0 congiunzione
negazione
+

_
L’algebra della logica delle proposizioni
+, , _, 0, 1> è un’algebra di Boole
 y=f(p, q, ...)
p, q proposizioni
 I postulati dell’algebra sono proprietà della
logica: __
 <K,
f(a,b)=ab+ab
funzione di equivalenza
ab
x  y è, nell’algebra della logica, x  y
infatti: 0  0; 0  1; 1  1
L’algebra della logica delle proposizioni
(P e Q) o L
y = f(P, Q, L)
oppure
non
e
Forme elementari
 Letterale
La variabile x o il suo complemento x
 Termine
elementare o Clausola
il prodotto di n letterali di variabili distinte
 Fattore
elementare
La somma di n letterali di variabili distinte
ac
d
acd
clausole
a+b
a+c b+d+x
fattori elementari
Forme elementari
 Costituite
da somme di clausole o da
prodotti di fattori elementari
ac+ad+bx
(a+b)(d+c+x)(a+d)
Forme elementari

Mintermine (P)
 Un termine elementare (clausola) di ordine n, cioè un
prodotto dei letterali di tutte le n variabili
P0=ab
P1=ab P2=ab P3=ab 112=3
 Esistono 2n

mintermini
Maxtermine (S)
 La somma di n letterali, uno per ciascuna variabile.
S5=a+b+c
Forme elementari
Pi=Si
PiPj=0
2 n 1
 Pi  1
i 0
Si+Sj=1
con ij
2n 1
S
i 0
i
0
Tabella di Verità
 Una
funzione si dice algebrica se è
esprimibile come funzione delle sole
funzioni elementari
 Se
l’algebra è finita, una funzione può
rappresentarsi in forma tabellare definendo
il valore della variabile dipendente per ogni
combinazione dei valori delle n variabili
indipendenti
Tabella di verità
 N=K
n
N
K
numero complessivo di punti
valori dell’algebra primordiale
n
K
 M=K
M
Kn
 M=
numero di funzioni di n variabili
numero complessivo di punti
n
n
2
2 =4
nell’algebra primordiale
La tabella definisce una funzione che si chiama tabella di
verità
a
0
0
0
0
1
1
1
1
b
0
0
1
1
0
0
1
1
c
0
1
0
1
0
1
0
1
y
1
1
1
1
0
0
0
1
Forma canonica di primo tipo (P)
 Una
funzione di variabili, assegnata da una
tabella di verità può essere espressa sotto
forma disgiuntiva di congiunzioni (somma di
prodotti).
 Ciascun
termine della somma è associato
ad un “1” presente nella colonna della
tabella ed è un prodotto delle n variabili,
ciascuna delle quali è negata se compare
uno “0” oppure non negata se c’è un “1”
Forma canonica di primo tipo (P)
f(x1, x2, …, xi, …, xn) = xif(x1, x2, …, 1, …, xn) +
xif(x1, x2, …, 0, …, xn)
f(x1, x2,.., xi,.., xn) = x1f(0, x2,.., xn) + x1f(1, x2, …, xn)
= x1x2f(0, 0, x3,.., xn) + x1x2f(0, 1, x3,.., xn) +
x1x2f(1,0, x3,.., xn) + x1x2f(1,1, x3,..,xn) =
= P0f(0, 0, …, 0) + P1f(0, 0, …, 1) + ...
2n 1
f ( x1, x 2,..., xn)  i Pi
i 0
Esempio
a
0
0
0
0
1
1
1
1
b
0
0
1
1
0
0
1
1
c
0
1
0
1
0
1
0
1
y
1
1
1
1
0
0
0
1
y=(0, 1, 2, 3, 7) = P0+P1+P2+P3+P7=
= abc + abc + abc + abc + abc
Esempio
Y = a + bc
 Dalla
forma algebrica alla forma canonica
somma elementare di clausole
moltiplicare per il prodotto
(xi+xi)(xj+xj)…=1
Esempio
Y=bc(ad+b+c)+c(d+a)(b+c)
Y=ab+bc+bd
Y=[ab(c+c)(d+d)]+[bc(a+a)(d+d)]+[bd(a+a)(c+c)]=
=[P7+P6+P5+P4]+[P15+P14+P7+P6]+[P15+P13+P7+P5]=
(4, 5, 6, 7, 13, 14, 15)
Numeri caratteristici
È la stringa di valori ordinati i
n.c. f = 11110001 = 241
f241
n.c. a = 00001111 n.c. b = 00110011
n.c. c = 01010101
il n.c. di a+b è dato dalla somma dei n.c.
Equazioni booleane
 Pi=1
abc=1
a=1, b=1, c=0
 più
in generale si ha:
f(x1, x2, …, xn)=1
le soluzioni si ottengono da:
2n 1
 P  1
i 0
i i
Equazioni booleane
Esempio:
abc+abc+abc=1
si hanno le tre radici
a=1, b=1, c=1; a=1, b=1, c=0; a=1, b=0, c=1
Equazioni booleane
Piu’ in generale un’equazione booleana può
porsi nella forma
f(X)=g(X)
ciò implica che i valori di verità di f(X) e g(X)
devono coincidere
f(x)g(x)+f(x)g(x)=1
cioè
F(x)=1
Funzioni incompletamente specificate
y=f(x1, x2, …, xn)
indifferente in alcuni punti (don’t care)
 Funzione
Ø
compatibile
una y’ che abbia gli stessi valori di y tranne che
nei punti di non specificazione
2m
m don’t care
Funzioni incompletamente specificate
 Le
condizioni di indifferenza si possono
esprimere algebricamente tramite “vincoli”
sulle variabili mediante una equazione
booleana
(x1, x2, …, xn)=1
con radici nei punti di definizione o con
(x1, x2, …, xn)=1
con radici nei punti di dont’care
Esempio
(x1, x2, …, xn)=1
a
0
0
0
0
1
1
1
1
b
0
0
1
1
0
0
1
1
c
0
1
0
1
0
1
0
1
y
1
1
Ø
Ø
1
1
1
1
(x1, x2, …, xn)=1
Condizione di vincolo:
abc+abc+abc+ abc+abc+abc=1
Condizione di indifferenza:
abc+abc=1
 Una
condizione di vincolo molto diffusa è
che posto
y = f(x1, x2, …, xk, l1, l2, …, lq) = f(X, L)
sussista la relazione
xi·xj=0
con ij
con i  1, k  j
 su k delle n variabili mai due di esse uguali
ad 1
 Esempio
n = k+q =3 k = 2, q=1 supponiamo siano x1,x2
solo due punti in cui si ha x1, x2=1
a
0
0
0
0
1
1
1
1
b
0
0
1
1
0
0
1
1
c
0
1
0
1
0
1
0
1
y
0
1
1
0
1
0
Ø
Ø
 Esempio
n = k+q =3 k = 3, q=0
a
0
0
0
0
1
1
1
1
b
0
0
1
1
0
0
1
1
c
0
1
0
1
0
1
0
1
y
0
1
1
0
1
0
Ø
Ø
4 punti in cui si hanno 2
variabili uguali a 1
k
y  P0x f 0 ( L)   x j f j ( L)
{1}
j 1
P0x=x1·x2 ·... ·xn
mintermine
f0(L) particolare funzione di I1, …, Iq
Se q=0 si ha che k=n e la {1} cambia
k
y  P a j   x ja j
x
0
j 1
Implicanti di funzione
 ff1; f1f
f1+f=1
 f1 è un implicante di f
 Primo
f possiede {If};
implicante
Un implicante che non implica nessun altro
f2 f1
f
f3 f4
Mappe di Karnaugh
x1
x1x2
x 1 x2
x2
x1
0
1
x1x2
x1x2
x2
0
P0
P2
x1x2
x1x2 x
2
1
P1
P3
x 1 x2
x1x2
x1

I mintermini che si oppongono in 1 variabile sono adiacenti

n2 le clausole di ordine n-1 che si oppongono in 1
variabile sono ancora adiacenti. Le quadruple sono
clausole di ordine n-2
n3 le ottuple rappresentano clausole di ordine n-3

Clausole
n
n-1
n-3
n-2
n-3
Proprietà
 Data
una funzione in forma elementare di
tipo P le n clausole Ai sono implicanti di f
Una clausola B ne implica un’altra A se e solo
se B contiene tutti i letterali di A
Ax+Ax=A
es. abc+abc=ab
Ad una funzione f può essere aggiunto un suo
implicante senza alterarne il valore
A è un implicante di f se e solo se nella prima
forma canonica di f sono presenti tutti i
mintermini implicanti A
Esempio
x3x4
00
01
11
10
x1x2
00
00
01
11
10
x1x2
1
01
1
1
11
10
x3x4
1
1
00
01
1
1
11
1
1
10
y=x1x3+x2x4+x1x2x4
1
1
1
1
1
1
1
1
1
y=x1x3+x2x4+x2x3x4+x1x2x3x4