Pages: [1] 2 3 4   Go Down
Print
Author Topic: Aiuto esercizio Lambda-calcolo  (Read 10125 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Joe
Apprendista Forumista
**
Offline Offline

Posts: 492


« on: 24-03-2013, 08:44:46 »

Salve a tutti, ho appena iniziato a studiare il lambda-calcolo e, purtroppo, sto avendo delle difficoltà su come funziona il meccanismo della sostituzione. Premetto che ho capito più o meno la nozione di variabile libera e legata e che la variabile che va sostituita deve essere libera, ma non ho ben chiaro come la si effettua su espressioni più articolate, ad esempio le seguenti:

  • \lambda y.y(\lambda z.xz)[\lambda z.y/x]
  • x(\lambda yx.x)[(yz)/x]
  • x(\lambda yx.zx)[(\lambda y.y)/x, x/z]

Qualcuno può spiegarmi l'approccio?
« Last Edit: 24-03-2013, 20:45:19 by Joe » Logged
Acicatena86
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 404


See full me now who neon


« Reply #1 on: 25-03-2013, 11:33:24 »

    Salve a tutti, ho appena iniziato a studiare il lambda-calcolo e, purtroppo, sto avendo delle difficoltà su come funziona il meccanismo della sostituzione. Premetto che ho capito più o meno la nozione di variabile libera e legata e che la variabile che va sostituita deve essere libera, ma non ho ben chiaro come la si effettua su espressioni più articolate, ad esempio le seguenti:

    • \lambda y.y(\lambda z.xz)[\lambda z.y/x]
    • x(\lambda yx.x)[(yz)/x]
    • x(\lambda yx.zx)[(\lambda y.y)/x, x/z]

    Qualcuno può spiegarmi l'approccio?

    Allora...
    • \lambda y.y(\lambda z.xz) [\lambda z.y/x]
      La variabile z è legata, quindi facciamo un  \alpha -conversione
       \lambda y.y(\lambda w.xw) [\lambda z.y/x]

      adesso posso sostituire , quindi :
       \lambda y.y(\lambda w. (\lambda z.y)w)
    • x(\lambda yx.x)[(yz)/x]
    Qui le variabili legate sono x,y, quindi  \alpha -conversione :
    \lambda x (\lambda ab.zb) [(yz)/x]
    Sostituendo otteniamo
    yz.(\lambda ab.zb)
    [/list]


    EDIT:
    Sperando che siano giusti (Prof?), a questo punto lascio a te il terzo Smiley[/list]
    « Last Edit: 25-03-2013, 11:47:32 by Acicatena86 » Logged
    Joe
    Apprendista Forumista
    **
    Offline Offline

    Posts: 492


    « Reply #2 on: 25-03-2013, 11:44:57 »

    Salve a tutti, ho appena iniziato a studiare il lambda-calcolo e, purtroppo, sto avendo delle difficoltà su come funziona il meccanismo della sostituzione. Premetto che ho capito più o meno la nozione di variabile libera e legata e che la variabile che va sostituita deve essere libera, ma non ho ben chiaro come la si effettua su espressioni più articolate, ad esempio le seguenti:

    • \lambda y.y(\lambda z.xz)[\lambda z.y/x]
    • x(\lambda yx.x)[(yz)/x]
    • x(\lambda yx.zx)[(\lambda y.y)/x, x/z]

    Qualcuno può spiegarmi l'approccio?

    Allora...
    • \lambda y.y(\lambda z.xz) [\lambda z.y/x]
      La variabile z è legata, quindi facciamo un  \alpha -conversione
       \lambda y.y(\lambda w.xw) [\lambda z.y/x]

      adesso posso sostituire , quindi :
       \lambda y.y(\lambda w. (\lambda z.y)w)


    Appena faccio gli altri aggiungo qui Smiley


    Ti ringrazio, sto già iniziando a capire
    Logged
    Acicatena86
    Apprendista Forumista
    **
    Offline Offline

    Gender: Male
    Posts: 404


    See full me now who neon


    « Reply #3 on: 25-03-2013, 11:46:18 »

    Salve a tutti, ho appena iniziato a studiare il lambda-calcolo e, purtroppo, sto avendo delle difficoltà su come funziona il meccanismo della sostituzione. Premetto che ho capito più o meno la nozione di variabile libera e legata e che la variabile che va sostituita deve essere libera, ma non ho ben chiaro come la si effettua su espressioni più articolate, ad esempio le seguenti:

    • \lambda y.y(\lambda z.xz)[\lambda z.y/x]
    • x(\lambda yx.x)[(yz)/x]
    • x(\lambda yx.zx)[(\lambda y.y)/x, x/z]

    Qualcuno può spiegarmi l'approccio?

    Allora...
    • \lambda y.y(\lambda z.xz) [\lambda z.y/x]
      La variabile z è legata, quindi facciamo un  \alpha -conversione
       \lambda y.y(\lambda w.xw) [\lambda z.y/x]

      adesso posso sostituire , quindi :
       \lambda y.y(\lambda w. (\lambda z.y)w)


    Appena faccio gli altri aggiungo qui Smiley


    Ti ringrazio, sto già iniziando a capire

    Se ci riesci, posti qui le tue soluzioni? Così magari le confrontiamo Smiley
    Logged
    Joe
    Apprendista Forumista
    **
    Offline Offline

    Posts: 492


    « Reply #4 on: 25-03-2013, 13:33:29 »

    Salve a tutti, ho appena iniziato a studiare il lambda-calcolo e, purtroppo, sto avendo delle difficoltà su come funziona il meccanismo della sostituzione. Premetto che ho capito più o meno la nozione di variabile libera e legata e che la variabile che va sostituita deve essere libera, ma non ho ben chiaro come la si effettua su espressioni più articolate, ad esempio le seguenti:

    • \lambda y.y(\lambda z.xz)[\lambda z.y/x]
    • x(\lambda yx.x)[(yz)/x]
    • x(\lambda yx.zx)[(\lambda y.y)/x, x/z]

    Qualcuno può spiegarmi l'approccio?

    Allora...
    • \lambda y.y(\lambda z.xz) [\lambda z.y/x]
      La variabile z è legata, quindi facciamo un  \alpha -conversione
       \lambda y.y(\lambda w.xw) [\lambda z.y/x]

      adesso posso sostituire , quindi :
       \lambda y.y(\lambda w. (\lambda z.y)w)


    Appena faccio gli altri aggiungo qui Smiley


    Ti ringrazio, sto già iniziando a capire

    Se ci riesci, posti qui le tue soluzioni? Così magari le confrontiamo Smiley

    Ecco le mie soluzioni:

    • \lambda y.y(\lambda z.xz)[\lambda z.y/x] -> \lambda y.y(\lambda w.xw)[\lambda z.y/x] ->
          -> \lambda y.y(\lambda w.(\lambda z.y)w)
    • x(\lambda yx.x)[(yz)/x] -> \lambda x(\lambda ab.b)[(yz)/x] ->
          -> yz(\lambda ab.b)
    • x(\lambda yx.zx)[(\lambda y.y)/x, x/z] -> \lambda x(\lambda ab.zb)[(\lambda y.y)/x, x/z] ->
          -> (\lambda y.y)(\lambda ab.xb)

    « Last Edit: 25-03-2013, 14:59:48 by Joe » Logged
    Acicatena86
    Apprendista Forumista
    **
    Offline Offline

    Gender: Male
    Posts: 404


    See full me now who neon


    « Reply #5 on: 25-03-2013, 13:55:21 »

    Esercizio 13

    • (\lambda x.yx) [yz/x]
                  \rightarrow (\lambda a.xa) \rightarrow (\lambda a.yza)
    •  (\lambda z.(\lambda x.yx)xz)[zx/x]
                   \rightarrow (\lambda a.(\lambda b.yb)xa) \rightarrow (\lambda a.(\lambda b.yb)(zx)a)


    Esercizio 14:
    Eseguire la seguente sostituzione:

    z(\lambda y.wy)\lambda z.((\lambda x.yx)xz)[yz/x,yz/w]
       \rightarrow (\lambda a.wa)\lambda b.((\lambda c.yc)xb)\rightarrow z(\lambda a.yza)\lambda b.((\lambda c.yc)yzb)


    « Last Edit: 25-03-2013, 13:57:06 by Acicatena86 » Logged
    Acicatena86
    Apprendista Forumista
    **
    Offline Offline

    Gender: Male
    Posts: 404


    See full me now who neon


    « Reply #6 on: 25-03-2013, 15:40:46 »

    Esercizio 31
    Professore mi potrebbe dire come procedere?, arrivati al punto  c) mi blocco  cry

    Trovare la forma normale (se esiste) di :

    (\lambda x.xxy)(\lambda xy.xyy)

    a)Metto qualche parentesi e il termine diventa:
    ((\lambda x.(xx))y))(\lambda x.(\lambda y.(xy)y)) e' corretto?

    b) Ricerco le variabili legate, così da poterle rinominare, in particolare io ho fatto le seguenti \alpha-conversioni
    ((\lambda a.(xx)y))(\lambda x.(\lambda b.(xy)y))  è corretto?

    c) Adesso se i punti a-b sono giusti come procedo?
    Logged
    Franco Barbanera
    Moderator
    Forumista Eroico
    *****
    Offline Offline

    Posts: 3.079



    WWW
    « Reply #7 on: 25-03-2013, 15:45:25 »


          • x(\lambda yx.x)[(yz)/x]
          Qui le variabili legate sono x,y, quindi  \alpha -conversione :
          \lambda x (\lambda ab.zb) [(yz)/x]
          Sostituendo otteniamo
          yz.(\lambda ab.zb)
          [/list]


          EDIT:
          Sperando che siano giusti (Prof?), a questo punto lascio a te il terzo Smiley[/list]

          Sul secondo c'e' un problema:

           x(\ yx.x)[(yz)/x]

          Tu dici

                      Qui le variabili legate sono x,y, quindi \alpha -conversione :
                       \x.(\ab.zb) [(yz)/x]
                      Sostituendo otteniamo
                       yz.\ab.zb)


          Con l'alpha conversione tu ottieni in realta'
          x(\ab.a)[(yz)/x]
          e ora con la sostituzione
          (yz)(\ab.a)

          In realta' non c'era neanche bisogno di fare l'alpha conversione,
          poiche' la x a destra e' legata e non sostituiamo solo variabili libere,
          che in questo caso era la x a sinistra, Questa, non essendo nel corpo di
          alcuna lambda astrazione, si poteva sostituire senza problemi.

          FB[/list]
          « Last Edit: 25-03-2013, 15:48:13 by Franco Barbanera » Logged
          Franco Barbanera
          Moderator
          Forumista Eroico
          *****
          Offline Offline

          Posts: 3.079



          WWW
          « Reply #8 on: 25-03-2013, 15:55:06 »

            a)Metto qualche parentesi e il termine diventa:
               ((\lambda x.(xx))y))(\lambda x.(\lambda y.(xy)y)) e' corretto?

          corretto

               b) Ricerco le variabili legate, così da poterle rinominare, in particolare io ho fatto le seguenti alpha-        
                   conversioni
                  ((\lambda a.(xx)y))(\lambda x.(\lambda b.(xy)y))  è corretto?

          sbagliato

          se vuoi rinominare le variabili legate ottieni

          ((\lambda a.(aa))y))(\lambda b.(\lambda c.(bc)c))

          Ora l'intero termine e' un redex, che puoi ridurre,
          ottenendo  

          ((aa)y)[(\lambda b.(\lambda c.(bc)c)) / a]

          cioe'

          (\lambda b.(\lambda c.(bc)c)) (\lambda b.(\lambda c.(bc)c))y

          In questo termine esiste un unico redex: il sottotermine
          (\lambda b.(\lambda c.(bc)c)) (\lambda b.(\lambda c.(bc)c))



          riduci questo redex e vai avanti

          FB
          « Last Edit: 25-03-2013, 15:59:22 by Franco Barbanera » Logged
          Acicatena86
          Apprendista Forumista
          **
          Offline Offline

          Gender: Male
          Posts: 404


          See full me now who neon


          « Reply #9 on: 25-03-2013, 16:04:30 »


                • x(\lambda yx.x)[(yz)/x]
                Qui le variabili legate sono x,y, quindi  \alpha -conversione :
                \lambda x (\lambda ab.zb) [(yz)/x]
                Sostituendo otteniamo
                yz.(\lambda ab.zb)
                [/list]


                EDIT:
                Sperando che siano giusti (Prof?), a questo punto lascio a te il terzo Smiley[/list]

                Sul secondo c'e' un problema:

                 x(\ yx.x)[(yz)/x]

                Tu dici

                            Qui le variabili legate sono x,y, quindi \alpha -conversione :
                             \x.(\ab.zb) [(yz)/x]
                            Sostituendo otteniamo
                             yz.\ab.zb)


                Con l'alpha conversione tu ottieni in realta'
                x(\ab.a)[(yz)/x]
                e ora con la sostituzione
                (yz)(\ab.a)

                In realta' non c'era neanche bisogno di fare l'alpha conversione,
                poiche' la x a destra e' legata e non sostituiamo solo variabili libere,
                che in questo caso era la x a sinistra, Questa, non essendo nel corpo di
                alcuna lambda astrazione, si poteva sostituire senza problemi.

                FB[/list]
                Non so perchè ma ho  ricopiato male lo svolgimento dell'esercizio, infatti quella z non c'entrava niente Smiley .
                Ottengo infatti il suo medesimo risultato Smiley

                x(\lambda yx.x) [(yz)/x]
                \rightarrow x(\lambda tw.w)\rightarrow yz(\lambda tw.w)
                Logged
                Joe
                Apprendista Forumista
                **
                Offline Offline

                Posts: 492


                « Reply #10 on: 25-03-2013, 16:10:32 »

                Scusi prof. è corretta questa sostituzione?:

                x(\lambda yx.x)[(yz)/x] \rightarrow x(\lambda ya.a)[(yz)/x] \rightarrow (yz)(\lambda ya.a)
                Logged
                Acicatena86
                Apprendista Forumista
                **
                Offline Offline

                Gender: Male
                Posts: 404


                See full me now who neon


                « Reply #11 on: 25-03-2013, 16:28:16 »

                 a)Metto qualche parentesi e il termine diventa:
                     ((\lambda x.(xx))y))(\lambda x.(\lambda y.(xy)y)) e' corretto?

                corretto

                     b) Ricerco le variabili legate, così da poterle rinominare, in particolare io ho fatto le seguenti alpha-        
                         conversioni
                        ((\lambda a.(xx)y))(\lambda x.(\lambda b.(xy)y))  è corretto?

                sbagliato

                se vuoi rinominare le variabili legate ottieni

                ((\lambda a.(aa))y))(\lambda b.(\lambda c.(bc)c))

                Ora l'intero termine e' un redex, che puoi ridurre,
                ottenendo  

                ((aa)y)[(\lambda b.(\lambda c.(bc)c)) / a]

                cioe'

                (\lambda b.(\lambda c.(bc)c)) (\lambda b.(\lambda c.(bc)c))y

                In questo termine esiste un unico redex: il sottotermine
                (\lambda b.(\lambda c.(bc)c)) (\lambda b.(\lambda c.(bc)c))



                riduci questo redex e vai avanti

                FB


                Professore non riesco a capire questo passaggio :
                Ora l'intero termine e' un redex, che puoi ridurre,
                ottenendo 

                ((aa)y)[(\lambda b.(\lambda c.(bc)c)) / a]

                cioe'

                (\lambda b.(\lambda c.(bc)c)) (\lambda b.(\lambda c.(bc)c))y

                Potrebbe postare in dettaglio i passaggi? pray
                Logged
                Joe
                Apprendista Forumista
                **
                Offline Offline

                Posts: 492


                « Reply #12 on: 25-03-2013, 17:44:05 »

                Non ho capito come si trova la forma normale di una espressione...ad esempio su questa:

                (λx.((λy.z)x))((λx.xx)(λx.xx))
                Logged
                Franco Barbanera
                Moderator
                Forumista Eroico
                *****
                Offline Offline

                Posts: 3.079



                WWW
                « Reply #13 on: 25-03-2013, 21:28:40 »

                Scusi prof. è corretta questa sostituzione?:

                x(\lambda yx.x)[(yz)/x] \rightarrow x(\lambda ya.a)[(yz)/x] \rightarrow (yz)(\lambda ya.a)

                si, pero' le frecce non hanno senso

                fb
                Logged
                Joe
                Apprendista Forumista
                **
                Offline Offline

                Posts: 492


                « Reply #14 on: 26-03-2013, 13:53:50 »

                Scusi prof. è corretta questa sostituzione?:

                x(\lambda yx.x)[(yz)/x] \rightarrow x(\lambda ya.a)[(yz)/x] \rightarrow (yz)(\lambda ya.a)

                si, pero' le frecce non hanno senso

                fb

                Grazie mille, ho messo le frecce solo per denotare i passaggi
                Logged
                Pages: [1] 2 3 4   Go Up
                Print
                Jump to: