Pages: [1] 2   Go Down
Print
Author Topic: esercizi sul lambda calcolo  (Read 371 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
luca98
Matricola
*
Offline Offline

Posts: 78



« on: 22-12-2017, 12:48:00 »

professore  può dirmi se questi esercizi sono corretti?

Esercizio 25


Rinominare le variabili legate nel seguente termine in modo che non ci siano due variabili legate con lo stesso nome
x(λx.((λx.x)x))

x (\x.((\t.t)x))



Logged
luca98
Matricola
*
Offline Offline

Posts: 78



« Reply #1 on: 22-12-2017, 12:51:01 »

Esercizio 33

Eseguire le seguenti sostituzioni:
(λx.yx)[yz/x]
(λy.xy)[yz/x]
(λz.(λx.yx)xz)[zx/x]


---------------------------------------------------------------------------

1 credo che nella prima non si possa sostituire dato che la x è legata(mi corregga se sbaglio)
2 \t.(yz)t
3 \p.(\x.yx)(zx)p)
Logged
luca98
Matricola
*
Offline Offline

Posts: 78



« Reply #2 on: 22-12-2017, 12:55:23 »

Esercizio 34

Eseguire la seguente sostituzione:
z(λy.wy)λz.((λx.yx)xz) [yz/x,yz/w]

--------------------------------------------------------------------------

z(\t.(yz)t)\m.((\x.yx)(yz)m)
Logged
luca98
Matricola
*
Offline Offline

Posts: 78



« Reply #3 on: 22-12-2017, 13:00:01 »

Esercizio 36

Dire qual e' il risultato della seguente sostituzione:
((λy.yy)y(λy.y(λy.y)))[λy.zy/y]

---------------------------------------------------------------------------------------

((\t.tt)(\y.zy)(\m.m(\p.p)))
Logged
luca98
Matricola
*
Offline Offline

Posts: 78



« Reply #4 on: 22-12-2017, 13:08:32 »

Esercizio 37

Qual e' il risultato delle seguenti sostituzioni?
λy.x(λx.x)[λy.yx/x]
y(λz.xz)[λyzy.x/x]
λy.y(λz.xz)[(λz.y)/(λz.xz)]
-------------------------------------------------------------------------------------------

1\t.(\y.yx)(\x.x))
2 y(\t.(\yzy.x)t)
3 \m.m(\z.y)
Logged
luca98
Matricola
*
Offline Offline

Posts: 78



« Reply #5 on: 22-12-2017, 13:12:49 »

e poi una cosa...

è possibile fare una sostituzione del genere?

\y.x [xy/x]

io credo di no perchè BV(\y.x) n FV(xy) != 0, però non sono convìnto di questa cosa
Logged
luca98
Matricola
*
Offline Offline

Posts: 78



« Reply #6 on: 22-12-2017, 13:29:22 »

questo è l'esercizio 35(con la soluzione riportata nella pagina degli esercizi)

((λy.xy)(λz.y(λy.x)))[xyz/x]
Rinominiamo le variabili legate, ottenendo
((λt.xt)(λv.y(λw.x)))[xyz/x]
Effettuiamo ora la sostituzione.
((λt.(xyz)t)(λv.y(λw.xyz))

non capisco perchè è necessario cambiare da \z a \v...
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.900



WWW
« Reply #7 on: 23-12-2017, 17:01:35 »

Esercizio 33

Eseguire le seguenti sostituzioni:
(λx.yx)[yz/x]
(λy.xy)[yz/x]
(λz.(λx.yx)xz)[zx/x]
---------------------------------------------------------------------------
1 credo che nella prima non si possa sostituire dato che la x è legata(mi corregga se sbaglio)
2 \t.(yz)t
3 \p.(\x.yx)(zx)p)

la 1 non e' che non si possa fare,
e' che e' una sostituzione che non cambia nulla
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.900



WWW
« Reply #8 on: 23-12-2017, 17:05:17 »

Esercizio 37

Qual e' il risultato delle seguenti sostituzioni?
λy.x(λx.x)[λy.yx/x]
y(λz.xz)[λyzy.x/x]
λy.y(λz.xz)[(λz.y)/(λz.xz)]
-------------------------------------------------------------------------------------------

1\t.(\y.yx)(\x.x))
2 y(\t.(\yzy.x)t)
3 \m.m(\z.y)


la 3  NON e' una sostituzione!!!
E' una trappola !!!!

Quello che si puo' sostituire e' sempre e comunque una variabile!!!
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.900



WWW
« Reply #9 on: 23-12-2017, 17:07:43 »

e poi una cosa...

è possibile fare una sostituzione del genere?

\y.x [xy/x]

Certo!!!!

Perche' non sarebbe possibile?

Ogni sostituzione e' applicabile!
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.900



WWW
« Reply #10 on: 23-12-2017, 17:09:38 »

questo è l'esercizio 35(con la soluzione riportata nella pagina degli esercizi)

((λy.xy)(λz.y(λy.x)))[xyz/x]
Rinominiamo le variabili legate, ottenendo
((λt.xt)(λv.y(λw.x)))[xyz/x]
Effettuiamo ora la sostituzione.
((λt.(xyz)t)(λv.y(λw.xyz))

non capisco perchè è necessario cambiare da \z a \v...

Perche' z e' legata nel termine su cui effettui la sostituzione,
mentre e' libera nel termine che sostituisci al posto di x.
Dobbiamo sempre fare in modo che una variabile libera non diventi legata
dopo una sostituzione.
Logged
luca98
Matricola
*
Offline Offline

Posts: 78



« Reply #11 on: 24-12-2017, 14:58:06 »

Esercizio 33

Eseguire le seguenti sostituzioni:
(λx.yx)[yz/x]
(λy.xy)[yz/x]
(λz.(λx.yx)xz)[zx/x]
---------------------------------------------------------------------------
1 credo che nella prima non si possa sostituire dato che la x è legata(mi corregga se sbaglio)
2 \t.(yz)t
3 \p.(\x.yx)(zx)p)

la 1 non e' che non si possa fare,
e' che e' una sostituzione che non cambia nulla


Quindi se ho capito bene potrei scrivere...

(λx.yx)[yz/x] -> (λyz.yyz)

Logged
luca98
Matricola
*
Offline Offline

Posts: 78



« Reply #12 on: 24-12-2017, 15:00:19 »

e poi una cosa...

è possibile fare una sostituzione del genere?

\y.x [xy/x]

io credo di no perchè BV(\y.x) n FV(xy) != 0, però non sono convìnto di questa cosa

Scusi professore ma noi non avevamo detto che se si verifica

BV(\y.x) n FV(xy) != 0 NON si poteva sostituire?

Non ho capito molto bene questa cosa...
Logged
teo998
Matricola
*
Offline Offline

Posts: 40



WWW
« Reply #13 on: 28-12-2017, 15:36:53 »

Quindi se ho capito bene potrei scrivere...

(λx.yx)[yz/x] -> (λyz.yyz)
no, puoi scrivere (λx.yx)[yz/x] -> (λx.yx), perché (λx.M)[N/x] ≡ λx.M (definizione di sostituzione dal PS)


e poi una cosa...

è possibile fare una sostituzione del genere?

\y.x [xy/x]

io credo di no perchè BV(\y.x) n FV(xy) != 0, però non sono convìnto di questa cosa

Scusi professore ma noi non avevamo detto che se si verifica

BV(\y.x) n FV(xy) != 0 NON si poteva sostituire?

Non ho capito molto bene questa cosa...

una sostituzione si può sempre svolgere; quello che non si può fare quando il parametro formale dell'astrazione (y) è contenuto in FV(N) (N=xy) è applicare la regola (λy.M)[N/x] ≡ λy.(M[N/x])

nel caso \y.x[xy/x] si può applicare invece la regola (λy.M)[N/x] ≡ λy'.(M{y′/y}[N/x]), con y' nuova
\y.x[xy/x] -> \y'.(x[xy/x]) -> \y'.xy


(le due regole sopracitate le trovi sempre nella definizione di sostituzione nel PS)
Logged

Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.900



WWW
« Reply #14 on: 28-12-2017, 18:19:20 »

Esercizio 33

Eseguire le seguenti sostituzioni:
(λx.yx)[yz/x]
(λy.xy)[yz/x]
(λz.(λx.yx)xz)[zx/x]
---------------------------------------------------------------------------
1 credo che nella prima non si possa sostituire dato che la x è legata(mi corregga se sbaglio)
2 \t.(yz)t
3 \p.(\x.yx)(zx)p)

la 1 non e' che non si possa fare,
e' che e' una sostituzione che non cambia nulla


Quindi se ho capito bene potrei scrivere...

(λx.yx)[yz/x] -> (λyz.yyz)



(λx.yx)[yz/x] -> (λyz.yyz)
Non ci va la freccia!
E abbiamo detto che si sostituiscono solo le variabili libere!
La x in (λx.yx) NON e' libera.

Logged
Pages: [1] 2   Go Up
Print
Jump to: