[Question]
  [
# Church booleans
A [Church boolean](https://en.wikipedia.org/wiki/Church_encoding#Church_Booleans) is a function that returns `x` for true and `y` for false where `x` is the first argument to the function and `y` is the second argument to the function. Further functions can be composed from these functions which represent the `and` `not` `or` `xor` and `implies` logical operations.
# Challenge
Construct the Church booleans and `and` `not` `or` `xor` and `implies` Church gates in a language of your choice. `and` `or` and `xor` should take in two functions (representing Church booleans) and return a function (representing another Church boolean). Likewise, `not` should invert the function it takes and the `implies` gate should perform boolean implies logic where the first argument `implies` the second.
# Scoring
The total length of all of the code required to make Church `true` and `false` in your language and the `and` `not` `or` `xor` and `implies` Church gates excluding the function's name. (for example, `false=lambda x,y:y` in Python would be 13 bytes). You can reuse these names later in your code with them counting 1 byte toward the byte total of that gate.
# Pseudo code Examples:
The functions you create should be able to be called later in your code like so.
```
true(x, y) -> x
false(x, y) -> y
and(true, true)(x, y) -> x
and(true, false)(x, y) -> y
# ... etc
```
  
[Answer]
# [Haskell](https://www.haskell.org/), 50 - 6 = 44 bytes
*-1 byte thanks to Khuldraeseth na'Barya, and -1 byte thanks to Christian Sievers.*
```
t=const
f=n t
n=flip
a=n n f
o=($t)
x=(n>>=)
i=o.n
```
[Try it online!](https://tio.run/##bcwxDsIwDIXh3afw0KFdEBzAvUsEWFgEu6IZcvtQKiFV5I3v6df3SOvznnNrRa7hayEV50Iumm2htA1npZBxKBNVGX2eZSKTOHl7JXO5BRHz8jYvPHDhC58PW/d9OLxLvI/SFv1n30@7T0GnPRgADAAGAAOBFYAVgBWAFYEGQAOgAdB@YPsA "Haskell ‚Äì Try It Online")
[Answer]
# [Binary Lambda Calculus](https://tromp.github.io/cl/cl.html), 13.875 12.875 bytes (103 bits)
Binary Lambda Calculus Language (BLC) by John Tromp is basically an efficient serialization format for lambda calculus. It is a great fit for this task, as Church notation is even the "idiomatic" way to work with booleans in BLC.
I used the following lambda functions for the combinators, some of which I copied and golfed from the Haskell answer:, which were found by an exhaustive search with a proof limit of 20 Œ≤-reductions for each case. There is a good chance these are shortest possible.
```
True:  (\a \b a)
False: (\a \b b)
Not:   (\a \b \c a c b)
And:   (\a \b b a b)
Or:    (\a a a)
Xor:   (\a \b b (a (\c \d d) b) a)
Impl:  (\a \b a b (\c \d c))
```
These translate to the following (binary) BLC code sequences:
```
 bits |  name | BLC
------+-------+---------
    7 | True  | 0000 110
    6 | False | 0000 10
   19 | Not   | 0000 0001 0111 1010 110
   15 | And   | 0000 0101 1011 010
    8 | Or    | 0001 1010
   28 | Xor   | 0000 0101 1001 0111 0000 0101 0110
   20 | Impl  | 0000 0101 1101 0000 0110
```
Functions above are in total 111 bits long (13.875 bytes) 103 bits long (12.875 bytes). They don't need to be aligned to byte boundaries to be used inside a program, so it makes sense to count fractional bytes. 
There is no code re-use between the combinators, because there are no variables/references/names in BLC - everything had to be copied over. Still, the efficiency of the encoding makes for quite a terse representation.
[Answer]
# [Python 2](https://docs.python.org/2/), (-3?) ~~¬†101¬†~~ 95 bytes
[David Beazley](https://www.youtube.com/watch?v=pkCLMl0e_0k "YouTube: Lambda Calculus from the Ground Up - PyCon 2019") eat your heart out!
-6 thanks to Chas Brown (moved the repeated `:` into the join text >.<)
```
exec'=lambda x,y=0:'.join('F y;T x;N x(F,T);A x(y,F);O x(T,y);X x(N(y),y);I O(y,N(x))'.split())
```
**[Try it online!](https://tio.run/##lZExb4MwEIV3fsVt51OtKOkIYsiClAUWhgyVIpqahAoMoiTCv56eQ5zWTdSqN51833vPZ3dmOLb6eZrUqPYY10Xz@lbAKE28DHHx3lZaYAImymGMUhhFInOK1twYmVCUcZNLQ9GWm1QYsv0GMp6mYiTCxUdXV4Mgmsq2B100CioNbIkSMEcKA@AqT3oPMahzUQvL0OW06ys9zJonwJAVlhMruSQWv2gMghnBNMTA@hf94dQoPexcECY5zhFu5GI89HueN5CQ3ki6JLtIDvc3Wmfbzf/2mVE2qVU57H65uy2Pcd73QroJrHFfHY5/OtvyQWf/QE6ebN7o/hbyUfL1@zz6J3h94y9vfufpEw "Python 2 ‚Äì Try It Online")**
I think it might be `95 - 3` because I don't reuse the functions `A`, `X`, or `I`, but I use a single `=` for assignment (in front of `lambda`). Maybe I cant remove any; maybe I even get to remove 3.5?
[Answer]
# [JavaScript (Node.js)](https://nodejs.org), ~~92~~ ~~86~~ 83 - 7 = 76 bytes
```
t=p=>q=>p
f=t(q=>q)
n=p=>p(f)(t)
a=p=>n(p)(f)
o=p=>p(t)
x=p=>p(n)(f())
i=p=>n(p)(t)
```
[Try it online!](https://tio.run/##hY3RDoIwDEXf9xXEpzVRP0Ay/mUq1RmyDpi6v8cCESgh4aW57b2352U/tr01LsSTp3vZddEEU9SmCApN1CxqUL6/BY2gIyjbL14H4F3R6PA5jcrzWQMoN6UidO2TvuZqihv5lqryXNFDX3Vs3iWnbdWWXFh6h3iAXPUtbufSwsnCteUvWcyzOeC5PWuEdd5y/thXeCIXB81z/mD5w@LJsOJiRekibFBol0KSQpJCkkLblLRLSZKSJCVJStqmuF2KkxQnKU5S3J/S/QA "JavaScript (Node.js) ‚Äì Try It Online") Link includes basic test cases. Edit: Saved ~~6~~ 9 bytes thanks to @tsh.
[Answer]
# [Python 2](https://docs.python.org/2/), ~~133 - 6 = 127~~ 94 bytes
```
exec"t!u;f!v;n!u(f,t);a!u(v,f);o!u(t,v);x!u(n(v),v);i!o(v,n(u))".replace('!','=lambda u,v=0:')
```
[Try it online!](https://tio.run/##dc5BDsIgEAXQvaco3cAkxFSXkh4GKxNJKpAGCJ4eaXRRHbv78/l5ITzj3btzraaYqY8sKWRZOZYEyghKt5AlgvItRJlBlRacyLBmy3x7dSIB9MfFhFlPRnDGJR9n/bjedJdkHocLhxoW62IXxUkOcHgfuDk@lRMRthMnEOhKt59879YGfxokG5T/NE80TzRPNL@jFaIVohWilR3NEs0SzRLNEq2@AA "Python 2 ‚Äì Try It Online")
Shamelessly stealing the sneaky idea behind [Jonathan Allan's](https://codegolf.stackexchange.com/a/190361/69880) answer; no bytes deducted though.
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 61-7=54 bytes
```
t=#&
f=#2&
a=#2~#~f&
o=t~#~#2&
n=f~#~t&
x=n@#~#2~#&
i=#2~#~t&
```
[Try it online!](https://tio.run/##VcyxCsMgEAbg3aeQBJwc2o4BoUufQhwkreQGvVJuEEp9daOEJpfluPvv54uellf0BLOvlcyoRDDjTQnfZhlLUAINtaVnyYS2kRLZpHuPSqvDViRVH/OC9utt0MHZq744LftBx0H8Q//PT8vBp@ckByc2A7mB3EBu4NnAzyQPI3MjcyNzI5@N3JHdAG4AN4AbcDYgvpmR7N5LlrUSUm/VFQ "Wolfram Language (Mathematica) ‚Äì Try It Online")
un-golfed: inspired by [Wikipedia](https://en.wikipedia.org/wiki/Church_encoding#Church_Booleans),
```
t[x_, y_] := x
f[x_, y_] := y
and[x_, y_] := x[y, f]
or[x_, y_] := x[t, y]
not[x_] := x[f, t]
xor[x_, y_] := y[not[x], x]
imply[x_, y_] := x[y, t]
```
[Answer]
# [Underload](https://github.com/catseye/stringie), ~~56~~ 52 bytes
```
(~!)(!)((~)~*):((!)~^)*(:^)(~(!)~^(~)~*)(()~(~)~^~*)
```
[Try it online!](https://tio.run/##zZK9CsMgEMd3n8JuZ6DQdvQ1sguCtgSsFpNAp3t1m1y0ZGjqqpv@P@6HOntjowvapAR4Evy74HLW8cGnOFspesYkB37XbrQCgU4Fqh7YKsE@V4LkrSYBBXYlDVdK@jCV3EKE6ld8ETkciVu3BDKIbuu@Ubf2Zt9dH/DXQeIxR@mokYJU@QoyZYgNQiIZ8oNl0OH5coMdG6SFdc6yp9@Vad8N3mtKHw "Underload ‚Äì Try It Online") (includes a testsuite and text identifying parts of the program)
This scores surprisingly well for a very low-level esolang. (Church numerals, Church booleans, etc. are very commonly used in Underload for this reason; the language doesn't have numbers and booleans built in, and this is one of the easier ways to simulate them. That said, it's also common to encode booleans as the Church numerals 0 and 1.)
For anyone who's confused: Underload lets you define reusable functions, but doesn't let you name them in the normal way, they just sort of float around on the argument stack (so if you define five functions and then want to call the first one you defined, you need to write a new function that takes five arguments and calls the fifth of them, then call it with insufficiently many arguments so that it looks for spare arguments to use). Calling them destroys them by default but you can modify the call to make it non-destructive (in simple cases, you just need to add a colon to the call, although the complex cases are more common because you need to make sure that the copies on the stack don't get in your way), so Underload's function support has all the requirements we'd need from the question.
## Explanation
### true
```
(~!)
(  )  Define function:
 ~      Swap arguments
  !     Delete new first argument (original second argument)
```
This one's fairly straightforward; we get rid of the argument we don't want and the argument we do want just stays there, serving as the return value.
### false
```
(!)
( )   Define function:
 !      Delete first argument
```
This one's even more straightforward.
### not
```
((~)~*)
(     )  Define function:
    ~*     Modify first argument by pre-composing it with:
 (~)         Swap arguments
```
This one's fun: `not` doesn't call its argument at all, it just uses a function composition. This is a common trick in Underload, in which you don't inspect your data at all, you just change how it functions by pre- and post-composing things with it. In this case, we modify the function to swap its arguments before running, which clearly negates a Church numeral.
### and
```
:((!)~^)*
 (     )   Define function:
     ~^      Execute its first argument with:
  (!)          false
               {and implicitly, our second argument}
        *  Edit the newly defined function by pre-composing it with:
:            {the most recently defined function}, without destroying it
```
The question permits defining functions in terms of other functions. We define "and" next because the more recently "not" has been defined, the easier it is to use it. (This doesn't subtract from our score, because we aren't naming "not" at all, but it saves bytes over writing the definition out again. This is the only time that one function refers to another, because referring to any function but the most recently defined would cost too many bytes.)
The definition here is `and x y = (not x) false y`. In other words, if `not x`, then we return `false`; otherwise, we return `y`.
### or
```
(:^)
(  )  Define function:
 :      Copy the first argument
  ^     Execute the copy, with arguments
          {implicitly, the original first argument}
          {and implicitly, our second argument}
```
@Nitrodon pointed out in the comments that `or x y = x x y` is normally shorter than `or x y = x true y`, and that turns out to be correct in Underload as well. A naive implementation of that would be `(:~^)`, but we can golf off an additional byte by noting that it doesn't matter whether we run the original first argument or the copy of it, the result is the same either way.
Underload doesn't actually support currying in the usual sense, but definitions like this make it look like it does! (The trick is that non-consumed arguments just stick around, so the function you call will interpret them as its own arguments.)
### implies
```
(~(!)~^(~)~*)
(           )  Define function:
 ~               Swap arguments
     ~^          Execute the new first (original second) argument, with argument:
  (!)              false
                   {and implicitly, our second argument}
       (~)~*     Run "not" on the result
```
The definition used here is `implies x y = not (y false x)`. If y is true, this simplifies to `not false`, i.e. `true`. If y is false, this simplifies to `not x`, thus giving us the truth table we want.
In this case, we're using `not` again, this time by rewriting its code rather than referencing it. It's just written directly as `(~)~*` without parentheses around it, so it gets called rather than defined.
### xor
```
(()~(~)~^~*)
(          )  Define function:
   ~   ~^       Execute the first argument, with arguments:
    (~)           "swap arguments"
 ()               identity function
         ~*     Precompose the second argument with {the result}
```
This time, we're evaluating only one of our two arguments, and using it to determine what to compose onto the second argument. Underload lets you play fast and loose with arity, so we're using the first argument to choose between two two-argument two-return functions; the argument swap that returns them both but in the opposite order, and the identity function that returns them both in the same order.
When the first argument is true, we therefore produce an edited version of the second argument that swaps its arguments before running, i.e. precompose with "swap arguments", i.e. `not`. So a true first argument means we return `not` the second argument. On the other hand, a false first argument means we compose with the identity function, i.e. do nothing. The result is an implementation of `xor`.
[Answer]
# [J](http://jsoftware.com/), 67 bytes - 7 = 60
```
t=.[
f=.]
n=.~
a=.2 :'u v]'
o=.2 :'[u v'
x=.2 :'u~v u'
i=.2 :'v u['
```
[Try it online!](https://tio.run/##fZC9DsMgDIR3P4U3JwtDx0q8QaesKENU1QodwkIiprw6jaBJ84O7IHzH8R28Y/RaGWCtWhi0mqHT6oZ3GnFqCVwezDIRhK8zTzgS2Dwte0Px9ewd0oNQp9UjNQRZbFaRk3hWK49DvTu@3VHxalwcjx36usRIFpctllP8SxVg7hg7WiyVdzLMnWD7@kGGBRkWZFj48zIrf6OVYVaqyFsqfgA "J ‚Äì Try It Online")
Worth noting:
Higher order functions work differently in J than in a functional language. To create a new verb from 1 or 2 existing verbs, you need to use either an adverb (in the case of 1) or a conjunction (in the case of 2).
Syntactically, adverbs come after a verb, and conjunctions go between them. Thus to "not" a verb `f` you do `f n`, and to "and" verbs `f` and `g`, you `f a g`.
[Answer]
# [Ruby](https://www.ruby-lang.org/), 82 - 4 = 78 bytes
```
f,t,a,n,i,o,x=%w(y:y x:x f:y t:f t:y y:t y:n[y]).map{|s|eval"->x,y=0{x==f ?#{s}}"}
```
[Try it online!](https://tio.run/##VYjBCgIxDETvfkVYERSirNdC9UNCDxUMCNotblcTuv32WhEFD29m3tynk9bKmNBjwAsOKHb1XKtRECPArZPhhoKa1AikbrO7@ZjncT4//LXbHgTV9lmsZTgu81hKV2oEph73bhHBU0J2Xxv@LFD6baFA7PAdn6@@AA "Ruby ‚Äì Try It Online")
[Answer]
# Java 8, score: ~~360~~ ~~358~~ ~~319~~ ~~271~~ 233 (240-7) bytes
```
interface J<O>{O f(O x,O y,J...j);}J t=(x,y,j)->x;J f=(x,y,j)->y;J n=(x,y,j)->j[0].f(y,x);J a=(x,y,j)->j[0].f(j[1].f(x,y),y);J o=(x,y,j)->j[0].f(x,j[1].f(x,y));J x=(x,y,j)->j[0].f(j[1].f(y,x),j[1].f(x,y));J i=(x,y,j)->j[0].f(j[1].f(x,y),x);
```
~~This was trickier to accomplish than I thought when I started it.. Especially the `implies`. Anyway, it works.. Can probably be golfed a bit here and there.~~ EDIT: Ok, not re-using functions but just duplicating the same approach is a lot cheaper in terms of byte-count for Java.. And I get the full -7 bonus for not using any of the functions as well.
[Try it online.](https://tio.run/##rZBBa4MwGIbv/RUfngyk2Xada6E7DCZsHrrDoPSQtcmI00Q0dhHxt7vYS7eJ2pSGQPySx3zvk5ge6Dzef7W7hBYFvFAh61ZIzXJOdwzCh2hZR8D9CAyOoMIhISRGQROCXvgGVzhG86UJQuCnsrKlPJXx5nZLuF9hg@wB7R3Em7tusbvITouoHmLwL6hDzNAtXZf/sBhtaVO1AFn5kYgdFJpquxyU2ENq38Jf61zIz80WKKpnYEf3QpAuJPs@fvooOG6vq0KzlKhSk8z@oRPpe295yW6eaFKwe/CGuZRom8Vbedh79NAYx8/iRhK9Kj0RRZ5aYBsMnc/yyyKt5H4iEv0baTJWn@cOPHe8n1@uHuUT5srRXDmaK0dzdS3zdzWlbhzVjaO6cVQ311J/TrNEsGJCXzjqC0d94agvhvSbWdP@AA)
**Explanation:**
```
// Create an interface J to create lambdas with 2 Object and 0 or more amount of optional
// (varargs) J lambda-interfaces, which returns an Object:
interface J<O>{O f(O x,O y,J...j);}
// True: with parameters `x` and `y`, always return `x`
J t=(x,y,j)->x;
// False: with parameters `x` and `y`, always return `y`
J f=(x,y,j)->y;
// Not: with parameters `x`, `y`, and `j` (either `t` or `f`), return: j(y, x)
J n=(x,y,j)->j[0].f(y,x);
// And: with parameters `x`, `y`, and two times `j` (either `t` or `f`), return:
//      j1(j2(x,y), y);
J a=(x,y,j)->j[0].f(j[1].f(x,y),y);
// Or: with parameters `x`, `y`, and two times `j` (either `t` or `f`), return:
//     j1(x, j2(x,y))
J o=(x,y,j)->j[0].f(x,j[1].f(x,y));
// Xor: with parameters `x`, `y`, and two times `j` (either `t` or `f`), return:
//      j1(j2(y,x), j2(x,y))
J x=(x,y,j)->j[0].f(j[1].f(y,x),j[1].f(x,y));
// Implies: with parameters `x`, `y`, and two times `j` (either `t` or `f`), return:
//          j1(j2(x,y), x)
J i=(x,y,j)->j[0].f(j[1].f(x,y),x);
```
[Answer]
# C++17, ~~207−49=158~~ 195 − 58 = 137 bytes
The linebreaks are unnecessary (other than the first two).
```
#define A auto
#define D(v,p)A v=[](A x,A y){return p;};
D(true_,x)
D(false_,y)
A not_=[](A f){return f(false_,true_);};
D(and_,x(y,false_))
D(or_,x(true_,y))
D(xor_,x(not_(y),y))
D(implies,x(y,true_))
```
[Try it online!](https://tio.run/##nZOxboMwEIZ3nuKkDtgKGTp1QAxIjJlYqwpZYCJLxFjYREZRXr3UYGjahKaGDZ//784fhlyIfV4Rfuz7l4KWjFOIgbSq9uZlgs6BwDGco/cPFIMOYujwpaGqbTiI8Bp6CVJNS7NA4wSVpJLmsTMAr1VmmfI7X86BkcCGThDhhWFRF9gtbLrUzVCxXbuhoG1laIk6bGvsJCpG5YjadriXiiiWZ0RK2ijkH3yIIhg3h0UAfupjHHp3sXSM2fG/csvB8RR24rOuh1t4Mnva28aHlzGJw/8j0gdmadLf0HQZ6ybNkLuUuTx3pwfEQenGrDX6ybgIWUpvMNJblPQWJ71Wys6a/qe1X98d5qw2c@52y9yiIOMKToRxhOFy7T/zsiJH2e@lKqJ8t3t9@wI)
Unit-tested with assertions such as:
```
static_assert('L' == true_('L', 'R'));
static_assert('R' == not_(true_)('L', 'R'));
static_assert('L' == and_(true_, true_)('L', 'R'));
static_assert('L' == or_(true_, true_)('L', 'R'));
static_assert('R' == xor_(true_, true_)('L', 'R'));
static_assert('L' == implies(true_, true_)('L', 'R'));
```
UPDATED: formerly I'd had
```
A not_=[](A f){return[f](A x,A y){return f(y,x);};};
```
but [Roman's answer](https://codegolf.stackexchange.com/a/190398/11791) pointed the way to the shorter version. Notice that now `not_(std::plus<>)` is ill-formed, where formerly it was equivalent to `std::plus<>`; but since `std::plus<>` doesn't "represent a Church boolean," I think either behavior is okay by the rules.
[Answer]
# [Forth (gforth)](http://www.complang.tuwien.ac.at/forth/gforth/Docs-html/), 133  bytes - 7 = 126 122
```
: j execute ;
: t drop ;
: f nip ;
: n ['] f ['] t rot j ;
: a dup j ;
: o over j ;
: x 2dup a n -rot o a ;
: m over n -rot a o ;
```
[Try it online!](https://tio.run/##hY/NDsIgEITvPsXcsEm9eNRHUQ/Egta0bIPUtE9flz@jtlEOMAzf7C6arLtuLtof07TDDWpQ594p7Fc7OFSWuiA1TB2VwUGc@O53B0uOQ96XqPouaQI9lE2XAVv/Ijm58Tix9H4boeRK9vc8gXpNoNra4WyZFQPEyM2yE9YRzvZqPZQYi0Tob0LL5v6JCC5juAkyYsitfaFihgmuRxE9gmygylhyGZYZlqb6T5vIv9N@lphYjrS5Qd12Ta3uv5rokJolAlvi7cfTEw "Forth (gforth) ‚Äì Try It Online")
-4 bytes thanks to Quuxplusone
Initially I significantly overthought this, considering things like macros and literals, but then I realized that if I define things in terms of true and false (like I should have done in the first place), it gets much simpler.
### Code explanation
```
\ Helper function to save some bytes
: j        \ define a new word
  execute  \ execute the word at the provided address
;          \ end word definition
\ True
: t        \ define a new word
  drop     \ drop the second argument
;          \ end the word
\ False
: f        \ define a new word
  nip      \ drop the first argument
;          \ end the word
\ Not - The "hardest" one because we have to reference true and false directly
: n        \ define a new word
  ['] f    \ get address of false
  ['] t    \ get the address of true
  rot      \ stick the input boolean back on the top of the stack
  j        \ call the input boolean, which will select the boolean to return
;          \ end the word
\ And 
: a        \ define a new word
  dup      \ duplicate the 2nd input value
  j        \ call the 2nd input on the first and second input
;          \ end the word
\ Or
: o        \ define a new word
  over     \ duplicate the 1st input value
  j        \ call the 1st input on the first and second input
;          \ end the word
\ Xor
: x        \ define a new word
  2dup     \ duplicate both of the inputs
  a n      \ call and, then not the result (nand)
  -rot     \ move the result behind the copied inputs
  o a      \ call or on the original inputs, then call and on the two results
;          \ end the word
\ Implies
: m        \ define a new word
  over     \ duplicate the 1st input value
  n        \ call not on the 1st input value
  -rot     \ move results below inputs
  a o      \ call and on the two inputs, then call or on the two results
;          \ end the word
```
[Answer]
## SKI-calculus + C combinator, ~~36~~ 33 bytes
```
true=K
false=SK
not=C
and=SCI
or=SII
xor=C(CIC)I
implies=CCK
```
I don't actually know of any interpreter that allows you to define additional combinators in terms of previous ones, so I had to test this using <http://ski.aditsu.net/> by pasting in the desired combinators e.g. `CCKK(SK)pq` outputs `q`, showing that `K` does not imply `SK`.
Edit: Saved 3 bytes thanks to @Bubbler.
[Answer]
# [APL (dzaima/APL)](https://github.com/dzaima/APL), 47 [bytes](https://codegolf.meta.stackexchange.com/a/9429/43319 "When can APL characters be counted as 1 byte each?")[SBCS](https://github.com/abrudz/SBCS ".dyalog files using a single byte character set")
Based on [Jonah's J solution](https://codegolf.stackexchange.com/a/190379/43319).
`true` and `false` are infix functions, `not` is a suffix operator, and the rest are infix operators.
```
true‚Üê‚ä£
false‚Üê‚ä¢
and‚Üê{‚ç∫(‚ç∂‚çπfalse)‚çµ}
not‚Üê‚ç®
or‚Üê{‚ç∫(true‚ç∂‚çπ)‚çµ}
xor‚Üê{‚ç∫(‚ç∂not‚çπ‚ç∂)‚çµ}
implies‚Üê{‚ç∫(‚çπ‚ç∂true)‚çµ}
```
As per OP, this counts everything from and including `‚Üê` to the end of each line, and counts each call a previous definition as a single byte.
[Try it online!](https://tio.run/##dZFNDsIgEIX3nKI7dNELeBuS1oSkLQ2tCWrcujAh8Qy68QKa1ONwEHGA/gDibnjvm/cmgbRVXhwIrYnWPd@V6nxVlzvakqpz8w2RpoDpqOR7peRLycGaayWfJ9Sw3lDygRifIBtjQceIxQLZbMgBBmfSuq1o2S2AsUyCtbXGZs7ghMy2bjDCAmdWxHv3sIZ7AecTZi1Aw7Ao4YdeZA@H@/0KeEb8rDDug4wnTgExdUnMzqoPh/EimS/@FIh0Q4SPf@PXjFKianJSdcmt0JrXPqztKWs6nXdf "APL (dzaima/APL) ‚Äì Try It Online")
true and false are the left and right identity functions.
`not` simply swaps the arguments of its operand function.
The rest implement the decision tree:
`and` uses the righthand function `‚çπ` to select the result of the lefthand function `‚ç∂` if true, else the result of the `false` function.
`or` uses the lefthand function `‚ç∂` to select the `true` if true, else the result of the righthand function `‚çπ`.
`xor` uses the righthand function `‚çπ` to select the the negated result of the lefthand function `‚ç∂not` if true, else the result of the lefthand function.
`implies` uses the lefthand function `‚ç∂` to select the result of the righthand function `‚çπ` if true, else the result of the `true` function.
[Answer]
# [Julia 1.0](http://julialang.org/), 36 bytes
```
(b::Bool)(x,y)=b ? x : y;i(x,y)=!x|y
```
I don't know if that counts, I'm actually just overloading the native `Bool` type to be callable, so I get most of the logic gates for free. Unfortunately, Julia doesn't have an `implies` gate, so I had to write my own function.
[Try it online!](https://tio.run/##yyrNyUw0rPj/XyPJysopPz9HU6NCp1LTNknBXqFCwUqh0joTIqBYUVP5v6AoM68kJ0@jpKg0VcOqQkfBqlJTkwsmmpaYU4xFWEMRpFwTiwRIXKFGAawPp7waQXlFXAoywSp0cEuDZXRQnfcfAA "Julia 1.0 ‚Äì Try It Online")
[Answer]
# [Perl 6](https://github.com/nxadm/rakudo-pkg), ~~120~~ ~~106~~ ~~102~~ 101 bytes
*-1 byte thanks to Jo King*
```
my (\t,\f,&n,&a,&o,&i,&x)={@_[0]},{@_[1]},|<f,t &^v,f t,&^v &^v,t n(&^v),&v>>>.&{"&\{\&^u($_)}".EVAL}
```
[Try it online!](https://tio.run/##bY/NasMwEITP1lMsxmxk2Jr20kN@THJoTj2GXqommDQLhkQKjhocFD@7K9kkNSWnmZ2P0aDjrtq/tu3hAlJZUkyoCQtCQ1gS1unMzTefz18NBX3xep0yWcD1mRgsee28BS29poTnPM8zdDEqp3D9I5NN2sTZ28fivQkryWoJM7hOV7DMJ0KcigvEdgwObCY9S6GJJ33KIeX/qTZW2nQMqL10bEi4J3wngk0lolGhv0cE/l/emypYE2x5OO7L3SncZbjrntXiKYdEe7cFF4moez7RSlrqprfewN/6kPOd8wPOtz4/7vOtz8N@0/4C "Perl 6 ‚Äì Try It Online")
[Answer]
# C++17, ~~202−49=153~~ 193 − 58 = 135 bytes
Inspired by the comment-discussion of what counts as a 2-ary function anyway, here's a [curried](https://en.wikipedia.org/wiki/Currying) version of my previous C++17 solution. It's actually shorter because we can use the same macro to define `not_` as to define all the other functions!
```
#define D(v,p)auto v=[](auto x){return[=](auto y){return p;};};
D(true_,x)
D(false_,y)
D(not_,x(false_)(true_)(y))
D(and_,x(y)(false_))
D(or_,x(true_)(y))
D(xor_,x(not_(y))(y))
D(implies,x(y)(true_))
```
[Try it online!](https://tio.run/##nZNBj4MgEIXv/RUke5BJ28Oe9tB489iT16ZpCGJDYtEINpimf31ZEE271u2i8YJv3pvhA6VVtaUFEWdjPjKWc8FQgq@bCkijSnSND0fcrTTcaqaaWhziXmkHBVW7u31WCVZ1w04bDQnOSSHtsrVLUSqr9Qp4D@AWbImIzJVaGKpWK2snPbu0l1wfJ3iRX6qCM@nT3g1GKqI4PREpWa1wtI9QHKOu6F4AR2kEsFuNbGln8zv45Zs2dvvo9/em6/5hHtDf9fZ2dyBD7/9HpC@ZqUl/h0ZXMi8UDmWvL5zpJRKA9MjMJXrOhAD5lF5ApJcg6SVMei6Un9X/UHO/vlEsGG3IhdNN5yYBuVDoQrjAgG53803zgpyl2UqVxXS9/vz6AQ)
This one is tested with assertions like
```
static_assert('R' == and_(true_)(false_)('L')('R'));
static_assert('L' == or_(true_)(false_)('L')('R'));
```
Notice that `or_` is defined as effectively
```
auto or_=[](auto x){return[=](auto y){return x(true_)(y);};};
```
We could define `or_` more "concisely" as
```
auto or_=[](auto x){return x(true_);};
```
but that would cost us because we wouldn't get to use the `D` macro anymore.
[Answer]
# [Birb](https://esolangs.org/wiki/Birb), 23 (or 41?) bytes
```
true: üê¶üê•
false: üê•üê¶
not: üê•ü¶©üïä
and: üê¶ü¶©ü¶úüê•ü¶¢
or: üêßüê¶ü¶ú
xor: ü¶©ü¶©ü¶©üê¶ü¶©
implies: ü¶úü¶©üê•
```
It works a bit like @Neil's answer, but Birb's alternating associative order changes things a bit. Here are the respective parentheses to indicate the associativity:
```
true: (üê¶üê•)
false: (üê•üê¶)
not: ((üê•ü¶©)üïä)
and: ((üê¶((ü¶©ü¶ú)üê•))ü¶¢)
or: ((üêßüê¶)ü¶ú)
xor: ((ü¶©((ü¶©ü¶©)üê¶))ü¶©)
implies: ((ü¶úü¶©)üê•)
```
You may realize that several programs could be significantly shorter (e.g. `true: üê•`, `not: ü¶©`, `or: ü¶ú`, or `and: ü¶©ü¶¢ü¶¢üê•`. However, to have a uniform way of application (due to Birb's alternating associativity), `true` and `false` need to have the same length and all other functions need an odd length >2. I also tried to use a variety of birbs :)
Example applications:
```
not true
~> üê¶üêß üê•ü¶©üïä üê¶üê•
~> [üê¶] (false)
xor true false
~> üê¶üêß üê¶üêß ü¶©ü¶©ü¶©üê¶ü¶© üê¶üê• üê•üê¶
~> üê• (true)
```
I'm unsure whether to count the additional üê¶üêß.. If not, the sum of the length of all Birb functions is 23 bytes. If yes, `2+l(not) + 4+l(and) + 4+l(or) + 4+l(xor) + 4+l(implies) = 41` bytes.
[Answer]
# [Stax](https://github.com/tomtheisen/stax), 34 [bytes](https://github.com/tomtheisen/stax/blob/master/docs/packed.md#packed-stax)
```
¬øS¬£‚Üì‚ô£‚îî¬≤‚â°√©‚ô´J√≠g‚ñëE√®Œ©RŒ¶‚ôÇ¬∞‚î§r√†‚ïù¬∂œÄ√Ø‚ï°^O|Œò√†
```
[Run and debug it at staxlang.xyz!](https://staxlang.xyz/#p=a8539c1905c0fdf0820e4aa167b0458aea52e80bf8b47285bc14e38bb55e4f7ce985&i=)
Pushes a bunch of blocks to the stack. Each block expects its last argument atop the stack, followed in reverse order by the rest.
### Unpacked (41 bytes):
```
{sd}Y{d}{y{d}a!}X{ya!}{b!}{cx!sa!}{sx!b!}
```
Each pair of `{ }` is a block. I used the two registers X and Y to hold `true` and `not` so I could access 'em easily later. Unfortunately, `false` couldn't simply be a no-op, as that would leave the stack cluttered and mess up a single XOR case.
[Test suite, commented](https://staxlang.xyz/#c=%7Bsd%7DY%09%09false%0A%7Bd%7D%09%09true%0A%7By%7Bd%7Da%21%7DX%09not%0A%7Bya%21%7D%09%09and%0A%7Bb%21%7D%09%09or%0A%7Bcx%21sa%21%7D%09xor%0A%7Bsx%21b%21%7D%09%09implies%0A%0ALr%7E%09%09Put+in+a+list+in+the+input+stack%0A%0A%22false%3A+%22p%0A%3B0%40%09%09Push+false%0AOZ%21P%09%09Apply+to+1+and+0%3B+print%0ALrh%7E%09%09Clean+up+the+stack%0A%0A%22true%3A+%22p%0A%3B1%40%09%09Push+true%0AOZ%21P%09%09Apply+to+1+and+0%3B+print%0ALrh%7E%09%09Clean+up%0A%0A%22not%3A+%22p%0A%3B0%40%09%09Push+false%0A%3B2%40%21%09%09Apply+not%0AOZ%21p%09%09Apply+to+1+and+0%3B+print%0A%3B1%40%09%09Push+true%0A%3B2%40%21%09%09Apply+not%0AOZ%21P%09%09Apply+to+1+and+0%3B+print%0A%0A%22and%3A+%22p%0A%3B0%40%3B0%40%09%09Push+false+and+false%0A%3B3%40%21%09%09Apply+and%0AOZ%21p%09%09Apply+to+1+and+0%3B+print%0A%3B0%40%3B1%40%09%09Push+false+and+true%0A%3B3%40%21%09%09Apply+and%0AOZ%21p%09%09Apply+to+1+and+0%3B+print%0A%3B1%40%3B0%40%09%09Push+true+and+false%0A%3B3%40%21%09%09Apply+and%0AOZ%21p%09%09Apply+to+1+and+0%3B+print%0A%3B1%40%3B1%40%09%09Push+true+and+true%0A%3B3%40%21%09%09Apply+and%0AOZ%21P%09%09Apply+to+1+and+0%3B+print%0A%0A%22or%3A+%22p%0A%3B0%40%3B0%40%09%09Push+false+and+false%0A%3B4%40%21%09%09Apply+or%0AOZ%21p%09%09Apply+to+1+and+0%3B+print%0A%3B0%40%3B1%40%09%09Push+false+and+true%0A%3B4%40%21%09%09Apply+or%0AOZ%21p%09%09Apply+to+1+and+0%3B+print%0A%3B1%40%3B0%40%09%09Push+true+and+false%0A%3B4%40%21%09%09Apply+or%0AOZ%21p%09%09Apply+to+1+and+0%3B+print%0A%3B1%40%3B1%40%09%09Push+true+and+true%0A%3B4%40%21%09%09Apply+or%0AOZ%21P%09%09Apply+to+1+and+0%3B+print%0A%0A%22xor%3A+%22p%0A%3B0%40%3B0%40%09%09Push+false+and+false%0A%3B5%40%21%09%09Apply+xor%0AOZ%21p%09%09Apply+to+1+and+0%3B+print%0A%3B0%40%3B1%40%09%09Push+false+and+true%0A%3B5%40%21%09%09Apply+xor%0AOZ%21p%09%09Apply+to+1+and+0%3B+print%0A%3B1%40%3B0%40%09%09Push+true+and+false%0A%3B5%40%21%09%09Apply+xor%0AOZ%21p%09%09Apply+to+1+and+0%3B+print%0A%3B1%40%3B1%40%09%09Push+true+and+true%0A%3B5%40%21%09%09Apply+xor%0AOZ%21P%09%09Apply+to+1+and+0%3B+print%0A%0A%22implies%3A+%22p%0A%3B0%40%3B0%40%09%09Push+false+and+false%0A%3B6%40%21%09%09Apply+implies%0AOZ%21p%09%09Apply+to+1+and+0%3B+print%0A%3B0%40%3B1%40%09%09Push+false+and+true%0A%3B6%40%21%09%09Apply+implies%0AOZ%21p%09%09Apply+to+1+and+0%3B+print%0A%3B1%40%3B0%40%09%09Push+true+and+false%0A%3B6%40%21%09%09Apply+implies%0AOZ%21p%09%09Apply+to+1+and+0%3B+print%0A%3B1%40%3B1%40%09%09Push+true+and+true%0A%3B6%40%21%09%09Apply+implies%0AOZ%21P%09%09Apply+to+1+and+0%3B+print&i=&a=1)
```
false
{sd}    stack:   x y
 s      swap:    y x
  d     discard: y
true
{d}    stack:   x y
 d     discard: x
not
{y{d}a!}    stack:  p
 y{d}       push:   p f t
     a      rotate: f t p
      !     apply:  p(f,t)
and
{ya!}    stack:  p q
 y       push:   p q f
  a      rotate: q f p
   !     apply:  p(q,f)
or
{b!}    stack:  p q
 b      copies: p q p q
  !     apply:  p q(q,p)
xor
{cx!sa!}    stack:  p q
 c          copy:   p q q
  x!        not:    p q nq
    s       swap:   p nq q
     a      rotate: nq q p
      !     apply:  p(nq,q)
implies
{sx!b!}    stack:  p q
 s         swap:   q p
  x!       not:    q np
    b      copies: q np q np
     !     apply:  q np(np,q)
```
[Answer]
# [Befunge-98](https://github.com/catseye/Funge-98/blob/master/doc/funge98.markdown#funge-98-final-specification), ~~105~~ ~~77~~ 65 bytes
Playing further with the notion of "function" in languages without functions... here's a Befunge-98 version of Church booleans!
In this constrained dialect of Befunge-98, a program consists of a series of "lines" or "functions," each of which begins with a `>`(Go Right) instruction in column x=0. Each "function" can be identified with its line number (y-coordinate). Functions can take input via Befunge's *stack*, as usual.
Line 0 is special, because (0,0) is the starting IP. To make a program that executes line L, just place instructions on line 0 that, when executed, fly the instruction pointer to (x=L, y=0).
The magic happens on line 1. Line 1, when executed, pops a number `L` from the stack and jumps to line number `L`. (This line had previously been `> >>0{{2u2}2}$-073*-\x`, which can "absolute jump" to any line; but I just realized that since I know this line is pegged to line 1, we can "relative jump" `L-1` lines in a heck of a lot less code.)
Line 2 represents Church `FALSE`. When executed, it pops two numbers `t` and `f` from the stack and then flies to line number `f`.
Line 3 represents Church `TRUE`. When executed, it pops two numbers `t` and `f` from the stack and then flies to line number `t`.
Line 6, representing Church `XOR`, is innovative. When executed, it pops two numbers `a` and `b` from the stack, and then flies to line `a` with stack input `NOT EXEC b`. So, if `a` represents Church `TRUE`, the result of `a NOT EXEC b` will be `NOT b`; and if `a` represents Church `FALSE`, the result of `a NOT EXEC b` will be `EXEC b`.
---
Here's the ungolfed version with test harness. On line 0, set up the stack with your input. For example, `338` means `IMPLIES TRUE TRUE`. Make sure the closing `x` appears at exactly (x,y)=(0,15) or else nothing will work! Also make sure your stack setup begins with `ba`, so that the program will actually terminate with some output.
[Try it online!](https://tio.run/##dZBda4MwFIbv9yteSi8iNGLUrl1wobJZKNgP1EIvRGhBy27aXSgoY7/daVaDY3rIRd4Dz5Nzckmz4nZN6cuSflbyWtcCuJxhWTZgZJSVTwJCMGqcaVyiX/7HLQXj8E7eGyk1ouu6hldc7/kdLTVNHDh9wFGUybF2/dAjuUYyRUrRIzZ8PE3wvyRvcUTBcQjPFW7Fo7jNsQ/akau/cNNptaovLeaAR1rmHLt91Nu8c8jVOtXDw@L5mOeZ4zQ2TvOARtqgRKYw7a@YFe0xLFp8J0q04HB378OiSo3VLTb0O7@eJcdme/A3Xjjq6u3WuCbeMYgms6ZWMoW@u5ZxtqrrHw)
```
>  ba 334  0f-1x
> >>1-0a-\x             Line 1: EXEC(x)(...) = goto x
> $^< <            <    Line 2: FALSE(t)(f)(...) = EXEC(f)(...)
> \$^                   Line 3: TRUE(t)(f)(...) = EXEC(t)(...)
> 3\^                   Line 4: OR(x)(y)(...) = EXEC(x)(TRUE)(y)(...)
> 3\2\^                 Line 5: NOT(x)(...) = EXEC(x)(FALSE)(TRUE)(...)
> 1\5\^                 Line 6: XOR(x)(y)(...) = EXEC(x)(NOT)(EXEC)(...)
> 2>24{\1u\1u\03-u}^    Line 7: AND(x)(y)(...) = EXEC(x)(y)(FALSE)(...)
> 3^                    Line 8: IMPLIES(x)(y)(...) = EXEC(x)(y)(TRUE)(...)
> "EURT",,,,@
> "ESLAF",,,,,@
```
---
Here's the version whose bytes I counted.
```
>>>1-0a-\x
>$^<< }u-30\<
>\$^
>3\^\
>3\2^
>1\5^
>2>24{\1u\1u^
>3^
```
Notice that to define a function in this dialect you don't mention its name at all; its "name" is determined by its source location. To call a function, you do mention its "name"; for example, `XOR` (`6`) is defined in terms of `NOT` and `EXEC` (`5` and `1`). But all my "function names" already take only one byte to represent. So this solution gets no scoring adjustments.
]