Cheat sheet di Matematica

Logica proposizionale

Proposizioni o formule atomiche: le affermazioni con un solo valore di verità, vero o falso.

∧ ∨ ⇒ P Q P Q P Q P Q P ¬P

Visualizzazione ad albero: V V V V V V F V F F V F F V F V F V V F F F F V

Usando i quattro connettivi infinite proposizioni. Virgola e disgiunzioni: o Virgola (, frase,): ()

Logica del prim’ordine

Logica del prim’ordine (variabili) Attenzione all’ordine!

- Definizione 2.15. Sia F(x) una proposizione dipendente da x:

• ∃x • F(x): esiste un modo di riempire i puntini che rende la frase vera (quantificatore esistenziale);
• ∀x • F(x): in qualunque modo riempiamo i puntini la frase è vera (quantificatore universale).

- Theorem 2.23. Siano P e Q due proposizioni. Allora: Sia P(x) una proposizione dipendente. Allora:

• ∧ ∨ • ¬(P Q) è equivalente a (¬P) (¬Q) (legge di De Morgan); ∀x • ¬(∃x P(x)) è equivalente a ¬P(x);
• ∨ ∧ • ¬(P Q) è equivalente a (¬P) (¬Q) (legge di De Morgan); ∃x • ¬(∀x P(x)) è equivalente a ¬P(x).
• • ¬(¬P) è equivalente a P (legge della doppia negazione);
• ⇒ ∧ • ¬(P Q) è equivalente a P ¬Q.

Gli elementi di logica devono essere razionali (no fallaci logiche)

Insiemi

Insiemi - x ∈ A: x è un elemento di A x /∈ A: x non è un elemento di A.

∅. ∈ ∅, ∀x ∅.

L’insieme vuoto non ha elementi. In logica, il vuoto è l’unico insieme che ¬∃x x o equivalentemente x /∈

Ci sono due modi per descrivere un insieme:

• Rappresentazione estensiva, ovvero scrivere tutti i suoi elementi. {}, l’ordine in cui scriviamo gli elementi di un insieme non importa. Non contano neanche le ripetizioni. ∈
• Rappresentazione intensiva, ovvero scrivere una proprietà che caratterizzi tutti gli elementi. Es. {x N : x è pari} ⊆

- Theorem 2.29. L’insieme vuoto è sottoinsieme ( ) di qualsiasi insieme.

- Theorem 2.30. Ogni insieme è sottoinsieme di se stesso.

∪ ∈ ∨ ∈

- Definizione 2.33. L’unione dei due insiemi, A B, {x : (x A) (x B)}, tutto A B Diagrammi di Venn:

∈ ∈

- Definizione 2.34. L’intersezione dei due insiemi, A∩B, {x : (x A)∧(x B)}, sia A sia B

- Definizione 2.35. Fissiamo un insieme V, e sia A un sottoinsieme di V. Si scrive come Ac.

Il complementare di A in V è l’insieme degli elementi che stanno in V ∈ ∈ ma non in A, ovvero {x V : ¬(x A)}, ∈ P(x) {x V : P(x)}

- Definizione 2.36. Dati due insiemi A e B, A\B (si dice A meno B) è l’insieme degli elementi che stanno ∧ ∩ ∈ in A ma che non stanno in B, quindi {x A : x /∈ B}.

∨ ∪ ∅ ∈ ∈

Le parti di un insieme: calcoliamo P({3, 5}): P({3, 5}) e {3, 5} P({3, 5}). Altri due sottoinsiemi sono ¬ c {3} e {5}, e non ce ne sono altri, quindi P({3, 5}) = {∅, {3}, {5}, {3, 5}}.

⇒ ⊆ Attenzione: ∅

• Non confondere 3 con {3}! Il primo è un numero, il secondo è un insieme.
• Non confondere {3} con {{3}}: entrambi insiemi con un solo elemento, l’elemento del primo è un numero, l’elemento del secondo è un insieme.
• E {∅}, perché sono entrambi insiemi, ma il primo non ha elementi, mentre il secondo ne ha uno.

- Definizione 2.43. Una sequenza è una collezione ordinata di oggetti. Si scrive con le parentesi tonde.

- Definizione 2.44. Dati due insiemi A e B, il prodotto cartesiano di A e B, scritto A × B, è l’insieme delle coppie il cui primo elemento è un elemento di A e il secondo elemento è un elemento di B.

Funzioni

Funzioni ES. Sofia, camminando fra la gente, nota i diversi colori delle magliette delle persone che incontra per strada.

È una funzione che associa ad ogni persona il colore della sua maglietta.

• Sono ben fissati la partenza e l’arrivo della funzione
• Tutti gli oggetti di partenza devono essere considerati
• La funzione associa un unico oggetto ad ogni oggetto di partenza

- Definizione 2.46. Siano X e Y insiemi, e sia f un’associazione che associa elementi di X a elementi di Y. Allora f è una funzione se:

• ∀x ∈ ∃y ∈ ∀x ∈ ∀y ∈ ⇒ ∈ ⇒ X Y f(x) = y;
• X Y (f(x) = y (∀z Y (f(x) = z y = z))). In tal caso scriviamo f : X → Y.

- Definizione 2.49. Sia f : X → Y. Allora X è il dominio di f, si scrive anche dom(f), e Y è il codominio di f.

La funzione “colore della maglietta” ha come codominio l’insieme dei colori, ma magari ci sono colori che non vengono indossati (p.es. eliotropo)

- Definizione 2.51. L’insieme immagine di una funzione è l’insieme dei valori assunti da una funzione. Ovvero, se f : X→Y, ∈ ∃x ∈ allora Im(f) = {y Y : X f(x) = y}. Possiamo scrivere anche f[dom(f)].

La funzione “colore della maglietta” ha come insieme immagine l’insieme dei colori delle magliette.

⊆ ∈ ∃x ∈

- Definizione 2.52. Sia f : X → Y, e sia A X. Allora f[A] è l’insieme immagine di f su A, ovvero {y Y : A f(x) = y}.

∈

• Rappresentazione per rimpiazzamento: {f(x) : x A} è f[A]. ∈

- Definizione 2.55. Una funzione f : X → Y si dice suriettiva se f[X] = Y, ovvero se preso un qualunque elemento y Y, ∈ esiste un elemento x X tale che f(x) = y. Ovvero, ogni elemento di Y è immagine di un elemento di X.

- Definizione 2.56. Una funzione f : X → Y si dice iniettiva se non esistono due elementi di X che sono stati associati allo ∀x1, ∈ ⇒ stesso elemento di Y, ovvero x2 X f(x1) = f(x2) x1 = x2

- Biettiva: un solo e unico elemento x→y

Funzione inversa di f: scriviamo falla−1, questa associazione è una funzione con dominio Y e codominio X.

Come con le proposizioni, gli insiemi e i numeri, si possono fare operazioni anche fra funzioni. La più comune e usata è la composizione. Si tratta di mettere due funzioni una dopo l’altra.

- Definizione 2.60. Siano X, Y, Z insiemi, siano f : X → Y e g : Y → Z due funzioni. La funzione composta di f e g, scritta g ◦ f, ∈ è la funzione di dominio X, codominio Z, che associa ad ogni x X g(f(x)).

Esempi di composizione

ES. Come si risolve:

g(x) = y e fog(x)=f(g(x))=f(y)=t ripeti finché non finisce g soluzione= fog: A->C e fog(x)=fog(z)=t quando fog f B->C e g A->B fog->AC f II e g I quando gof f A->B e g B->C gof->AC f I e g II

- Definizione 2.63. Una funzione f : X → Y si dice invertibile se esiste una funzione g : Y → X tale che ∈ ∈ per ogni x X vale g ◦ f(x) = x, e per ogni y Y vale f ◦ g(y) = y.

- Theorem 2.64. Per ogni funzione f, f è biiettiva se e soltanto se f è invertibile.

- Definizione 2.65. Sia A un insieme finito. La cardinalità di A, scritta |A|, è il numero di elementi di A.

⊆

- Theorem 2.66. Se A e B sono due insiemi finiti, e A B, allora |A| ≤ |B|.

- Theorem 2.70. Siano A e B due insiemi finiti. Allora

• Se |A| < |B|, esistono da A a B
• Se |A| > |B|, ex da A a B funzioni
• Se |A| = |B|, allora esistono funzioni neutre e funzioni iniettive neutre e funzioni suriettive; funzioni di tutti i quattro tipi.

∈ ∈

- Theorem 2.75. |{n N : n > 0}| = |N|, come testimoniato da f : {n N : n > 0} → N, f(n) = n − 1.

∈

Ma se f : {n N : n > 0} → N è biiettiva, esisterà anche l’inversa, ovvero f−1(n) = n + 1, che ci testimonia dunque che ‘‘infinito meno uno = infinito”, “infinito meno due = infinito”

∈ ∈

- Theorem 2.76. |{n N : n è pari }| = |N|, come testimoniato da f : {n N : n è pari} → N, f(n) = n/2. falla−1(n) = 2n

- Theorem 2.79. Non esistono funzioni suriettive da N a R

Relazioni

Relazioni - Definizione 2.82/3/4. Sia R una relazione su X.

• R si dice riflessiva se ogni elemento di X è in relazione con se stesso, ovvero ∀a ∈ X aRa.
• R si dice irriflessiva se nessun elemento di X è in relazione con se stesso, ovvero ∀a ∈ X ¬(aRa).
• R si dice simmetrica se tutte le relazioni sono reciproche, ovvero ∀a, ∈ ⇒ b X (aRb bRa).
• R si dice anti-simmetrica se nessuna relazione è reciproca a parte gli elementi in relazione con se stessi, ovvero ∀a, ∈ b ⇒ X (aRb∧bRa a = b). Attenzione! Rimane il caso in cui per alcune coppie la relazione è reciproca, per altre no. In quel caso la relazione non è né simmetrica né anti-simmetrica.
• R si dice transitiva se si “trasmette” da un elemento all’altro, ovvero ∀x, ∈ ∧ ⇒ y, z X (xRy yRz xRz). Attenzione! C’è di ⇒: nuovo il problema di Cosa succede se non esistono tre elementi, il primo in relazione con il secondo e il secondo in relazione con il terzo? La relazione è transitiva (banalmente), proprio perché l’antecedente dell’implicazione è falso, e dunque l’implicazione è vera.

- Definizione 2.86. Una relazione irriflessiva e simmetrica si chiama grafo. Basta disegnare un punto per ogni elemento dell’insieme su cui il grafo è definito, e unire con una linea gli elementi che sono in relazione fra di loro. Gli elementi dell’insieme su cui il grafo è definito si chiamano nodi o vertici, le linee che li uniscono