Relazioni binarie. Consideriamo due insiemi A e B A Palermo. Torino. Milano....
-
Upload
benedetta-borrelli -
Category
Documents
-
view
214 -
download
0
Transcript of Relazioni binarie. Consideriamo due insiemi A e B A Palermo. Torino. Milano....
Relazioni binarie
Consideriamo due insiemi A e B
A
Palermo.
Torino.
Milano.
Venezia.
.Sicilia
.Veneto
.Lazio
.Piemonte
.Toscana
Catania.
B
R={(Catania , Sicilia) ; (Palermo , Sicilia) ; (Torino , Piemonte) ; (Venezia , Veneto)}
Una relazione tra due insiemi A e B è costituita da tutte le coppie ordinate (x,y) con xA e yB che rendono vera una determinata proposizione aperta p(x,y) che costituisce la legge della relazione
Per definire una relazione sono necessari due insiemi e una proposizione logica aperta
InsiemiA={Catania; Palermo;Torino;Venezia;Roma}B={Sicilia; Piemonte;Veneto;Toscana; Lazio}
Legge della relazione p(x,y):<<x si trova nella regione y>>
Dominio : Sottoinsieme di A che contiene tutti gli elementi che sono in relazione con elementi di B
Codominio: Sottoinsieme di B che contiene tutti gli elementi che sono in relazione con elementi di A
D={Catania; Palermo;Torino; Venezia}
C={Sicilia; Veneto, Piemonte}
A
Palermo.
Torino.
Milano.
Venezia.
.Sicilia
.Veneto.Lazio
.Piemonte
.Toscana
Catania.B
Controimmagini
Immagini
Esempio:
1 10,8,5,1A 12,8,3,0B
Legge della relazione P(x,y):<<x + y è dispari>>
5 R 3 5 + 3 è pari, quindi 5 R 3
8 R 3 8 + 3 è dispari, quindi 8 R 3
1 R 8 1 + 8 è dispari, quindi 1 R 8
10 R 12 10 + 12 è pari, quindi 10 R 12
Esempio: 10,8,5,1A 12,8,3,0B
Legge della relazione p(x,y):<<x + y è dispari>>
Modi per rappresentare una relazione
Rappresentazione per elencazione
R = {(1,0),(1,8),(1,12),(5,0),(5,8),(5,12),(8,3),(10,3)}
Rappresentazione sagittale
.0 B.1
.3
.8
.12
.5.8
.10
A
Esempio: 10,8,5,1A 12,8,3,0B
Modi per rappresentare una relazione
Rappresentazione mediante tabella a doppia entrata
Rappresentazione mediante diagramma cartesiano
A\B 0 3 8 12
1 V F V V
5 V F V V
8 F V F F
10 F V F F 1 5 8 10 xA
yB
0
3
8
12
Legge della relazione p(x,y):<<x + y è dispari>>
Legge della relazione p(x,y):<<x y>>
Modi per rappresentare una relazione
Quando gli insiemi A e B coincidono la rappresentazione sagittale assume una forma particolare
Rappresentazione mediante grafo
A=B=2;3;4;6;7
6
4
3
2
7
RELAZIONE INVERSA
Dati due insiemi A e B e una relazione R si chiama relazione inversa della R e si indica R –1 la relazione da B verso A che fa corrispondere alle immagini nell’insieme B le controimmagini nell’insieme A. Nella relazione inversa R –1 rispetto alla relazione R il dominio e il codominio si scambiano.
Esempio:
RELAZIONE INVERSA
A=1;2;3;4;6 B=2;3;4;6;9,12
.2 B.1
.3.4.6
.2.3.4
A
.6.9
.12
.2 B.1
.3.4.6
.2.3
.4
A
.6
.9
.12
Legge della relazione R
p(x,y):<<x è la metà di y>>
Legge della relazione R-1
p(x,y):<<y è il doppio di x>>
Dominio della R
Codominio della R
Dominio della R-1
Codominio della R-1
Proprietà delle relazioni binarieProprietà delle
relazioni binarie
Consideriamo il caso in cui gli insiemi A e B coincidono
A = B
1 Proprietà Riflessiva
xRx
Una relazione R definita in un insieme A gode della proprietà riflessiva quando ciascun elemento è in relazione con se stesso
In simboli :Ax
Proprietà Riflessiva
esempio ΝBA
Relazione R definita da P(x,y) = <<x è multiplo di y>>
3 R 3 perché 3 è multiplo di se stesso,
10 R 10 perché 10 è multiplo di se stesso,
………………………………., in generale
x R x perché un numero x è multiplo di se stesso.
xN x R x Pertanto vale la proprietà riflessiva
Proprietà Riflessiva
esempio ZBA
Relazione R definita da p(x,y)=<<x + y > 0>>
3 R 3 perché 3 +3 >0,
Poiché abbiamo già individuato almeno un elemento di Z che non è in relazione con se stesso non vale la proprietà riflessiva
-10 R -10 perché (-10)+(-10)<0.
In simboli xZ│ x R x pertanto la relazione non gode della proprietà riflessiva
Proprietà Riflessiva
esempio ZBA
-5 R -5 perché (-5) • (-5) 0,
10 R 10 perché (10) • (10) 0,
0 R 0 perché (0) • (0) 0,
x R x perché x • x = x2 0.
Relazione R definita da P(x,y) = << x • y ≥0>>
xZ x R x Pertanto vale la proprietà riflessiva
Proprietà Riflessiva
esempio
Relazione R definita da P(x,y) = << x + y è pari>>
A=B={1,2,3,4,5}
Rappresentazione mediante tabella a doppia entrata
A 1 2 3 4 5
1 V V V
2 V V
3 V V V
4 V V
5 V V V
La proprietà riflessiva è facilmente riconoscibile nella rappresentazione mediante tabella a doppia entrata. Basta verificare che tutte le caselle della diagonale principale fanno parte della relazione.
Diagonale principale
Proprietà Riflessiva
esempio
Relazione R definita da P(x,y) = << x + y è pari>>
A=B={1,2,3,4,5}
Rappresentazione mediante grafo
La proprietà riflessiva è facilmente riconoscibile nella rappresentazione mediante grafo. Basta verificare che su ciascun elemento c’è un arco che ritorna su se stesso.5
2 1
3
4
2 Proprietà antiriflessiva
Una relazione R definita in un insieme A gode della proprietà antiriflessiva quando tutti gli elementi dell’insieme non sono in relazione con se stessi
In simboli :Ax xRx
esempio
Relazione R definita da P(x,y) = << x + y è dispari>>
A=B=N
Proprietà antiriflessiva
In generale
5 R 5 perché 5+5 è pari
8 R 8 perché 8 + 8 è pari
x R x perché x + x = 2x che è sempre pari
xZ x R x Pertanto vale la proprietà antiriflessiva
esempio
Relazione R definita da P(x,y) = << x + y è dispari>>
A=B={1,2,3,4,5}
A 1 2 3 4 5
1 V V
2 V V V
3 V V
4 V V
5 V V
La proprietà antiriflessiva è facilmente riconoscibile nella rappresentazione mediante tabella a doppia entrata. Basta verificare che nessuna delle caselle della diagonale principale fa parte della relazione.
Diagonale principale
Proprietà antiriflessiva
Proprietà antiriflessiva
esempio
Relazione R definita da P(x,y) = << x + y è dispari>>
A=B={1,2,3,4,5}
Rappresentazione mediante grafo
La proprietà antiriflessiva è facilmente riconoscibile nella rappresentazione mediante grafo. Basta verificare che nessun elemento è dotato di un arco che ritorna su se stesso.5
2 1
3
4
Proprietà riflessiva e antiriflessiva
Spesso le relazioni non godono ne della proprietà riflessiva ne di quella antiriflessiva. Ciò avviene quando alcuni elementi, ma non tutti, sono in relazione con se stessi.
Alcuni elementi sono in relazione con se stessi altri no
3 Proprietà Simmetrica
:, Ayx Se x R y allora y R x
Una relazione R definita in un insieme A gode della proprietà simmetrica quando se l’elemento x è in relazione con l’elemento y anche y è in relazione con x
In simboli
Proprietà Simmetrica
esempio
9 R 3 perché 9 + 3 è pari.
3 R 9 perché 3 + 9 è pari (proprietà commutativa)
Ragionando in generale abbiamo che:
ΝBA
Relazione R definita da P(x,y) = <<x + y è pari>>
xN se x R y anche y R x Pertanto vale la proprietà simmetrica
esempio
Relazione R definita da P(x,y) = << x + y è pari>>
A=B={1,2,3,4,5}
Rappresentazione mediante tabella a doppia entrata
A/B 1 2 3 4 5
1 V V V
2 V V
3 V V V
4 V V
5 V V V
La proprietà simmetrica è facilmente riconoscibile nella rappresentazione mediante tabella a doppia entrata. Basta verificare che la tabella è simmetrica rispetto alla diagonale principale.
Diagonale principale
Proprietà Simmetrica
esempio
Relazione R definita da P(x,y) = << x + y è pari>>
A=B={1,2,3,4,5}
Rappresentazione mediante grafo
La proprietà simmetrica è facilmente riconoscibile nella rappresentazione mediante grafo: basta verificare che se esiste l’arco (freccia) in una direzione, esiste anche l’arco nella direzione opposta.5
2 1
3
4
Proprietà Simmetrica
Proprietà Simmetrica
esempio
ΝBA x, yN; x R y : x è multiplo di y
9 R 3 perché 9 è multiplo di 3
non vale la proprietà simmetricaBasta questo per dire che
3 R 9 perché 3 non è multiplo di 9.
Proprietà Antisimmetrica
:, Ayx
Una relazione R definita in un insieme A gode della proprietà antisimmetrica quando se l’elemento x è in relazione con l’elemento y allora y non è in relazione con x
In simboli
4
Se x R y allora y R x
Proprietà antisimmetrica
esempio
9 R 3 perché 9 è maggiore di 3
Ragionando in generale abbiamo che:
ΝBA
Relazione R definita da p(x,y) = <<x > y>>
3 R 9 perché 3 non è maggiore di 9
x,y N se x R y risulta y R x Pertanto vale la proprietà antisimmetrica
esempio
Relazione R definita da P(x,y) = << x < y >>
A=B={1,2,3,4,5}
Rappresentazione mediante grafo
La proprietà antisimmetrica è facilmente riconoscibile nella rappresentazione mediante grafo: basta verificare che l’arco (freccia) esiste solo in una direzione ma non in quella opposta.5
2 1
3
4
Proprietà antisimmetrica
Proprietà simmetrica e antisimmetrica
Spesso le relazioni non godono ne della proprietà simmetrica ne di quella antisimmetrica. Ciò avviene quando alcune coppie di elementi sono in relazione solo in un verso e altre coppie in entrambi i versi.
Proprietà Transitiva
:,, Azyx
Una relazione R definita in un insieme A gode della proprietà transitiva quando se x è in relazione con y e y è in relazione con z allora anche x risulta in relazione con z
In simboli
5
Se x R y e y R z risulta x R z
5 Proprietà Transitiva
esempio ΝBA
27(x) R 9(y) perché 27 è multiplo di 9,
9(y) R 3(z) perché 9 è multiplo di 3.
Infine 27(x) R 3(z) perché 27 è multiplo di 3.
Relazione R definita da p(x,y) = <<x è multiplo di y>>
36(x) R 6(y) perché 36 è multiplo di 6,
6(y) R 2(z) perché 6 è multiplo di 2.
Infine 36(x) R 2(x) perché 36 è multiplo di 2.
5 R 0 perché 5 + 0 è dispari,
0 R 9 perché 0 + 9 è dispari,
ma, 5 R 9 perché 5 + 9 è pari e non dispari.
Pertanto non vale la proprietà transitiva
Proprietà Transitiva
esempio ΝBA
Relazione R definita da p(x,y) = <<x + y è dispari>>
Proprietà Transitiva
Se tre elementi sono mutuamente in relazione il senso di percorrenza degli archi deve essere non circolare.
La proprietà transitiva non è immediatamente riconoscibile e verificabile con la rappresentazione mediante tabella o grafico cartesiano. Solo nella rappresentazione mediante grafo è possibile individuare detta proprietà
Relazione transitiva
z
x y
Relazione non transitiva
z
x y
Esercizi
1
Verificate di quali proprietà godono le seguenti relazioni definite in Z
2
3
4
5
R definita da p(x,y) = <<x - y è positivo>>
R definita da p(x,y) = << x • y è positivo>>
R definita da
R definita da p(x,y) =<<2x+y è multiplo di 3>>
R definita da p(x,y) = << x - 3y > 100 >>
p(x,y) = <<|x| è divisore di |y|>>
Relazioni di equivalenza
Una relazione, definita in un insieme A, si dice di equivalenza se e solo se gode delle proprietà
Riflessiva1
2
3
Simmetrica
Transitiva
esempio NBA
Riflessiva
Simmetrica
Transitiva
x R x perché x + x = 2x che è pari.
Se x R y allora x + y = 2a
Se x R y allora x + y = 2a,
Poiché anche y + x = 2a allora y R x.
se y R z allora y + z = 2b. Sommando
x + 2y + z = 2a + 2b da cui
x + z = 2a + 2b - 2y ; x + z = 2(a + b - y)
Ossia anche x + z è pari, ossia x R z
Relazione R definita da P(x,y) = << x + y è pari>>
esempio NBA
Relazione R definita da P(x,y) = << x + y è pari>>
Poiché la relazione considerata gode delle proprietà riflessiva, simmetrica e transitiva essa è una relazione di equivalenza
Esercizi
1
Dite quali fra le seguenti relazioni definite in Z sono di equivalenza.
2
3
4
p(x,y) = << x - y è positivo>>R definita da
R definita da
R definita da
R definita da
p(x,y) = << x.y è positivo>>
p(x,y) = << x + y è dispari>>
p(x,y) = << x - y è multiplo di 3>>
Classi di equivalenza
Data una relazione di equivalenza definita in A e x un suo elemento, una classe di equivalenza, indicata con [x], è un sottoinsieme di A formato da tutti gli
elementi di A in relazione con x.
xyAyx R|
esempio
E’ facile vedere che tale relazione è di equivalenza perché soddisfa le proprietà
riflessiva simmetrica transitiva
R definita da p(x,y) = << la retta x è parallela alla retta y>>
A=B={x | x è una retta del piano}
x
Se xRy allora yRx
y
xRx
x
Se xRy e yRz allora xRz
y z
esempio
Ogni classe di equivalenza individua quella che viene detta Direzione
R definita da p(x,y) = << la retta x è parallela alla retta y>>
A=B={x | x è una retta del piano}
Relazioni di ordine
Una relazione, definita in un insieme A, si dice di ordine se e solo se gode almeno delle proprietà
1
2
Antisimmetrica
Transitiva
Una relazione è di ordine largo se gode anche della proprietà Riflessiva
Una relazione è di ordine stretto se gode anche della proprietà Antiriflessiva
esempio NBA
Antisimmetrica
Transitiva
Se x R y perché x è multiplo di y
Se x R y e y R z allora anche x R z
y R x perché y non può essere multiplo di x
Consideriamo ad esempio x=18 y=9 z=3
Relazione R definita da
p(x,y) = <<x è multiplo di y>>
Poiché la relazione gode della proprietà antisimmetrica e transitiva è una relazione d’ordine
18 R 9 e 9 R 3 anche 18 R 3
Poiché la relazione gode della proprietà riflessiva (ogni numero e multiplo di se stesso) la relazione di ordine largo
Una relazione d’ordine totale si ha quando gli elementi dell’insieme sono tutti confrontabili, cioè per ogni coppia di elementi deve esistere la relazione in un senso o in quello opposto
Una relazione d’ordine parziale si ha quando gli ele-menti dell’insieme non sono tutti confrontabili tra di loro
esempio 2,12,6,10,24BA
Questa è una relazione d’ordine totale perché tutti gli elementi sono confrontabili tra di loro
Relazione R definita da p(x,y) = <<x è maggiore di y>>
2
6
10
1224
Le relazione d’ordine totale operano un ordinamento completo degli elementi dell’insieme
esempio 60,36,24,12,10,6,2BA
Questa è una relazione d’ordine parziale perché esistono almeno due elementi che non sono confrontabili tra di loro es. (24,60) e (24,36)
Relazione R definita da p(x,y) = <<x è multiplo di y>>
2
610
12
24
3660
Le relazione d’ordine parziale operano un ordinamento parziale degli elementi dell’insieme
FUNZIONI
B A
Si chiama funzione o applicazione di A in B una relazione che ad ogni elemento dell’insieme A fa cor-rispondere uno ed un solo elemento dell’insieme B.
Le funzioni sono quindi particolari relazioni in cui il dominio coincide con l’insieme A e ad ogni elemento di A deve essere associato un solo elemento di B
FUNZIONI
Questa relazione non è una funzione perché esiste un elemento di A che non è in relazione con nessun elemento di B
BA
BA Questa relazione non è una funzione perché esiste un elemento di A che è in relazione con più di un elemento di B
FUNZIONI
Una funzione si indica con la seguente simbologiaf : A→B o anche con y = f(x)
BA
Funzione f : A→B definita da y = x2
esempio A={1,-2,2,3,-4,5} B={1,4,9,16,25}
x y
1-223-45
y = 12 = 1y = (-2)2 = 4y = 22 = 4y = 32 = 9y = (-4)2 = 16y = 52 = 25
3
2
1
9
1
-2
4
-4 5
16
25
FUNZIONI
f : N→N definita da y = 2x+1esempio A=B=N
x y
1234.
12.
100.
y = 2.1+1=2+1=3y = 2.2+1=4+1=5y = 2.3+1=6+1=7y = 2.4+1=8+1=9……………………..…..y = 2.12+1=24+1=25………………………....y = 2.100+1=200+1=201………………………….
La x che fissiamo noi si chiama variabile indipendente
La y che viene calcolata in base alla legge della funzione si chiama variabile dipendente
CLASSIFICAZIONE DELLE FUNZIONI
Una funzione f: A →B si dice iniettiva quando ad elementi distinti di A corrispondono elementi distinti di B
Funzione iniettiva
BA BA
Funzione non iniettiva
Funzione iniettiva
CLASSIFICAZIONE DELLE FUNZIONI
Una funzione f: A →B si dice suriettiva quando il codominio coincide con l’insieme B
Funzione suriettiva Funzione non suriettiva
Funzione suriettiva
BA BA
CLASSIFICAZIONE DELLE FUNZIONI
Una funzione f: A →B si dice biiettiva quando è contemporaneamente iniettiva e suriettiva
Funzione biiettiva Funzione non biettiva
Funzione biiettiva
BA BA
Funzione suriettiva e non iniettiva Funzione biiettiva
BA
BA
BA
BA
Funzione generica Funzione iniettiva e non suriettiva
PRODOTTO DI FUNZIONI
Date le funzioni f: A →B e g: B →C si chiama prodotto delle funzioni g○f la funzione k : A →C che associa ad ogni elemento di A un solo elemento di C
fA CB
k = g ○ f
g
PRODOTTO DI FUNZIONI
f : Z→Z definita da y = x+1esempio A=B=C=Z
x y =f(x)=x+1
-4-21 3..
y = -4+1=-3y = -2+1=-1y = 1+1= 2 y = 3+1= 4…………..
g: Z→Z definita da z = 2y-1
y z =g(y)=2y-1
-3-12 4..
z = 2. (-3)-1=-6-1=-7z = 2. (-1)-1=-2-1=-3z = 2.2-1=4-1=3 z = 2.4-1=8-1=7……………….
Funzione f Funzione g
PRODOTTO DI FUNZIONI
f : Z→Z definita da y = x+1esempio A=B=C=Z
g: Z→Z definita da z = 2y-1
Z ZZ
-4-3
-7
-2
1
3
-1 -3
2
4
3
7
PRODOTTO DI FUNZIONI
f : Z→Z definita da y = x+1esempio A=B=C=Z
x z = g[f(x)] =2x+1
-4-21 3..
y = 2(-4)+1=-8+1=-7y = 2(-2)+1=-4+1=-3y = 2.1+1=2+1=3 y = 2.3+1=6+1=7…………..
g: Z→Z definita da z = 2y-1
Funzione k = g ○ f
z = g(y) = g[f(x)] = 2y-1 = 2(x+1)-1 = 2x+2-1 = 2x+1in definitiva z = 2x+1
Z Z-4 -7
-2
1
3
-3
3
7
k = g ○ f