Note Ingegneria Informatica · UniTN
Analisi Matematica 1
Esercizi
Lezione
14 set
in corso

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 (insiemi da pagina 8, proposizioni da pagina 12, quantificatori da pagina 22, quiz da pagina 25). Esercizi: foglio 0 e esercizi svolti di logica (Pinamonti, a.a. 2021/22). Vocabolario: Linguaggio matematico. Si continua con Numeri reali, sup e inf.

Il filo dell’argomento:

insiemi           elenco o proprietà; ∪ ∩ \ ; sottoinsieme ⊆
   |
   v
proposizioni      V o F; connettivi e, o, non, ⇒, ⇔; tavole di verità
   |
   v
regole            De Morgan: non(P e Q) = non P o non Q
   |              non(P ⇒ Q) = P e non Q
   |              P ⇒ Q equivale a non Q ⇒ non P   (contronominale)
   v
quantificatori    ∀ ed ∃; negare = scambiare ∀ ↔ ∃ e negare il predicato in fondo

1Definizioni

1.1Insiemi

Insieme. Si può dare come elenco (A:={a,c,b,e,f,d}A := \{a, c, b, e, f, d\}) oppure con una proprietà caratteristica (D:={2k+1:k=0,1,2,… }D := \{2k+1 : k = 0, 1, 2, \dots\}), slide 12 (pagina 8). Il prof annota: “l’ordine non conta”, quindi {1,2,3}={3,1,2}\{1, 2, 3\} = \{3, 1, 2\}. Il simbolo :=:= significa “è definito come”, e non è lo stesso di == (il prof lo cerchia: “definizione”). Il :: dentro le graffe si legge “tale che”.

Esempi:

Appartenenza. a∈Aa \in A se aa è un elemento di AA, a∉Aa \notin A altrimenti. Esempio delle slide: 23∉D\frac{2}{3} \notin D, perché DD contiene solo interi dispari. A sinistra di ∈\in c’è sempre un elemento, a destra un insieme.

Operazioni fra insiemi (slide 13, pagina 9). L’idea: l’unione mette insieme tutto, l’intersezione tiene solo il comune, la differenza toglie da AA quello che sta in BB. Dati AA e BB:

A∪B:={x:x∈A o x∈B}A \cup B := \{x : x \in A \text{ o } x \in B\} A∩B:={x:x∈A e x∈B}A \cap B := \{x : x \in A \text{ e } x \in B\} A∖B:={x:x∈A e x∉B}A \setminus B := \{x : x \in A \text{ e } x \notin B\}

L‘“o” dell’unione non è esclusivo: il prof lo annota come “almeno una delle due opzioni”, e vale anche se valgono entrambe. Nella differenza il secondo pezzo è x∉Bx \notin B, e B∖A={x:x∈B e x∉A}B \setminus A = \{x : x \in B \text{ e } x \notin A\} è un insieme diverso da A∖BA \setminus B.

Esempi, dal più facile:

Il secondo esempio mostra dove si sbaglia: agli estremi. Per ogni estremo ci si chiede “sta in AA? sta in BB?” e si applica la definizione.

Insieme vuoto. ∅\emptyset, l’insieme senza elementi. Serve perché intersezione e differenza restino sempre definite, anche quando non resta niente: {1,2}∩{3}=∅\{1, 2\} \cap \{3\} = \emptyset, {1}∖{1,2}=∅\{1\} \setminus \{1, 2\} = \emptyset. Sulla slide c’è scritto a mano “pallina sbarrata, non è il numero zero!!!”: {0}\{0\} ha un elemento, ∅\emptyset nessuno.

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

A⊆B  ⟺  ∀a∈A⇒a∈BA \subseteq B \iff \forall a \in A \Rightarrow a \in B

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

Esempi e controesempio:

Inclusione stretta (pagina 11). A⊊BA \subsetneq B indica l’inclusione stretta, cioè A⊆BA \subseteq B e A≠BA \neq B. La forma scritta a mano dal prof dice cosa controllare in pratica:

A⊊B  ⟺  (∀a∈A⇒a∈B)  e  (∃ b∈B:b∉A)A \subsetneq B \iff (\forall a \in A \Rightarrow a \in B) \ \text{ e } \ (\exists\, b \in B : b \notin A)

La prima parentesi è l’inclusione, la seconda dice che in BB c’è almeno un elemento in più. Esempio: {1,3}⊊{1,2,3}\{1, 3\} \subsetneq \{1, 2, 3\} (l’elemento in più è 22). Controesempio: {1,2,3}⊆{3,2,1}\{1, 2, 3\} \subseteq \{3, 2, 1\} ma non strettamente, perché i due insiemi sono uguali.

Non sottoinsieme. A⊈BA \not\subseteq B è la negazione di A⊆BA \subseteq B. Si ottiene con le regole di Negazione dei quantificatori:

non(∀a∈A, a∈B)  ⟺  ∃ a∈A:a∉B\text{non}(\forall a \in A,\ a \in B) \iff \exists\, a \in A : a \notin B

cioè esiste un elemento di AA che non sta in BB. Il prof annota: da non confondere con A⊊BA \subsetneq B (pagina 26). Sono quasi opposti: A⊊BA \subsetneq B dice che AA sta dentro BB (ed è più piccolo), A⊈BA \not\subseteq B dice che AA esce da BB. Da non confondere nemmeno ∈\in e ⊆\subseteq: 4∈A4 \in A e {4}⊆A\{4\} \subseteq A sono corretti, 4⊆A4 \subseteq A è scritto male, perché a sinistra di ⊆\subseteq ci va un insieme.

1.2Proposizioni e connettivi

Proposizione (slide 15, pagina 12). La logica matematica considera proposizioni che possono essere o vere (V) o false (F), senza terze possibilità. Esempio delle slide: P=P = “3 è un numero pari” è falsa, Q=Q = “28 è divisibile per 4” è vera. Allora “PP e QQ” è falsa (serve che valgano tutte e due), “PP o QQ” è vera (ne basta una), “non PP” è vera. Controesempio: “che ore sono?” non è una proposizione, perché non è né vera né falsa.

Predicato. Una proposizione che contiene una variabile, quindi il suo valore di verità dipende dalla variabile: P(x)=P(x) = “xx è un numero pari”. Da solo non è né vero né falso: P(4)P(4) è vera, P(3)P(3) è falsa. Diventa una proposizione quando si sostituisce un valore o quando si mette davanti un quantificatore (“ogni x∈Nx \in \mathbb{N} è pari” è una proposizione, falsa).

Connettivi logici. e, o, non (sulla slide del 22 compare anche il simbolo ¬\neg per il non), più l’implicazione ⇒\Rightarrow (“se PP allora QQ”, oppure “PP implica QQ”) e la doppia implicazione ⇔\Leftrightarrow (“PP se e solo se QQ”, oppure “PP è equivalente a QQ”). La tavola di e, o, non, che la slide usa senza scriverla:

PPQQnon PPPP e QQPP o QQ
VVFVV
VFFFV
FVVFV
FFVFF

“e” è vera in una sola riga (tutte e due vere), “o” è falsa in una sola riga (tutte e due false). La prima riga della colonna “o” è V: è l‘“o” non esclusivo.

Tautologia (foglio 0, es. 1). Una proposizione composta che è vera in tutte le righe della sua tavola di verità, qualunque valore abbiano le lettere. Esempio: “AA o non AA”. Controesempio: “AA e non AA” è falsa in tutte le righe (è una contraddizione), e quindi la sua negazione è una tautologia (Esercizio 3).

1.3Quantificatori

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

∀x∈A,  P(x)∃x∈A:P(x)\forall x \in A, \; P(x) \qquad \exists x \in A : P(x)

Il primo si legge “per ogni xx appartenente ad AA, P(x)P(x) (è vera)”, il secondo “esiste xx appartenente ad AA tale che P(x)P(x) (è vera)”. Punteggiatura del corso: virgola dopo il ∀\forall, due punti dopo l’∃\exists.

Cosa serve per decidere se sono vere:

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

∀s∈S    ∃ ε∈E:s ha superato ε\forall s \in S \;\; \exists\, \varepsilon \in E : s \text{ ha superato } \varepsilon

L’ordine conta. ∃ ε∈E:∀s∈S,…\exists\, \varepsilon \in E : \forall s \in S, \dots direbbe che c’è un esame superato da tutti, che è un’altra frase. Regola: “∀x,∃y\forall x, \exists y” permette a yy di dipendere da xx; “∃y:∀x\exists y : \forall x” chiede una yy sola, la stessa per tutti gli xx.

Esempi in N\mathbb{N}:

2Enunciati

2.1Tavola di verità dell’implicazione

Slide 16 (pagina 13). Il prof annota che “P⇒QP \Rightarrow Q” si può leggere “PP implica QQ” o “se PP allora QQ”, e “P⇔QP \Leftrightarrow Q” si legge “PP è equivalente a QQ” o “PP se e solo se QQ”.

PPQQP⇒QP \Rightarrow QP⇔QP \Leftrightarrow Q
VVVV
VFFF
FVVF
FFVV

P⇒QP \Rightarrow Q risulta falsa esclusivamente quando PP è vera e QQ è falsa. In P⇒QP \Rightarrow Q la PP si chiama premessa, ipotesi o condizione sufficiente; la QQ conclusione, tesi o condizione necessaria. P⇔QP \Leftrightarrow Q equivale a “(P⇒Q)(P \Rightarrow Q) e (Q⇒P)(Q \Rightarrow P)”, e si usa per dire che due proposizioni sono equivalenti: è vera quando PP e QQ hanno lo stesso valore.

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

PPQQP⇒QP \Rightarrow Qcosa succede
VVVc’è il sole e vado al parco: promessa mantenuta
VFFc’è il sole e non vado al parco: promessa tradita
FVVnon c’è il sole e vado al parco lo stesso
FFVnon c’è il sole e non 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 xx è uno chef allora xx sa preparare una torta”. Se xx è 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.

Due esempi matematici:

2.2Negazione dell’implicazione

L’unico modo in cui P⇒QP \Rightarrow Q è falsa è PP vera e QQ falsa, quindi

non(P⇒Q)  ⟺  P e non Q\text{non}(P \Rightarrow Q) \iff P \text{ e non } Q

La tavola lo conferma, colonna per colonna:

PPQQP⇒QP \Rightarrow Qnon(P⇒Q)(P \Rightarrow Q)non QQPP e non QQ
VVVFFF
VFFVVV
FVVFFF
FFVFVF

La negazione di un “se… allora” non è un altro “se… allora”: è un “e”. Esempio: la negazione di “se c’è il sole vado al parco” è “c’è il sole e non vado al parco”. La negazione di “∀x∈R,(x>2⇒x2>4)\forall x \in \mathbb{R}, (x > 2 \Rightarrow x^2 > 4)” è “∃x∈R:x>2\exists x \in \mathbb{R} : x > 2 e x2≤4x^2 \leq 4”.

2.3Leggi di De Morgan

Slide 18 (pagina 17).

Negando, l‘“e” diventa “o” e viceversa, e ogni pezzo viene negato. L’intuizione: “PP e QQ” pretende due cose; per smentirla basta che ne manchi una, ed ecco l‘“o”. “PP o QQ” si accontenta di una; per smentirla devono mancare tutte e due, ed ecco l‘“e”.

Con PP = “x∈Ax \in A” e QQ = “x∈Bx \in B” le due leggi diventano un disegno: la II dice che non stare nell’unione è lo stesso che stare fuori da AA e fuori da BB; la I dice che non stare nell’intersezione è lo stesso che stare fuori da AA o fuori da BB.

Esempi:

Le tavole di verità che le dimostrano il prof le lascia da completare per esercizio (pagine 18-19): sono svolte in Esercizio 1.

2.4Forma contronominale

Slide 19 (pagina 20).

Questo fatto è fondamentale e giustifica il ragionamento per assurdo. Esempio delle slide: “se xx è uno chef allora xx sa preparare una torta” equivale a “se xx non sa preparare una torta, allora xx non è uno chef”. L’intuizione: se ogni chef sa fare la torta, chi non sa farla non può essere uno chef.

Dall’implicazione P⇒QP \Rightarrow Q si costruiscono tre frasi, e solo una le equivale:

nomefraseequivale a P⇒QP \Rightarrow Q?
contronominalenon Q⇒Q \Rightarrow non PPsì
inversaQ⇒PQ \Rightarrow Pno
contrarianon P⇒P \Rightarrow non QQno (è la contronominale dell’inversa)

Esempio con “se x>2x > 2 allora x2>4x^2 > 4”, vera:

La tavola è rimasta da completare (pagina 21), ed è in Esercizio 2.

2.5Negazione dei quantificatori

Slide 21 (pagina 23).

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

L’intuizione. “Tutti gli xx hanno la proprietà” è smentita da un solo xx che non ce l’ha: ecco perché la negazione di ∀\forall è un ∃\exists. “Qualcuno ha la proprietà” è smentita solo se nessuno ce l’ha, cioè se tutti non ce l’hanno: la negazione di ∃\exists è un ∀\forall. L’insieme AA non cambia.

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”.

Quantificatori annidati. Si applica la regola una volta per quantificatore, da sinistra, facendo avanzare il “non” verso destra. Esempio, la negazione di “∀x∈R,∃y∈R:y>x\forall x \in \mathbb{R}, \exists y \in \mathbb{R} : y > x”:

non(∀x∈R, ∃y∈R:y>x)\text{non}\big(\forall x \in \mathbb{R},\ \exists y \in \mathbb{R} : y > x\big)   ⟺  ∃x∈R:non(∃y∈R:y>x)(negazione di ∀)\iff \exists x \in \mathbb{R} : \text{non}\big(\exists y \in \mathbb{R} : y > x\big) \qquad \text{(negazione di } \forall\text{)}   ⟺  ∃x∈R:∀y∈R, non(y>x)(negazione di ∃)\iff \exists x \in \mathbb{R} : \forall y \in \mathbb{R},\ \text{non}(y > x) \qquad \text{(negazione di } \exists\text{)}   ⟺  ∃x∈R:∀y∈R, y≤x(non > eˋ ≤)\iff \exists x \in \mathbb{R} : \forall y \in \mathbb{R},\ y \leq x \qquad \text{(non } > \text{ è } \leq\text{)}

A parole: “c’è un reale maggiore o uguale a tutti i reali”, che è falsa (con y=x+1y = x + 1). Infatti l’originale è vera.

Quantificatori con una condizione. Nelle definizioni di Analisi si scrive spesso ∀ε>0\forall \varepsilon > 0 o ∀n>ν\forall n > \nu: è un ∀\forall su un insieme, ε∈(0,+∞)\varepsilon \in (0, +\infty). Negando cambia il quantificatore, la condizione resta:

non(∀ε>0, P(ε))  ⟺  ∃ ε>0:non P(ε)\text{non}\big(\forall \varepsilon > 0,\ P(\varepsilon)\big) \iff \exists\, \varepsilon > 0 : \text{non } P(\varepsilon)

e non ∃ ε≤0\exists\, \varepsilon \leq 0. Il motivo: l’insieme su cui si quantifica è sempre (0,+∞)(0, +\infty), e la regola generale non tocca l’insieme AA.

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 nn proposizioni elementari la tavola ha 2n2^n righe, perché ogni lettera può essere V o F indipendentemente dalle altre: con tre lettere sono 2⋅2⋅2=82 \cdot 2 \cdot 2 = 8 righe. Conviene incolonnare prima i pezzi intermedi (le negazioni singole, gli “e” e gli “o”) e poi comporre. Per una tautologia la colonna finale deve essere tutta V.

Ordine delle righe che non fa dimenticare casi: la prima lettera alterna a blocchi di metà (VVVVFFFFVVVVFFFF), la seconda a blocchi di un quarto (VVFFVVFFVVFFVVFF), l’ultima una riga sì e una no (VFVFVFVFVFVFVFVF).

Negare una proposizione con quantificatori.

  1. Se la frase è in italiano, scrivila prima in simboli: individua insiemi, variabili, predicato.
  2. Scorri da sinistra a destra: ogni ∀\forall diventa ∃\exists, ogni ∃\exists diventa ∀\forall. L’ordine dei quantificatori non si tocca, e nemmeno gli insiemi o le condizioni (∀ε>0\forall \varepsilon > 0 diventa ∃ε>0\exists \varepsilon > 0).
  3. Alla fine nega il predicato: ≤\leq diventa >>, << diventa ≥\geq, == diventa ≠\neq, “e” diventa “o” e “o” diventa “e” (De Morgan), P⇒QP \Rightarrow Q diventa “PP e non QQ”.
  4. Ritraduci in italiano e rileggi: la negazione deve essere vera esattamente quando l’originale è falsa.

Nei casi difficili si scrive un passaggio per riga, con la regola usata accanto, come in Esercizio 7.

Dire se un enunciato con quantificatori è vero o falso. Si riconosce dal testo “dire se è vera” davanti a una formula con ∀\forall ed ∃\exists.

  1. Leggilo a parole, partendo da sinistra: chi si sceglie prima e chi dopo.
  2. Se pensi che sia vero: a ogni ∀\forall l’avversario sceglie un valore qualunque, a ogni ∃\exists scegli tu, e puoi usare i valori già scelti a sinistra. Scrivi esplicitamente la tua scelta (per esempio y=−2xy = -2x) e controlla che il predicato valga.
  3. Se pensi che sia falso: scrivi la negazione e dimostra che è vera. In pratica serve un controesempio, cioè un valore per il ∃\exists che compare nella negazione.
  4. Controllo: prova il predicato con uno o due numeri concreti.

Dimostrare un’implicazione con la contronominale. Se “P⇒QP \Rightarrow Q” è scomoda da dimostrare (perché QQ è una negazione, o perché da PP non si ricava niente di utile), si dimostra “non Q⇒Q \Rightarrow non PP”, che è equivalente. Esempio in Esercizio 12.

Dimostrare che due insiemi sono uguali. Si prova la doppia inclusione, cioè A⊆BA \subseteq B e B⊆AB \subseteq A. Ognuna si prova prendendo un elemento generico del primo insieme e mostrando che sta nel secondo. Quando ogni passaggio è un “se e solo se”, le due inclusioni si fanno insieme con una catena di   ⟺  \iff, come in Esercizio 13.

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. Poi si disegnano gli insiemi sulla retta e si guardano gli estremi uno per uno.

4Esempi svolti a lezione

4.1Due proposizioni equivalenti? (14/9, pagine 15-16)

Mostrare che

P=(A e B)⇒Cnon eˋ equivalente aQ=((non A) o (non B))⇒non CP = (A \text{ e } B) \Rightarrow C \qquad \text{non è equivalente a} \qquad Q = \big((\text{non } A) \text{ o } (\text{non } B)\big) \Rightarrow \text{non } C

Tipo: equivalenza di due proposizioni composte. Metodo: tavola di verità di entrambe. Tre lettere, quindi 23=82^3 = 8 righe. Si calcolano prima i pezzi e poi le implicazioni (è la tavola del prof, pagine 15-16).

AABBCCAA e BBPPnon AA o non BBnon CCQQ
VVVVVFFV
VVFVFFVV
VFVFVVFF
VFFFVVVV
FVVFVVFF
FVFFVVVV
FFVFVVFF
FFFFVVVV

Come si legge una riga, per esempio la terza (AA V, BB F, CC V):

  1. AA e BB è F, perché BB è F;
  2. PP = (F ⇒\Rightarrow V) è V, premessa falsa;
  3. non AA o non BB = F o V = V;
  4. non CC = F;
  5. QQ = (V ⇒\Rightarrow F) è F, l’unico caso falso dell’implicazione.

Conclusione del prof: siccome le tavole di verità delle due proposizioni sono diverse, le due proposizioni non sono equivalenti. Bastava una riga: già la seconda ha PP falsa e QQ vera. Il motivo di fondo: per De Morgan “non AA o non BB” è “non(AA e BB)”, quindi QQ è non(AA e BB) ⇒\Rightarrow non CC, cioè PP con ipotesi e tesi negate senza scambiarle: è la contraria, non la contronominale. La contronominale giusta sarebbe non C⇒(non A o non B)\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” (pagina 17).

Tipo: negazione di una congiunzione in italiano. Metodo: tradurre in simboli e applicare De Morgan.

  1. Il prof corregge a mano il “ma” in “e”: logicamente “ma” è una congiunzione, con una sfumatura di contrasto che la logica ignora.
  2. PP = “la matematica è inutile”, QQ = “una laurea in ingegneria vale molto”. La frase è “PP e QQ”.
  3. Per la I legge di De Morgan: non(PP e QQ)   ⟺  \iff (non PP) o (non QQ).
  4. non PP = “la matematica è utile”, non QQ = “una laurea in ingegneria non vale granché”.

Risposta c) della slide: “la matematica è utile o una laurea in ingegneria non vale granché”. La a) sbaglia perché tiene l‘“e”, la b) nega solo il primo pezzo, la d) cambia argomento.

4.3Quiz 1 (slide 22)

La negazione di “ogni mela contiene almeno 4 semi” è (pagina 25):

  1. nessuna mela contiene almeno 4 semi
  2. esiste una mela con almeno 4 semi
  3. ogni mela contiene al massimo 3 semi
  4. esiste una mela con meno di 4 semi

Il prof scrive AA = {mele} e P(x)P(x) = “xx ha almeno 4 semi”.

  1. La frase è ∀x∈A,P(x)\forall x \in A, P(x).
  2. Per la negazione di ∀\forall: ∃x∈A:non P(x)\exists x \in A : \text{non } P(x).
  3. non P(x)P(x) = “xx ha meno di 4 semi” (non ≥4\geq 4 è <4< 4).

Risposta d. La a) e la c) dicono la stessa cosa (“ogni mela ha al massimo 3 semi”) e lasciano il ∀\forall; la b) cambia il quantificatore ma non nega il predicato.

4.4Quiz 2 (slide 22)

La negazione di ∃ a∈A:∀b∈B, a≠b\exists\, a \in A : \forall b \in B,\ a \neq b è:

  1. B⊆AB \subseteq A
  2. ∀a∈A ∃ b∈B:a=b\forall a \in A\ \exists\, b \in B : a = b
  3. ∀a∈A,∀b∈B, a=b\forall a \in A, \forall b \in B,\ a = b
  4. ∃ a∈A,∃ b∈B:a=b\exists\, a \in A, \exists\, b \in B : a = b

Svolgimento del prof (pagine 26-27): si chiama P(a)P(a) il pezzo “∀b∈B,a≠b\forall b \in B, a \neq b”, così la frase ha un solo quantificatore esterno.

  1. La frase è ∃a∈A:P(a)\exists a \in A : P(a).
  2. Negazione di ∃\exists: ∀a∈A,non P(a)\forall a \in A, \text{non } P(a).
  3. non P(a)=non(∀b∈B,a≠b)\text{non } P(a) = \text{non}(\forall b \in B, a \neq b), e per la negazione di ∀\forall è ∃b∈B:non(a≠b)\exists b \in B : \text{non}(a \neq b).
  4. non(a≠b)\text{non}(a \neq b) è a=ba = b.

In conclusione la negazione è

∀a∈A  ∃b∈B:a=b\forall a \in A \ \ \exists b \in B : a = b

risposta b. A parole: ogni elemento di AA coincide con qualche elemento di BB, cioè A⊆BA \subseteq B. La frase di partenza diceva quindi “AA non è sottoinsieme di BB”, A⊈BA \not\subseteq B (il prof annota: da non confondere con ⊊\subsetneq). La a) scrive l’inclusione al contrario; la c) ha ∀b\forall b, che chiederebbe ad aa di essere uguale a tutti gli elementi di BB; la d) lascia l’∃\exists davanti.

5Esercizi tipo esame

In una pagina a parte, dal più facile al livello del 30: Insiemi e logica (esercizi).

6Errori tipici

7Domande