Logica e matematica discreta

LOGICA - MDL

CAPITOLO 1 - TEOREMI, DIMOSTRAZIONI E TAVOLE DI VERITÀ

1.1 - TEOREMI e DIMOSTRAZIONI

Nelle discipline scientifiche, per stabilire la veridicità di un’affermazione si ricorre a:

• Misurazioni
• Esperimenti ⟹ Se questi (fatti da più persone più volte) confermano l’affermazione, questa viene accettata (almeno temporaneamente), altrimenti viene rifiutata.
• Simulazioni

In matematica (ma anche in informatica) questo metodo scientifico non funziona:

• Nessun esperimento potrà stabilire se √2 sia un numero razionale (√2 = m/n con m,n ∈ ℤ)
• Controllare alcuni casi specifici può essere utile per avere indizi sulla verità o meno di un’affermazione, ma a volte questo può anche essere fuorviante.

Esempio: congettura: 992 n² + 1 4 non è mai un quadrato perfetto

• Falso 2 sono infiniti numeri del tipo:
• 992n²+1 che sono quadrati perfetti ma il più piccolo è maggiore del diametro della terra/distanza Luna.

Controllare a mano la congettura con degli esempi farà erroneamente indotti a crederla vera.

In matematica, per stabilire la verità di un'affermazione si deve ricorrere ad una dimostrazione:

Catena di ragionamento che ci permette di concludere che la tesi del teorema deve essere vera partendo dall’assunzione che le ipotesi del teorema siano vere.

La stessa cosa vale in informatica:

Per fornire una dimostrazione del fatto che un algoritmo funziona dobbiamo mostrare la sua correttezza.

Affermare (riguardante numeri, funzioni, entità geometriche, o altri oggetti matematici) che si vuole dimostrare.

Se valgono certe ipotesi allora anche la tesi del teorema è vera.

Esempio: 9 < 0 9

LOGICA - MDL

CAPITOLO 1 - TEOREMI, DIMOSTRAZIONI E TAVOLE DI VERITÀ

1.1 - TEOREMI e DIMOSTRAZIONI

Nelle discipline scientifiche, per stabilire la veridicità di un'affermazione, si ricorre a:

• Misurazioni
• Esperimenti
• Simulazioni

Se questi (fatti da più persone più volte) confermano l'affermazione, questa viene accettata (almeno temporaneamente), altrimenti viene rifiutata.

In matematica (ma anche in informatica) questo metodo scientifico non funziona.

Nessun esperimento potrà stabilire se √2 sia un numero razionale (√2 = m/n con m, n ∈ Z).

Controllare alcuni casi specifici può essere utile per avere indizi sulla verità o meno di un'affermazione, ma a volte questo può anche essere fuorviante.

Esempio: congettura 993 siamo scorretto o meno.

La stessa cosa vale in informatica.

Per fornire una dimostrazione del fatto che un algoritmo funziona, dobbiamo mostrare la sua correttezza.

1. Catena di ragionamenti
2. Conclusione

Che cos'è un teorema?

Enunciato della forma:

Se valgono P₁ e P₂ ... e P_n, allora vale anche Q.

Affermazioni dette ipotesi del teorema.

Tesi del teorema.

Esempio:

Se m è un numero naturale dispari ed m è un numero naturale pari, allora m+ m è dispari.

Sinonimi di teorema: proposizione, lemma, ...

• Dal punto di vista tecnico, indicano la stessa cosa
• La differenza è soggettiva = importanza attribuita da chi parla
• Teorema: affermazioni veramente importanti e significative
• Proposizione: meno importante ma pur sempre abbastanza significative
• Lemma: di per sé non significative ma utili per dimostrare altri fatti più importanti

Si intende asserire che:

• In qualunque contesto o situazione le affermazioni P₁, P₂ ... P_m sono verificate, anche l'affermazione Q risulta essere vera.
• Devono valere tutte.

Scrittura: P₁, P₂ ... P_m ⇔ Q

Q è conseguenza logica di P₁, P₂ ... P_m

P₁, P₂, ... P_m hanno come conseguenza logica Q

Alcune affermazioni Q sono valide in qualunque contesto = teorema che non ha bisogno di ipotesi.

Tautologia

Strategie dimostrative

• Dimostrazione diretta: strategia più semplice. Assume di trovarsi in un contesto in cui siano verificate le ipotesi P₁, ..., P_n e sulla base di semplici e rigorosi ragionamenti stabilisce che in tale contesto anche la tesi Q è verificata.
• Dimostrazione per assurdo (o indiretta): si assume che Q sia falsa e da questa assunzione deriva (utilizzando anche le ipotesi P₁