Operador lógica AND no Cálculo Lambda

---

Summary

O operador lógico “E” (AND) é definido no cálculo lambda como $\lambda ab.abF$, utilizando os booleanos de Church $T$ e $F$.

No cálculo lambda, operações lógicas como o “E” (AND) são expressas como funções.

Já vimos que “verdadeiro” ($T$) e “falso” ($F$) são codificados como seletores de argumentos. Agora, vamos construir o operador “E” — que retorna “verdadeiro” apenas se ambos os operandos forem verdadeiros.

Definição

O operador lógico “E” (AND) no cálculo lambda é definido como:

$$AND\equiv \lambda ab.abF$$

Onde:

• $a$ e $b$ são booleanos no cálculo lambda (ou seja, $T\equiv \lambda xy.x$ ou $F\equiv \lambda xy.y$),
• $T=\lambda xy.x$ (escolhe o primeiro argumento),
• $F=\lambda xy.y$ (escolhe o segundo argumento).

A expressão $\lambda ab.abF$ pode ser interpretada assim:

• $a$ é aplicado a $b$ e $F$ como argumentos.
• Se $a=T$, então $TbF=b$ (escolhe $b$), e o resultado depende de $b$.
• Se $a=F$, então $FbF=F$ (escolhe $F$), e o resultado é sempre falso.

Isso captura a essência do “E”: o resultado é verdadeiro ($T$) apenas se ambos $a$ e $b$ forem verdadeiros.

Para transformar toda essa formalidade em forma mais visual e simples de interpretar isso e visualizar a função AND seria utilizando a tabela verdade abaixo:

Referência: Drawing 2025-03-03 10.40.11.excalidraw

Lemos essa imagem com a seguinte pergunta:

Visualizando operador AND na tabela verdade

Para confirmar que $\lambda ab.abF$ corresponde ao operador “E” lógico, vamos calcular todas as combinações possíveis de $a$ e $b$ ($T$ ou $F$) e comparar com a tabela verdade padrão.

Tabela verdade do “E” lógico:

$a$	$b$	$a\wedge b$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$F$
$F$	$F$	$F$

Agora, vamos testar $ANDab=(\lambda ab.abF)ab$ para cada caso.

Caso 1: $a=T$, $b=T$

$$ANDTT=(\lambda ab.abF)TT$$

• Substituímos $a$ por $T$: $$(\lambda b.TbF)T$$
• Substituímos $b$ por $T$: $$TTF=(\lambda xy.x)TF=T$$
• Resultado: $T$ (verdadeiro).

Caso 2: $a=T$, $b=F$

$$ANDTF=(\lambda ab.abF)TF$$

• Substituímos $a$ por $T$: $$(\lambda b.TbF)F$$
• Substituímos $b$ por $F$: $$TFF=(\lambda xy.x)FF=F$$
• Resultado: $F$ (falso).

Caso 3: $a=F$, $b=T$

$$ANDFT=(\lambda ab.abF)FT$$

• Substituímos $a$ por $F$: $$(\lambda b.FbF)T$$
• Substituímos $b$ por $T$: $$FTF=(\lambda xy.y)TF=F$$
• Resultado: $F$ (falso).

Caso 4: $a=F$, $b=F$

$$ANDFF=(\lambda ab.abF)FF$$

• Substituímos $a$ por $F$: $$(\lambda b.FbF)F$$
• Substituímos $b$ por $F$: $$FFF=(\lambda xy.y)FF=F$$
• Resultado: $F$ (falso).

Resultado final

$a$	$b$	$ANDab$	Esperado ($a\wedge b$)
$T$	$T$	$T$	$T$
$T$	$F$	$F$	$F$
$F$	$T$	$F$	$F$
$F$	$F$	$F$	$F$

Referências

---

Aula 1 - Cálculo Lambda