Page 22, corrected

CAPITOLO 2. GLI INSIEMI
22
(a) A [ (B \C)
(b) (A [ B) \C
Figura 2.8: Diagrammi di Eulero-Venn per gli insiemi A [ (B \C) e (A [ B) \C.
comune tra A [ B e C (Figura 2.8(b)). E` immediato notare che le aree evidenziate nei due diagrammi non
coincidono e che quella nel secondo diagramma (Figura 2.8(b)) e` contenuta strettamente in quella del primo
diagramma (Figura 2.8(a)). Possiamo quindi dedurre che
A [ (B \C) ◆ (A [ B) \ C
ma non il viceversa. A questo punto, per costruire un controesempio all’uguaglianza delle due espressioni,
basta popolare con un elemento una delle aree che sono colorate nel primo diagramma ma non nel secondo.
Per esempio, possiamo prendere A = { 1 } e B = C = ?, da cui si ha A [ (B \C) = { 1 } e (A [ B) \ C = ?.
2.4.5
Le dimostrazioni (formali) per sostituzione
La tecnica di dimostrazione per sostituzione, introdotta nella Sezione 1.4 per dimostrare uguaglianze algebriche, pu`o essere usata in modo del tutto analogo per dimostrare uguaglianze di insiemi, sfruttando come giustificazioni le leggi della Sezione 2.4.1, o anche le nuove uguaglianze gi`a dimostrate. Vediamo alcuni esempi di
dimostrazioni di questo tipo.
E SEMPIO 2.15 ( DIMOSTRAZIONE DI A [ (A \ B) = A \ (A [ B))
Dimostriamo per sostituzione che per ogni A, B:
A [ (A \ B) = A \ (A [ B)
Partiamo dal membro sinistro dell’uguaglianza, e mostriamo che si pu`o trasformare nel membro destro con una
sequenza di uguaglianze in cui ad ogni passo una sottoespressione viene sostituita con una equivalente. Come
giustificazione di ogni passaggio indichiamo la legge applicata.
A [ (A \ B)
{ (distributivit`a) }
(A [ A) \ (A [ B)
=
{ (idempotenza), applicata alla sotto-formula sottolineata }
A \ (A [ B)
=
E SEMPIO 2.16 ( DIMOSTRAZIONE DI (A [ B) = B \ A)
(A [ B)
=
{ (De Morgan) }
A \ (B)
=
{ (doppio complemento) }
A\B
=
{ (commutativit`a) }
B\A

Download Report