Logica e Algebra - Appunti riassuntivi e svolgimento esercizi

Algebra

Parte I

Proprietà delle relazioni binarie su un insieme

⊆ × Le relazioni possono godere delle seguenti proprietà:

(, )∀ ∈ ∈ ∈ .

Proprietà seriale

Proprietà seriale: se esiste almeno un tale che1 1

Dal grafo di incidenza: se da ogni vertice parte almeno una freccia.

Dalla matrice di incidenza: se in ogni riga della matrice c’è almeno un 1.

(,∀ ∈ ) ∈ .

Proprietà riflessiva

Proprietà riflessiva: se si ha che

Dal grafo di incidenza: se da ogni vertice parte un autoanello.

Dalla matrice di incidenza: se la diagonale principale è tutta fatta di 1.

( ) ( )∀ , ∈ , , ∈ , ∈ .

Proprietà simmetrica

Proprietà simmetrica: se implica1 2 1 2 2 1

Dal grafo di incidenza: se ogni arco ha una doppia freccia.

Dalla matrice di incidenza: se la matrice coincide con la propria trasposta (cioè è simmetrica).

( ) ( )∀ , ∈ , , ∈ , ∈ = Proprietà antisimmetrica: se e implicano .1 2 1 2 2 1 1 2

Dal grafo di incidenza: se non ci sono archi con doppia freccia al di fuori degli autoanelli.

Dalla matrice di incidenza: se la somma della matrice con la sua trasposta non ha alcun 2 al di fuori della diagonale principale.

( ) ( ) ( )∀ , , ∈ , , ∈ , ∈ , ∈ .

Proprietà transitiva

Proprietà transitiva: se e implicano1 2 3 1 2 2 3 1 3

Dal grafo di incidenza: se ogni volta che si può andare da un vertice ad un vertice seguendo due frecce consecutive c’è un altro arco che1 2 collega direttamente e .1 2

Dalla matrice di incidenza: se tutte le volte che sia l’elemento di posto (i,k) sia l’elemento di posto (i,j) sono 1 allora anche l’elemento di posto(i,j) è 1.

Chiusura riflessiva

Chiusura riflessiva ( ).∀ ∈ , Significa aggiungere alla relazione

Nel grafo di incidenza: aggiungere tutti gli autoanelli.

Nella matrice di incidenza: mettere tutti 1 sulla diagonale principale.

Chiusura simmetrica

Chiusura simmetrica (,∀(, ) ∈ ).Significa aggiungere alla relazione

Nel grafo di incidenza: aggiungere tutte le doppie frecce.

Nella matrice di incidenza: rendere la matrice coincidente con la propria trasposta (simmetrica).

Chiusura transitiva

Chiusura transitiva(, (, (,) ∈ ) ∈ )Se e significa aggiungere alla relazione.

Nel grafo di incidenza: se da un vertice posso raggiungere un vertice passando attraverso due frecce, bisogna aggiungere la freccia che1 2 collega direttamente a .1 2

Nella matrice di incidenza: se sia l’elemento di posto (i,k) che l’elemento di posto (k,j) sono 1, bisogna porre a 1 anche l’elemento di posto (i,j).

Relazione di equivalenza

È una relazione binaria su A che gode delle proprietà riflessiva, simmetrica e transitiva.

Classi di equivalenza e insieme quoziente

, -classi Dato il seguente grafico che rappresenta una relazione di equivalenza su un insieme le di sono:

[] [] [] {, [] [] {, [] {}= = = , } = = } = -classi /.

L’insieme delle di si dice insieme quoziente di rispetto a e si indica Dunque:

[] []/ = {[] , , }

-classe -classe

Preso ogni elemento del codominio di una funzione, la di un elemento è l’insieme degli elementi del -classerispettivo dominio. In altre parole la di un elemento coincide con l’insieme degli elementi del dominio chehanno per immagine quell’elemento del codominio.

2 {−1,1}.() = -classe

Ad esempio: sia , la di 1 è

Relazione d’ordine

È una relazione binaria su A che gode delle proprietà riflessiva, antisimmetrica e transitiva.

Diagramma di Hasse

Si ottiene partendo dal grafo di incidenza usando alcune convenzioni:

• Non si rappresentano gli autoanelli;
• Non si mette la freccia sugli archi (si assume che ogni arco vada dal vertice più in basso a quello più in alto);
• Se c’è un arco che va dal vertice A al vertice B ed uno che va dal vertice B al vertice C, si evita di disegnare l’arco che va dal vertice A al vertice C

Funzioni

(, ⊆ × ∈ ∈ ) ∈ .

Una relazione tale che per ogni esiste uno ed uno solo tale che si dice funzione da a.

Dal grafo di incidenza: se c’è uno e un solo arco uscente da ogni vertice che rappresenta un elemento di

Dalla matrice di incidenza: se c’è uno e un solo 1 su ogni riga.

) ) ∈ ( = ( = Funzione iniettiva: se ogni ha al più una controimm