Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

i dont know how to ask my question but here it is...

i have implementation of "NOT" and "True" and "false",but if i want to have "xnor" according to the example beneath:

(true) T--->λx.λy.x

(false) F----> λx.λy.y

(true) Q =((TQ)P) => ((λX.λY.X Q)P= (λY.Q)P=Q (false) P =((FQ)P) => ((λX.λY.Y Q)P= (λY.Y)P=P

Not ---> λx.((xF)T)

Not T ---> λx.((xF)T) T = ((TF)T=F

Not F ---> λx.((xF)T) F = ((FF)T=T

what "xnor" will be according to these examples? i have "not" ,"true" and "false",how i can get "xnor" or "or" or "and" ?(cause i can get to the Xnor with at least "or" and "and" )

share|cite|improve this question
Have you seen this? – Rudy the Reindeer Jan 6 '12 at 18:33
thank you so much – sam Jan 6 '12 at 18:37

The reason we define $$T = \lambda x. \lambda y. x$$ $$F = \lambda x. \lambda y. y$$ is so that you can easily define an "if" function $Q$ satisfying $$QTxy = x$$ $$QFxy = y$$ by $Qxyz = xyz$ (so $Q = \lambda x. \lambda y. \lambda z. x y z$).

Now it's easy to write things like an "and" function $A$ satisfying $$ATT = T$$ $$ATF = F$$ $$AFy = F$$ by $Axy = Qx(QyTF)F$ so $A = \lambda x. \lambda y. Qx(QyTF)F$. You could unfold the definition of $Q$ inside $A$ and beta reduce it a bit, but that will just give a slightly more compresses lambda term.

You can easily define the other boolean combinators using the same idea.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.