Logica, appunti e esercizi

Logicalogica

Argomenti principali

1. Logica proposizionale:
   • Sintassi
   • Semantica
   • Teoria della dimostrazione
2. Logica del primo ordine
   • Sintassi
   • Semantica: modelli e soddisfacibilità
   • Traduzione dal linguaggio normale a quello di primo ordine

Affermazioni matematiche → Teoremi

Sotto dato ipotesi (o ammissioni) vale una tesi (o conclusione)

Esempio: affermazione: n è un numero naturale dispari

• ✔️ è vera con n = 3
• ❌ è falsa con n = 8

Dimostrazione

1. Diretta

   Assumo che siano vere le ipotesi, allora anche (Q) deve essere verificata

   es. P₁: n è un num. dispari int.
   P₂: m è un pari int.
   Q: n + m è un int. dispari

2. Dimostrazione per assurdo

   es. se x + y > s, allora x ≥ s o y ≥ s

   Ipotesi: P: x + y ≥ s
   Tesi: Q: x ≤ s y ≤ 1 ⟹ n assume che la Tesi è falsa e quindi vado a contraddire l'ipotesi.

   Oppure:

   es. per ogni n, se n² è pari, allora n è pari.

   Ipotesi: P: n² è pari
   Tesi: Q: n è pari ⟹ n assume che sia falsa, quindi penso che n sia in qualche modo dispari

3. Dimostrazione per contrapponimento

   es.: Se P allora Q ⇩ Se non Q, allora non P e non viceversa!

   ad es. se piove, prendo l'ombrello
   P: piove
   Q: prendo l'ombrello.

Esempio generale

Teorema: (THM) Se P allora Q

Dimostrazione per assurdo: Se P e non Q allora contraddizione

Dimostrazione per contrapponimento: Se non Q allora non P

Si può dimostrare un Teorema dimostrando la sua contrapposizione

1. Ipotesi: P: n² è un n intero pari
   Tesi: Q: n è un intero dispari
2. Ipotesi: P: n² è un n pari
   Tesi: Q: n è un n pari

Basta dimostrare

Dimostrazione per composizione

Teorema: n dispari m pari Ipotesi (n+m)² dispari

Se Q allora R perché supponiamo che Q è vera, dimostrato già prima

Dimostrazione per con.

Se P allora Q
P₁, P₂, ..., P_n allora dimostro n teoremi

Se P₁ allora Q
Se P₂ allora Q
Se P_n allora Q

Si assume P allora: Se P, allora Q

Esempio:

Teorema: Per ogni numero reale x si ha x ≤ |x|

Ipotesi: P: nessuna
Tesi: Q: x ≤ |x|

Se x ≥ 0, allora x ≤ |x|

Per def.: |x| = x quindi è ver

Equivalenza:

Siano P e Q tali che:

• Se P allora Q
• Se Q allora P

In questo caso P è equipollente, perché solitamente P ha più informazioni dell'altro.

Nozione di conseguenza

• Riflessiva: Qualunque sia P: P ha come conseguenza P
• Transitiva: Se P ha come conseguenza Q e Q ha come conseguenza R, P ha come conseguenza R (controllare che sia giusto)

Nozione di equivalenza

• Riflessiva: P è equivalente a P
• Transitiva: Se P è equivalente a Q, Q è equivalente a R, P è equivalente a R
• Simmetrica: Se P è equivalente a Q, allora Q è equivalente a P

Esempio: Definiamo su numeri interi. x R y se e solo se x - y è pari.

Esercizio: Dimostrare che R è riflessiva, transitiva e simmetrica.

Variabili reali

x, y, z ... (lettere) i, o, k, m, n... m denotiamo nel dominio preso in considerazione

Simboli predefiniti: carini oh ogni simbolo, sempre dovrebbero spiegare il corso e loro significato (vedi es. I)

Simboli per denotare operazioni o funzioni (vedi es. +, -)

Simboli per esprimere relazioni tra loro (vedi es. >, =)

Affermazione: 5 non dà un nuovo elemento

Simbolo di uguaglianza / relazione binaria: L'oggetto sx = oggetto dx

Verbo essere (è) (2 + 2 = 5) -> è un'affermazione

Simbolo di relazioni non possono restare fuori di senso compiuto. Questi simboli restano oggetto di lavoro di primo ordine.

Ragionare in matematica -> passare da un'affermazione all'altra.

1. non, ¬
2. se ... allora ... -> P allora Q
3. se ... se e solo se ... -> P se e solo se Q
4. esiste un oggetto x tale che

∃ x | x ≤ y

5. per ogni oggetto x ... (applica una proprietà)