Insiemi e logica

Argomento di Analisi Matematica 1, nozioni preliminari, sezione 1.1. Fatto a lezione il 14/9, slide 11-22: slide annotate del 14/9. Vocabolario: Linguaggio matematico. Si continua con Numeri reali, sup e inf.

1Definizioni

Insieme. Si può dare come elenco ($A := \{a, c, b, e, f, d\}$) oppure con una proprietà caratteristica ($D := \{2k+1 : k = 0, 1, 2, \dots\}$). L’ordine degli elementi non conta. Il simbolo $:=$ significa “è definito come”, e non è lo stesso di $=$ (il prof lo cerchia a lezione: “definizione”).

Appartenenza. $a \in A$ se $a$ è un elemento di $A$, $a \notin A$ altrimenti. Esempio delle slide: $\frac{2}{3} \notin D$, perché $D$ contiene solo interi dispari.

Operazioni fra insiemi. Dati $A$ e $B$:

L‘“o” dell’unione non è disgiuntivo: il prof lo annota come “almeno una delle due opzioni”, e vale anche se valgono entrambe. Nella differenza il secondo pezzo è $x \notin B$, non $x \in B$, e $B \setminus A = \{x : x \in B \text{ e } x \notin A\}$ è un insieme diverso da $A \setminus B$. Il simbolo $:$ dentro le graffe si legge “tale che”.

Esempio: $A = \{1, 2, 3\}$, $B = \{3, 4\}$. Allora $A \cup B = \{1, 2, 3, 4\}$, $A \cap B = \{3\}$, $A \setminus B = \{1, 2\}$, $B \setminus A = \{4\}$.

Insieme vuoto. $\emptyset$, l’insieme senza elementi. Serve perché intersezione e differenza restino sempre definite, anche quando non resta niente. Sulla slide c’è scritto a mano “pallina sbarrata, non è il numero zero!!!”.

Sottoinsieme. Parole del prof (slide 14): $A$ è un sottoinsieme di $B$ (o $A$ è contenuto in $B$) se ogni elemento di $A$ è anche elemento di $B$, e si scrive $A \subseteq B$ (oppure $A \subset B$). In simboli, come annotato sulla slide:

Il simbolo di inclusione non esclude l’uguaglianza $A = B$, che equivale alla validità di entrambe le inclusioni $A \subseteq B$ e $B \subseteq A$.

Inclusione stretta. $A \subsetneq B$ indica l’inclusione stretta, cioè $A \subseteq B$ e $A \neq B$. La forma scritta a mano dal prof dice cosa controllare in pratica:

La prima parentesi è l’inclusione, la seconda dice che in $B$ c’è almeno un elemento in più.

Non sottoinsieme. $A \not\subseteq B$ è la negazione di $A \subseteq B$: esiste un elemento di $A$ che non sta in $B$. Il prof annota: da non confondere con $A \subsetneq B$. Sono quasi opposti: $A \subsetneq B$ dice che $A$ sta dentro $B$ (ed è più piccolo), $A \not\subseteq B$ dice che $A$ esce da $B$. Da non confondere nemmeno con $\notin$, che lega un elemento a un insieme: $4 \in A$ e $\{4\} \subseteq A$ sono corretti, $4 \subseteq A$ è scritto male.

Proposizione. Una frase che è vera (V) o falsa (F), senza terze possibilità. Esempio delle slide: $P =$ “3 è un numero pari” è falsa, $Q =$ “28 è divisibile per 4” è vera. Allora ”$P$ e $Q$” è falsa (serve che valgano tutte e due), ”$P$ o $Q$” è vera (ne basta una), “non $P$” è vera.

Predicato. Una proposizione che contiene una variabile, quindi il suo valore di verità dipende dalla variabile: $P(x) =$ ”$x$ è un numero pari”. Da solo non è né vero né falso.

Connettivi logici. e, o, non (sulla slide del 22 compare anche il simbolo $\neg$ per il non), più l’implicazione $\Rightarrow$ (“se $P$ allora $Q$”, oppure ”$P$ implica $Q$”) e la doppia implicazione $\Leftrightarrow$ (”$P$ se e solo se $Q$”, oppure ”$P$ è equivalente a $Q$”).

Quantificatori. $\exists$ (quantificatore esistenziale, “esiste”) e $\forall$ (quantificatore universale, “per ogni”). Specificano la validità di un predicato in relazione a un insieme:

Punteggiatura del corso: virgola dopo il $\forall$, due punti dopo l’$\exists$ (si leggono “tale che”).

Con quantificatori, variabili e insiemi si traducono frasi intere. Con $S$ = studenti di Ingegneria ed $E$ = esami, “ogni studente ha superato almeno un esame” diventa

L’ordine conta: $\exists\, \varepsilon \in E : \forall s \in S, \dots$ direbbe che c’è un esame superato da tutti, che è un’altra frase.

2Enunciati

2.1Tavola di verità dell’implicazione

$P \Rightarrow Q$ è falsa in un solo caso: premessa vera e conclusione falsa. In $P \Rightarrow Q$ la $P$ si chiama premessa, ipotesi o condizione sufficiente; la $Q$ conclusione, tesi o condizione necessaria. $P \Leftrightarrow Q$ equivale a ”$(P \Rightarrow Q)$ e $(Q \Rightarrow P)$”, e si usa per dire che due proposizioni sono equivalenti.

Esempio del prof (14/9, pagina dopo la slide 16). $P$ = “oggi c’è il sole”, $Q$ = “oggi vado al parco”. L’implicazione $P \Rightarrow Q$ è la promessa “se c’è il sole vado al parco”.

Le ultime due righe non tradiscono la promessa, che parlava solo delle giornate di sole: per questo l’implicazione resta vera.

Perché con premessa falsa l’implicazione è vera. Lo stesso con un predicato: “se $x$ è uno chef allora $x$ sa preparare una torta”. Se $x$ è il professore, che chef non è, la regola non viene violata qualunque cosa sappia cucinare. Un’implicazione è falsa solo quando qualcuno la smentisce davvero: uno chef che non sa fare una torta.

2.2Negazione dell’implicazione

L’unico modo in cui $P \Rightarrow Q$ è falsa è $P$ vera e $Q$ falsa, quindi

La negazione di un “se… allora” non è un altro “se… allora”: è un “e”.

2.3Leggi di De Morgan

Negando, l‘“e” diventa “o” e viceversa, e ogni pezzo viene negato. Le tavole di verità che le dimostrano il prof le lascia da completare per esercizio: sono svolte in Esercizi tipo esame.

2.4Forma contronominale

È il fatto che giustifica il ragionamento per assurdo. Esempio delle slide: “se $x$ è uno chef allora $x$ sa preparare una torta” equivale a “se $x$ non sa preparare una torta, allora $x$ non è uno chef”. Attenzione: equivale alla contronominale, non all’inversa $Q \Rightarrow P$, che è un’altra cosa e in generale è falsa. Anche questa tavola è rimasta da completare, ed è in Esercizi tipo esame.

2.5Negazione dei quantificatori

Il prof le disegna con due frecce: il quantificatore si scambia, e il “non” scivola dentro sul predicato. La seconda si scrive anche $\nexists\, x \in A : P(x)$.

Esempi delle slide: la negazione di “ogni studente ha superato l’esame di analisi” è “esiste almeno uno studente che non ha superato l’esame di analisi”; la negazione di “esiste un numero primo di 4 cifre decimali” è “ogni numero primo non è di 4 cifre decimali”.

3Metodo

Verificare se due proposizioni composte sono equivalenti. Si costruisce la tavola di verità di entrambe e si confrontano le colonne finali: equivalenti se coincidono riga per riga, diverse se c’è anche una sola riga che differisce. Con $n$ proposizioni elementari la tavola ha $2^n$ righe, quindi con tre lettere sono otto righe. Conviene incolonnare prima i pezzi intermedi (le negazioni singole) e poi comporre.

Negare una proposizione con quantificatori.

1. Se la frase è in italiano, scrivila prima in simboli: individua insieme, variabile, predicato.
2. Scorri da sinistra a destra: ogni $\forall$ diventa $\exists$, ogni $\exists$ diventa $\forall$. L’ordine dei quantificatori non si tocca.
3. Alla fine nega il predicato: $\leq$ diventa $>$, $=$ diventa $\neq$, “e” diventa “o”, $P \Rightarrow Q$ diventa ”$P$ e non $Q$”.
4. Ritraduci in italiano e rileggi: la negazione deve essere vera esattamente quando l’originale è falsa.

Dimostrare che due insiemi sono uguali. Si prova la doppia inclusione, cioè $A \subseteq B$ e $B \subseteq A$. Ognuna si prova prendendo un elemento generico del primo insieme e mostrando che sta nel secondo.

Dire se un’affermazione su insiemi è vera. Prima si controlla che sia scritta bene: a sinistra di $\in$ ci va un elemento, a sinistra di $\subseteq$ un insieme. Una scrittura scorretta conta come falsa.

4Esempi svolti a lezione

4.1Due proposizioni equivalenti? (14/9, pagine dopo la slide 16)

Mostrare che

Tre lettere, quindi $2^3 = 8$ righe. Si calcolano prima i pezzi e poi le implicazioni (è la tavola del prof, pagine 15-16).

Conclusione del prof: siccome le tavole di verità delle due proposizioni sono diverse, le due proposizioni non sono equivalenti. Il motivo di fondo: $Q$ ha negato ipotesi e tesi di $P$ senza scambiarle, cioè è l’inversa di $P$ scritta con De Morgan, non la contronominale. La contronominale giusta sarebbe $\text{non } C \Rightarrow (\text{non } A \text{ o non } B)$.

4.2Negare con il “ma” (slide 18)

Negare “la matematica è inutile ma una laurea in ingegneria vale molto”. Il prof corregge a mano il “ma” in “e”: logicamente è una congiunzione. Per la I legge di De Morgan la negazione è “la matematica è utile o una laurea in ingegneria non vale granché”, risposta c) della slide. La a) sbaglia perché tiene l‘“e”.

4.3Quiz 1 (slide 22)

La negazione di “ogni mela contiene almeno 4 semi” è: a) nessuna mela contiene almeno 4 semi; b) esiste una mela con almeno 4 semi; c) ogni mela contiene al massimo 3 semi; d) esiste una mela con meno di 4 semi.

Il prof scrive $A$ = {mele} e $P(x)$ = ”$x$ ha almeno 4 semi”. La frase è $\forall x \in A, P(x)$, e la negazione è $\exists x \in A : \text{non } P(x)$, cioè “esiste una mela con meno di 4 semi”. Risposta d. La a) sbaglia il quantificatore, la c) nega il predicato ma lascia il $\forall$.

4.4Quiz 2 (slide 22)

La negazione di $\exists\, a \in A : \forall b \in B,\ a \neq b$ è: a) $B \subseteq A$; b) $\forall a \in A\ \exists\, b \in B : a = b$; c) $\forall a \in A, \forall b \in B,\ a = b$; d) $\exists\, a \in A, \exists\, b \in B : a = b$.

Svolgimento del prof (pagina 26): si chiama $P(a)$ il pezzo "$\forall b \in B, a \neq b$". La frase è $\exists a \in A : P(a)$, la negazione è $\forall a \in A, \text{non } P(a)$, e $\text{non } P(a)$ è $\exists b \in B : a = b$. In conclusione la negazione è

risposta b. A parole: ogni elemento di $A$ coincide con qualche elemento di $B$, cioè $A \subseteq B$. La frase di partenza diceva quindi ”$A$ non è sottoinsieme di $B$”, $A \not\subseteq B$. La a) scrive l’inclusione al contrario.

5Esercizi tipo esame

5.1Crocette (stile parte 1)

C1 (quiz 3 della slide 22, lasciato a casa). Supponendo vera l’implicazione “se piove allora si deve prendere l’ombrello”, cosa deduce un matematico? a) se non piove, allora non si deve prendere l’ombrello b) se non si deve prendere l’ombrello vuol dire che non piove c) se si prende l’ombrello significa che piove d) niente, è troppo perso nel mondo dei numeri

C2 (quiz 4 della slide 22, lasciato a casa). La negazione logica dell’implicazione “se c’è il sole allora faccio una passeggiata” è: a) se c’è il sole allora non faccio una passeggiata b) c’è il sole e non faccio una passeggiata c) se non c’è il sole non faccio una passeggiata d) se non faccio una passeggiata allora non c’è il sole

C3. La negazione di $\forall x \in A,\ \exists y \in B : x < y$ è: a) $\exists x \in A : \forall y \in B,\ x \geq y$ b) $\forall x \in A,\ \exists y \in B : x \geq y$ c) $\exists x \in A,\ \exists y \in B : x \geq y$ d) $\forall x \in A,\ \forall y \in B,\ x \geq y$

C4 (dal foglio 0 e dagli esercizi svolti di Pinamonti). Siano $A = [-2, 5)$ e $C = \{-1, 2\}$. Quale affermazione è falsa? a) $\{-1\} \subseteq C$ b) $A \cap C = C$ c) $4 \subseteq A$ d) $(-2, 5) \subseteq A$

5.2Esercizi (stile parte 2)

Esercizio 1 (tavole di De Morgan, “da completare per esercizio”, 14/9 pagine 18-19). Verificare con le tavole di verità le due leggi di De Morgan.

Esercizio 2 (tavola della contronominale, “completare”, 14/9 pagina 21). Verificare che $P \Rightarrow Q$ e $\text{non } Q \Rightarrow \text{non } P$ sono equivalenti.

Esercizio 3 (foglio 0, es. 1). Siano $A$ e $B$ proposizioni. Provare che $\big[\text{non } B \text{ e } (A \Rightarrow B)\big] \Rightarrow \text{non } A$ è una tautologia, cioè è vera in tutte le righe della tavola (è il modus tollens).

Esercizio 4 (foglio 0, es. 4). Dire quali proposizioni sono vere e quali false, motivando (per esempio mostrando che la negazione è vera): a) $\forall x \in \mathbb{Z},\ \exists y \in \mathbb{N} : x - y \leq 0$ b) $\forall x \in \mathbb{N},\ \exists y \in \mathbb{Z} : 2x - 4y = 0$ c) $\forall x, y \in \mathbb{R},\ \big[(x \neq y) \Rightarrow (x^2 \neq y^2)\big]$ d) $\exists x \in \mathbb{Q} : \forall y \in \mathbb{R},\ (2x + 1)y = 0$

Esercizio 5 (foglio 0, es. 3; svolto negli esercizi di Pinamonti). Sia $P(x, y)$ = “la rivista scientifica $y$ si trova nella biblioteca del dipartimento $x$ dell’Università di Trento”. Tradurre in italiano corrente $\exists y : \forall x, P(x, y)$ e $\forall x, \exists y : P(x, y)$, e dire se sono equivalenti.

Esercizio 6 (esercizi di Pinamonti, es. 3). Sia $A \subseteq \mathbb{R}$. Dire se sono vere qualunque sia $A$, e scriverne la negazione: a) $\exists y \in \mathbb{R} : \forall x \in A,\ x \leq y$ b) $\forall x \in A,\ \exists y \in A : x < y$

6Errori tipici

• Negare un “se… allora” con un altro “se… allora”. La negazione di $P \Rightarrow Q$ è ”$P$ e non $Q$” (quiz 4).
• Confondere contronominale e inversa. $P \Rightarrow Q$ equivale a non $Q \Rightarrow$ non $P$, non a $Q \Rightarrow P$ né a non $P \Rightarrow$ non $Q$. L’esercizio del 14/9 con $A$, $B$, $C$ è esattamente questa trappola.
• Negare il predicato e dimenticare il quantificatore, o viceversa: “ogni mela ha al massimo 3 semi” non è la negazione di “ogni mela ha almeno 4 semi”.
• Scambiare l’ordine dei quantificatori quando si nega: l’ordine resta quello, cambiano solo i simboli.
• Leggere $\subset$ come inclusione stretta. Nel corso $\subset$ è $\subseteq$; la stretta è $\subsetneq$.
• Confondere $\not\subseteq$ con $\subsetneq$, o $\in$ con $\subseteq$ ($4 \subseteq A$ è scritto male).
• Pensare che l‘“o” sia esclusivo. ”$P$ o $Q$” è vera anche quando valgono entrambe.

7Domande

• Qual è la differenza fra $A \setminus B$ e $B \setminus A$?

• In quale unico caso $P \Rightarrow Q$ è falsa?

• Enuncia le due leggi di De Morgan.

• Qual è la contronominale di “se $x$ è uno chef allora $x$ sa preparare una torta”? E l’inversa? Quale delle due equivale all’originale?

• Come si nega $\forall x \in A, \exists y \in B : P(x,y)$?

• Perché serve introdurre l’insieme vuoto?

• Una proposizione e un predicato: qual è la differenza?

• Come si nega un’implicazione $P \Rightarrow Q$?

• Perché $P \Rightarrow Q$ è vera quando $P$ è falsa? Spiegalo con l’esempio dello chef.

• Quante righe ha la tavola di verità di una proposizione con 3 lettere, e perché?

• Scrivi in simboli, nella forma del prof, che $A \subsetneq B$.

• Nel corso, cosa significa $A \subset B$? E che differenza c’è fra $A \not\subseteq B$ e $A \subsetneq B$?