Matematica discreta

Appunti per il corso di Matematica discreta

Tenuto dalla professoressa Rosaria Rota

Premessa

Salve, mi chiamo Giancarlo è come si può immaginare sono uno studente di ingegneria che si diletta nello scrivere appunti relativi ai corsi tenuti dai professori di ingegneria presso l’università Roma Tre. Questa non è la prima volta che scrivo un elaborato ma tengo sempre a precisare che io sono uno studente e non un professore perciò le mie dispense, se così le vogliamo chiamare, sono da prendere con il beneficio del dubbio, ovvero la probabilità che all’interno di queste ci siano errori non è sicuramente nulla.

Inoltre esse non rappresentano (e mai lo faranno) un libro di testo sul quale ci si può basare il proprio studio per superare l’esame della materia corrispondente, ma al contrario esse devono servire esclusivamente per avere un’idea generale degli argomenti trattati a lezione. Ricordatevi che un libro è sempre un libro, non solo perché è scritto da persone competenti, ma anche perché è scritto in maniera più fluida soffermandosi anche su aspetti e esempi per rendere più chiaro possibile l’argomento trattato, cosa che nelle mie dispense non capita spesso perché scrivo solo ciò che il professore spiega a lezione, cercando sì di collegare tutto quello che è possibile ma con il risultato sempre approssimato perché la mia preparazione è ancora da affinare.

Proprio per questo motivo che invito i lettori delle mie dispense ad integrare con un libro di testo o con altro materiale ritenuto adatto questi miei appunti. Grazie

Indice

• Definizione di Relazione………………………………pag. 2
• Proprietà delle Relazione………………………………..pag. 3
• Relazione di Equivalenza………………………………..pag. 4
• Congruenza modulo m…………………………………...pag. 8
• Costruzione di campi finiti a partire da Zm………......pag. 12
• Metodi per trovare gli inversi…………………….…......pag. 21
• Costruzione di altri campi……………………………….....pag. 24
• Relazioni d’ordine…………………………………………pag. 29
• Diagrammi di Hasse…………………………………… pag. 32
• Max, min, magg, min, sup e inf....................................pag. 33
• Definizione di Reticolo……………………………………pag. 39
• Considerare un reticolo una struttura algebrica…….....pag. 40
• Algebra di Boole……………………………………… ….pag. 41
• Tipologie di esercizi sull’algebra di Boole…………….pag. 42
• Teoria dei grafi…………………………………………..pag. 47
• Grafi orientati………………………………………………pag. 61
• Colorazione dei vertici…………………………………..pag. 68
• Colorazione dei lati………………………………………pag. 78
• Reti di flusso………………………………………………pag. 82

Matematica Discreta 1

Definizione di relazione

Si definisce relazione R su di un insieme A quel particolare sottoinsieme contenente elementi appartenenti al prodotto cartesiano AxA.

Per definizione il prodotto cartesiano AxA è l’insieme dei prodotti ordinati di tutti gli elementi appartenenti all’insieme A, ovvero espresso sotto la forma di espressione si ha:

{( ) }= ∈, / ,AxA x y x y A

Allora se ad esempio l’insieme A è definito come segue:

{ }= , , ,A a b c d

Una possibile relazione R sull’insieme A può essere la seguente:

{( ) ( ) ( ) ( )}= , , , , , , ,R a a c c a b b c

Si dice allora che R è una relazione su A in quanto i suoi elementi appartengono anche al prodotto cartesiano dell’insieme A per se stesso.

Una relazione R può essere descritta mediante una matrice, detta matrice di incidenza, la quale è una matrice quadrata di ordine n con la particolarità di avere i coefficienti così definiti: = ⇔ ∈0 ,r r r Rij i j = ⇔ ∉1 ,r r r Rij i j

Ad esempio: { } {( ) ( ) ( ) ( )}== , , , , , , ,R a a c c a d b c, , ,A a b c d er r r r1 2 3 4

Si osservi che: = == = ; ;; ; r c r dr a r b 3 41 2

La matrice che si deve costruire sarà una 4x4; laddove la coppia ∈,r r Ri j

Si scriverà un 1, altrimenti uno zero (la coppia i,j non appartiene alla relazione R) ∉,r r R .i j

Matematica Discreta 2

La matrice che si ottiene seguendo i passaggi descritti è la seguente:

   r r r r 1 0 0 1

   11 12 13 14

   r r r r 0 0 1 0

   21 22 23 24

= =M    r r r r 0 0 1 0

   31 32 33 34      r r r r 0 0 0 041 42 43 44

Dalla matrice si osserva che nel sottoinsieme R sono contenuti gli elementi costituiti dalle coppie: ( ) ( ) ( ) ( ), ,r r r r , ,r r r r, , , .1 1 1 4 2 3 3 3

Proprietà delle relazioni

Le relazioni si differenziano le une dalle altre in base alle proprietà che soddisfano. Tali proprietà sono elencate qui di seguito:

• Proprietà riflessiva: ( ) ∈ ∀ ∈, ___a a R a A o anche aRa (si legge a è in relazione con a)
• Proprietà di Simmetria: se ( ) ( )∈ → ∈, ,a b R b a R → aRb bRa
• Proprietà di Antisimmetria: se → =,aRb bRa a b
• Proprietà transitiva: se →,aRb bRc aRc

Matematica Discreta 3

Queste proprietà vengono anche riscontrate nelle matrici d’incidenza M; ad esempio per la proprietà 1) si ha una matrice avente tutti 1 sulla diagonale principale (quando i pedici i, j=r r coincidono); per la 2) la matrice presenta la caratteristica di avere ; per la 3)ij ji= −r r invece .ij ji

Viene definita ora una particolare relazione, la Relazione d’ordine, la quale verrà ripresa più in là.

Dato un insieme A, R è definita relazione d’ordine se soddisfa le seguenti proprietà:

• Proprietà riflessiva;
• Proprietà antisimmetrica;
• Proprietà transitiva;

(A,R) viene definito Reticolo.

Relazione di equivalenza

Dato un certo insieme A ed una relazione R su di esso, R viene detta relazione di equivalenza se soddisfa le tre proprietà seguenti;

• Proprietà riflessiva;
• Proprietà simmetrica;
• Proprietà transitiva;

Da questo momento in poi, finché non verrà specificato, si considereranno solo delle relazioni di equivalenza.

La relazione di equivalenza permette di suddividere l’insieme A in tanti sottoinsiemi definiti come classi di equivalenza e simboleggiati come segue:

[ ] =x x

Una classe di equivalenza altro non è che un sottoinsieme di A costituito da tutti quegli elementi y appartenente ad A che sono in relazione con x;

[ ] { }= ∈ /x y A xRy

I sottoinsiemi, cioè le classi di equivalenza sono a due a due disgiunti, non hanno alcun elemento in comune; l’unione tra tutte le classi appartenenti all’insieme A dà come risultato proprio l’insieme A.

Matematica Discreta 4

Figura 1

Teorema

Ipotesi: Se R è una relazione di equivalenza allora:

Tesi:

• ∈ ∀ ∈[ ],a a a A
• [ ] [ ]∈ ⇔ =[ ]b a a b
• [ ] [ ] [ ] [ ]∩ = =0 _ _a b oppure a b

Il primo punto dice che l’elemento a appartiene alla classe di equivalenza a per qualsiasi a che appartiene a tutto l’insieme completo A.

Il secondo punto dice che se l’elemento b appartiene alla classe allora si è sicuri che la classe di equivalenza b coincide proprio con la classe di equivalenza a; questo perché come accennato qualche rigo in su, le classi sono a due a due disgiunte, quindi non possono avere elementi in comune: l’unico caso per averli è quello di far coincidere le due classi.

Il terzo punto invece dice che l’intersezione tra le classi d’equivalenza a ed b è nulla, sempre per il motivo che non ci sono elementi in comune, oppure se non è nulla le due classi coincidono.

Dimostrazione del teorema

• ∈ ∀ ∈[ ],a a a A1.

Sia a un elemento appartenente all’insieme A, dunque

Matematica Discreta 5

→ ∈ [a ]aRa a

a è in relazione con a e questo implica l’appartenenza alla classe di equivalenza di a.

[ ] [ ]∈ ⇔ =[ ]b a a b2. Dimostrazione della freccia verso sinistra:

• Per ipotesi =[ ] [ ]a b

Quindi gli elementi della classe di equivalenza di a coincidono con quella di b, quindi qualsiasi elementi di b appartiene anche alla classe di equivalenza di a (proprietà riflessiva).

Dimostrazione freccia verso destra:

• Per ipotesi ∈ [a ]b

Dunque ci si domanda se sia vero che =[ ] [ ]a b .

L’espressione risulta vera se le relazioni di inclusione dei due sottoinsiemi risultano vere, quindi se risultano o la 1 o la 2 ≤1)[ ] [ ]a b ≤2 )[ ] [ ]b a

Per la 1 si prende un elemento ∈ [a ]z

Quindi da questa espressione si può dire che z è in relazione con a

zRa

Per ipotesi però si era detto che ∈ [a ]b, dunque anche b è in relazione con a

Matematica Discreta 6

aRb

(per la proprietà simmetrica si sono scambiati di posto a e b)

Allora se aRbzRa , ,(per la proprietà transitiva delle relazioni z è in relazione con b)

zRb

La dimostrazione della 2 è analoga a quella svolta per la 1, quindi viene omessa.

[ ] [ ] [ ] [ ]∩ = =0 _ _a b oppure a b3.

Dire che la classe a e la classe b hanno un elemento in comune significa dire che le due classi coincidono; se si prende un elemento z appartenente all’intersezione tra le due classi di equivalenza, questi apparterrà sia alla classe a che alla classe b.

∈ ∩ = ∈ ∈[ ] [ ] [ ] _ _ [ ]z a b z a e z b

Di conseguenza zRbzRa e

Per la proprietà riflessiva si possono scambiare di posto la a e la b con la z:

bRzaRz ,

Usando la proprietà transitiva, se a è in relazione con z e b è anch’esso in relazione con z, allora a e b sono in relazione tra di loro.

aRb bRa(o anche )

La relazione aRb implica che ∈ ∈[b ] [a ]a b(o )

Ma se a appartiene alla classe di equivalenza b (o b appartiene alla classe di equivalenza a), per la tesi numero 2 del teorema visto, le due classi coincidono

=[ ] [ ]a b

Matematica Discreta 7

Si definisce Insieme quoziente di A rispetto ad R, l’insieme di tutte le classi di equivalenza al variare di x in A A { }= ∈[ ] /x x AR

Ricapitolando:

• Ogni classe di equivalenza è una partizione dell’insieme A;
• L’unione di tutte le classi di equivalenza dà l’insieme intero A;
• L’intersezione tra tutte le classi di equivalenza dà come risultato un insieme vuoto;
• Se due classi hanno degli elementi in comune, i due insiemi coincidono;

Congruenza modulo m

Verrà adesso introdotto il concetto di Congruenza modulo m attraverso un esempio.

Esempio:

Si prenda in considerazione l’insieme dei numeri interi relativi Z e si fissi m=5.

La relazione di equivalenza R su Z è la congruenza modulo 5.

La definizione di congruenza modulo 5 è la seguente:

Presi x e y appartenenti all’insieme dei numeri interi relativi Z, si dice che x è congruo ad y modulo 5 se e soltanto se la differenza tra x ed y è un multiplo di 5:

∈∈ ≡ ⇔ − = ⋅, k Zx y Z 5x y x y k(mod 5 )

Osservazione:

La congruenza modulo 5 è una relazione di equivalenza? Per rispondere a questa domanda bisogna vedere se vengono soddisfatte le 3 proprietà di relazione di equivalenza:

• Proprietà riflessiva: si tratta di verificare se preso un certo x appartenente all’insieme Z esso sia congruo a se stesso. ≡ ⇔ − = ⋅ → = ⋅5 0 5 0x x x x k(mod 5 ) la prima proprietà è verificata;
• Proprietà di simmetria: bisogna verificare che, presi un x ed un y appartenenti a Z, x sia congruo a y modulo 5 e viceversa.

Matematica Discreta 8

≡ ⇔ − = ⋅5x y x y k(mod 5 )

− − = ⋅ −( ) 5 ( )x y k

− = ⋅ −5 ( )y x k

≡ ⇔ − = ⋅5y x y x u(mod 5 ) = −u k

Con

La seconda proprietà è verificata: ≡ ≡x y y ze ,

• Proprietà transitiva: Date due congruenze differenti mod 5 mod 5 ≡x z bisogna verificare che mod 5

≡ → − = ⋅5x y x y kmod 5

≡ → − = ⋅5y z y z tmod 5

= ⋅ +5y t z

≡ → − = ⋅ → − ⋅ + = ⋅5 ( 5 ) 5x y x y k x t z kmod 5 − ⋅ + = ⋅(5 ) 5x t z k

− = ⋅ + → − = ⋅5 ( ) 5 ( )x z k t x z s

= +s k t

≡ → − = ⋅5 ( )x z x z smod 5

Anche la terza proprietà è verificata. La congruenza modulo 5 è dunque una relazione di equivalenza.

Osservazione:

Si prenda in considerazione ≡x y mod 5

L’elemento x è congruo modulo 5 a y se e soltanto se sia x che y divisi per 5 danno lo stesso resto.

Infatti: = ⋅ +5x q r1 1

= ⋅ +5y q r2 2

Matematica Discreta 9

≡ → − = ⋅5x y x y tmod 5

La differenza tra x ed y deve essere un multiplo di 5. allora per le espressioni scritte:

− = ⋅ − + −5 ( ) ( )x y q q r r1 2 1 2

Affinché x sia congruo ad y è necessario che i due resti siano uguali in modo tale da avere

− = ⋅ − → − = ⋅5 ( ) 5x y q q x y s con s appartenente a Z1 2

Nel caso di congruenza modulo 5 i possibili resti r possono essere 0,1,2,3,4. Preso un qualsiasi z appartenente a Z lo si divide per 5:

= ⋅ +5z q r

Ma − = ⋅5z r q

Dunque la differenza z-r è un multiplo di 5, quindi z è congruo r modulo 5 e appartiene alla classe resto r: ≡ → → ∈ [ ]z r zRr z rmod 5

Ad esempio se si prende il numero 9, esso è congruo modulo 5 ed appartiene alla classe resto 4 ≡ → − = ⋅9 4 9 4 5 1mod 5

Altri esempi:

≡ → − = ⋅7 2 7 2 5 1mod 5

≡ → − = ⋅17 2 17 2 5 3mod 5

≡ → − = ⋅24 4 24 4 5 4mod 5

≡ → − = ⋅124 4 124 4 5 24mod 5

≡ → − = ⋅23 3 23 3 5 4mod 5

Si costruisce l’insieme quoziente di Z a partire dalle classi resto. Nel caso della congruenza modulo 5 le classi resto sono:

[ 0 ], [1], [ 2], [3], [ 4 ]

Matematica Discreta 10

0,1,2,3,4 sono detti rappresentanti delle classi. Lo scopo è quello di, (partiti dall’insieme dei numeri interi relativi), costruire una struttura finita che abbia la forma di campo, Z 5 Ze questo lo si fa prendendo in considerazione le classi resto. L’insieme è formato5 dagli elementi classi resto: { }= [ 0], [1], [ 2 ], [3], [ 4 ]Z 5

Qualunque intero dell’insieme degli interi relativi appartiene ad una delle 5 classi resto che Z formano . Ad esempio, nel disegno riportato sotto sono inseriti alcuni numeri nelle5 classi resto di appartenenza:

Fino ad ora si è visto un caso particolare, la congruenza modulo 5; più in generale si ha la congruenza modulo m con ≥ 2m

La congruenza modulo m in Z è una relazione di equivalenza

{ }= −[ 0], [1], [ 2 ], [3],......., [ 1]Z mm

Zm è l’insieme delle classi resto modulo m. I campi finito vengono costruiti a partire dall’