Fondamenti di informatica - Laurea triennale Informatica/Metodi di prova: sistemi matematici, dimostrazioni dirette e controesempi

Sistemi matematici

Un sistema matematico è formato da:

• assiomi: affermazioni assunte vere senza dimostrazione;
• definizioni: introducono nuovi concetti usando termini già noti;
• termini indefiniti: non vengono definiti esplicitamente, ma il loro significato è determinato dagli assiomi.

A partire da questi elementi si possono dimostrare dei risultati chiamati teoremi.

Tipi particolari di teoremi:

• lemma: teorema utile soprattutto per dimostrare altri teoremi;
• corollario: teorema che segue facilmente da un altro teorema.

Una dimostrazione è un argomento logico che stabilisce la verità di un teorema.

Esempi di sistemi matematici

Geometria euclidea

Ha assiomi su punti, rette e parallelismo.

I termini “punto” e “retta” sono indefiniti.

Include definizioni come:

• triangoli congruenti;
• angoli supplementari.

Numeri reali

Ha assiomi sulle proprietà dei numeri reali e delle operazioni.

Per esempio, viene definito l’insieme dei numeri reali positivi e il valore assoluto.

Teoremi, lemmi e corollari: esempi

• teoremi: risultati importanti dimostrati;
• corollari: conseguenze immediate di teoremi già provati;
• lemmi: risultati intermedi, utili ma non sempre interessanti da soli.

Dimostrazioni dirette

Molti teoremi hanno la forma:

Per ogni x, se P(x), allora Q(x).

Per dimostrare una proposizione di questo tipo con una dimostrazione diretta si segue questa idea:

1. si prendono elementi arbitrari del dominio;
2. si assume vera l’ipotesi P;
3. usando definizioni, assiomi, teoremi già noti e regole logiche, si mostra che anche la conclusione Q è vera.

Quindi una dimostrazione diretta parte dalle ipotesi e arriva direttamente alla tesi.

Esempio con numeri pari e dispari

• un intero è pari se esiste un intero k tale che n=2k;
• un intero è dispari se esiste un intero k tale che n=2k+1.

Con queste definizioni si dimostra, ad esempio:

• se m è dispari e n è pari, allora m+n è dispari.

La dimostrazione consiste nel sostituire:

• m=2r+1,
• n=2s,

e mostrare che

m+n=2(r+s)+1

che ha la forma di un numero dispari.

si può anche dimostrare che : ∃k (m=2k+1) se m è dispari, oppure ∃k (n=2k) se n è pari

Questo esempio fa vedere come, in una dimostrazione diretta, sia fondamentale usare correttamente le definizioni.

---

Esempi con insiemi

Per provare che due insiemi sono uguali, bisogna dimostrare doppia inclusione:

• ogni elemento del primo appartiene al secondo;
• ogni elemento del secondo appartiene al primo.

Questa tecnica viene applicata a identità tra intersezioni, unioni e differenze di insiemi.

Ad esempio nell'intersezione fra insiemi si può dimostrare che:

A∩(B−C) = (A∩B)−(A∩C)

si parte affermando la condizione di un elemento x

x∈b−c

da cui si deduce:

x∈B∧x∈/C x∈A∩B x∈A∧x∈B

Analogamente riprendendo la prima formula, mediante equivalenze logiche:

x∈A∩(B−C)

equivale a:

x∈A∧x∈B∧x∈/C

Uso di sottodimostrazioni

A volte, durante una dimostrazione, serve prima provare un risultato ausiliario.

Questa piccola dimostrazione intermedia è chiamata sottodimostrazione.

Serve a spezzare una prova complessa in parti più semplici.

Confutare un enunciato universale: controesempi

Per smentire un’affermazione del tipo:

“per ogni x, P(x)”

non bisogna mostrare che è falsa in molti casi: basta trovare un solo valore per cui è falsa.

Questo valore si chiama controesempio.

Esempio: l’enunciato “per ogni intero n, n2+n+41 è primo” è falso, perché esiste almeno un valore di n che produce un numero non primo.

Il controesempio è quindi lo strumento fondamentale per negare una proposizione universale.

Suggerimenti per costruire una dimostrazione

• scrivere chiaramente ipotesi e tesi;
• tenere sempre presente cosa si deve dimostrare;
• usare le definizioni in modo esplicito;
• guardare esempi concreti per capire meglio l’enunciato;
• giustificare ogni passaggio;
• segnalare chiaramente le parti della dimostrazione;
• se si sospetta che un enunciato sia falso, cercare un controesempio.

Inoltre, quando una prova fallisce, spesso questo fallimento può suggerire proprio dove trovare un controesempio.

Errori comuni

a. Usare la stessa lettera per quantità diverse

Non si può usare lo stesso simbolo per due numeri che potrebbero essere diversi.

Questo porta a conclusioni scorrette.

b. Verificare solo esempi particolari

Mostrare che un enunciato è vero per alcuni valori non basta a dimostrarlo in generale.

c. Ragionamento circolare

Non si può assumere come vera proprio la conclusione che si deve dimostrare.

Questo errore è chiamato petizione di principio o ragionamento circolare.

Idee chiave

• la matematica si basa su sistemi formati da assiomi e definizioni;
• i teoremi si dimostrano con ragionamenti rigorosi;
• uno dei metodi più importanti è la dimostrazione diretta;
• per negare un enunciato universale basta trovare un controesempio;
• scrivere una dimostrazione richiede precisione, chiarezza e attenzione agli errori logici.