Matematica discreta

A ∩B

¿

c) Trova (differenza tra A e B)

A

Soluzione:

Matematica discreta 12

∪B={1, }

A 2,3, 4,5, 6

a) L'unione contiene tutti

gli elementi che appartengono ad A o a B (o ad

entrambi). }

A ∩B={3, 4

b) L'intersezione contiene solo gli

elementi che appartengono sia ad A che a B.

¿ ¿

c) La differenza contiene gli

={1, }

A 2 A

elementi di A che non appartengono a B.

¿

¿ )

X

Esercizio [1]. È vero che ?

)∩¿

X ¿=¿

X ( A ∩ B

No, questa affermazione non è vera. Vediamo

perché:

1. rappresenta il complemento

(

X A ∩ B)

dell'intersezione di A e B rispetto a X.

¿

¿ )

X

2. rappresenta l'intersezione dei

)∩¿

X ¿

complementi di A e B rispetto a X.

Queste due espressioni in realtà producono

risultati diversi. Per dimostrarlo, possiamo usare

le leggi di De Morgan:

( ( ¿

X A ∩ B)=X A ∩ B

Matematica discreta 13

¿

¿ )

X (per la prima legge di De Morgan).

)∪ ¿

X ¿¿

Come si può vedere, il risultato corretto è

l'unione dei complementi, non la loro

intersezione. Per rendere l'affermazione vera,

dovremmo modifcarla così:

¿

¿ )

X

∪

) ¿

X

(

X A ∩ B)=¿

Oppure, se vogliamo mantenere l'intersezione

nel lato destro, dovremmo complementare

l'unione:

¿

¿ )

X

)∩ ¿

X ∪

(

X A B)=¿

Questa ultima forma è la seconda legge di De

Morgan.

1.2 Diagrammi di Venn.

Già abbiamo osservato nel paragrafo

precedente alcuni diagrammi/grafci, ma cosa

rappresentano in dettaglio?

Si identifca ogni insieme con i punti racchiusi in

una curva. I diagrammi di Venn sono strumenti

Matematica discreta 14

visivi utilizzati per rappresentare le relazioni tra

insiemi o gruppi di elementi. Sono formati da

cerchi sovrapposti o intersecati per mostrare le

intersezioni e le differenze tra gli insiemi. Il

diagramma di Venn aiuta l’intuizione, non

dimostra, al contrario delle tabelle di verità.

Possiamo osservare che:

Tavole di verità: dimostrano ma non

 aiutano l’intuizione;

Diagramma di Venn: Aiuta l’intuizione ma

 non dimostra;

ragionamento

il dimostra, ma ha il

 bisogno dell’intuizione.

Vediamo alcune delle

operazioni viste in

precedenza con i diagrammi

di Eulero-Venn.

Matematica discreta 15

In fgura è rappresentata il complemento di un

insieme A.

In queste due fgure ci sono altri esempi, sulle

operazioni sugli insiemi che abbiamo visto in

precedenza.

1.3 Altre osservazioni ed esercizi sugli insiemi.

Esercizio [1]. Siano A, B, C insieme con

( )

⊆ ∪ ∪

è vero che ?

C A A ∩B C= A ∩(B C)

Per dimostrare se l’uguaglianza è vera o falsa,

possiamo utilizzare le leggi di De Morgan e le

leggi distributive dell'algebra degli insiemi.

Partiamo dall'uguaglianza da dimostrare:

( ) ∪ ∪C)

A ∩B C= A ∩(B

Applichiamo la distributiva

( )=( ) ( )

∪C ∪

A ∩ B A ∩ B A ∩C :

( ) ∪ ∪(

A ∩B C=( A ∩ B) A ∩C)

Ora, per dimostrare se queste due parti sono

uguali, dobbiamo dimostrare che C è uguale a

. Questo è vero solo se C è un

A ∩C

Matematica discreta 16

⊆

sottoinsieme di A. Se allora .

C A A ∩C=C

In questo caso, l'uguaglianza è verifcata.

⊆

Quindi, se , allora

C A

( ) ∪ ∪C) è vero.

A ∩B C= A ∩(B ( )

Esercizio [2] . ¿

Chi è ( ?

N xZ ∩ Z xP

( )

N xZ ∩ ( ) ∈( )

¿ ¿

Sia ( allora e

x , y N x Z

Z x P

( ) ∈¿

x , y

( ) ∈(Z , abbiamo quindi

x , y x P)

∈ ∈ ∈ ∈ ∈(

, quindi e

)

x N , y Z , x Z , y P x N ∩Z

∈ ∈

∈( da cui deriva: , si

x N y P

y Z ∩ P)

( ) ∈(N

arriva a: x , y x P)

Prop. 1.3.1. Siano A, B, C insiemi allora

( )=( ) ( ) , vediamo la

Ax B ∩C AxB ∩ AxC

dimostrazione:

sia allora e

( ) ∈ ∈

x , y Ax( B ∩C) x A

quindi possiamo osservare che

∈(B

y ∩C) ( ) ∈(

. => e

∈ ∈ ∈ x , y AxB)

x A e y B e y C

=> ( ) ( ) ( )

∈

(x )∈( ) x , y AxB ∩ AxC .

, y AxC

Problema sat. Date due formule composte da un

∪

numero fnito di insiemi, , decidere se

∩,

sono uguali come insiemi in un tempo

ragionevole.

1.4 Le corrispondenze

Signifca studiare gli insiemi uno rispetto

all’altro.

Matematica discreta 17

∀ insiemi si dice corrispondenza da A a B

A , B

ogni sottoinsieme che si può

φ di AxB(φ⊆ AxB)

anche esprimere come:

|

{ ( ) ∈ } . Inoltre, si dice

φ= a , b AxB b corrisponde ad a

che il Dominio di è A, mentre Codominio di

φ

.

φè B

∀ ⊆ si pone

A' A

( )

' , ovvero

∶={b ∈ ∈ }

φ A B∨∃ a A :(a , b)∈ φ

l’immagine di A’ in .

φ ⊆

Una corrispondenza e si indica anche

φ AxB A φ B

⋯>B

come: o anche , in dettaglio

φ : A →

la posso rappresentare

anche con un grafo

bipartito come in

fgura.

Le frecce uniscono gli

elementi del dominio

con quelli del

codominio.

(

∃una ↦b ∈ )

freccia a per ogni coppia(a , b) φ

}∶=P

A=B={ persone

Esempio. , indichiamo con

∶=fratello ∶=sorella ⊆

, e ( ) sono

φ δ AxB

corrispondenze da a

A B

Quindi si ha:

( ) ∈φ

a , b ∆ b è fratello di a/¿(a , b)∈δ ∆ b è sorella dia .

⇔ ⇔

Matematica discreta 18

∶={0,1,2,3 }

A=B=N , …

Esempi. e sia

∶=minore si può defnire

w o uguale

( ) ∈

a , b w≤¿ a è minore o uguale a b .

Questi casi sono sempre validi, esistono però

∀

dei casi speciali, si ha:

A , B

1. corrispondenza vuota da a è

A B

∅(⊆ AxB)

2. corrispondenza totale da a è

A B

AxB

3. corrispondenza identica o diagonale da

a (o identità su A) è

A A |

{ } i ii i ii

( ) ∈ ∈ ∈

= ={( ) =a }

id a , a AxA a A a , a AxA∨a

A

.

Vediamo le costruzioni tra corrispondenze, e si

∀ ⊆

parte da una corrispondenza come φ AxB

si hanno le corrispondenze:

detta complementare di , ed è

 ' φ

⊆

φ AxB ¿ dunque equivale a

' ( )=(

∶=∁

φ φ AxB)

AxB

(a (a

, b)∈ φ ' ∆ , b)∉ φ ∶=φ

si scrive anche ,

φ '

⇔ ∀

assumendo che .

(a , b)∈( AxB)

si dice inversa di , è data

−1

 φ

⊆

φ BxA −1

(b (

, a)∈ φ ∆ a , b)∈ φ

( )

∀ ∈ con un

b , a BxA , ⇔

−1

diagramma di si ottiene invertendo le

φ

frecce.

Utilizzando i diagrammi di Eulero-Venn possiamo

rappresentare ciò che abbiamo osservato così:

Matematica discreta 19

In nero è rappresentata la funzione , mentre

φ

−1

in blu è rappresentata la funzione .

φ

È possibile osservare le possibili operazioni che

si possono fare con le corrispondenze come

abbiamo fatto con gli insiemi. Tenendo in

'

considerazione (ovvero due

∀ ⊆ (AxB)

φ ,φ ' '

corrispondenze di a , quindi con lo

A B

stesso dominio e lo stesso codominio) si hanno

1. Operazioni insiemistiche:

' ' ''

⊕

}φ

' ' , φ φ

¿

' '

}φ

' , φ ¿

' ' ' ' ' '

∪φ

φ ∩φ , φ , φ

2. È possibile fare la composizione o il

prodotto, in particolare:

∀ ⊆ ∀ ⊆BxC ∃σ ⊆

, data

φ AxB , δ ° φ AxC

da: ∶={(a ϵ ϵ ∧(b ∈σ

)∈ }

σ ° φ , c AxC∨∃b B :(a , b) φ , c)

( ) ( )

' '

∶=σ ( )

σ ° φ= A φ A

in modo equivalente: '

∀ ⊆ ¿

A A ,

Matematica discreta 20

Vediamo alcune proprietà del prodotto:

1. Associatività:

∀ ⊆ ∀ ⊆ ∀ ⊆ si ha:

φ AxB , δ BxC , τ CxD

( )=( ) e si può anche dire:

τ ° δ ° φ τ ° δ ° φ

τ ° δ ° φ∈ AxD

2. In generale non vale la commutatività: se

⊆ ⊆ in generale .

φ AxB , δ BxC δ ° φ ≠ φ ° δ

A=B={ persone}

Esempio. siano e

∶=madre

defniamo poi le funzioni ,

μ

∶= , in questo caso abbiamo che

π padre

∃ ∃

e anche , ma le due

μ° π π ° μ

indicano cose diverse: μ ° π=nonna paterna

, .

π ° μ=nonno materno ∃id ⊆ ⊆

AxA , id BxB

∀ ⊆

3. si ha ( ),

φ AxB A B

=φ

φ ° id id ° φ=φ

e anche .

A B

Corrispondono ad un’identità come nella

moltiplicazione. ∀ ⊆

4. Corrispondenza inversa si ha

φ AxB

−1

∃φ ⊆ BxA

Matematica discreta 21

∀ ⊆ ∀ ⊆BxC

5. , si ha

φ AxB , δ

−1 −1 −1 . Grafcamente si ha:

(δ =φ

° φ) ° δ

∀ ⊆

6. cioè la corrispondenza di

φ AxA φ

0 2

A in A, , , in generale

∶=id

φ ∶=φ°

φ φ

A

+1

n n . Quindi possiamo dire che la

=φ∗φ

φ è una relazione binaria, ovvero una

φ

potenza della corrispondenza.

1.5 Le funzioni.

Una applicazione (o funzione o map