Dipartimento di Informatica - Nessun titolo diapositiva...Congettura di Goldbach (1742) Proposizione...

Progamma sintetico

• Nozioni preliminari

• Automi Finiti

• Macchine di Turing

• Limiti delle macchine di Turing

• La tesi di Church-Turing

• Le classi P e NP

•

Nozioni preliminari

•Conoscenza del significato dei termini:

Definizione, Enunciato, Dimostrazione, Implicazione, Equivalenza,...

• Familiarità con i vari tipi di dimostrazioni:

per contraddizione, prova per induzione, …

• Definizioni delle operazioni logiche AND, OR, NOT.

• Alfabeti

• Stringhe

• Linguaggi

DIMOSTRAZIONE ?

DIMOSTRAZIONE

Metodo per stabilire una verità

DIMOSTRAZIONE


Differente in vari campi

• Legale: giuria – prove processuali

• Scientifica: esperimenti ripetibili

• Filosofica: persuasione basata su argomenti plausibili

DIMOSTRAZIONE


Differente in vari campi

• Legale: giuria – prove processuali

• Scientifica: esperimenti ripetibili

• Filosofica: persuasione basata su argomenti plausibili

Cartesio: “Cogito ergo sum,”

Deriva esistenza dal fatto di pensare sull'esistenza

PROVA Matematica

Una prova formale è una catena di deduzioni logiche che portano ad una affermazione partendo da un insieme di assunzioni

c=cent E=Euro

Assunzione 1E=100c

1 c= 0,01 E=(0,1 E)2=(10c)2=100c=1E

?

Dimostrazione

c=cent E=Euro

1 c= 0,01 E=(0,1 E)2=(10c)2=100c=1E

ERRATA!!

Affermazione

Se a e b sono due numeri reali uguali allora a = 0.

Affermazione


Dimostrazione

Assunzione a=b

Affermazione errata:


Dimostrazione sbagliata:

• Proposizione: affermazione che può essere vera o falsa

• Proposizioni matematiche devono essere formulate in modo preciso

Aldo guarda Beatrice con il binocolo

• Proposizione: affermazione che può essere vera o falsa

• Proposizioni matematiche devono essere formulate in modo preciso

Aldo guarda Beatrice con il binocolo

• Devono riferirsi ad oggetti ben definiti matematicamente (numeri, insiemi, funzioni,...)

• Es. 2 + 3 = 5.

Proposizione: può essere vera o falsa

Dimostrazione: Data una proposizione, vogliamo dimostrare che essa è vera.

Es.Proposizione p(n)=n2+n+41 è numero primo

per ogni n > 1.

Come facciamo?

Es.p(n)=n2+n+41 è primo

per ogni n > 1.

Proviamo per qualche valorep(1)=43 primoP(2)=47 primoP(3)=53 primo

Proviamo per qualche valorep(1)=43 primoP(2)=47 primoP(3)=53 primo…P(20)=461 primo


per ogni n > 1.

Proviamo per qualche valorep(1)=43 primoP(2)=47 primoP(3)=53 primo…P(20)=461 primo…P(39)=1601 primo

VERA?


per ogni n > 1.


P(40)=40x40+40+41=41x41 FALSO!


per ogni n > 1.


P(40)=40x40+40+41=41x41 FALSO!


per ogni n > 1.

Dimostrazione per esempi=

Esempio di dimostrazione sbagliata

Es.Proposizionea4 +b4 +c4 = d4 non ha soluzione con a, b, c, d interi positivi

Congettura di Eulero del 1769. Dimostrata FALSA 218 anni dopo da Noam Elkies:

a = 95800; b = 217519; c = 414560; d = 422481.

Es.Proposizione313(x3 +y3 ) = z3

non ha soluzione con x,y,z interi positivi

FALSA:controesempio più piccolo ha più di 1000 digit!

Es.Congettura di Goldbach (1742)

Proposizione P(n): n si può scrivere come somma di due primi

per ogni n>2 ?

Non possimo stabilire VERO provando per un numero finito di valori!

Servono altri metodi!

Es.Congettura di Goldbach (1742)

Proposizione P(n): n si può scrivere come somma di due primi

per ogni n>2 ?

Proposizione: affermazione che può essere può essere vera o falsa

Dimostrazione: Data una proposizione, vogliamo dimostrare che essa è vera.

Proposizione P: vera (T) o falsa (F)

Operazioni Logiche: NOT, OR, AND

Tavole di verità:

Implicazioni: Deduzioni logiche per provare nuove proposizioni a partire da altre note (vere)

• P Q(P implica Q: se P è vera allora Q e' vera )


• P Q(P implica Q: se P è vera allora Q è vera )

Es. “Se gli asini volano, allora voi capirete questa lezione.”E’ un insulto?


• P Q(P implica Q: se P è vera allora Q e' vera )

Es. “Se gli asini volano, allora voi capirete questa lezione.”E’ un insulto?Nel linguaggio comune: SiMatematicamente è un affermazione vera!


• P Q(P implica Q: se P è vera allora Q è vera )

Es. “Se gli asini volano, allora voi capirete questa lezione.”E’ un insulto?Nel linguaggio comune: SiMatematicamente è un affermazione vera!

PQ è vera ogni volta che P è falsa o Q è vera

Deduzioni logiche: per provare nuove proposizioni a partire da altre note (vere)

• (P vera, P Q) Allora Q Vera

Es. • P: la vittima è stata uccisa nella vasca da bagno e

ritrovata sul letto• Q: l’omicida ha abbastanza forza da spostare un

cadavere• PQ: se la vittima è stata spostata allora l’assassino ha

abbastanza forza da spostare un cadavere• (P vera, PQ) l’omicida è ‘’forte’’


• (P vera, P Q) ALLORA Q vera

• (P Q; Q falsa) ALLORA P?

Es. • P: la vittima è stata uccisa nella vasca da bagno e

ritrovata sul letto• Q: l’omicida ha abbastanza forza da spostare un

cadavere; Q falsa: l’omicida è debole• PQ: se la vittima è stata spostata allora l’assassino ha

abbastanza forza da spostare un cadavere• (PQ, Q falsa) Il cadavere non può essere stato

spostato


• (P vera, P Q) ALLORA Q vera

• (P Q; Q falsa) ALLORA P Falsa

Deduzioni logiche

• NOT(Q) NOT(P)

Equivalente a PQEs. • P: la vittima è stata uccisa nella vasca da bagno e

ritrovata sul letto• Q: l’omicida è abbastanza ‘’forte’’; • PQ: se la vittima è stata spostata allora l’assassino ha

abbastanza forza da spostare un cadavere• NOT(Q) NOT(P): Se l’omicida non è abbastanza forte

allora la vittima non è stata spostata

Deduzioni logiche

• NOT(Q) NOT(P)

Equivalente a PQ

• NOTA: NOT(P) NOT(Q) NON EQUIVAL. P Q: Es. • P: la vittima è stata uccisa nella vasca da bagno e

ritrovata sul letto• Q: l’omicida è ‘’forte’’; • PQ: se la vittima è stata spostata allora l’assassino ha

abbastanza forza da spostare un cadavere• NOT(P) NOT(Q): Se la vittima non è stata spostata

allora non è vero che l’omicida deve essere forte

Come dimostrare che P Q:1. “Assumiamo P.”2. mostriamo che Q segue

Come dimostrare che P Q:1. “Assumiamo P.”

2. mostriamo che Q segue

Es.Se 0<x<2, allora -x3 + 4x + 1 > 0.

Dim. Assumiamo 0 < x < 2.

Come dimostrare che P Q:1. “Assumiamo P.”

2. mostriamo che Q segue

Es.Se 0 < x < 2, allora -x3 + 4x + 1 > 0.

Dim. Assumiamo 0 < x < 2

Scriviamo -x3 + 4x = x(2 - x)(2 + x)Sappiamo che x, 2 - x, e 2 + x nonnegativi ( >0 ). Allora il loro prodotto è nonnegativo (>0). Sommando 1 abbiamo numero positivo (>0):

-x3 + 4x+1= x(2 - x)(2 + x) + 1 > 0.

“P IFF Q”

equivale a

“P Q” AND “Q P”.

“P IFF Q”

equivale a

“P Q” AND “Q P”.

Provare “iff” :

1. “Proviamo che P implica Q e vice-versa.”

2.“Per prima cosa, mostriamo che

P implica Q.” (Come prima)

3. “Secondo passo, mostriamo che Q

implica P.” (Come prima)

Dimostrazione per contraddizione

per dimostrare P

Schema:

1.Assumiamo che l’ipotesi P è falsa

2.Dimostriamo che NOT(P) NOT(Q) per qualche Q che sappiamo essere vera

3.A questo punto abbiamo una contraddizione e possiamo concludere che P deve essere vera

Teorema. La radice quadrata di 2 è un numero irrazionale.

Dim.

Assumiamo che ipotesi P è falsa, cioè

NOT(P): sqrt(2)=m/n (m,n interi primi fra loro)

Dimostriamo NOT(P) NOT(Q) [Q: m, n primi tra loro]


Dim.

Assumiamo che ipotesi P è falsa, cioè

sqrt(2)=m/n (m,n interi primi fra loro)


m2 =(n sqrt(2))2=n22 m2=2n2 m2 pari m pari,


Dim.

Assumiamo che l’ipotesi P è falsa, cioè




Poniamo m=2k

Allora 2n2= m2= 4k2 n2=2k2

n pari


Dim.





Poniamo m=2k


n pari

Abbiamo che n,m entrambi pari m,n hanno fattore comune 2


Dim.





Poniamo m=2k


n pari

Abbiamo che n,m entrambi pari m,n hanno fattore comune 2

A questo punto abbiamo NOT(Q)

possiamo dedurre che P è falsa (cioè sqrt(2) è irrazionale)

Teorema.

La radice quadrata di 2 è un numero irrazionale.

Dim.

Assumiamo che l’ipotesi è falsa, possiamo scrivere

a) sqrt(2)=m/n

b) con m,n interi primi fra loro

Abbiamo

• m2 =(n sqrt(2))2=n22 m2=2n2 m2 pari m pari,

• Ponendo m=2k si ha 2n2= m2= 4k2 n2=2k2

n pari

Quindi n,m entrambi pari m,n hanno fattore comune 2

che contraddice punto b)

possiamo concludere che sqrt(2) è irrazionale.

Dimostrazioni Corrette in Pratica• Definire il metodo che si vuole seguirees. “Usiamo un distinzione di casi” o

“Ragioniamo per assurdo.”

• Una dimostrazione e` un “saggio” non un calcolo

Approccio errato: sequenza di espressioni senza commenti

Una dimostrazione comprensibile e` un “saggio” inframmezzato da calcoli

Buone dimostrazioni Buoni programmi

Stesso rigore necessario per scrivere programmi funzionanti

• Programma che ''sembra funzionare'' puo` causare molti problemi

Buone dimostrazioni <=> Buoni programmi

Stesso rigore necessario per scrivere programmi funzionanti

• Programma che ''sembra funzionare'' può causare molti problemi

• Es. Therac 25: macchina per radioterapia che ''ogni tanto'' ha ucciso i pazienti per eccesso di radiazioni (problema software)

• Es. (Agosto 2004) problema software usato da United e American Airlines ha messo a terra l'intera flotta delle due compagnie

Buone dimostrazioni Buoni programmi

• Es. Errori di commutazione nei computer di gestione delle chiamate della AT&T rendono inutilizzabile per nove ore la rete interurbana e interstatale statunitense della societa’.

• Es. Il vettore Ariane 5 esplode al decollo. Il 4 giugno 1996 viene lanciato per la prima volta il vettore Ariane 5. Dopo 39 secondi di volo interviene il sistema di autodistruzione, trasformando l’Ariane 5 e il suo carico pagante (quattro satelliti scientifici non assicurati) in quello che e’ stato definito “il piu’ costoso fuoco d’artificio della storia”.Il disastro avviene perche’ un programma del sistema di navigazione tenta di mettere un numero a 64 bit in uno spazio a 16 bit.

INDUZIONE

Data una affermazione, vogliamo dimostrare che essa vale per ogni intero n>a.

Es.La somma dei primi n interi vale n(n+1)/2per ogni n > 1.

INDUZIONE

Vogliamo dimostrare che un certo predicato è vero.

• Formaliziamo con affermazione S(n) • dimostriamo per induzione che S(n) vera

(per ogni intero n>a).

Una dimostrazione per induzione consiste di 2 fasi

1. BASE INDUTTIVA. Si dimostra che l’affermazione è vera per il primo valore, cioè S(a) è vera.

1. PASSO INDUTTIVO. Assumiamo che S(n-1) è vera e dimostriamo che allora anche S(n) è vera.

INDUZIONE

Formalizzazione

S(n):

Si vuole dimostrare per induzione che S(n) vale per ogni n > 1.

Es.La somma dei primi n interi vale n(n+1)/2per ogni n > 1.

2/)1(...211

nnnin

i

INDUZIONE

1. BASE INDUTTIVA. S(a) è vera.2. PASSO INDUTTIVO. S(n-1) implica S(n) vera.

Es.S(n):

Si vuole dimostrare che S(n) vale per ogni n > 1.

2/)1(...211

nnnin

i

INDUZIONE


Es.S(n):


Base. S(1) è vera perché

2/)1(...211

nnnin

i

2/)11(111

1

i

i

INDUZIONE


Es.S(n):



Passo. Ipotesi induttiva S(n-1):

2/)11(111

1

i

i

2/)1(1

1

nnin

i

2/)1(...211

nnnin

i

INDUZIONE


Es.S(n):



Passo. Ipotesi induttiva S(n-1):

Si ha

Quindi S(n) è vera.

2

)1(

2

2)1(

2

)1(1

11

nnnnnn

nnnii

n

i

n

i

2/)1(...211

nnnin

i

2/)11(111

1

i

i

2/)1(1

1

nnin

i

INDUZIONE

Esercizio.

Dimostrare per induzione che la seguente affermazione S(n) è vera per ogni intero n>0.

S(n):

2i

i0

n

2n1 1

INDUZIONE

Es. Se x≥4, allora 2x ≥x2

•Affermazione S(x): 2x ≥x2

•Mostriamo per induzione che S(x) vera per ogni x≥4.

Base: x = 4 ⇒ 2x = 24 = 16 e x2 = 42 = 16

Passo I.: Supponiamo che 2x ≥x2 per x ≥ 4 Dobbiamo dimostrare che 2x +1 ≥ (x + 1)2

Abbiamo: 2x +1 = 2 2x ≥ 2 x2 (dalla ipotesi induttiva)

Dimostriamo adesso che 2x2 ≥ (x + 1)2=x2+1+2xSemplificando: x2-2x ≥ 1Se x ≥ 4, x(x-2) ≥ 8>1

VALIDITA’ delle dimostrazioni per INDUZIONE

Dim. per induzione S(n) vera, ogni n>aBase: S(a) vera

Passo induttivo

Minimo controesempio. IPOTESI: S(n) falsa per qualche n.Sia b il più piccolo intero tale che S(b) falsa.



Passo induttivo

Minimo controesempio. IPOTESI: S(n) falsa per qualche n.Sia b il più piccolo intero tale che S(b) falsa.DEDUCIAMO:Se b=a contraddiciamo la base. Quindi b>a.



Passo induttivo


Essendo b = minimo intero per cui l’affermazione è falsa, risulta S(b-1) vera (nota b-1 > a).Per il Passo Induttivo, S(b-1) S(b).

Allora S(b) vera



Passo induttivo



Allora S(b) vera: contraddizione con assunzione che S(b) falsa. Quindi ipotesi è sbagliata



Passo induttivo

PER CONTRADDIZIONE IPOTESI: S(n) falsa per qualche n.Sia b il più piccolo intero tale che S(b) falsa.DEDUCIAMO:Se b=a contraddiciamo la base. Quindi b>a.


Allora S(b) vera: contraddizione con assunzione che S(b) falsa. Quindi ipotesi è sbagliata,Cioè non esiste intero per cui l’affermazione è falsaCioè S(n) vera per ogni intero

Teorema. Tutti i cavalli hanno lo stesso colore

Dim. Sia P(n): ''in ogni insieme di n cavalli, tutti i cavalli hanno lo stesso colore.''

Mostriamo per induzione che P(n) vera per ogni n ≥ 1.

Base : P (1) vera.

Passo. Assumiamo P (n) vera, n>1.

Consideriamo insieme di n + 1 cavalli:h1 , h2 , . . . , hn , hn+1




Base : P (1) vera.



Per I.I. I primi n cavalli h1 , h2 , . . . , hn hanno stesso colore,

Per I.I. Gli ultimi n cavalli h2 , h3 , . . . , hn+1 hanno stesso colore,




Base : P (1) vera.



Per I.I. I primi n cavalli h1 , h2 , . . . , hn hanno stesso colore,

Per I.I. Gli ultimi n cavalli h2 , h3 , . . . , hn+1 hanno stesso colore,

Quindi h1 , h2 , . . . , hn+1 hanno stesso colore, e P(n+1) vera

Poiche` P (n) P (n + 1), allora P(n) vera per ogni n ≥ 1.


Dim. Per induzione su n. Sia P(n): ''in ogni insieme di n cavalli, tutti i cavalli hanno lo stesso colore.''

Conseguenza: se n=(numero cavalli nel mondo)

allora tutti cavalli hanno lo stesso colore.



Conseguenza: se n=(numero cavalli nel mondo) allora tutti cavalli hanno lo stesso colore.

Abbiamo provato una cosa FALSA!

ERRORE?



Conseguenza: se n=(numero cavalli nel mondo) allora tutti cavalli hanno lo stesso colore.

Abbiamo provato una cosa FALSA!

ERRORE?

Abbiamo provato:P (1) P (2) P (3), P (3) P (4), etc.

NON P (1) P (2)

INDUZIONE COMPLETA

Vogliamo dimostrare che P(n) vale per ogni intero n>a.

Dimostrazione per induzione completa:

1. BASE INDUTTIVA. Si dimostra che l’affermazione è vera per il primo valore, cioè P(a) è vera.

2. PASSO INDUTTIVO. Assumiamo che P(a), P(a+1),…, P(n-1)

sono tutte vere e dimostriamo che anche P(n) è vera.

Teorema. Ogni intero maggiore di 1 è un prodotto di primi

Dim. Stabiliamo affermazioneP(n): l’intero n è un prodotto di primiVogliamo dimostrare per induzione completa che p(n) vera per ogni n>1.



Base. P(2) vera, poichè 2 è primo



Base. P(2) vera, poichè 2 è primoPasso. II: p(2),…,p(n-1) vere

Proviamo che P(n) è vera.



Base. P(2) vera, poichè 2 è primoPasso. II: p(2),…,p(n-1) vere

Proviamo che P(n) è vera.Se n è primo, okSe n non è primo allora n=km per qualche k e mII ci dice che P(k), p(m) vere,Cioè k ed m sono prodotti di primiQuindi anche il loro prodotto n=km è un prodotto di primi.

Definizioni Induttive

;Una definizione per induzione (o induttiva o ricorsiva)di un insieme di oggetti consiste di una base e di un passo induttivo.

BASE definisce uno o più oggetti elementari. Passo Induttivo definisce la regola che permette di costruire oggetti più complessi in termini di quelli già definiti


;


Es. Definizione induttiva di n! (prodotto primi n interi)

BASE 1!

P.I. n!=n (n-1)! Per ogni n>1


;


Es. Definizione dei numeri di fibonacci

BASE f(0)=f(1)=1

P.I. f(n)=f(n-1)+f(n-2), per ogni n>1

Definizioni Induttive e Dimostrazioni Induttive

;

Es. Mostrare che il numero di fibonacci f(n) soddisfa

f(n)<2n, per ogni n>0

Definizioni Induttive e Dimostrazioni Induttive

;

Dimostrare che il numero di coppie (x,y) con x<y scelti tra 1 ed n è n(n-1)/2

Dipartimento di Informatica - Nessun titolo diapositiva...Congettura di Goldbach (1742) Proposizione...

Documents

Transcript of Dipartimento di Informatica - Nessun titolo diapositiva...Congettura di Goldbach (1742) Proposizione...