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)