variabili libere di (?x.xy) x e variabili vincolate di ?xy.x
-
16-10-2019 - |
Domanda
Stavo risolvendo esercizi su Lambda calcolo. Tuttavia, le mie soluzioni sono diverse dalle risposte e non riesco a vedere ciò che è sbagliato.
-
Trova variabili libere di $ (\ lambda x.xy) x $.
Le mie lavorazioni: $ FV ((\ lambda x.xy) x) = FV (\ lambda x.xy) \ tazza FV (x) = \ {y \} \ tazza \ {x \} = \ {x, y \ } $.
Il modello di risposta: $ FV ((\ lambda x.xy) x) = \ {x \} $ .
-
Trova le variabili legate di $ \ lambda xy.x $.
Le mie lavorazioni: Una variabile $ y $ ha il suo vincolante, ma dato che non è presente nel corpo del $ \ lambda $ -abstraction esso non può essere vincolata e quindi $ BV (\ lambda xy.x) = \ {x \} $ solo.
Il modello di risposta:. $ BV (\ lambda xy.x) = \ {x, y \} $
Soluzione
-
La tua risposta è corretta, $ y $ è sicuramente libero. Il modello si è sbagliato. Forse c'è stato un errore di battitura e la risposta è stata pensata per $ (\ lambda y.xy) x $
-
Dipende dalla definizione precisa di $ BV $. Spesso solo $ FV $ è definita formalmente, perché è più importante. (Variabili vincolate possono essere liberamente rinominato in un sottotermine, ma variabili libere non possono.) Quindi, se $ BV $ è definito come \ Begin {eqnarray *} BV (x) & = & \ {\} \\ BV (M N) & = & BV (M) \ tazza BV (N) \\ BV (\ lambda x.M) & = & \ {x \} \ tazza BV (M) \\ \ End {eqnarray *} allora il modello risposta è corretta. Si noti che questa definizione ha un senso: se si dispone di un termine di $ M $ e sostituto di una variabile libera $ x $ un altro termine $ N $ senza variabili vincolate ($ BV (N) = \ {\} $), ci si aspetta che $ BV (M) = BV (M [x: = N]) $. Se desideri prendere in considerazione solo variabili vincolate che appaiono anche sotto il $ \ lambda $, questa struttura non avrebbe retto.