Appunti Matematica discreta – Informatica (Insiemi, funzioni, algebra)

Antonio Wang - PEU-Z

Matematica Discreta

Spiegazione

Teoria degli insiemi DEFINIZIONE

una collezione di oggetti. Denotiamo un insieme con le lettere maiuscole(A, ...)

B, C,

Insieme:è

Per esempio possiamo chiamare l’insieme delle lettere dell’alfabeto, ecc...

A

Gli elementi dell’insieme, invece, vengono denotati con la lettera minuscola(a, ...)

b, c,

Gli insiemi che contengono un singolo elemento vengono denominati = {a})

singleton(A

Un insieme che non ha elementi si denota con il simbolo ∅

ESEMPI

= {a,

A b, c, ...}

Nota bene: Per denotare un insieme non contano le ripetizioni e non conta l’ordine degli elementi

= 1, 2, 3} = 2, 3} = 2, 1}

{1, {1, {3,

A IDEA INTUITIVA

La nostra concezione di = è che due insiemi sono uguali se hanno gli stessi elementi.

(uguale)

Come si descrive un insieme?

Elencando tutti gli elementi;

• Descrivendone le proprietà. 1

•

Prima di poter capire cos’è realmente la concezione di “uguale” per quanto

riguarda gli insiemi, dunque, dobbiamo capire i modi per descrivere un insieme.

ESEMPI

Prendiamo in esempio l’insieme delle vocali

= = :

{a, {x

V e, i, o, u} xvocale}

Nota bene: gli insiemi più “importanti” degni di nota sono i seguenti:

4 A x x P

Per esempio: = : gode della proprietà

1

Antonio Wang - PEU-Z

= un numero naturale} = 1, 2, 3,

{x | {0,

xè ...}

N ⊬

= un numero naturale e = 0} = 2, 3,

{x | ̸ {1,

xè x ...}

N = un numero intero} =

{x | {0, ±1, ±2, ±3,

xè ...}

Z 1

= un numero razionale} =

{x | xè , ...

Q 2

√

n o

= un numero reale} = 2,

{x | xè π, ...

R = un numero complesso}

{x | xè

C

Dopo che abbiamo visto questi insiemi dobbiamo prima di tutto prendere dimes-

tichezza con il simbolo (appartiene).

∈ = : 0} =

{x ∈ ∅

A x <

N

I numeri naturali non possono essere negativi, dunque si tratta di un

insieme vuoto.

Se è un insieme, affermare che significa dire che è un elemento di

∈

A x A x A.

D’altro canto, affermare che significa dire che è un elemento di

∈

x / A x A.

non

Nota: è preferibile leggere le sezioni di Sottoinsiemi e Sottoinsieme proprio prima

di finire di leggere e poter comprendere la parte finale di questa sezione.

Ritornando all’idea intuitiva esposta precedentemente, potremmo perfezionare

la nostra definizione dicendo che:

Due insiemi e sono uguali per definizione se soddisfano i seguenti

A B

requisiti: • ⊆

A B

• ⊆

B A

Sottoinsiemi

A B A B

Siano e due insiemi. Si dice che è un sottoinsieme di se

A B.

ogni elemento di appartiene anche a

Dunque definiamo i sottoinsiemi in maniera matematica.

DEFINIZIONE

def

⊆ ⇐⇒ ∀a ∈ ∈

A B A, a B

Prendiamo un esempio per capire meglio questo concetto.

2

Antonio Wang - PEU-Z

L’insieme delle vocali è contenuto nell’insieme dell’alfabeto.

V A

= =

{a, ⊆ {a,

V e, i, o, u} A b, c, ...}

OSSERVAZIONE

(a ∈ → ∈ → ⊆

A a B) A B

Se un elemento generico appartiene all’insieme e appartiene

a A

anche ad un insieme allora possiamo dire che è un sottoinsieme

B A

di B

se abbiamo due proposizioni e (due affermazioni,

P Q

Digressione:

in gergo comune): →

P Q

La proposizione implica la proposizione

P Q.

Dobbiamo dimostrare se

Cosa dobbiamo dimostrare in questo caso?

l’ipotesi è vera oppure falsa. Partiamo da un esempio per comprendere con più

facilità il tutto: ESEMPIO

⊆

Z N

Esiste ma non

−2 ∈ −2 ∈

Z N

C’è almeno caso in cui se è

P

Cosa osserviamo in questo esempio? un

vera, non lo è. Per dimostrare che un’affermazione sia vera dunque dobbiamo

Q

dimostrare quest’affermazione per tutti i casi. Per dimostrare il contrario invece

basta per cui la nostra affermazione non può funzionare.

un solo caso

Sottoinsieme proprio

Siano e due insiemi, si dice che è un sottoinsieme proprio di

A B A

se soddisfa questi due requisiti

B

• è sottoinsieme di

A B;

• è diverso da

A B.

Ovviamente come già visto in precedenza dobbiamo dimostrarlo.

DEFINIZIONE

⊂

A B

Per definizione è:

⊆

A B

=

̸

A B

3

Antonio Wang - PEU-Z

Come di consueto, di seguito alcuni esempi:

ESEMPI

⊂

N N

⊬

poiché

⊆

N N

⊬

=

̸

N N

⊬

Possiamo notare che tra gli insiemi che abbiamo visto precedentemente si possono

individuare dei sottoinsiemi propri.

ESEMPIO

⊂ ⊂ ⊂ ⊂ ⊂

N N Z Q R C

⊬

Proprietà transitiva dell’inclusione e dell’uguaglianza

Proprietà transitiva dell’inclusione

Siano e tre insiemi. Se consideriamo che è un sottoinsieme

A, B C A

di e è un sottoinsieme di allora per logica automaticamente

B B C

è un sottoinsieme di

A C.

Scriviamolo dunque in notazione matematica:

⊆ ∧ ⊆ → ⊆

A B B C A C

Proprietà transitiva dell’uguaglianza

Se consideriamo che è uguale a e è uguale a allora per

A B B C

intuizione è uguale a

A C.

Scriviamolo dunque in notazione matematica:

= = =

∧ →

A C B C A C

4

Antonio Wang - PEU-Z DIMOSTRAZIONE #1

Vogliamo dimostrare che ⊆

A C.

Partiamo dalla di ciò che abbiamo scritto.

definizione

def

⊆ ⇐⇒ ∀a ∈ ∈

A C A, a C

Riprendiamo anche la definizione in scrittura matematica

che abbiamo preso in precedenza con le nostre ipotesi:

⊆ ∧ ⊆

A B B C

Riscriviamo prima in un altro modo:

⊆

A B

∈ → ∈

a A a B

Possiamo fare lo stesso ragionamento per ⊆

B C

∈ → ∈

a B a C

Concateniamo il tutto e otteniamo:

∈ → ∈ → ∈

a A a B a C

DIMOSTRAZIONE #2

Vogliamo dimostrare che =

A C.

Partiamo dalla di ciò che abbiamo scritto.

definizione

• ⊆

A C

• ⊆

C A

Riprendiamo le nostre ipotesi:

= =

∧

A B B C

Come le possiamo riscrivere?

= e =

A B B C

e

• ⊆ ⊆ → ⊆

A B B C A C

e

• ⊆ ⊆ → ⊆

B A C B C A

Perché proprio ⊆

C A?

Nota:

Ciò che abbiamo scritto può essere scritto anche come ⊆ ⊆

C B A,

per cui otteniamo ciò che abbiamo scritto.

= è la stessa cosa di = No.

{3, {3}} {3}?

A A

Digressione:

Il primo elemento dell’insieme è il numero 3, mentre il secondo

A

Perché no?

elemento dell’insieme è il sottoinsieme che contiene 3.

A

Cardinalità degli insiemi

Se è un insieme finito con il simbolo si indica la cardinalità

| |

A A

di cioè il numero di elementi di

A A.

5

Antonio Wang - PEU-Z ESEMPIO

= {a,

V e, i, o, u}

5

| |=

V

Nota bene: c’è una differenza tra e

appartiene è contenuto in:

∈

a V

{a} ⊆ V

Teoria dell’insieme delle parti

Sia un insieme. L’insieme delle parti di si denota con e

P(A)

A A

contiene tutti i sottoinsiemi di A.

DEFINIZIONE

=

P(A) {x | ⊆

x A}

ESEMPIO

= {a,

A b}

=

P(A) {∅, {a} {b}}

A, ,

Se prendiamo invece come esempio un insieme da più di 2 elementi si

prendono tutte le combinazioni possibili chiaramente.

= {a,

A b, c}

=

P(A) {∅, {a} {b} {c} {a, {a, {b,

A, , , , b} , c} , c}}

TEOREMA 2

n

| |= →| P(A) |=

A n

PROPOSIZIONE

Siano e due insiemi, se allora

⊆ P(A) ⊆ P(B)

A B A B

Operazioni tra gli insiemi

Unione

Siano e due insiemi:

A B DEFINIZIONE

def e

∪ ⇐⇒ {x | ∈ ∈

A B x A x B}

def o

∈ ∪ ⇐⇒ ∈ ∈

x A B x A x B

def e

∈ ∪ ⇐⇒ ∈ ∈

x / A B x / A x / B

6

Antonio Wang - PEU-Z ESEMPIO

= 2, 3}

{1,

A = {2,

B c, d}

= 2, 3, 2, = 2, 3,

∪ {1, {1,

A B c, d} c, d}

= 1, 2, 3} = 1, 3}

∪ {2, {2,

B A c, d, c, d,

Osserviamo che =

∪ ∪

A B B A. Ma è vero in generale?

PROPOSIZIONE

Siano e due insiemi, allora = (vale la proprietà commutativa).

∪ ∪

A B A B B A

Come di consueto, dimostriamolo. 7

Antonio Wang - PEU-Z DIMOSTRAZIONE

Dobbiamo dimostrare che =

∪ ∪

A B B A.

Sappiamo che l’uguaglianza tra insiemi si dimostra dimostrando

i seguenti due punti:

• ∪ ⊆ ∪

A B B A

• ∪ ⊆ ∪

B A A B

Dimostriamo il primo punto.

Dobbiamo dimostrare quindi la seguente affermazione:

∈ ∪ → ∈ ∪

x A B x B A

A cosa equivale l’espressione a sinistra?

oppure

∈ ∪ → ∈ ∈

x A B x A x B

oppure

∈ ∪ → ∈ ∈

x A B x B x A

∈ ∪ → ∈ ∪

x A B x B A

Cosa abbiamo capito dunque? L’affermazione con possiamo

oppure

scriverla anche invertendo i due "membri" e senza farlo apposta

(facendolo apposta) abbiamo ottenuto proprio l’affermazione che ci serviva.

Facendo qualche passo indietro ciò che abbiamo dimostrato è semplicemente:

∪ ⊆ ∪

A B B A

Dimostriamo il secondo punto.

Il ragionamento è uguale alla dimostrazione del primo punto:

Dobbiamo dimostrare quindi la seguente affermazione:

∈ ∪ → ∈ ∪

x B A x A B

A cosa equivale l’espressione a sinistra?

oppure

∈ ∪ → ∈ ∈

x B A x B x A

oppure

∈ ∪ → ∈ ∈

x B A x A x B

∈ ∪ → ∈ ∪

x B A x A B

Facendo qualche passo indietro ciò che abbiamo dimostrato è semplicemente:

∪ ⊆ ∪

B A A B

Nel caso in cui abbiamo due insiemi generici e ad intuizione l’insieme e

A B, A

l’insieme saranno sicuramente sottoinsiemi dell’insieme Dimostriamolo.

∪

B A B.

8

Antonio Wang - PEU-Z Dobbiamo dimostrare che:

=⇒

∈ ∈ ∪

x A x A B

Se ipotizziamo che allora la seguente affermazione è vera:

∈

x A

=⇒ oppure

∈ ∈ ∈

x A x A x B

Questa scrittura è come abbiamo visto in precedenza la definizione di:

=⇒

∈ ∈ ∪

x A x A B

Di conseguenza possiamo dire che ⊆ ∪

A A B ∈

x B:

Ora dobbiamo dimostrare anche che questo valga per

=⇒

∈ ∈ ∪

x B x A B

Se ipotizziamo che allora la seguente affermazione è vera:

∈

x A

=⇒ oppure

∈ ∈ ∈

x B x A x B

Questa scrittura è come abbiamo visto in precedenza la definizione di:

=⇒

∈ ∈ ∪

x B x A B

Di conseguenza possiamo dire che ⊆ ∪

B A B

Facciamo qualche altro esempio per capire se ci sono altre proprietà

nell’operazione di unione tra insiemi. 9

Antonio Wang - PEU-Z ESEMPIO

= 2, 3,

{1,

A a, b}

= 3}

{1,

C

= 2, 3, =

∪ {1,

A C a, b} A

OSSERVAZIONE

Se uniamo e nel caso in cui sia un sottoinsieme di l’unione

A C C A,

dei due insiemi è uguale ad A.

PROPOSIZIONE

Siano e due insiemi, se allora =

⊆ ∪

A B B A A B A

DIMOSTRAZIONE

Cosa dobbiamo dimostrare dunque?

• ∪ ⊆

A B A

• ⊆ ∪

B A A

Dimostriamolo.

Partiamo dalla dimostrazione del primo punto:

∈ ∪ → ∈

x A B x A

Questo è quello che dobbiamo dimostrare, iniziamo:

=⇒ oppure

∈ ∪ ∈ ∈

x A B x A x B

Sappiamo però per ipotesi che dunque

⊆ ∈

B A, x B

è ridondante

=⇒

∈ ∪ ∈

x A B x A

Adesso facciamo la dimostrazione del secondo punto:

oppure

∈ → ∈ ∈

x B x A x B

Abbiamo fatto questa dimostrazione precedentemente,

nel momento in cui abbiamo dimostrato che e

⊆ ∪ ⊆ ∪

A A B B B A.

Ma adesso la domanda sorge spontanea: vale anche il ragionamento con-

Cioè l’affermazione = =⇒ è giusta? Ad intuizione sì,

∪ ⊆

A B A B A

trario?

ma dimostriamolo: 10

Antonio Wang - PEU-Z DIMOSTRAZIONE

Sappiamo per ipotesi che =

∪

A B A

Sappiamo inoltre perché l’abbiamo dimostrato in precedenza che

(A così come (A

⊆ ∪ ⊆ ∪

B B) A B)

Di conseguenza

=⇒

⊆ ∪ ⊆

B A B B A

Dato che abbiamo ripreso la nostra ipotesi che =

∪

A B A

Facciamo un altro esempio per dimostrare un’altra proprietà dell’operazione di

unione. PROPOSIZIONE

Siano e tre insiemi.

A, B C

IPOTESI

• ⊆

A C

• ⊆

B C

DIMOSTRAZIONE

Vogliamo dimostrare che:

Cosa vogliamo dimostrare?

(A ∪ ⊆

B) C

Dimostriamolo.

(A =⇒ oppure

∈ ∪ ∈ ∈

x B) x A x B

Per ipotesi però sappiamo che e sono sottoinsiemi di

A B C.

Quindi ciò che abbiamo scritto è la stessa cosa di scrivere:

(A =⇒ oppure

∈ ∪ ∈ ∈

x B) x C x C

Di conseguenza:

(A =⇒

∈ ∪ ∈

x B) x C

Ciò che abbiamo scritto equivale a dire

(A ∪ ⊆

B) C

Vogliamo visto dunque che questo ragionamento con i sottoinsiemi funziona,

perché l’abbiamo dimostrato. Ma possiamo dimostrare la stessa cosa con

i sottoinsiemi propri? 11

Antonio Wang - PEU-Z PROPOSIZIONE

Siano e tre insiemi.

A, B C

IPOTESI

• ⊂

A C

• ⊂

B C

CONTROESEMPIO

Quando facciamo un’affermazione, come detto nella prima lezione,

nel caso in cui volessimo confutarla serve un solo caso in cui essa

non funzioni. Per cui in questo caso faremo un controesempio:

= 2}

{1,

A = 4}

{3,

B

= 2, 3, 4}

{1,

C perché:

⊂

A C

• ⊆

A C

=

• ̸

A C

perché:

⊂

B C

• ⊆

B C

=

• ̸

B C

La nostra domanda iniziale era capire se ∪ ⊂

A B C.

=⇒ (A (A =

∪ ⊂ ∪ ⊆ ∧ ∪ ̸

A B C B C) B C)

Nel nostro caso cos’è ∪

A B?

= 2, 3, 4} =

∪ {1,

A B C

Per far sì che la nostra affermazione precedente sia falsa, basta

una sola proposizione che sia falsa.

Dunque la proposizione = è falsa e ciò dimostra che

∪ ̸

A B C

la nostra proposizione iniziale (A è falsa.

∪ ⊂

B C)

Un’altra proprietà degli insiemi è la Dimostriamolo:

proprietà associativa.

12

Antonio Wang - PEU-Z Siano e tre insiemi

A, B C

DIMOSTRAZIONE

Vogliamo dimostrare che:

Cosa vogliamo dimostrare?

(A = (B

∪ ∪ ∪ ∪

B) C A C)

L’uguaglianza la si dimostra se si soddisfano due requisiti:

(A (B

• ∪ ∪ ⊆ ∪ ∪

B) C A C)

(B (A

• ∪ ∪ ⊆ ∪ ∪

A C) B) C

Dimostriamo il primo punto.

Sia un elemento generico

x oppure

∈ ∪ → ∈ ∈

x A B x A x B

(A oppure oppure

∈ ∪ ∪ → ∈ ∈ ∈

x B) C x A x B x C

(B oppure

∈ ∪ ∪ → ∈ ∈ ∪

x A C) x A x B C

oppure oppure

→ ∈ ∈ ∈

x A x B x C

Per definizione ⊆ → ∀x ∈ ∈

A B A, x B

In questo caso:

(A (B

∀x ∈ ∪ ∪ ∈ ∪ ∪

B) C, x A C)

oppure oppure oppure oppure

∀x ∈ ∈ ∈ ∈ ∈ ∈

A x B x C, x A x B x C

Dunque abbiamo dimostrato il primo punto, cioè che (A (B

∪ ∪ ⊆ ∪ ∪

B) C A C)

Adesso dimostriamo il secondo punto.

Sia un elemento generico

x

(B oppure (B

∈ ∪ ∪ → ∈ ∈ ∪

x A C) x A x C)

oppure oppure

→ ∈ ∈ ∈

x A x B x C

(A (A oppure

∈ ∪ ∪ → ∈ ∪ ∈

x B) C x B) x C

oppure oppure

→ ∈ ∈ ∈

x A x B x C

Per definizione ⊆ → ∀x ∈ ∈

A B A, x B

In questo caso:

(B (A

∀x ∈ ∪ ∪ ∈ ∪ ∪

A C), x B) C

oppure oppure oppure oppure

∀x ∈ ∈ ∈ ∈ ∈ ∈

A x B x C, x A x B x C

Dunque abbiamo dimostrato il secondo punto, cioè che (A (A

∪ ∪ ⊆ ∪ ∪

B) C B) C

Avendo dimostrato entrambi i punti, dunque, abbiamo dimostrato che la proprietà

associativa funzion