linguaggi naturali e linguaggi formali sistemi formali
TRANSCRIPT
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!