Adição no Cálculo Lambda §

---

Abstract

A adição é realizada no cálculo lambda, utilizando numerais de Church e a função de sucessor, mostrando passo a passo como é computado a partir de , resultando em .

No cálculo lambda, operações aritméticas como a adição são expressas de forma puramente funcional, sem usar símbolos numéricos tradicionais como ”+“. Em vez disso, usamos os numerais de Church — que representam números como funções — e a função de sucessor para “somar”.

De forma simplifica a adição como uma maneira de aplicar repetidamente a ideia de “incrementar” um número a outro.

Definição §

A adição no cálculo lambda pode ser entendida como a aplicação repetida da função de sucessor () de um número ao outro. Formalmente, para somar dois numerais de Church e , podemos definir como:

• Pegar o numeral e usá-lo para aplicar (sucessor) vezes ao numeral .

No exemplo dado:

• ,
• (função de sucessor),
• ,

A adição é expressa como , onde o numeral 2 atua como uma função que aplica duas vezes ao numeral 3.

Detalhando a Adição §

Vamos dissecar o processo para entender como a adição emerge dessa construção.

Numerais de Church como Iteradores §

Os numerais de Church são funções que “repetem” uma operação um certo número de vezes:

• significa “aplique duas vezes a “.
• Quando usamos , estamos dizendo: “pegue como a operação e aplique-a duas vezes a 3”.

Isso reflete a ideia intuitiva de soma: é o mesmo que incrementar 3 duas vezes ().

Passos da substituição

A expressão envolve substituições no cálculo lambda (β-redução).

Exemplo §

Exemplo: Calculando §

Dado:

• ,
• ,
• ,

Queremos resolver:

Passo 1: Substituição de por §

Substituímos por (primeiro argumento):

Isso significa que , e agora aplicamos o corpo da função ao próximo argumento :

Aqui, se torna , ou seja, aplicar duas vezes a .

Passo 2: Aplicação a 3 §

Substituímos por :

Isso é uma aplicação direta:

Passo 3: Calcular §

Sabemos que incrementa um numeral:

• ,
• .

Resolvendo:

• Substituímos por :
• Avaliamos :
  • , , então ,
  • Resultado: .

Assim, .

Passo 4: Calcular §

Agora aplicamos a :

• ,
• .

Resolvendo:

• Substituímos por :
• Avaliamos: ,
• Resultado: .

Assim, .

Resultado §

A expressão inicial se reduz a , que é 5:

Referências §

---

Aula 1 - Cálculo Lambda