Linguaggi  naturali e

linguaggi formali

Sistemi formali  

I linguaggi  naturali  

• All’origine dei linguaggi naturali vi è la necessità di comunicare concetti in modo comprensibile .

• Il primo passo è attribuire un significato ad una forma, sia essa  un disegno, un suono o una

parola.

Per esempio per individuare il significato di

cane

posso disegnare un cane    

 ascoltare l’abbaiare di un cane  

O il suo ansimare

o scrivere la parola   

cane

Nel linguaggio naturale si distinguono quindi

forma e significato

successione di caratteri che formano le parole e successioni di parole che, unitamente a regole

( la sintassi ), diventano frasi

forma

significato

interpretazione che si attribuisce alla forma (la semantica)

Per scrivere una parola usiamo i caratteri (l’alfabeto della lingua italiana) ma li uniamo in modo univoco per non incorrere in ambiguità

• C a n e ma anche

• C e n a

con significato diverso o anche

• N e c a oppure

• N a c e

che non hanno significato

Senza spazi tra le parole l’ambiguità sarebbe ancora maggiore :

Leggiamo questa successione di caratteri :

FUNICOLAREDINAPOLI

che può essere interpretata come :

FUNICOLARE DI NAPOLI

ma anche

FU NICOLA RE DI NAPOLI

Un uso misto di immagini e caratteri non è sicuramente adatto per una comprensione immediata di una frase

E’ il caso dei rebus dove immagini e caratteri messi nel modo corretto portano ad una frase di senso compiuto

Rebus

Dif lto m

Che appunto spesso risulta una

difficoltosa impresa

Così come concateniamo le parole tra loro per comporre una frase utilizzando regole di sintassi

Il libro sulla televisione

E’ una frase con una sintassi corretta ma un significato ambiguo

E’ un libro che parla di televisione o è un libro che è stato poggiato sulla televisione?

Il linguaggio naturale è spesso ambiguo

Per superare l’ambiguità occorre il contesto della

frase :

• Guarda che hai lasciato il libro sulla televisione

• Il libro sulla televisione che ho letto non mi è piaciuto.

Ora tutto è chiaro!

RidondanzaIl linguaggio naturale è spesso

ridondante: lunghe perifrasi per un semplice concetto:

…. Mi sia consentito di esprimere in questa sede e davanti a tale consesso di professori il mio sia pur inesperto pensiero..

Traduzione “io penso”

Superamento • Uso di una sintassi rigorosa• Schematizzazione

Autoreferenza nel linguaggio naturale

• Linguaggio che “parla”di se stesso• Frasi• Immagini• Situazioni• Funzioni e procedure (in informatica si chiama ricorsività)

Frasi autoreferenti

Problema n.1La proposizione “Questa frase è falsa “ è vera o falsa?

Soluzione problema n.1

Se la proposizione “Questa frase è falsa “ è vera. allora afferma il vero ossia che la

frase è falsa contraddizione

Se la proposizione “Questa frase è falsa “ è falsa, non è vero che la frase è falsa e quindi la frase è vera

contraddizione

Problema n.2

Su di un foglio vi sono le seguenti proposizioni:

“ Alice non esiste “ “Entrambe queste proposizioni

sono false “Lo sapevi che Alice non esiste? Perché ?

Soluzione problema n.2

Se la 2) è vera allora la 2) è falsa contraddizione Se la 2) è falsa allora è falso che la 1) e la

2) siano entrambe false quindi almeno una delle due è vera e non potendo essere vera la 2), essendo falsa per ipotesi, allora è vera la 1) e quindi

Alice non esiste

1) “Alice non esiste “ 2) “Entrambe queste proposizioni sono false “

Immagini autoreferenti

Mani che disegnano di M.C.Escher

Schematizziamo

Come superare l’autoreferenza?

La mano di Escher disegna

Mano con sfera riflettente di M.C.Escher 1935

Autoreferenza

Superamento dell'autoreferenza

Situazioni autoreferenti:i tre scrittori

• X , Y e Z sono 3 scrittori• X scrive di Y• Y scrive di Z• Z scrive di X

Superamento

Funzioni ricorsive n! n! = 1x2x3x4x….x(n-1)xn

n! = (n-1)!xn

il fattoriale di un numero n è una funzione ricorsiva               

I numeri di Fibonacci

1 , 1 , 2 , 3 , 5 , 8 , 13 ......

fibo(1)=1 fibo(2)=1 fibo(n) = fibo(n-1) + fibo(n-2 )Per n >2 Funzione ricorsiva

I numeri di Padovan

1  1   1  2  2   3  4  5  7  ... 

P(1)=1 P(2)=1 P(3)=3

P(n) = P(n-3)+ P(n-2)Per ogni n >3 Funzione ricorsiva

I frattaliLa curva di Koch , classico

esempio di oggetto frattale , dalla proprietà di essere autoreferente , proprietà che in geometria si chiama autosomiglianza ,e che si disegna utilizzando procedure ricorsive.

La curva di Koch è costruita partendo da un triangolo equilatero .

Si divide il lato in tre parti uguali e su ogni lato, nella parte centrale, si disegna un 

nuovo triangolo equilatero di lato l/3. Si ripete il procedimento su ogni segmento

Ad ogni passo il contorno diventa più frastagliato

Altri esempi di oggetti autoreferenti

Triangolo di Sierpinski Fiocco di neve

Un lato della curva di Koch

Esercizi

Riconoscere funzioni ricorsive

I numeri naturali

n

n = (n-1) +1 per n>1

(Banale!!!)

I numeri pari

2n

2n = 2(n-1) +2

Ogni numero pari è dato dal numero pari precedente +2

I numeri dispari

n 2n+1 n-1 2(n-1) +1

I numeri dispariricorsività

n 2n+1 n-1 2(n-1) +1 2n+1 = 2n+1-2+2 =(2n-2)+1+2= =(2(n-1)+1)+2

Ogni numero dispari è dato dal numero dispari precedente +2

La potenza an

Ogni potenza è dato dalla potenza precedente moltiplicata per a

an = an-1 a

I numeri triangolari 1 3 6 10 15 ….Ottenuti sommando 1+ 2+ 3+ 4+ 5+ ..

T(1)=1 T(2)=1+2=3 T(3)=1+2+3=6 T(4)=1+2+3+4=10

T(5)=1+2+3+4+5+=15 T(n) = T(n-1) + n

I numeri quadrati

1 4 9 16

Si ottengono sommando i numeri dispari 1 3 5 7 …Q(1)=1 Q(2)=1+3=4 Q(3)=1+3+5=9

Q(4)=1+3+5+7=16 Q(n+1) = Q(n) +2n+1

Numeri triangolari e quadrati

I numeri tetraedrici(piramidali a base triangolare)

1 4 10 20 35

Ottenuti sommando i numeri triangolari 1 3 6 10 15 P(1)=1 P(2)=1+3=4 P(3)=1+3+6=10

P(4)=1+3+6+10=20 P(5)=1+3+6+10+15=35 P(n) = P(n-1) +T(n)

I numeri tetraedrici(piramidali a base

triangolare)

1 4 10 20 35Ma anche P(n) = n(n+1)(n+2)/6

P(n+1) = (n+1) ( n+1+1)(n+1+2)/6=(n+1)(n+2)(n+3)/6=

= n(n+1)(n+2)(n+3)/n6= P(n)(n+3)/n P(n+1)=P(n)(n+3)/n Esempio 35=

20(4+3)4=20x7/4=35

I numeri piramidali a base quadrata

1 5 14 30

Si ottengono sommando i numeri quadrati 1 4 9 16 P(1)=1 P(2)=1+4=5 P(3)=1+4+9=14

P(4)=1+4+9+16=30

P(n)=P(n-1) + Q(n)

Numeri piramidali

I linguaggi formali  

Eliminando

• Ambiguità• Ridondanza• Autoreferenza proviamo a…..

costruire un linguaggio formale

stabilendo l’alfabeto, la sintassi ossia le regole e la stringa iniziale ( l’assioma )

• Alfabeto: A={ I , + , = }

• La stringa di partenza I + I = II (assioma)• Le regole 1) da x + y = z posso dedurre

xI + y = zI 2) da x + y = z posso dedurre y + x = z ( dove x e y sono stringhe di I)

• Ogni stringa ottenuta dall’applicazione di una regola è una stringa ammessa (formula ben formata fbf)

• Ogni fbf dedotta mediante regole da altre fbf è un teorema

• L’insieme delle stringhe ammesse forma il linguaggio

Esercizio

dimostrate passo passo che

IIII + III = IIIIIII

x I+Y= Z I

Se x + y = z

1° regola

I + I = II assiomaII + I = III regola 1)III + I = IIII regola 1)IIII + I = IIIII regola 1)I + IIII = IIIII regola 2)II + IIII = IIIIII regola 1)III + IIII = IIIIIII regola 1)IIII + III = IIIIIII regola 2)

Soluzione

Come si può vedere questo linguaggio formale fa parte di un

Sistema Formale

Sistemi formaliSistemi formaliSistemi formaliSistemi formali

Un sistema formale è una quadrupla (A,L,S,P) dove :

• A alfabeto ( insieme numerabile di simboli)

• L linguaggio ( insieme di formule ben formate fbf)

• S insiemi di assiomi (sottoinsieme di L)

• P regole di produzione (regole di inferenza che permettono di dedurre formule ben formate da formule ben formate(teoremi))

L’esercizio precedente non è altro che l’insieme dei numeri naturali N con l’operazione interna +

(N , +)

• Alfabeto: A= { I , + , = }

• La stringa di partenza I + I = II (assioma)• Le regole 1) da x + y = z posso

dedurre xI + y = zI 2) da x + y = z posso dedurre y + x = z ( dove x e y sono stringhe di I)

Interpretazione dei simboli

• I 1• II 2• III 3• IIII 4• IIIII 5• + è l’addizione• = è l’uguaglianza

• L’assioma è la somma di 1 + 1 =2

• La regola 1) : se la somma di due numeri naturali x e y è

un numero naturale ( l’addizione è l’operazione interna e N è chiuso

per l’addizione + ) allora la somma del successivo di x e di y è il successivo di z• La regola 2) è la proprietà commutativa

L’esercizio proposto

IIII + III = IIIIIII

era quindi dimostrare che

4 + 3 = 7

Il sistema pg

A ={-,p,g}

L : insieme dei teoremi e assiomi

S :infiniti assiomi del tipo

x p – g x -

P : se è un teorema

allora è un teoremax p y g z

x p y – g z -

Regola

Se x p y g z allora

x p y - g z -

Esercizio

1. Scrivere il primo assioma2. Scrivere i primi 5 assiomi3. Applicare la regola al 3° assioma4. ---p---g--- è o no un teorema ?5. ----p-----g--------- è o no un teorema ?

Esercizion n.1

1. Scrivere il primo assioma x p – g x - - p - g - -

Esercizio n. 2Scrivere i primi 5 assiomi

x p – g x - 1. -p-g-- 2. --p-g--- 3. ---p-g----4. ----p-g-----5. -----p-g------

Esercizio n.3

Applicare la regola xpygz xpy-gz- al 3° assioma ---p-g---- poichè x pyg z x py-g z- ---p-g---- allora ---p--g----- applicando la regola

Esercizio n.4 ---p---g--- è o no un teorema ?

Da –p-g-- assioma --p-g--- assioma ---p-g---- assioma applicando la regola x p y g z x p y - g z - si ottiene --- p – g ---- --- p -- g-----Riapplicandola --- p-- g----- ---p --- g------ quindi ---p --- g------ per cui ---p --- g--- non è un teorema

La risposta è no

Esercizio n.5

----p-----g--------- è o no un teorema ?

-p- g-- --p- g--- ---p- g--------p- g---------p-- g------ applicando la regola x p y g z x p y- g z-----p--- g------- applicando la regola----p---- g-------- applicando la regola----p----- g--------- applicando la regola

Quindi ----p-----g--------- è un teorema

Avete decodificato il sistema pg?

- 1 p +-- 2 g =--- 3 quindi il sistema è (N+)---- 4----- 5 ma è l’unica interpretazione?

2° interpretazione - p - g - - 1° assioma 1 = 1 sottratto da 2--p - g --- 2° assioma2 = 1 sottratto da 3 mentre la regola si tradurrà come: --p-- g ---- allora –-p--- g -----Se 2=2 sottratto da 4 allora 2 = 3 sottratto da 5

quindi- 1 P =-- 2 g sottratto da --- 3---- 4----- 5 anche questa

interpretazione è corretta

• Un sistema formale può avere più interpretazioni

Ancora un esempio

Alfabeto A { I , ∙ , = }L’assioma I ∙ I = ILe regole 1) da x ∙ y =z posso

dedurre ???????????????? 2) da x ∙ y =z posso dedurre ???????????????? (x,y,z stringhe di I)

Completare le regole

in modo che

III ∙ II = IIIIII

SoluzioneRegola 1) da x∙y=z posso dedurre xI ∙y = zyRegola 2) da x∙y=z posso dedurre y∙x=z

Costruiamo le stringhe• I∙I = I assioma• II∙I =II regola 1) da x∙y=z si deduce xI ∙y = zy • III∙I = III regola 1)• I∙III =III regola 2)• II∙III = IIIIII regola 1)• III∙II = IIIIII regola 2)

ecco quindi III∙II = IIIIII

Interpretazione

I 1 ∙ moltiplicazione

II 2 = uguaglianzaIII 3IIII 4IIIII 5

quindi• 1x1 = 1• 2x1 = 2• 3x1=3• Se axb=c (a+1)xb = axb + b = c

+ b• Se axb=c bxa=c

Alcuni alfabeti• Calcolo algebrico {a,b,c,..,+,-,x,/..}• Numerazione romana {I,II,III,V,X,L,C,D,M}Calcolo degli enunciati {p,q,..,v, ,

…}

Il gioco del MU

Alfabeto A={M,I,U}Assioma MI

1° regola se una stringa finisce per I a essa si può aggiungere U …..I …..IU2° regola se Mx allora Mxx

3° regola ….III…. …U…

4° regola ….UU… …..

x è una stringa di I e U

Domanda

• Si può costruire la stringa MU ?

• Proviamo a giocare

MI

MIU MII

MIUIU

MIUIUIU

MIUIUIUIU

MIIU MIIII

MIIUIIU MIU

MUI

MIIIIIIII

MIIIIU

La successione di IU dopo M si ripete all’infinito

Anche qui dopo Msi ripete la successione diIIU

In ogni caso il numerodi I non è mai 3 o multiplo di 3 e quindi non può essere eliminato per diventare MU

1 2

2

2

2

1

2

2

3

3

2

1

MUI

MUIU MUIUI

MUIUUIU

MUIIU

MUIIUUIIU

MUIIIIU

MUUIU

MIUSi ritorna a MIU

Analizzando il ramo MUI

MUIUI

MUIUIU MUIUIUIUI

MUIUIUUIUIU

MUIUIIUIU

MUIUIIUIUUIUIIUIU

MUIUIIUIIUIIUIU

In ogni caso il numerodi I non è mai 3 o multiplo di 3 e quindi non può essere eliminato per diventare MU

Analizzando il ramo MUIUI

concludendoCon un ragionamento al di fuori

delle regole del gioco siamo in grado di dire che

non si può costruire

MU

Quello che abbiamo utilizzato è un

modo intelligente di ragionare

Una macchina che volesse risolvere il problema potrebbe fare solo, mediante un opportuno programma :

• Acquisire una stringa • Verificare che sia fbf (ossia formata da Mx con

x stringa di I e U)• Applicare le 4 regole per arrivare a ottenere

MU In realtà la macchina entrerebbe in un loop

infinito non riuscendo a costruire MU oppure

• Potrebbe produrre tutte le stringhe che si ottengono applicando le 4 regole.

• Sarebbe quindi un costruttore di stringhe

• Comunque una macchina può solo applicare le regole e non ragionare per dedurre se il ragionamento porterà alla conclusione desiderata.

Questo è un ragionamento meccanico

Un teorema è deducibile se esiste una dimostrazione basata sull’applicazione delle regole

Un teorema è decidibile se esiste una procedura che consente di decidere se esso è deducibile

• Il primo è un processo meccanico all’interno del sistema

• Il secondo è un processo intelligente

all’esterno del sistema e questo è lasciato agli studiosi!