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: se esiste almeno un tale che

1 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: 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: se implica

1 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: se e implicano

1 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 che

1 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 ( ).

∀ ∈ ,

Significa aggiungere alla relazione

Nel grafo di incidenza: aggiungere tutti gli autoanelli.

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

Chiusura simmetrica (,

∀(, ) ∈ ).

Significa aggiungere alla relazione

Nel grafo di incidenza: aggiungere tutti le doppie frecce.

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

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 che

1 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

-classe

rispettivo dominio. In altre parole la di un elemento coincide con l’insieme degli elementi del dominio che

hanno 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