4.2 Le proprietà delle relazioni

RELAZIONI E FUNZIONI esempio O Si è svolto un torneo di calcetto a eliminazione diretta tra otto squadre. Lo schema che segue rappresenta il grafo della relazione «aver sconfitto , definita nell insieme delle squadre. Qual è la squadra vincitrice? b a e h c g f d Dal grafo risulta, per esempio, che: Q a ha sconfitto b; Q c ha sconfitto a e d; Q f ha sconfitto c, e, h; Q b, d, e, g non hanno sconfitto nessuno; Q h ha sconfitto g. Quindi possiamo dedurre che è risultata vincitrice la squadra che ha vinto tutti gli incontri cioè f. Infatti, da f partono frecce (verso c, e, h) che indicano le sue vittorie, ma nessuna freccia arriva a f (nessuno ha sconfitto tale squadra). Nel caso del precedente esempio, un altro modo di organizzare le informazioni è quello di disporle ad albero, indicando i vari livelli (eliminatorie, quarti di finale, semifinale, ) degli incontri come illustra il seguente grafico. FISSA I CONCETTI Q Q Una relazione è un predicato con due argomenti che appartengono allo stesso insieme. Un grafo è uno schema formato da punti, detti nodi, e da archi o frecce che li collegano. a b c a d e c f g f c h h f f 4.2 Le proprietà delle relazioni Per analizzare alcune proprietà delle relazioni, spesso dovremo fare riferimento a una relazione generica e non a qualcuna specifica. Indicheremo tale relazione generica con la scrittura rel. Così, la notazione: a rel b indica che l elemento a è in relazione con l elemento b, senza stare a indicare di quale relazione si tratti. Quando in un insieme A definiamo una relazione, allora, comunque scegliamo una coppia di suoi elementi, x e y, è vera una (e una soltanto) di queste due proposizioni: x rel y l elemento x è in relazione con l elemento y x rel y l elemento x non è in relazione con l elemento y Per esempio, se nell insieme delle rette del piano consideriamo la relazione «essere parallele , allora due rette qualunque o sono parallele o non lo sono: non vi è una terza possibilità. 24

Il Maraschini-Palma - volume 1
Il Maraschini-Palma - volume 1