variabili libere di (?x.xy) x e variabili vincolate di ?xy.x

Question

Stavo risolvendo esercizi su Lambda calcolo. Tuttavia, le mie soluzioni sono diverse dalle risposte e non riesco a vedere ciò che è sbagliato.

1. 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 \} $

.

2. 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 \} $

Answer 1

1. 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 $

2. 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.