Cenni di logica matematicae di teoria degli insiemi

CORSI INTRODUTTIVIDipartimento di Ingegneria di Perugia

a.a. 2016/2017Paola Rubbioni

1

Corsi Introduttivi - a.a. 2016/2017 2

1 Logica matematica

• Serve ad inquadrare in schemi rigorosi gli strumenti ed i metodi di ragionamento dellamatematica

• In matematica si definiscono gli oggetti, se ne definiscono le proprieta, si fannodeduzioni logiche

• Il complesso di espressioni delle quali si possa dire se sono Vere o False costi-tuisce un SISTEMA LOGICO

Atomo: oggetto del sistema logico; si indica con a, b, x, ...; possono essere numeri, frasi,...

Esempio: x = [popolazione di Roma]; a = [oggi piove]

Proposizione: frase di cui si possa dire se V oppure F

Esempi:

[11 e dispari] V ;

[13 e pari] F ;

[30 e divisibile per 2] V .

Predicato: proposizione contenente una variabile e che quindi puo essere V o F a seconda delvalore della variabile

Esempi:

p(x) = [x e un quadrato perfetto] V se x = 4, 9, 16, ... mentre e F se x = 2, 3, 5, ...;

p(x) = [x e un numero pari] e V se... mentre e F se ...

• Proposizioni e predicati si possono legare tra loro con i

CONNETTIVI LOGICI

¬: negazione

Esempio: P = [il numero 6 e primo];

¬P = [non e vero che il numero 6 e primo] = [il numero 6 non e primo]

∧: congiunzione (et)

Esempio: P = [oggi piove]; Q = [porto l’ombrello]

P ∧Q = [oggi piove e porto l’ombrello]

∨: disgiunzione (vel)

Esempio: P = [oggi piove]; Q = [porto l’ombrello]

P ∨Q = [oggi piove o porto l’ombrello]

TABELLE DI VERITA’

Corsi Introduttivi - a.a. 2016/2017 3

P ¬ P ¬ (¬ P )V F VF V F

;

P Q P ∧ Q P ∨ QV V V VF F F FV F F VF V F V

Esempio: P = [il numero 6 e primo] F ; Q = [il numero 5 e primo] VP ∧Q = [sia il numero 6 che il numero 5 sono primi] FP ∨Q = [o il numero 6 e primo o il numero 5 e primo] V

P Q ¬ (P ∧ Q) ¬ (P ∨ Q) ¬ P ∨ ¬ Q ¬ P ∧ ¬ QV V F F F FF F V V V VV F V F V FF V V F V F

dunque

Leggi di De Morgan

¬ (P ∧ Q) = ¬ P ∨ ¬ Q

¬ (P ∨ Q) = ¬ P ∧ ¬ Q

Esempio: ¬ (P ∧ Q) = [non e vero che 6 e 5 sono entrambi primi]¬ P ∨ ¬ Q = [non e vero che il numero 6 e primo oppure non e vero che il numero 5 e

primo]

IMPLICAZIONE ED EQUIVALENZA

⇒: implica

A⇒ B si legge:

[se A e vera, allora B e vera]

[A e condizione sufficiente per B]

[B e condizione necessaria per A]

⇔: equivale

A⇔ B si legge:

[A e B sono equivalenti]

[A e condizione necessaria e sufficiente per B (e viceversa)]

(A⇒ B) ∧ (B ⇒ A)

• Formulazione astratta-logica degli enunciati dei teoremi

Corsi Introduttivi - a.a. 2016/2017 4

Teorema: CN perche un parallelogramma sia un quadrato e che abbia le diagonali uguali

= [P e un quadrato ⇒ P ha le diagonali uguali]= [se un parallelogramma e un quadrato︸ ︷︷ ︸

ipotesi

, allora ha le diagonali uguali︸ ︷︷ ︸tesi

]

= [CS perche un parallelogramma abbia le diagonali uguali e che sia un quadrato]

La CN non e anche CS, ovvero [P ha le diagonali uguali 6⇒ P e un quadrato]; controes:rettangolo

Teorema: CS perche un numero sia pari e che sia divisibile per 2

= [x e divisibile per 2 ⇒ x e pari]= [se x e divisibile per 2︸ ︷︷ ︸

ipotesi

allora x e pari︸ ︷︷ ︸tesi

]

In questo caso e vero anche il viceversa, cioe la CS e anche necessaria, quindi le due proposizionisono equivalenti, ovvero[x e divisibile per 2 ⇔ x e pari]

Osservazione: [A⇒ B] equivale a [¬B ⇒ ¬A]

Esempio: A = [n e divisibile per 9]; B = [n e divisibile per 3]A⇒ B = [se n e divisibile per 9, allora n e divisibile per 3]¬B ⇒ ¬A = [se n non e divisibile per 3, allora n non e divisibile per 9]

Att.!! situazione diversa da B 6⇒ A = [che n sia divisibile per 3 non implica che n sia divisibileper 9]; questa infatti nel caso in questione e falsa: controes: n = 6 e divisibile per 3 ma nonper 9.

Esempio: A = [x > 9]; B = [x > 5]

A⇒ B significa [se x > 9 allora x > 5]; o equivalentemente [CS perche x > 5 e che x > 9]; oequivalentemente [CN perche x > 9 e che x > 5];

per l’osservazione precedente questo equivale a

¬B ⇒ ¬A, che significa [se non e x > 5 allora non e x > 9].

Anche qui si ha che non e vero che

B 6⇒ A, il quale significa [x > 5 non implica x > 9]; controes: x = 7

QUANTIFICATORI esistenziale ed universale

∃: esiste

∀: per ogni

NEGARE I PREDICATI

∀x⇒ P (x) = [per ogni valore della variabile accade che la proprieta P (x) e vera]

∃x : Q(x) = [esiste almeno un valore della variabile per cui la proprieta Q(x) e vera]

Corsi Introduttivi - a.a. 2016/2017 5

Vediamo come si nega.

Esempio: [Non e vero che ogni studente ha una penna] = [almeno uno studente non ha unapenna]dunque

[¬ (∀x⇒ P (x))] equivale a [∃x : ¬P (x)]

In generale:

∀ ←→ ∃ ; ⇒←→ : ; poi si nega la proprieta

Esempio: un insieme C e convesso se∀A,B in C ⇒ AB contenuto in C;

un insieme C non e convesso se∃A,B in C : AB non e contenuto in C

Esempi:

1. Negare che [ogni studente e biondo e con gli occhi azzurri].

In simboli, devo negare che [∀x⇒ P (x) ∧Q(x)], quindi la negazione e

[∃x : ¬(P (x) ∧ Q(x))] ⇔︸︷︷︸DeMorgan

[∃x : ¬P (x) ∨ ¬Q(x)], quindi [c’e almeno uno studente

che o non e biondo o non ha gli occhi azzurri].

2. Negare la frase [∀x ∈ R∃y ∈ R : xy = 1].

[∃x ∈ R : ¬(∃y ∈ R : xy = 1)] ⇔ [∃x ∈ R : ∀y ∈ R ⇒ xy 6= 1)].

3. Negare la frase [La mamma cucina e parla al telefono].

frase: [C ∨ T ]; negata (per De Morgan) e [¬C ∧ ¬T ] ovvero [la mamma o non cucina onon parla al telefono].

4. Negare la frase [Tutte le sere leggo a letto].

frase: [∀S ⇒ L]; negata e [∃S : ¬L], ovvero [c’e almeno una sera in cui non leggo a letto].

Corsi Introduttivi - a.a. 2016/2017 6

2 Numeri

• N numeri naturali: 0, 1, 2, 3, 4, ....

(N,+)

(G1) elemento neutro: 0

(G2) proprieta associativa: (n + m) + p = n + (m + p)

(C) proprieta commutativa: n + m = m + n

Ma NON esiste in N l’opposto, cioe l’elemento che sommato ad un numero forniscal’elemento neutro.

• (Z,+) numeri interi

(G1) elemento neutro: 0

(G2) proprieta associativa: (n + m) + p = n + (m + p)

(G3) opposto: ∀n∃m : n + m = 0; l’elemento opposto di n si indica con il simbolo −n;

(C) proprieta commutativa: n + m = m + n.

(Z,+) e un gruppo abeliano o commutativo

• (Z,+, ·)

(G1) elemento neutro: 1

(G2) proprieta associativa: (n ·m) · p = n · (m · p)

(C) proprieta commutativa: n ·m = m · n(D) proprieta distributiva: n · (m + p) = n ·m + n · p.

Ma NON esiste in N l’inverso, cioe l’elemento che moltiplicato per un numero interofornisca l’elemento neutro.

• (Q,+, ·) numeri razionali

(G1) elemento neutro: 1

(G2) proprieta associativa: (n ·m) · p = n · (m · p)

(G3) opposto: ∀p 6= 0∃q : p · q = 1; l’elemento opposto di p si indica con il simbolo 1p;

(C) proprieta commutativa: n ·m = m · n(D) proprieta distributiva: n · (m + p) = n ·m + n · p.

Q escluso 0 e un gruppo rispetto al prodotto.

• (R,+, ·) numeri reali

(G1) elemento neutro: 1

(G2) proprieta associativa: (n ·m) · p = n · (m · p)

(G3) opposto: ∀p 6= 0∃q : p · q = 1; l’elemento opposto di p si indica con il simbolo 1p;

Corsi Introduttivi - a.a. 2016/2017 7

(C) proprieta commutativa: n ·m = m · n(D) proprieta distributiva: n · (m + p) = n ·m + n · p.

I numeri reali nascono per risolvere problemi di incommensurabilita (lato e diagonale delquadrato) o di esaustione (lnghezza della circonferenza).

Osserviamo che:

• q ∈ Q si puo scrivere in infiniti modi:

0, 75 =75

100=

3

4= ...(decimale esatto)

0, 6 =6

9=

60

90=

2

3=

4

6=−2

−3= ...(decimale periodico)

• costruisco la frazione di un decimale periodico:

x = 0, 6 = 0, 666666....⇒10x = 6, 66666... = 6 + 0, 66666... = 6 + x⇒

9x = 6⇒ x =6

9;

• costruisco la frazione di un decimale periodico:

x = 0, 12 = 0, 12121212...⇒102x = 12, 121212... =

= 12 + 0, 121212.... =

= 12 + 0, 12 = 12 + x⇒x(102 − 1) = 12⇒

x =12

99;

• costruisco un numero irrazionale, cioe di R \Q:

0, 101100111000111100001111100000...

In R sussiste una relazione d’ordine totale ’≤’, cioe valgono le seguenti proprieta:

riflessiva: ∀x ∈ R⇒ x ≤ x

antisimmetrica: ∀x, y ∈ R : x ≤ y ∧ y ≤ x⇒ x = y

transitiva: ∀x, y, z ∈ R : x ≤ y ∧ y ≤ z ⇒ x ≤ z

tricotomia (?): ∀x, y ∈ R⇒ x ≤ y ∨ y ≤ x

Corsi Introduttivi - a.a. 2016/2017 8

3 Teoria degli insiemi

Parole chiave: insieme (A); elemento (a); appartenenza (∈)

Descrizione per tabulazione: A = {1, 2, 5} (ordine irrilevante)

Descrizione per proprieta: A = {studenti aventi nome con iniziale A}

Insiemi numerici

N={0, 1, 2, ...}

Z={...,−2,−1, 0, 1, 2, ...}

Q={

ab

: a, b ∈ Z, b 6= 0}

R={tutti i decimali periodici e non periodici, limitati e non limitati}

Possiamo allora dare la definizione di intervallo: dati a, b ∈ R, si pone

[a, b] = {x ∈ R : a ≤ x ≤ b}

e analogamente

[a, b[= {x ∈ R : a ≤ x < b}; ]a, b] = {x ∈ R : a < x ≤ b}; ]a, b[= {x ∈ R : a < x < b}.

RELAZIONI TRA INSIEMI

A ⊂ B = A e contenuto in B; A e sottoinsieme di B; vuol dire che ∀x ∈ A⇒ x ∈ B , cioeogni elemento di A e anche elemento di B

Esempio: A = {1, 2} ⊂ B = {1, 2, 7}

Esempio: A = {studenti aventi nome con iniziale A} ⊂ B = {studenti}Esempio: N ⊂ Z ⊂ Q ⊂ R.

A 6⊂ B = A non e contenuto in B; A non e sottoinsieme di B; vuol dire che ∃x ∈ A : x 6∈ B ,cioe esiste almeno un elemento di A che non appartiene a B

Esempio: A = {studenti oggi in aula}; B = {studenti domani in aula}

Corsi Introduttivi - a.a. 2016/2017 9

Esempio: A = {studenti oggi in aula}; B = {studenti oggi a medicina}

A = B = A ⊂ B ∧B ⊂ A; vuol dire che (∀x ∈ A⇒ x ∈ B) ∧ (∀x ∈ B ⇒ x ∈ A)

Esempio: A = {persone presenti in aula} ⊂ B = {persone entrate in aula e non ancora uscite}

A 6= B = A 6⊂ B ∨B 6⊂ A

Osservazione 3.1 Non scambiare ∈ con ⊂! La prima e relazione tra elementi, la seconda trainsiemi: sono livelli diversi della realta.

Osservazione 3.2 Un insieme puo essere un elemento in un insieme di insiemi.Esempio: (0, 0) ∈ r = {(x, y) ∈ R2 : y = x} ∈ F = {y = mx : m ∈ R}.

Insiemi degeneri

∅ = insieme vuoto

P(A) = insieme delle parti

Esempio: A = {1, 2, 3}P(A) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, A}

OPERAZIONI tra insiemi in X insieme universo

A ∩B = {x ∈ X : x ∈ A ∧ x ∈ B} intersezione

Corsi Introduttivi - a.a. 2016/2017 10

• A ∩B ⊂ A e A ∩B ⊂ B

• A ⊂ B ⇒ A ∩B = A

• due insiemi sono disgiunti se A ∩B = ∅

A ∪B = {x ∈ X : x ∈ A ∨ x ∈ B} unione

• A ⊂ A ∪B e B ⊂ A ∪B

• A ⊂ B ⇒ A ∪B = B

AC = {x ∈ X : ¬(x ∈ A)} = {x ∈ X : x 6∈ A} complementare

A \B = {x ∈ X : x ∈ A ∧ x 6∈ B} = {x ∈ X : x ∈ A} ∩ {x ∈ X : x 6∈ B} = A ∩BC

differenza

Corsi Introduttivi - a.a. 2016/2017 11

A×B = {(x, y) ∈ X ×X : x ∈ A, x ∈ B} prodotto cartesiano

• le coppie sono ordinate: A×B 6= B × A

Esempio: A = {1, 2}, B = {2, 3}⇒ A×B = {(1, 2), (1, 3), (2, 2), (2, 3)}, B × A = {(2, 1), (2, 2), (3, 1), (3, 2)}• PIANO CARTESIANO

• [0, 1]× [−1, 1]

[0, 1]×]− 1, 1[

]0, 1]× [−1, 1]

...

Proprieta Leggi di De Morgan

(A ∪B)C = AC ∩BC (A ∩B)C = AC ∪BC

Corsi Introduttivi - a.a. 2016/2017 12

Proviamo la prima. Dobbiamo dimostrare la doppia inclusione.

’⊂’: Ip: x ∈ (A ∪B)C ; Ts: x ∈ AC ∩BC

x ∈ (A ∪B)C ⇒ x 6∈ A ∪B ⇒ ¬(x ∈ A ∪B)⇒⇒ ¬(x ∈ A ∨ x ∈ B) ⇒︸︷︷︸

DeMorgan

¬(x ∈ A) ∧ ¬(x ∈ B)⇒ x 6∈ A ∧ x 6∈ B ⇒

⇒ x ∈ AC ∧ x ∈ BC ⇒ x ∈ AC ∩BC

’⊃’: Ip: x ∈ AC ∩BC ; Ts: x ∈ (A ∪B)C

x ∈ AC ∩BC ⇒ x 6∈ A ∧ x 6∈ B ⇒ ¬(x ∈ A) ∧ ¬(x ∈ B) ⇒︸︷︷︸DeMorgan

⇒ ¬(x ∈ A ∨ x ∈ B)⇒ ¬(x ∈ A ∪B)⇒ x 6∈ A ∪B ⇒⇒ x ∈ (A ∪B)C

Proprieta dell’intersezione

• A ∩B = B ∩ A commutativa

• A ∩ (B ∩ C) = (A ∩B) ∩ C associativa

• A ∩ A = A idempotenza

Proprieta dell’unione

• A ∪B = B ∪ A commutativa

• A ∪ (B ∪ C) = (A ∪B) ∪ C associativa

• A ∪ A = A idempotenza

Esercizio 3.1 Provare la proprieta distributiva dell’intersezione sull’unione, cioe che

A ∩ (B ∪ C) = (A ∩B) ∪ (A ∩ C).

Svolgimento:

x ∈ A ∩ (B ∪ C) ⇔ x ∈ A ∧ (x ∈ B ∨ x ∈ C)⇔ (x ∈ A ∧ x ∈ B) ∨ (x ∈ A ∧ x ∈ C)⇔⇔ x ∈ (A ∩B) ∨ x ∈ (A ∩ C)⇔ x ∈ (A ∩B) ∪ (A ∩ C)

Corsi Introduttivi - a.a. 2016/2017 13

Esercizi 3.1

1. Provare la proprieta distributiva dell’unione sull’intersezione, cioe che A ∪ (B ∩ C) =(A ∪B) ∩ (A ∪ C)

2. Provare che A ∪ (A ∩B) = A

3. Provare che AC ∪ (A ∩B) = AC ∪B

4. Provare che A ∪B = A ∪ (B \ A)

5. Provare che A \ (B ∪ C) = (A \B) ∩ (A \ C)