Linguaggi e metodi della matematica

Materie:	Appunti
Categoria:	Matematica
Download:	118
Data:	23.01.2002
Numero di pagine:	3
Formato di file:	.doc (Microsoft Word)

LINGUAGGI E METODI DELLA MATEMATICA

TAVOLE DI VERITA’

• PRINCIPIO DEL TERZO ESCLUSO: una proposizione o è vera o è falsa.
• PRINCIPIO DI NON CONTRADDIZIONE: una proposizione non può essere sia vera sia falsa nello stesso momento.
• Una FORMULA PROPOSIZIONALE è un’espressione ottenuta combinando simboli detti VARIABILI PROPOSIZIONALI con parentesi e connettivi booleani. Sostituendo alle variabili proposizionali delle proposizioni si ottiene una PROPOSIZIONE.
• Una formula proposizionale è una TAUTOLOGIA se sostituendo alle variabili proposizionali delle proposizioni qualsiasi si ottiene una proposizione che è SEMPRE VERA.
• Una formula proposizionale è CONTRADDITTORIA se sostituendo alle sue variabili qualsiasi proposizioni, si ottiene una proposizione che è SEMPRE FALSA.

CONNETTIVI BOOLEANI : LEGGI

¬ = negazione (non); ^ = congiunzione(e); ° = disgiunzione (oppure) → = implicazione (se….allora…) ←> = doppia implicazione (…se e solo se…, indica equivalenza delle due proposizioni, cioè esse hanno la medesima tabella di verità)
• LEGGE DISTRIBUTIVA DELLA CONGIUNZIONE SULLA DISGIUNZIONE: A ^ (B°C) ←> (A^B)°(A^C)
• LEGGE DISTRIBUTIVA DELLA DISGIUNZIONE SULLA CONGIUNZIONE: A°(B^C) ←> (A°B) ^ (A°C)
• LEGGI DI DE MORGAN: ¬(A^B) ←> ¬A ° ¬B ¬(A°B) ←>¬A ^ ¬B
• LEGGE COMMUTATIVA DELLA CONGIUNZIONE: A^B ←> B^A
• LEGGE COMMUTATIVA DELLA DISGIUNZIONE: A°B ←>B°A

PROPOSIZIONI E PREDICATI

• Un PREDICATO è un’espressione che può contenere variabili. Se esse vengono sostituite con oggetti di un opportuno dominio (per esempio numeri naturali) si ottiene una PROPOSIZIONE.
• Una FORMULA PREDICATIVA è un’espressione composta formata da predicati proposizioni, variabili, connettivi e parentesi.
• Una formula predicativa è LOGICAMENTE VALIDA se risulta vera in qualsiasi modo possano essere interpretati i simboli per predicati e proposizioni che vi compaiono.

RELAZIONI

• Una RELAZIONE BINARIA da A a B è un sottoinsieme R di AxB, ma a noi interessano quelle da A a A.
• PROPRIETA’ DELLE RELAZIONI:
1. R è RIFLESSIVA se ogni elemento è in relazione con se stesso.
2. R è transitiva se aRb (si legge “a è in relazione con b”) e bRc implica che aRc
3. R è simmetrica se aRb implica che bRa
4. R è antisimmetrica se i fatti che aRb e bRa implicano necessariamente che a=b.
• Una relazione è DI ORDINE se è contemporaneamente RIFLESSIVA, ANTISIMMETRICA E TRANSITIVA.
• Una relazione è DI EQUIVALENZA (o semplicemente è un’equivalenza) se gode delle seguenti proprietà: TRANSITIVITA’, SIMMETRIA, RIFLESSIVITA’.

INDUZIONE

Molte dimostrazioni matematiche si effettuano attraverso l’induzione. Ve ne sono di due tipi: l’induzione normale e l’induzione forte.
Vediamo prima quella normale: articoliamone in modo schematico e semplice i passi.
1. Si verifica la BASE D’INDUZIONE (di solito P(0))
2. Si dimostra che per ogni numero maggiore di quello prima verificato se è vero P(n) è vero anche P(n+1). Per fare questo dobbiamo assumere vero P(n) (detto IPOTESI INDUTTIVA) e cercare di dimostrare P(n+1) riconducendoci in qualche modo a P(n), di cui possiamo usare le informazioni in quanto vere per ipotesi induttiva.

Per quanto riguarda l’INDUZIONE FORTE, essa si distingue da quella normale perché invece di una singola base d’induzione, possono essercene diverse e non solo si assume per vero P(n) (vedi punto num.2), ma anche tutti i suoi predecessori, cioè P(n-1), P(n-2), e così via.

L’induzione funziona solo sui numeri naturali, poiché essa trova giustificazione e appoggio in due importanti principi che sono presenti, appunto, solo sull’insieme dei naturali: il principio del BUON ORDINAMENTO e l’ESISTENZA DEL PREDECESSORE per ogni numero naturale diverso sa 0.
Il principio del buon ordinamento ci assicura che ogni insieme non vuoto di numeri naturali ha un elemento minimo. Se tale elemento non esiste significa che l’insieme è vuoto.

DIVISIONE CON RESTO

Teorema: per ogni a e per ogni b, se b è diverso da 0, allora esistono due numeri q e r tali che r = a-bq e 0 0}
pongo r = a-bq = min(S), cioè r è l’elemento minimo dell’insieme S. sappiamo che tale elemento esiste grazie al principio del buon ordinamento ( S infatti non è vuoto perché di sicuro a ne fa parte [quando b=0]).
Ora dobbiamo dimostrare che r < b.
Se per assurdo r >= b, esisterebbe un numero p>= 0 tale che r = b + p, quindi dall’uguaglianza r = a-bq : a = b + p + bq; a = p + b(q +1), da cui p= a-b(q+1). Notiamo che allora anche p fa parte dell’insieme S e che p