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
forma
successione di caratteri che
formano le parole e successioni di
parole che, unitamente a regole
( la sintassi ), diventano frasi
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
• C
e
n
n
e
ma anche
a
con significato diverso
o anche
• N e
• N
c a
oppure
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!
Ridondanza
Il 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.1
La 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
1) “Alice non esiste “
2) “Entrambe queste proposizioni sono false “
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
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
P(1)=1 P(2)=1 P(3)=3
P(n) = P(n-3)+ P(n-2)
Per ogni n >3
Funzione ricorsiva
7 ...
I frattali
La 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
n-1
2n+1
2(n-1) +1
I numeri dispari
ricorsività
n
n-1
2n+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(4)=1+3+6+10=20
P(3)=1+3+6=10
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
Ma anche
P(n) = n(n+1)(n+2)/6
20
35
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
1° regola
Se
x + y = z
x I +Y= Z I
Soluzione
I + I = II
assioma
II + 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)
Come si può vedere questo linguaggio
formale fa parte di un
Sistema Formale
Sistemi 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
• Le regole
I + I = II
(assioma)
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
L
={-,p,g}
: insieme dei teoremi e assiomi
S
:infiniti assiomi del tipo
xp–gx-
P
:
se
x p y g z
allora
è un teorema
x p y – g z -
è un teorema
Regola
Se x p y g z
xpy
allora
- gz -
Esercizio
1.
2.
3.
4.
5.
Scrivere il primo assioma
Scrivere i primi 5 assiomi
Applicare la regola al 3° assioma
---p---g--- è o no un teorema ?
----p-----g--------- è o no un teorema ?
Esercizion n.1
1. Scrivere il primo assioma
xp–gx-p- g--
Esercizio n. 2
Scrivere i primi 5 assiomi
xp–gx1.
2.
3.
4.
5.
-p-g---p-g-----p-g-------p-g---------p-g------
Esercizio n.3
Applicare la regola xpygz
xpy-gzal 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
si ottiene
--- p – g ---Riapplicandola
--- p-- g----quindi
x py- gz--- p -- g-------p --- g------
---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
----p--- g------- applicando la regola
----p---- g-------- applicando la regola
----p----- g--------- applicando la regola
Quindi ----p-----g--------- è un teorema
x p y- g z-
Avete decodificato il
sistema pg?
1
-2
--- 3
---- 4
----- 5
p +
g =
quindi il sistema è (N+)
ma è l’unica interpretazione?
2° interpretazione
-pg
-1° assioma
1 = 1 sottratto da 2
--p g
--- 2° assioma
2 = 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
-- 2
--- 3
---- 4
----- 5
P
g
=
sottratto da
anche questa
interpretazione è corretta
• Un sistema formale può avere più
interpretazioni
Ancora un esempio
Alfabeto
L’assioma
Le regole
A{I,∙,=}
I∙I=I
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
Soluzione
Regola 1) da x∙y=z posso dedurre
xI ∙y = zy
Regola 2) da x∙y=z posso dedurre
y∙x=z
Costruiamo le stringhe
• I∙I = I
• II∙I =II
•
•
•
•
assioma
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
II 2
III 3
IIII 4
IIIII 5
∙ moltiplicazione
= uguaglianza
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
…..IU
2° regola se Mx allora Mxx
3° regola
4° regola
….III….
….UU…
…U…
…..
x è una stringa di I e U
Domanda
• Si può costruire la stringa MU ?
• Proviamo a giocare
MIU
2
MIUIU
2
2
MIUIUIUIU
2
MI
1
MIUIUIU
MII
1
2
MIIU
MIIUIIU
Anche qui dopo M
si ripete la successione di
IIU
La successione di IU
dopo M si ripete all’infinito
2
MIIII
MIU
MUI
3
3
2
MIIIIIIII
MIIIIU
In ogni caso il numero
di I non è mai 3 o multiplo di 3 e
quindi non può essere eliminato
per diventare MU
1
MUI
Analizzando il ramo MUI
MUIU
MUIUI
MUIUUIU
MUIIU
MUIIUUIIU
MUIIIIU
MUUIU
Si ritorna a MIU
MIU
Analizzando il ramo MUIUI
MUIUI
MUIUIU
MUIUIUIUI
MUIUIUUIUIU
MUIUIIUIU
MUIUIIUIUUIUIIUIU
MUIUIIUIIUIIUIU
In ogni caso il numero
di I non è mai 3 o multiplo di 3 e
quindi non può essere eliminato
per diventare MU
concludendo
Con 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!