·   &nb 232j97c sp;    Una formula proposizionale è una TAUTOLOGIA se sostituendo alle variabili proposizionali delle proposizioni qualsiasi si ottiene una proposizione che è SEMPRE VERA.

·   &nb 232j97c sp;    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à)

·   &nb 232j97c sp;    LEGGE DISTRIBUTIVA DELLA CONGIUNZIONE SULLA DISGIUNZIONE: A ^ (B°C) > (A^B)°(A^C)

·   &nb 232j97c sp;    LEGGE DISTRIBUTIVA DELLA DISGIUNZIONE SULLA CONGIUNZIONE:  A°(B^C) > (A°B) ^ (A°C)

·   &nb 232j97c sp;    LEGGI DI DE MORGAN:   ¬(A^B) > ¬A ° ¬B  ¬(A°B) >¬A ^ ¬B

·   &nb 232j97c sp;    LEGGE COMMUTATIVA DELLA CONGIUNZIONE:    A^B > B^A

·   &nb 232j97c sp;    LEGGE COMMUTATIVA DELLA DISGIUNZIONE:   A°B >B°A

PROPOSIZIONI E PREDICATI

·   &nb 232j97c sp;    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.

·   &nb 232j97c sp;    Una FORMULA PREDICATIVA è un'espressione composta formata da predicati proposizioni, variabili, connettivi e parentesi.

·   &nb 232j97c sp;    Una formula predicativa è LOGICAMENTE VALIDA se risulta vera in qualsiasi modo possano essere interpretati i simboli per predicati e proposizioni che vi compaiono.

RELAZIONI

·   &nb 232j97c sp;    Una RELAZIONE BINARIA da A a B è un sottoinsieme R di AxB, ma a noi interessano quelle da A a A.

·   &nb 232j97c sp;    PROPRIETA' DELLE RELAZIONI:

1.   &nb 232j97c sp;  R è RIFLESSIVA se ogni elemento è in relazione con se stesso.

2.   &nb 232j97c sp;  R è transitiva se aRb (si legge "a è in relazione con b") e bRc implica che aRc

3.   &nb 232j97c sp;  R è simmetrica se aRb implica che bRa

4.   &nb 232j97c sp;  R è antisimmetrica se i fatti che aRb e bRa implicano necessariamente che a=b.

·   &nb 232j97c sp;    Una relazione è DI ORDINE se è contemporaneamente RIFLESSIVA, ANTISIMMETRICA E TRANSITIVA.

·   &nb 232j97c sp;    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.   &nb 232j97c sp;  Si verifica la BASE D'INDUZIONE (di solito P(0))

2.   &nb 232j97c sp;  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 <= r < b.

Dimostrazione:

prendiamo un insieme S =

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<r, ma questo contraddice la nostra ipotesi iniziale, cioè che r fosse l'elemento minimo dell'insieme. L'assurdo era infatti che r fosse maggiore o uguale a b, ne concludiamo quindi che r < b.

Teoremi sulla divisione:

·   &nb 232j97c sp;    Se a|b (si legge "a divide b", cioè "b è multiplo di a")  e a|c a|b+c infatti: b = ka c = ha b+c = ka+ha = a(h+k), che è divisibile per a

·   &nb 232j97c sp;    Se a|b e a|c a²| bc infatti: b = ka c =ha bc= kaha = a²kh, che è divisibile per a²

·   &nb 232j97c sp;    Se a e b sono coprimi fra loro e a|bc a|c

·   &nb 232j97c sp;    Se p è un numero primo e p|bc p|b oppure p|c

·   &nb 232j97c sp;    Se a|bc non ne segue che a|b oppure a|c: per esempio 4| 2*2, ma 4 non divide 2!

CRITERIO DI DIVISIBILITA' PER 3 E PER 9

Un numero è divisibile per 3 ( o per 9) se la somma delle cifre che lo compongono, in scrittura decimale, è un numero divisibile per 3 ( o per 9). Infatti ogni numero naturale è congruo alla somma delle cifre che lo compongono in scrittura decimale, sia modulo 3, sia modulo 9.

COUNTING (CALCOLO COMBINATORIO)

PERMUTAZIONI (O ANAGRAMMI)

Una permutazione su un insieme finito A è un ordinamento di A (senza ripetizioni di elementi). Tutte le possibili permutazioni su un insieme di n elementi è n! (n fattoriale), cioè n(n-1)(n-2)(n-3)..1.

Se però voglio scegliere una permutazione composta non da tutti gli elementi dell'insieme considerato si parla di:

DISPOSIZIONI SENZA RIPETIZIONI DI CLASSE r

Il numero di modi di scegliere una disposizione di r elementi scelti da un insieme di n elemento è n!/(n-r)!

DISPOSIZIONI DI CLASSE r CON RIPETIZIONI

Per questo tipo di disposizioni la regola è n elevato alla r perché ogni volta posso scegliere fra tutti gli n elementi presenti nell'insieme ( n*n*n*n..k volte).

COMBINAZIONI

Le combinazioni sono dei sottoinsiemi non ordinati.

La formula per calcolare quante combinazioni di r elementi presi da un insieme con n elementi è il coefficiente binomiale, che equivale a     n!/r!(n-r)!

Perché il coefficiente binomiale funziona per il calcolo delle combinazioni?

La risposta è semplice. Le combinazioni di classe r di n elementi possono essere viste come disposizioni di r elementi, identificando fra loro quelle disposizioni che variano solo per l'ordine degli elementi che le compongono (le combinazioni sono infatti insiemi NON ORDINATI). A loro volta le disposizioni si possono ottenere prima cercando tutte le possibili combinazioni e poi permutandone gli elementi in ogni modo possibile (cioè cambiare l'ordine degli elementi in ciascuna combinazione).

Con questo ragionamento siamo arrivati ad una semplice equazione che ci dice:

D(n,r) = C(n,r)*P(r) n!/(n-r)! = C(n,r)*r!

Da cui: C(n,r) = n!/(n-r)!r!

ORA DIAMO DELLE DEFINIZIONI MIGLIORI:

·   &nb 232j97c sp;    Dati n elementi distinti, si dicono PERMUTAZIONI tutti i possibili raggruppamenti ordinati che contengono tutti gli n elementi e che differiscono fra di loro per la posizione di almeno uno degli n elementi. Tutte le possibili permutazioni sono n!, poiché per la scelta del primo elemento ho n possibilità, per il secondo ne ho n-1, per il terzo n-2 e così via, finchè ho una sola possibilità per l'n-esimo (e ultimo) elemento.

·   &nb 232j97c sp;    Dati ne elementi distinti e un numero naturale k, si dicono DISPOSIZIONI DI CLASSE k tutti i raggruppamenti che si possono formare con gli n elementi dati, in modo che ciascun gruppo contenga k elementi diversi fra loro e che si distingua dagli altri o per almeno un elemento o per l'ordine in cui si susseguono gli elementi. Tutte le possibili disposizioni di classe k sono:  n!/(n-k)! Poiché per il primo elemento ho n possibilità di scelta, per il secondo ne ho n-1 e così via, finchè per il k-esimo (e ultimo elemento della disposizione) ho n-(k-1) possibilità di scelta. NB: quando k = n le disposizioni non sono altro che permutazioni.

·   &nb 232j97c sp;    Dati n elementi distinti, si dicono DISPOSIZIONI CON RIPETIZIONI di classe k quei raggruppamenti formati da k elementi scelti fra gli n dati senza la pretesa che quei k elementi scelti siano tutti diversi fra loro. Le possibili disposizioni di questo tipo sono quindi n elevato alla k poiché per ognuno dei k elementi ho n possibilità di scelta .

·   &nb 232j97c sp;    Dati n elementi distinti, si dicono COMBINAZIONI di classe k quei sottoinsiemi non ordinati formati da k elementi scelti fra gli n elementi dati, in modo che ciascun sottoinsieme si distingua per almeno un elemento. Tutte le possibili combinazioni sono n!/k!(n-k)!