1

I am learning lambda calculus and I was given the following assignment:

Working with these definitions of TRUE and FALSE:

λx y . x ≡ T

λx y . y ≡ F

I am asked to form the AND operator, that even though functions similarly, is not equivalent to the following definition of it:

∧ ≡ λx y .x y F

But everywhere I've checked this seems to be the only way to go at it. Can anyone provide any guidance as to how I should start thinking about it?

Rad
  • 33
  • 1
  • 3
  • What does"equivalent" mean here exactly? The first thing I'd want to look at would be, how similar my solution be and still be considered"inequivalent"? – MJD Jan 08 '17 at 16:38
  • Not syntactically the same I suppose. – Rad Jan 08 '17 at 16:41
  • In that case, my hint is: the AND operation is commutative. – MJD Jan 08 '17 at 16:43
  • Does this mean that: ∧ ≡ λx y .y x F would be a sufficient solution? Looking at it it seems too simple to be right. Weird. – Rad Jan 08 '17 at 16:53
  • This Wikipedia article contains alternative encoding. – Anton Trunov Jan 08 '17 at 17:15
  • I don't know if $ λx y .y x F$ would be a sufficient solution, because it turns on the meaning of “inequivalent”. If it means “not syntactically the same”, as you suggested, then it's fine. Other things you could consider are: $\eta$-expansion of the formula you have; or rewriting $x\land y$ as $\text{if } x \text{ then } x \text{ else } y$. – MJD Jan 08 '17 at 18:04
  • I meant "if y then x else y". – MJD Jan 08 '17 at 18:28
  • I just learned what exactly they meant with "inequivalent". It basically means, that if we were to plug in each function something other than boolean values, they would have different outcomes. – Rad Jan 08 '17 at 20:37

0 Answers0