Lambda微积分中对布尔的查询 [英] Query on Booleans in Lambda Calculus

问题描述

这是AND运算符的lambda演算表示：

  lambda（m）.lambda（n）.lambda（ a）λ（b）。 m（nab）b 
  

任何人都可以帮助我理解这种表示形式吗？$ b $为了理解如何在lambda演算中表示布尔值，有助于思考IF表达式，if a then b else c。这是一个表达式，选择第一个分支，b，如果它是真的，第二个，c，如果它是假的。 Lambda表达式可以很轻松地做到这一点：

  lambda（x）.lambda（y）.x 
  

会给你第一个参数，而

  lambda（x）.lambda（y）.y 
  

。因此，如果a是这些表达式之一，那么

  abc 
  

给出 b 或 c ，这正是我们希望IF能够做到。因此，定义

  true = lambda（x）.lambda（y）.x 
 false = lambda（x）。 lambda（y）.y 
  

和 abc 将表现得像，如果一个then b else c 。

在（ nab），这意味着如果n则a else b 。
然后 m（nab）b 表示

 如果m然后（如果n然后是其他b）其他b 
  

该表达式的计算结果为如果 m 和 n 都是真 c $ c>，否则为 b 。由于 a 是函数的第一个参数， b 是第二个参数，而 true 已被定义为一个函数，它给出了它的两个参数中的第一个，然后如果 m 和 n 都是 true ，整个表达式也是如此。否则它是 false 。这就是和！





的定义，所有这些都是由Alonzo Church发明的，他发明了lambda演算。

This is the lambda calculus representation for the AND operator:

lambda(m).lambda(n).lambda (a).lambda (b). m(n a b) b

Can anyone help me in understanding this representation?

解决方案

To understand how to represent Booleans in lambda calculus, it helps to think about an IF expression, "if a then b else c". This is an expression which chooses the first branch, b, if it is true, and the second, c, if it is false. Lambda expressions can do that very easily:

lambda(x).lambda(y).x

will give you the first of its arguments, and

lambda(x).lambda(y).y

gives you the second. So if a is one of those expressions, then

a b c

gives either b or c, which is just what we want the IF to do. So define

 true = lambda(x).lambda(y).x
false = lambda(x).lambda(y).y

and a b c will behave like if a then b else c.

Looking inside your expression at (n a b), that means if n then a else b. Then m (n a b) b means

if m then (if n then a else b) else b

This expression evaluates to a if both m and n are true, and to b otherwise. Since a is the first argument of your function and b is the second, and true has been defined as a function that gives the first of its two arguments, then if m and n are both true, so is the whole expression. Otherwise it is false. And that's just the definition of and!

All this was invented by Alonzo Church, who invented the lambda calculus.

这篇关于Lambda微积分中对布尔的查询的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！