Algebra e logica. 7. Algebre di Boole. Roma, 16 aprile 2004.
1. Sia X un insieme e sia P(X) l’insieme delle parti di X. Indichiamo con ∩, ∪ e rispettivamente le operazioni di intersezione, unione e complementare in P(X). Verificare che (P(X), ∩, ∪, )
`
e un’algebra di Boole.
2. Dato un numero naturale n, si denoti Dn = {m ∈ N : m divide n}. Supponiamo che n = p1p2· pk sia prodotto di k primi distinti. Dato a ∈ Dn, si definisca ¯a := na.
(a) Verificare che (Dn, mcd, mcm, ) `e un’algebra di Boole con 2k elementi.
(b) Sia X = {p1, p2, . . . , pk}. Verificare che l’applicazione
f : Dn−→ P(X), k = pi1. . . piα 7→ {pi1, . . . , piα}
`e un isomorfismo di algebre di Boole (ossia un’applicazione biiettiva che rispetta le oper- azioni delle due algebre).
3. Dimostrare che le algebre di Boole (P(N), ∩, ∪, ) e (P(R), ∩, ∪, ) non possono essere isomorfe.
4. Sia B l’insieme dei sottoinsiemi B ⊂ N che soddisfano una delle seguenti condizioni: la cardi- nalit`a di B `e finita oppure la cardinalit`a del complementare di B `e finita.
(a) Dimostrare che (B, ∩, ∪, ) `e un’algebra di Boole numerabile.
5. Sia (A, ⊗, ⊕, ) l’algebra Booleana formata dalle terne A = {000, 010, 001, 100, 110, 101, 011, 111}
con le operazioni definite cifra per cifra da
0 ⊕ 0 = 0, 1 ⊕ 0 = 0 ⊕ 1 = 1 ⊕ 1 = 1, 1 ⊗ 1 = 1, 1 ⊗ 0 = 0 ⊗ 1 = 0 ⊗ 0 = 0, ¯0 = 1.
(a) Qual `e l’identit`a per ⊕?
(b) Qual `e l’identit`a per ⊗?
(c) Calcolare le seguenti espressioni:
(001 ⊗ 001) ⊕ 100 = . . . , (111 ⊕ 001) ⊕ 100 = . . . , (001 ⊗ 001) ⊕ 101 ⊗ 010 = . . . . 6. Sia (A, ⊗, ⊕, ) un’algebra Booleana.
(a) Dimostrare che in un’algebra booleana valgono le Leggi di De Morgan:
(x ⊕ y) = x ⊗ y, x ⊗ y = x ⊕ y.
7. Si consideri l’espressione booleana E(x, y, z) = x ⊗ (x ⊗ y ⊕ x ⊗ y ⊕ y ⊗ z).
(a) Esprimere E(x, y, z) come somma di prodotti;
(b) Determinare un’espressione minimale di E(x, y, z) come somma di prodotti.
8. Sia B un’algebra di Boole. Per x, y ∈ B definiamo x + y = x ⊗ y ⊕ x ⊗ y. Dimostrare le seguenti uguaglianze o darne un controesempio.
(a) x + y = y + x;
(b) x + x = 0;
(c) x + y = (x ⊕ y) ⊗ x ⊗ y;
(d) x + (y + z) = (x + y) + z;
(e) x⊕(y +z) = (x⊕y)+(x⊕z);
(f) x+(y ⊕z) = (x+y)⊕(x+z).
9. Far vedere che il diagramma di Hasse 14–29 nel libro di Schaum `e sbagliato.
10. In un’algebra di Boole (dove x + y denota la somma di due elementi, xy il prodotto e x0 il complemento), scrivere le seguenti espressioni come somma di prodotti completata:
(a) x0y((zt)0+ x0)0; (b) (x + x0y + xy0z)(x0z); (c) x + x0yz.
11. Scrivere le seguenti espressioni in un’algebra di Boole come somma di implicanti minimali:
(a) xyz +xy0z +x0yz +x0y0z +x0y0z0; (b) txyz0+tx0yz +tx0yz0+t0xyz +t0xy0z +t0x0yz +t0x0y0z.
12. Trovare espressioni minimali Booleane per:
(a) x0y + x0y0; (b) xy + xy0; (c) xy + xy0+ x0y + xy0; (d) xyz + xy0z + x0yz + x0y0z + x0y0z0.
