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'AF-FERMAZIONE SI RICORRE A:

• MISURAZIONI
• ESPERIMENTI ➔ SE QUESTI (FATTI DA PIÙ PERSONE/PIÙ VOLTE) CONFERMANOL'AFFERMAZIONE QUESTA VIENE ACCETTATA (ALMENO TEMPO-RANEAMENTE), ALTRIMENTI VIENE RIFIUTATA.
• SIMULAZIONI

IN MATEMATICA (MA ANCHE IN INFORMATICA) QUESTO"METODO SCIENTIFICO" NON FUNZIONA

⇧⇩

NESSUN ESPERIMENTO POTRÀ STABILIRE CHE√2 SIA UNNUMERO RAZIONALE (√2 = m/n CON m,n ∈ ℤ)

CONTROLLARE ALCUNI CASI SPECIFICI PUÒ ESSERE UTILEPER AVERE INDIZI SULLA VERITÀ O MENO DI UN'AF-FERMAZIONE, MA A VOLTE QUESTA POSSONO ANCHEESSERE FUORVIANTI.Esempio: Congettura 3x^2 + 12x + 1₄ NON È MAI UN QUAD-RATO PERFETTO

FALSO ➔ CI SONO INFINITI NUMERI DEL TIPO3x^2 + 12x + 1₄ CHE SONO QUADRATI PERFETTI, MAIL PIÙ PICCOLO HA UN LATO DIAMETRODELLA CIRCONFERENZA.CONTROLLARE A MANO LA CONGETTURA CONSEGUITI NUMICI, CI SPINGE ERRONEAMENTEINPOSITI A CREDERE VERA.

IN MATEMATICA, PER STABILIRE LA VERITÀ DI UN'AFFERMAZIONE ➔ (TEOREMA)SI DEVE RICORRERE AD UNA DIMOSTRAZIONE

CATENA DI RAGIONAMENTO CHECI PERMETTE DI CONCLUDERECHE LA TESI DEL TEOREMA DEVEESSERE VERA PARTENDO DALLASANZIONE CHE LE IPOTESI DELTEOREMA SIANO VERE.

LA STESSA COSA VALE IN INFORMATICA

PER FORNIRE UNA DIMOSTRAZIONE DEL FATTO CHEIL PROGRAMMA FUNZIONA DOBBIAMO MOSTRARE LA SUACOORETENEZA.

Che cos'è un teorema?

Enunciato della forma:

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

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

Sinonimi di teorema: proposizione, lemma

• Dal punto di vista tecnico indicano la stessa cosa.
• La differenza è soggettiva e importanza attribuita da chi parla.
• Teorema: affermazioni veramente importanti e significative.
• Proposizione: meno importanti ma pur sempre abbastanza significative.
• Lemma: da 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_n sono verificate, anche l'affermazione Q risulta essere vera.

Scrittura: P₁, P₂,... P_n => Q

• Q è conseguenza logica di P₁, P₂,... P_n
• P₁, P₂,... P_n 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₁,... P_n, un risultato non compatibile (raramente si vera che falsa impossibile, quindi Q è vera).
• Dimostrazione per comparazione = simile a quella per assurdo si dimostra un teorema del tipo "non Q != non P".
• Dimostrazione per interpolazione = dimostrato il teorema P₁,... P_n => R ed il teorema R => Q, possiamo comporre le due dimostrazioni in "a": P₁,... P_n => Q es. se abc = ac allora ac = c

Espressioni equivalenti all'implicazione:

• "Affinché valga P deve valere anche Q"
• "Affinché valga P è necessario che valga Q"
• "Non può accadere che P valga ma Q no"

Se P allora Q ↓ P → Q

• "Affinché valga P è sufficiente che valga Q"
• "Non appena si sa che Q vale allora anche P deve valere"

Se Q allora P ↓ Q → P

P₁,..., P_m → Q se in ogni contesto in cui tutte le P₁,..., P_m sono vere si ha anche Q vera

• P₁,..., P_m → Q se e solo se
• P₁ ∧...∧ P_m → Q se e solo se
• ∴ P₁ ∧...∧ P_m → Q

Se P → Q non per forza Q → P. → Non è commutativo!

• P → Q ≡ ¬ Q → ¬ P (per doppia negazione e simmetria di &lor;)
• P → Q ≡ ¬ P &lor; Q
• ≡ ¬ Q &lor; ¬ P
• ≡ ¬ Q → ¬ P
• ≡ ¬ Q → P

P → Q ≠ Q → P No commutativo

P → (Q → R) ≠ (P → Q) → R No associato

Se P ≡ R e Q ≡ S, allora P → Q ≡ R → S

• ≡ ¬ P &lor; Q
• ≡ ¬ R &lor; S
• ≡ R → S

Modus Ponens

P → Q, P ∴ Q

Bi-implicazione ↔

Corrisponde all'espressione "... se e solo se ..."

Equivalenza Logica

Esempio

• A → B ≡ (¬A ∨ B) ≡ ¬(A ∧ B)

Su ciascuna riga P e Q hanno lo stesso valore di verità (o entrambe vere, o entrambe false) ⇒ P ≡ Q

Esempio

• A → B ≠ (A ∧ ¬B) ∨ (B → A)

Sulle righe 2 e 3, P e Q hanno diverso valore di verità (una è vera mentre l'altra è falsa) ⇒ P /≡ Q

Tautologie

Una proposizione si dice valida o tautologia se è vera per ogni assegnazione di valore di verità alle lettere che contiene

Esempio

• A ∨ ¬A

Nella colonna finale compaiono solo

esempio FAMIGLIA {A_m m∈ℕ} DI INTERVALLI DI ℝ DOVE A_m = [-1, a_j -2 ]

{ x∈ℝ | -1 < x < 1 -2}

∪_m∈ℕ A_m = [-1, 2[

{x∈ℝ| -1 < x < 2}

∩_m∈ℕ A_m = ∅

[ x∈ℝ | -1 ≤ x ≤ 0}=

...DIFFERENZA ∇

A∖B → INSIEME DI TUTTI GLI ELEMENTI CHE STANNO IN A MA NON IN B

A∖B = {x ∈A / x ∉B}

...DIFFERENZA SIMMETRICA Δ

A△B → INSIEME DI TUTTI GLI ENTI CHE STANNO IN UNO DEI DUE INSIEMI MA NON NELL'ALTRO

A△B = (A∖B)∪(B∖A) = (A∪B)∖(A∩B)

∀x(x∈A△B ⟺ (x∈A∧x∉B)∨(x∈B∧x∉A))

...COMPLEMENTARE C̅

C̅A- Spesso con conveniente assumere che tutti gli insiemi/oggetti/enti di cui ci stiamo occupando siano contenuti in un insieme universale U, detto appunto universo

U∖A = C̅A → C̅A = { x∈U∧ x∉A }

IDENTITÀ BOOLEANE PER LE OPERAZIONI INSIEMISTICHE

C̅C̅A=A → ∀x ( x∈C̅C̅A ⟺ x∈A )

x∈C̅C̅ ⟺ x∈A

¬( x∈C̅A)⟺x∈A Come ¬(¬P)⟺P

Esempio 2

Relazione ∈ su ℕ definita da m ✂️ n se e solo se m e n hanno lo stesso numero di cifre (in notazione decimale)

m, n ∈ ℕ

Riflessività: m ✂️ m perché ogni numero si scrive con lo stesso numero di cifre di se stesso.

Simmetria: m ✂️ n ⇒ n ✂️ m. Se m ha lo stesso numero di cifre di n allora vale anche il viceversa.

Transitività: se m ✂️ n allora entrambi hanno k cifre e inoltre m ✂️ p, ovvero n e p hanno lo stesso numero di cifre quindi anche p ha k cifre allora m ✂️ p.

Classi di equivalenza di ✂️: C_k= {m ∈ ℕ | m ha esattamente k cifre} per k ∈ ℕ \ {0} due cose sempre. C_k: {0, 1, 2, 3}

5, 6, 7, 8, 9 ✂️ C_k = {m ∈ ℕ | 10^k-1 1}

Quante classi distinte otteniamo? Infinitamente, una per ogni k ∈ ℕ \ {0}

Insieme quoziente ℕ/✂️ = {C_k | k ∈ ℕ \ {0}}

Esempio 3

Fin ✂️ = {X ⊂ ℕ | X è finito} ✂️ Consideriamo la relazione ✂️ su Fin definitada X ✂️ Y se e solo se X, Y hanno lo stesso numero di elementi

X, Y, Z ∈ Fin

Riflessività: X ✂️ X ovvio perché ogni insieme ha lo stesso numero di elementi di se stesso.

Simmetria: X ✂️ Y allora X e Y hanno stessa cardinalità quindi Y ✂️ X

Transitività: se X ✂️ Y e X ✂️ Z, Y hanno k elementi e inoltre Y ✂️ Z alloraanche Z ha k elementi quindi X ✂️ Z

Classi di equivalenza I_k = {X ∈ Fin, X ha k elementi} per k ∈ ℕ \ {0, 1, 2}

ogni classe ha infiniti elementi, se k ˃ 1 con k=0 ho un solo elementosono infinite, una per ogni k ∈ ℕ

insieme quoziente Fin/✂️ = {I_k | k ∈ ℕ}