Riassunti di logica e algebra

1 Relazioni

1.1 Definizioni propedeutiche {( )|

, … , × … × = , … , ∈ , = 1, … , }.

DEF. PRODOTTO CARTESIANO: siano insiemi, il loro prodotto cartesiano è l’insieme

1 1 1

DEF. RELAZIONE: una relazione n-aria (o di arità n) tra insiemi è un qualunque sottoinsieme del loro prodotto cartesiano. Si definiscono

 ∅ la relazione vuota dove nessun oggetto è in relazione con nessun altro;

 la relazione universale dove tutti gli oggetti sono in relazione tra loro.

×…×

1

Proprietà e osservazioni:

⊆ × … × ⊆ × … ×

Date le relazioni e si deducono le definizioni:

1 1

 ( ) ( )

⊆ , … , ∈ , … , ∈ ;

SSE per ogni si ha

1 1

 = ⊆ ⊆ ;

SSE e

 ( ) ( )

⊂ ⊆ , … , ∈ , … , ∉ ;

SSE ed esiste almeno una n-upla tale che

1 1

 {( )|( ) ( )

∩ = , … , , … , ∈ , … , ∈ };

1 1 1

 {( )|( ) ( )

∪ = , … , , … , ∈ , … , ∈ };

1 1 1

 {( )|∀ ( ) };

= , … , ∈ , , … , ∈

⋂ ∈ 1 1

 {( )|∃ ( ) }.

= , … , ∈ , , … , ∈

⋃ ∈ 1 1

Inoltre, essendo le relazioni insiemi esse godono delle proprietà di intersezione e unione tra insiemi:

 ∪ =∪ ∪;

commutatività di

 ( (

∪ ∪ ) = ∪ ) ∪ ∪;

associatività di

 ∩ =∩ ∩;

commutatività di

 ( (

∩ ∩ ) = ∩ ) ∩ ∩;

associatività di

 ( ( (

∩ ∪ ) = ∩ ) ∪ ∩ ) ∩ ∪;

distributività di su

 ( ( (

∩ ∩ ) = ∪ ) ∩ ∪ ) ∪ ∩.

distributività di su

1.2 Relazioni binarie ×

DEFINIZIONE: si tratta del caso particolare di sottoinsiemi del prodotto cartesiano tra due insiemi .

1 2

 ;

data la relazione binaria tra e si chiama dominio e codominio di

1 2 1 2

 ( )

, ∈ .

la notazione equivale alla scrittura

1 2 1 2

,

RAPPRESENTAZIONE: con gli insiemi finiti, la relazione definita su di loro può essere rappresentata tramite:

1 2

 (, ).

Grafo di incidenza: un grafo è una coppia di insiemi è l’insieme dei vertici del grafo ed è l’insieme degli archi. Gli archi sono una coppia di vertici

dei quali il primo sarà detto vertice iniziale ed il secondo finale. Se è una relazione tra gli insiemi disgiunti e il grafo di incidenza della relazione è

1 2

∪ .

il grafo i cui i vertici sono gli elementi di ed il cui insieme di archi è

1 2



Matrice di incidenza: dati due insiemi e , si sceglie un ordinamento arbitrario ma fissato tra gli oggetti di ciascun insieme. Si definisce la matrice di

1 2

| | | | {0,1}, (,

)

incidenza della relazione come la matrice di righe e colonne ad elementi nell’insieme tale che il suo elemento di posto valga 1 SSE la

1 2

,

coppia costituita dall’i-esimo elemento di e dal j-esimo elemento di appartiene ad nel caso contrario vale 0.

1 2

, ⊆ × , = ⨀ = ⨁ ⨀, ⨁

NB operazionalmente: date due relazioni e le rispettive matrici d’incidenza , si ha: e (con

1 2 ∩ ∪

che indicano operazioni sugli elementi delle matrici e non sulle matrici stesse).

⊆ × ⊆ × ⋅ = ×

DEF. PRODOTTO DI RELAZIONI: date due relazioni e , il loro prodotto è la relazione definita insiemisticamente come

1 2 2 3 1 3

{( )| ( ) ( )

⋅ = , ∃ ∈ . . , ∈ , ∈ }.

1 3 2 2 1 2 2 3 = ⋅

NB operazionalmente: la matrice della relazione prodotto è .

∙

Proprietà:

 ( (

⊆ × , ⊆ × , ⊆ × ⟹ ⋅ ) ⋅ = ⋅ ⋅ );

Proprietà associativa 1 2 2 3 3 4

 ⊆ ⊆ × , ⊆ ⊆ × ⟹ ⋅ ⊆ ⋅ ;

Compatibilità con l’inclusione 1 2 2 3

 Non è commutativo. ∙ = ∙ .

Possono comunque esistere relazioni dette permutabili per cui vale Una condizione necessaria ma non sufficiente per la permutabilità è che

⊆ × ⊆ × ⋅ = =

date le relazioni e il prodotto è permutabile solo se .

1 2 2 3 1 2 3

−1

⊆ × ⊆ ×

DEF. RELAZIONE INVERSA: data una relazione . Si definisce relazione inversa di la relazione definita insiemisticamente come

1 2 2 1

−1 {( )|( ) }.

= , , ∈

2 1 1 2 −1

.

NB operazionalmente: la matrice della relazione inversa si ottiene trasponendo la matrice di

1.3 Relazioni binarie su un insieme ⊆ × .

Studieremo ora il caso particolare di sottoinsiemi del prodotto cartesiano fatto sullo stesso insieme, ovvero {(,

= )| ∈ }.

DEF. RELAZIONE IDENTICA: in questo caso oltre alla relazione vuota e alla relazione universale si definisce

⊆ × ⋅ = ⋅ = , .

Osservazione: data si ha e ovvero permuta con ogni relazione su

= ⏟

⋅ ⋅ … ⋅ ∈ ℕ.

DEF. POTENZA: la potenza ad esponente intero positivo di una relazione R (potenza n-esima ) è , con

volte

0 + ⋅

( )

= ⋅ = =

Convenzionalmente si pone . Le proprietà sono e .

PROPRIETÀ FORMALI: seguono proprietà utili per l’applicazione pratica con tanto di caratteristiche che le legano all’inclusione tra relazioni o alle operazioni tra

relazioni. Data la relazione e l’insieme si ha quindi:

 ( )

∀ ∈ , ∃ ∈ : , ∈ .

Proprietà seriale: ne gode su se 1 2 1 2

o

Grafo: da ogni vertice di esce almeno un arco;

o Matrice: ha su ogni riga almeno un 1.

 (,

∀ ∈ ) ∈ . ⊆ .

Proprietà riflessiva: ne gode su se si ha è riflessiva SSE

o

Grafo: da ogni vertice di esce l’autoanello;

o Matrice: ha la diagonale principale composta tutta da 1.

 −1

( ) ( )

, ∈ , ∈ . ⊆ .

Proprietà simmetrica: ne gode su se implica è simmetrica SSE

1 2 2 1

o Grafo: ogni arco ha la doppia freccia (NB: gli autoanelli sono archi con la doppia freccia);

o Matrice: coincide con la trasposta (è simmetrica).

 −1

( ) ( )

, ∈ , ∈ = ∩ ⊆

Proprietà antisimmetrica: ne gode su se implica . è antisimmetrica SSE .

1 2 2 1 1 2

o Grafo: gli unici archi con la doppia freccia sono gli autoanelli;

o (, )

Matrice: la somma della matrice d’incidenza con la sua trasposta non ha nessun 2 fuori dalla diagonale principale, ovvero per ogni

(,

1 )

corrispondente ad un il simmetrico corrisponde ad uno 0.

 2

( ) ( ) ( )

, ∈ , ∈ , ∈ . ⊆ .

Proprietà transitiva: ne gode su se implica è transitiva SSE

1 2 2 3 1 3

o

Grafo: ogni volta che esiste un arco da un vertice ad e un altro arco da ad esiste anche un arco che va direttamente da ad ;

1 2 2 3 1 3

o (, (, (,

) ) )

Matrice: ogni volta che gli elementi e sono 1 anche l’elemento è 1.

⊂ ⊂ :

Con ⊆ × ⊆ ×

DEF. CHIUSURA: sia un insieme di proprietà formali e sia una relazione binaria. Si definisce chiusura rispetto a di una relazione tale che:

 ⊆ ;

 ;

gode di tutte le proprietà in

 ⊆ × ⊆ .

se è una relazione che gode di tutte le proprietà in e che contiene allora

-chiusura , ,

Proprietà: notando che la di se esiste, è la minima relazione che contiene ed ha tutte le proprietà in si può concludere che:

 -chiusura

la di se esiste è unica;

 -chiusura ;

la di può coincidere con SSE soddisfa le proprietà in

 -chiusura

possiamo garantire che esiste la di se: ;

- esiste una relazione che gode di tutte le proprietà in e che contiene

.

- l’intersezione di tutte le relazioni che godono delle proprietà in gode delle proprietà in

Costruzione della chiusura riflessiva, simmetrica e transitiva: .

dalle osservazioni fatte in precedenza possiamo concludere che esistono la chiusura riflessiva, simmetrica e transitiva per qualunque relazione Infatti la relazione

universale gode di ognuna di queste tre proprietà. In generale però non esistono la chiusura seriale e antisimmetrica.

 ∪

la chiusura riflessiva di una relazione è ;

 −1

∪

la chiusura simmetrica di una relazione è ;



la chiusura transitiva di una relazione è .

⋃ >0

=

DIM: ponendo (con grande quanto basta perché le matrici d’incidenza non introducano nuovi 1) allora :

⋃ >0 1

, ⊆

1) contiene infatti ;

⋃ >0 ℎ ℎ+

( ) ( ) ( ) ( )

, ∈ ( , ) ∈ ℎ, > 0 , ∈ , ∈ , ⊆ ;

2) è transitiva, infatti se e allora esistono tali che e e quindi

1 2 2 3 1 2 2 3 1 3 2

, , ⊆

3) è contenuta in ogni relazione transitiva che contenga infatti se è una relazione transitiva che contiene si ha per la transitività che e per

2 2 2 3 2

⊆ ⊆ . ⊆ ⊆

la compatibilità del prodotto da cui Ancora per la compatibilità del prodotto e la transitività e ripetendo il ragionamento

contiene tutte le potenze positive di da cui la tesi.

Chiusura rispetto a composto da più elementi

-chiusure ⊆ ×

Siccome gode delle proprietà in e le proprietà si mantengono per intersezione esistono le di una relazione .

 −1

∪ ∪

la chiusura riflessiva e simmetrica di è la relazione ;



la chiusura riflessiva e transitiva di è la relazione ;

⋃ ≥0

 −1

( )

∪

la chiusura simmetrica e transitiva di è la relazione ;

⋃ ≥0

 −1

( )

∪ ∪

la chiusura riflessiva, simmetrica e transitiva di è la relazione .

⋃ ≥0

1.3 Relazioni di equivalenza

DEF. RELAZIONE DI EQUIVALENZA: una relazione binaria su un insieme è detta di equivalenza su se è riflessiva, simmetrica e transitiva.

. .

DEF. equivalenza generata: è la chiusura riflessiva, simmetrica e transiva di una relazione Ovvero la minima relazione di equivalenza che contiene

): , ∀ ∈

DEF. classe di equivalenza (rispetto ad avente come rappresentante data una relazione di equivalenza su un insieme si tratta dell’insieme

[] {

= = ∈ |(, ) ∈ }

[] (, (, [] [] []

∈ ) ∈ ) ∈ , ∈ =

NB: se allora e per simmetria perciò implica , quindi ogni elemento di una classe può esserne scelto rappresentante.

{ |

ℬ = ∈ }

DEF. partizione: dato un insieme qualunque e un insieme di indici, si dice partizione di una famiglia di sottoinsiemi di tali che:

 ∀ ∈ ≠ ∅;

si ha

 = ℬ ;

forma un ricoprimento di

⋃ ∈

 ∩ ≠ ∅ ⟹ = ℬ

gli elementi di sono disgiunti.

{[] |

, -classi ℬ = ∈ } .

Teorema: sia una relazione d’equivalenza su un insieme allora l’insieme delle è una partizione di detta partizione indotta di

{ | (,

ℬ = ∈ } , ) ∈ ∈ : , ∈

Viceversa, data una partizione di la relazione definita ponendo SSE esiste è una relazione d’equivalenza e la partizione

ℬ ℬ

ℬ.

indotta da coincide con

ℬ , , -classi ,

DEF. insieme quoziente: sia una relazione d’equivalenza su la partizione indotta da su ovvero l’insieme delle di si dice insieme quoziente di

{ |

/, / = ∈ }.

rispetto ad e si indica con dunque

1.4 Relazioni d’ordine

DEF. RELAZIONE D’ORDINE: una relazione binaria su un insieme A è detta d’ordine su se è riflessiva, antisimmetrica e transitiva.

(, (,

∀, ∈ ) ∈ ) ∈ .

DEF. relazione d’ordine totale: la relazione è detta d’ordine totale se si ha o

(, ≤) ≤ .

DEF. insieme parzialmente ordinato (poset): è la coppia formata da un insieme e da una relazione d’ordine su

(, (,

, ∈ ) ∈ ) ∈ .

DEF. elementi non confrontabili: due elementi tali che né né si dicono non confrontabili rispetto ad

NB: in una relazione non esistono elementi non confrontabili rispetto ad SSE è una relazione d’ordine totale. (,

∀ ∈ ) ∉

DEF. relazione d’ordine stretto: è una relazione su che sia antisimmetrica e transitiva tale che si abbia (irriflessività).

(, ≤) ∈ :

DEF. minimo, minimale, massimo, massimale: sia un insieme parzialmente ordinato e sia

 ∀ ∈ ≤ ;

è l’elemento minimo di se si ha

 ∀ ∈ , ≤ = ;

è l’elemento minimale di se se allora

 ∀ ∈ ≤ ;

è l’elemento massimo di se si ha

 ∀ ∈ , ≤ = .

è l’elemento massimale di se se allora

NB: ogni minimo è un elemento minimale e ogni massimo è un elemento massimale, inoltre:

 (, ≤)

Se in esiste minimo (massimo), tale minimo (massimo) è unico;

 (,

≤)

Se è un insieme finito e ha un unico elemento minimale (massimale), questo è un minimo (massimo).

(, ≤) ⊆ ∈

DEF. estremi, minorante e maggiorante: siano un insieme parzialmente ordinato, ed

 ∀ ∈ ≤ ;

si dice minorante di se si ha

 ;

si dice estremo inferiore di se è il massimo dei minoranti di

 ∀ ∈ ≤ ;

si dice maggiorante di se si ha

 .

si dice estremo superiore di se è il minimo dei maggioranti di

(, ≤) ⊆ .

Proprietà: dato un insieme parzialmente ordinato e

 inf ;

Se ha un minimo questo è un minorante di ed è

 , inf ;

Se un minorante di appartiene a allora è il minimo di ed è

 sup ;

Se ha un massimo questo è un maggiorante di ed è

 , sup .

Se un maggiorante di appartiene a allora è il massimo di ed è

(, ≤) , ∈ inf{, } sup{, }.

DEF. reticolo: è un insieme parzialmente ordinato tale che per ogni esistano e

2. Funzioni

, , ⊆ ×

Dati gli insiemi le relazione è:

 (,

∈ ∈ ) ∈ ;

ovunque definita se per ogni esiste almeno un tale che

 (, ) (, )

∈ , ∈ , ∈ ∈