[Question]
  [
For example, the gate `A and B` is a logic gate with 2 inputs and 1 output.
There are exactly 16 of them, because:
* each logic gate takes two inputs, which can be truthy or falsey, giving us 4 possible inputs
* of the 4 possible inputs, each can have an output of truthy and falsey
* therefore, there are 2^4 possible logic gates, which is 16.
Your task is to write 16 programs/functions which implement all of them separately.
Your functions/programs **must be independent**.
They are valid as long as they output truthy/falsey values, meaning that you can implement `A or B` in Python as `lambda a,b:a+b`, even if `2` is produced for `A=True` and `B=True`.
Score is total bytes used for each function/program.
## List of logic gates
1. 0,0,0,0 (`false`)
2. 0,0,0,1 (`and`)
3. 0,0,1,0 (`A and not B`)
4. 0,0,1,1 (`A`)
5. 0,1,0,0 (`not A and B`)
6. 0,1,0,1 (`B`)
7. 0,1,1,0 (`xor`)
8. 0,1,1,1 (`or`)
9. 1,0,0,0 (`nor`)
10. 1,0,0,1 (`xnor`)
11. 1,0,1,0 (`not B`)
12. 1,0,1,1 (`B implies A`)
13. 1,1,0,0 (`not A`)
14. 1,1,0,1 (`A implies B`)
15. 1,1,1,0 (`nand`)
16. 1,1,1,1 (`true`)
Where the first number is the output for `A=false, B=false`,
the second number is the output for `A=false, B=true`,
the third number is the output for `A=true, B=false`,
the fourth number is the output for `A=true, B=true`.
# Leaderboard
```
var QUESTION_ID=82938,OVERRIDE_USER=48934;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+(?:\.\d+)?)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```
```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```
```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```
  
[Answer]
# [Dominoes](http://store.steampowered.com/app/286160/), 122,000 bytes or 72 tiles
The byte count is the size of the [saved file](http://steamcommunity.com/sharedfiles/filedetails/?id=876663282) which is `0.122 MB`.
[Domino computing](https://www.youtube.com/watch?v=OpLU__bhu2w) was the inspiration. I have tested all of these up to symmetry (and beyond!) via a virtual-reality Steam game called [*Tabletop Simulator*](http://store.steampowered.com/app/286160/).
## Details
* **I/O**
	+ **Start** - This is included for clarity (not counted towards total) and is what 'calls' or 'executes' the function. Should be 'pressed' after input is given **[Yellow]**.
	+ **Input A** - This is included for clarity (not counted towards total) and is 'pressed' to indicated a `1` and unpressed otherwise **[Green]**.
	+ **Input B** - This is included for clarity (not counted towards total) and is 'pressed' to indicated a `1` and unpressed otherwise **[Blue]**.
	+ **Output** - This is counted towards total. It is the domino that declares the result of the logic gate **[Black]**.
* **T/F**
	+ A fallen output domino represents a result of `True` or `1`
	+ A standing output domino represents a result of `False` or `0`
* **Pressing**
	+ To give input or start the chain, spawn the metal marble
	+ Set the lift strength to `100%`
	+ Lift the marble above the desired domino
	+ Drop the marble
[![enter image description here](https://i.stack.imgur.com/BmA89m.png)](https://i.stack.imgur.com/BmA89m.png)
## Gates
* **false, 1**
	+ [![enter image description here](https://i.stack.imgur.com/SwK9pm.png)](https://i.stack.imgur.com/SwK9pm.png)
* **and, ~~6~~ 4**
	+ [![enter image description here](https://i.stack.imgur.com/3bSW7m.png)](https://i.stack.imgur.com/3bSW7m.png)
* **A and not B, ~~4~~ 3**
	+ [![enter image description here](https://i.stack.imgur.com/8UiAmm.png)](https://i.stack.imgur.com/8UiAmm.png)
* **A, 1**
	+ [![enter image description here](https://i.stack.imgur.com/g1egvm.png)](https://i.stack.imgur.com/g1egvm.png)
* **not A and B, ~~4~~ 3**
	+ [![enter image description here](https://i.stack.imgur.com/WjwPKm.png)](https://i.stack.imgur.com/WjwPKm.png)
* **B, 1**
	+ [![enter image description here](https://i.stack.imgur.com/VdVLLm.png)](https://i.stack.imgur.com/VdVLLm.png)
* **xor, ~~15~~ 11**
	+ [![enter image description here](https://i.stack.imgur.com/qnaMMm.png)](https://i.stack.imgur.com/qnaMMm.png)
* **or, 1**
	+ [![enter image description here](https://i.stack.imgur.com/SKwmlm.png)](https://i.stack.imgur.com/SKwmlm.png)
* **nor, ~~3~~ 2**
	+ [![enter image description here](https://i.stack.imgur.com/Whukrm.png)](https://i.stack.imgur.com/Whukrm.png)
* **xnor, ~~17~~ 13**
	+ [![enter image description here](https://i.stack.imgur.com/QelNAm.png)](https://i.stack.imgur.com/QelNAm.png)
* **not B, 2**
	+ [![enter image description here](https://i.stack.imgur.com/vZdDlm.png)](https://i.stack.imgur.com/vZdDlm.png)
* **B implies A, ~~7~~ 6**
	+ [![enter image description here](https://i.stack.imgur.com/g2kGzm.png)](https://i.stack.imgur.com/g2kGzm.png)
* **not A, 2**
	+ [![enter image description here](https://i.stack.imgur.com/gFuXfm.png)](https://i.stack.imgur.com/gFuXfm.png)
* **A implies B, ~~7~~ 6**
	+ [![enter image description here](https://i.stack.imgur.com/kDziRm.png)](https://i.stack.imgur.com/kDziRm.png)
* **nand, ~~16~~ 15**
	+ [![enter image description here](https://i.stack.imgur.com/ZGeUam.png)](https://i.stack.imgur.com/ZGeUam.png)
	+ **true, 1**
	+ [![enter image description here](https://i.stack.imgur.com/86L2Gm.png)](https://i.stack.imgur.com/86L2Gm.png)
---
## TL;DR
I had been waiting/wanting a domino-friendly challenge and when I saw this, I couldn't pass it up. The only problem was that apparently no one owns dominoes any more! So eventually I gave in and bought a [*Double Twelve*](http://rads.stackoverflow.com/amzn/click/B00004T71M). This set has 91 tiles, which gave me the idea of have a 'function call'/start domino instead of the normal (long) 'time delay' method. Credit for the 90 degree turn belongs to [dominoesdouble07's channel](https://www.youtube.com/watch?v=oasKtlLNBZY).
After building these with physical dominoes, it was [ruled](http://meta.codegolf.stackexchange.com/a/10151/43214) on meta that valid solutions should be digital. So I recreated these gates in [*Tabletop Simulator*](http://store.steampowered.com/app/286160/). Sadly, TS and reality don't agree on domino physics. This required me adding 11 dominoes but I also saved 8. Overall, virtual dominoes are about x150 more effective in terms of building and testing (`Ctrl`+`Z`).
**Update**
* **-9** [17-03-13] Shortened `xor xnor nand`
* [17-03-04] Added link to workshop file
* **+11** [17-03-03] Added digital `xnor` and `xor`
* **-8** [17-03-03] Digitized all the gates (except `xor` and `xnor`). Blocking on Tabletop only requires 1 domino, instead of 2.
* [16-09-23] Shrunk images
* **-11** [16-09-18] Nearly cut xor in half again. Thanks to *@DJMcMayhem* for xnor and *Joe* for xor.
* **-31** [16-08-31] Updated some pics and shaved some tiles and cut *xor* in half
* [16-08-28] Added pictures
[Answer]
## [Hexagony](https://github.com/m-ender/hexagony), 89 bytes
*Thanks to FryAmTheEggman for some necessary inspiration for the XOR solution.*
```
0000 !@
0001 ?.|@!
0010 #?#!)@
0011 ?!@
0100 +?|@!?
0101 ??!@
0110 ?<@!!<_\~(
0111 ?<<@!
1000 )\!#?@{
1001 (~?/@#!
1010 ??|@!)
1011 \#??!1@
1100 ?(~!@
1101 ?.|@!)
1110 ?$@#)!<
1111 1!@
```
All programs use `0` for false and `1` for true.
[Try it online!](http://hexagony.tryitonline.net/#code=PzxAISE8X1x-KA&input=MSAw) This is not a test suite, you'll have to copy in the different programs and inputs yourself.
The above solution is within 2-bytes of optimality (unless we relax the truthy/falsy interpretation, I guess). I've let a brute force search run for close to two days over all programs that fit into side-length 2, i.e. up to 7 bytes (not *quite* all programs - I made a few assumptions on what every valid program needs and what no valid program could have). The search found solutions for 15 of the 16 possible gates - and often a lot more than just one. You can find a list of all the alternative solutions [in this pastebin](http://pastebin.com/EZV81AZt) where I've also grouped them by equivalent behaviour. The ones I'm showing above I've selected because they are either the simplest or the most interesting solution, and I'll add explanations for them tomorrow.
As for the 16th gate: XOR is the only gate that can apparently not be implemented in 7 bytes. A brute force search over larger programs is unfortunately not feasible with the code I currently have. So XOR had to be written by hand. The shortest I've found so far is the above 10-byte program, which is based on a failed (but very close) attempt by FryAmTheEggman. It's possible that an 8-byte or 9-byte solution exists, but other than that, all the solutions should indeed be optimal.
## Explanations
Warning: wall of text. On the off-chance anyone's interested how these highly compressed Hexagony programs actually work, I've included explanations for each of them below. I've tried to choose the simplest solution for each gate in cases where more than one optimal program exists, in order to keep the explanations reasonably short. However, some of them still boggle the mind, so I thought they deserve a bit more elaboration.
### `0000`: False
I don't think we'll need a diagram for this one:
```
 ! @
. . .
 . .
```
Since the entire memory grid is initialised to zeros, `!` simply prints a zero and `@` terminates the program.
This is also the only 2-byte solution.
### `0001`: And
```
 ? .
| @ !
 . .
```
This basically implements [short-circuiting](https://en.wikipedia.org/wiki/Short-circuit_evaluation). The grey diagram below shows the beginning of the program, where the first input is read with `?` and the instruction pointer (IP) wraps around to the the left corner where the `|` mirror reflects it. Now the corner acts as a conditional, such there are two different execution paths depending on the value of the first input. The red diagram shows the control flow for `A = 0` and the green diagram for `A = 1`:
[![i](https://i.stack.imgur.com/iKzSQ.png)](https://i.stack.imgur.com/iKzSQ.png) [![i](https://i.stack.imgur.com/pWnmj.png)](https://i.stack.imgur.com/pWnmj.png) [![i](https://i.stack.imgur.com/xdTI6.png)](https://i.stack.imgur.com/xdTI6.png)
As you can see, when the `A` is `0`, then we simply print it and terminate (remember that all `.` are no-ops). But when `A` is `1`, then the IP traverses the first row again, reading `B` and printing that instead.
In total there are sixteen 5-byte solutions for this gate. Fourteen of those are essentially the same as the above, either using `>` instead of `|` or replacing the `.` with a command that's effectively a no-op, or putting `?` in the second position:
```
?.|@!    .?|@!    ?=|@!    =?|@!    ?_|@!    _?|@!    ?0|@!
?.>@!    .?>@!    ?=>@!    =?>@!    ?_>@!    _?>@!    ?0>@!
```
And then there are two other solutions (which are equivalent to each other). These also implement the same short-circuiting logic, but the execution paths are a bit crazier (and left as an exercise to the reader):
```
?<!@|
?<!@<
```
### `0010`: A and not B
```
 # ?
# ! )
 @ .
```
This also implements a form of short-circuiting, but due to the use of `#` the control flow is much trickier. `#` is a conditional IP switch. Hexagony actually comes with six IPs labelled `0` to `5`, which start in the six corners of the grid, pointing along their clockwise edge (and the program always begins with IP `0`). When a `#` is encountered, the current value is taken modulo `6`, and control flow continues with the corresponding IP. I'm not sure what fit of madness made me add this feature, but it certainly allows for some surprising programs (like this one).
We will distinguish three cases. When `A = 0`, the program is fairly simple, because the value is always `0` when `#` is encountered such that no IP-switching takes place:
[![i](https://i.stack.imgur.com/NvdJc.png)](https://i.stack.imgur.com/NvdJc.png)
`#` does nothing, `?` reads `A` (i.e. also does nothing), `#` still does nothing, `!` prints the `0`, `)` increments it (this is important, otherwise the IP would not jump to the third line), `@` terminates the program. Simple enough. Now let's consider the case `(A, B) = (1, 0)`:
[![i](https://i.stack.imgur.com/a5MJS.png)](https://i.stack.imgur.com/a5MJS.png)
The red path still corresponds to IP `0`, and I've added the green path for IP `1`. We see that after `?` reads `A` (`1` this time), the `#` switches to the IP that starts in the top right corner. That means `?` can read `B` (`0`). Now `)` increments that to `1`, such that the `#` in the top left corner does nothing and we remain with IP `1`. The `!` prints the `1` and the IP wraps around the left diagonal. `#` still does nothing and `@` terminates the program.
Finally, the really weird case where both inputs are `1`:
[![i](https://i.stack.imgur.com/vr4k0.png)](https://i.stack.imgur.com/vr4k0.png)
This time, the second input is also `1` and `)` increments it to `2`. That means the `#` in the top left corner causes *another* IP switch to IP `2`, indicate in blue. On that path, we first increment it further to `3` (although that's irrelevant) and then pass the `?` a third time. Since we've now hit EOF (i.e. the input is exhausted), `?` returns `0`, `!` prints that, and `@` terminates the program.
Notably, this is the only 6-byte solution for this gate.
### `0011`: A
```
 ? !
@ . .
 . .
```
This is simple enough that we won't need a diagram: `?` reads `A`, `!` prints it, `@` terminates.
This is the only 3-byte solution for this gate. (In principle, it would also be possible to do `,;@`, but the search didn't include `;`, because I don't think it can ever save bytes over `!` for this task.)
### `0100`: B and not A
```
 + ?
| @ !
 ? .
```
This one is a lot simpler than its "brother" `0010`. The control flow is actually the same as we've seen above for `0001` (And). If `A = 0`, then the IP traverses the lower line, reading `B` and printing that before terminating. If `A = 1` then the IP traverses the first line again, also reading `B`, but the `+` adds two unused memory edges so all it does is reset the current value to `0`, so that `!` always prints `0`.
There are quite a lot of 6-byte alternatives to this (42 in total). First, there's a ton of solutions equivalent to the above. We can again choose freely between `|` and `>`, and `+` can be replaced with any other command that gives us an empty edge:
```
"?|@!?    &?|@!?    '?|@!?    *?|@!?    +?|@!?    -?|@!?    ^?|@!?    {?|@!?    }?|@!?
"?>@!?    &?>@!?    '?>@!?    *?>@!?    +?>@!?    -?>@!?    ^?>@!?    {?>@!?    }?>@!?
```
In addition, we can also use `]` instead of `?`. `]` moves to the next IP (i.e. selects IP `1`), so that this branch instead reuses the `?` in the top right corner. That gives another 18 solutions:
```
"?|@!]    &?|@!]    '?|@!]    *?|@!]    +?|@!]    -?|@!]    ^?|@!]    {?|@!]    }?|@!]
"?>@!]    &?>@!]    '?>@!]    *?>@!]    +?>@!]    -?>@!]    ^?>@!]    {?>@!]    }?>@!]
```
And then there's six other solutions that all work differently with varying levels of craziness:
```
/[<@!?    ?(#!@]    ?(#>@!    ?/@#/!    [<<@!?    [@$\!?
```
### `0101`: B
```
 ? ?
! @ .
 . .
```
Woohoo, another simple one: read `A`, read `B`, print `B`, terminate. There are actually alternatives to this though. Since `A` is only a single character, we can also read it with `,`:
```
,?!@
```
And there's also the option of using a single `?` and using a mirror to run through it twice:
```
?|@!    ?>@!
```
### `0110`: Xor
```
  ? < @
 ! ! < _
\ ~ ( . .
 . . . .
  . . .
```
Like I said above, this was the only gate that wouldn't fit in side-length 2, so this a handwritten solution by FryAmTheEggman and myself, and there's a good chance that it isn't optimal. There are two cases to distinguish. If `A = 0` the control flow is fairly simple (because in that case we only need to print `B`):
[![i](https://i.stack.imgur.com/EHmjZ.png)](https://i.stack.imgur.com/EHmjZ.png)
We start on the red path. `?` reads `A`, `<` is a branch which deflects the zero left. The IP wraps to the bottom, then `_` is another mirror, and when the IP hits the corner, it wraps to the top left corner and continues on the blue path. `?` reads `B`, `!` prints it. Now `(` decrements it. This is important because it ensures that the value is non-positive (it's either `0` or `-1` now). That makes IP wrap to the to right corner, where `@` terminates the program.
When `A = 1` things get a bit trickier. In that case we want to print `not B`, which in itself isn't too difficult, but the execution path is a bit trippy.
[![i](https://i.stack.imgur.com/Izycv.png)](https://i.stack.imgur.com/Izycv.png)
This time, the `<` deflects the IP right and then next `<` just acts as a mirror. So the IP traverses the same path in reverse, reading `B` when it encounters `?` again. The IP wraps around to the right corner and continues on the green path. It next encounters `(~` which is "decrement, multiply by -1", which swaps `0` and `1` and therefore computes `not B`. `\` is just a mirror and `!` prints the desired result. Then `?` tries to return another number but returns zero. The IP now continues in the bottom left corner on the blue path. `(` decrements, `<` reflects, `(` decrements again, so that the current value is negative when the IP hits the corner. It moves across the bottom right diagonal and then finally hits `@` to terminate the program.
### `0111`: Or
```
 ? <
< @ !
 . .
```
More short-circuiting. 
[![i](https://i.stack.imgur.com/OVNer.png)](https://i.stack.imgur.com/OVNer.png) [![i](https://i.stack.imgur.com/drUVV.png)](https://i.stack.imgur.com/drUVV.png)
The `A = 0` case (the red path) is a bit confusing here. The IP gets deflected left, wraps to the bottom left corner, gets immediately reflected by the `<` and returns to the `?` to read `B`. It then wraps to the rigt corner, prints `B` with `!` and terminates.
The `A = 1` case (the green path) is a bit simpler. The `<` branch deflects the IP right, so we simply print the `!`, wrap back to the top left, and terminate at `@`.
There is only one other 5-byte solution:
```
\>?@!
```
It works essentially the same, but the actual execution paths are quite different and it uses a corner for branching instead of a `<`.
### `1000`: Nor
```
 ) \
! # ?
 @ {
```
This might be my favourite program found in this search. The coolest thing is that this implementation of `nor` actually works for up to 5 inputs. I'll have to get into the details of the memory model a bit to explain this one. So as a quick refresher, Hexagony's memory model is a separate hexagonal grid, where each *edge* holds an integer value (initially all zero). There's a memory pointer (MP) which indicates an edge and a direction along that edge (such that there's two neighboring edges in front of and behind the current edge, with meaningful left and right neighbours). Here is a diagram of the edges we'll be using, with the MP starting out as shown in red:
[![i](https://i.stack.imgur.com/x7MWE.png)](https://i.stack.imgur.com/x7MWE.png)
Let's first consider the case where both inputs are `0`:
[![i](https://i.stack.imgur.com/4fWWM.png)](https://i.stack.imgur.com/4fWWM.png)
We start on the grey path, which simply increments edge **A** to `1` so that the `#` switches to IP `1` which is the blue path, starting in the top right corner. `\` does nothing there and `?` reads an input. We wrap to the top left corner where `)` increments that input. Now as long as the input is zero, this will result in a `1`, so that `#` doesn't do anything. Then `{` moves the MP to the left, i.e. on the first iteration from **A** to **B**. Since this edge still has its initial zero the IP wraps back to the top right corner and on a new memory edge. So this loop will continue as long as `?` reads zeros, moving the MP around the hexagon from **B** to **C** to **D** and so on. It doesn't matter whether `?` returns a zero because it was an input or because it was EOF.
After six iterations through this loop, `{` returns to **A**. This time, the edge already holds the value `1` from the very first iteration, so the IP wraps to the left corner and continues on the green path instead. `!` simply prints that `1` and `@` terminates the program.
Now what if any of the inputs is `1`?
[![i](https://i.stack.imgur.com/siLnN.png)](https://i.stack.imgur.com/siLnN.png)
Then `?` reads that `1` at some point and `)` increments it to `2`. That means `#` will now switch IPs again and we'll continue in the right corner on the red path. `?` reads another input (if there is one), which doesn't really matter and `{` moves one edge further. This has to be an unused edge, hence this works for up to 5 inputs. The IP wraps to the top right where it's immediately reflected and wraps to the left corner. `!` prints the `0` on the unused edge and `#` switches back to IP `0`. That IP was still waiting around on the `#`, going southwest (grey path), so it immediately hits the `@` and terminates the program.
In total there are seven 7-byte solutions for this gate. 5 of them work the same as this and simply use other commands to move to an unused edge (and may walk around a different hexagon or in a different direction):
```
)\!#?@"    )\!#?@'    )\!#?@^    )\!#?@{    )\!#?@}
```
And there is one other class of solutions which only works with two inputs, but whose execution paths are actually even messier:
```
?]!|<)@    ?]!|<1@
```
### `1001`: Equality
```
 ( ~
? / @
 # !
```
This also makes very clever use of conditional IP selection. We need to distinguish again between `A = 0` and `A = 1`. In the first case we want to print `not B`, in the second we want to print `B`. For `A = 0` we also distinguish the two cases for `B`. Let's start with `A = B = 0`:
[![i](https://i.stack.imgur.com/vQX3K.png)](https://i.stack.imgur.com/vQX3K.png)
We start on the grey path. `(~` can be ignored, the IP wraps to the left corner (still on the grey path) and reads `A` with `?`. `(` decrements that, so we get `-1` and IP wrap to the bottom left corner. Now like I said earlier, `#` takes the value modulo `6` before choosing he IP, so a value of `-1` actually gets out IP `5`, which starts in the left corner on the red path. `?` reads `B`, `(` decrements that as well so that we remain on IP `5` when we hit `#` again. `~` negates the `-1` so that the IP wraps to the bottom right corner, prints the `1` and terminates.
[![i](https://i.stack.imgur.com/p4gVz.png)](https://i.stack.imgur.com/p4gVz.png)
Now if `B` is `1` instead, the current value will be `0` when we hit `#` the second time, so we switch back to IP `0` (now on the green path). That hits `?` a third time, yielding `0`, `!` prints it and `@` terminates.
[![i](https://i.stack.imgur.com/hrtmn.png)](https://i.stack.imgur.com/hrtmn.png)
Finally, the case where `A = 1`. This time the current value is already zero when we hit `#` for the first time, so this never switches to IP `5` in the first place. We simply continue immediately on the green path. `?` now doesn't just give a zero but returns `B` instead. `!` prints it and `@` terminates again.
In total there are three 7-byte solutions for this gate. The other two work very differently (even from each other), and make even weirder use of `#`. In particular they read one or more values with `,` (reading a character code instead of an integer) and then use that value modulo 6 to pick an IP. It's pretty nuts.
```
),)#?@!
?~#,~!@
```
### `1010`: Not B
```
 ? ?
| @ !
 ) .
```
This one is fairly simple. The execution path is the horizontal branch we already know from `and` earlier. `??` reads `A` and then immediately `B`. After reflecting at `|` and branching, for `B = 0` we will execute the bottom branch, where `)` increments the value to `1` which is then printed by `!`. On the top branch (if `B = 1`) the `?` simply reset the edge to `0` which is then also printed by `!`.
There are eight 6-byte programs for this gate. Four of them are pretty much the same, using either `>` instead of `|` or `1` instead of `)` (or both):
```
??>@!)    ??>@!1    ??|@!)    ??|@!1
```
Two use a single `?` which is used twice due to a mirror. The negation then happens as we did for `xor` with either `(~` or `~)`.
```
?>!)~@    ?>!~(@
```
And finally, two solutions use a conditional IP switch, because why use the simple way if the convoluted one also works:
```
??#)!@    ??#1!@
```
### `1011`: B implies A
```
 \ #
? ? !
 1 @
```
This uses some rather elaborate IP switching. I'll start with the `A = 1` case this time, because it's simpler:
[![enter image description here](https://i.stack.imgur.com/IdZr3.png)](https://i.stack.imgur.com/IdZr3.png)
We start on the grey path, which reads `A` with `?` and then hits the `#`. Since `A` is `1` this switches to IP `1` (green path). The `!` immediately prints that, the IP wraps to the top left, reads `B` (unnecessarily) and terminates.
When `A = 0` things get a bit more interesting. First let's consider `A = B = 0`:
[![enter image description here](https://i.stack.imgur.com/JGdMf.png)](https://i.stack.imgur.com/JGdMf.png)
This time, the `#` does nothing and we remain on IP `0` (red path from that point onward). `?` reads `B` and `1` turns it into a `1`. After wrapping to the top left corner, we hit `#` again, so we end up on the green path after all, and print `1` as before, before terminating.
Finally, here is `(A, B) = (0, 1)`, the false case:
[![enter image description here](https://i.stack.imgur.com/uVdln.png)](https://i.stack.imgur.com/uVdln.png)
Note that I've removed the initial grey path for clarity, but the program begins the same way, and we end up on the red path as before. So this time the second `?` returns `1`. Now we encounter the `1`. At this point it's important to understand what digits actually do in Hexagony (so far we've only used them on zeros): when a digit is encountered, the current value is multiplied by 10 and then the digit is added. This is normally used to write decimal numbers verbatim into the source code, but it means that `B = 1` is actually mapped to the value `11`. So when we hit `#`, this is taken modulo `6` to give `5` and hence we switch to IP `5` (instead of `1` as before) and continue on the blue path. Hitting `?` a third time returns a zero, so `!` prints that, and after another two `?`, the IP wraps to the bottom right where the program terminates.
There are four 7-byte solutions to this and they all work differently:
```
#)/!?@$    <!?_@#1    \#??!1@    |/)#?@!
```
### `1100`: Not A
```
 ? (
~ ! @
 . .
```
Just a simple linear one: read `A` with `?`, negate with `(~`, print with `!`, terminate with `@`.
There's one alternative solution, and that's negating with `~)` instead:
```
?~)!@
```
### `1101`: A implies B
```
 ? .
| @ !
 ) .
```
This is a *lot* simpler than the opposite implication we just talked about. It's again one of those horizontal branch programs, like the one for `and`. If `A` is `0`, it simply gets incremented to `1` on the bottom branch and printed. Otherwise, the top branch is executed again where `?` reads `B` and then `!` prints that instead.
There's a *ton* of alternatives here (66 solutions in total), mostly due to free choice of effective no-ops. For a start we can vary the above solution in all the same ways we could for `and` and we can also choose between `)` and `1`:
```
?.|@!)    .?|@!)    ?=|@!)    =?|@!)    ?_|@!)    _?|@!)    ?0|@!)
?.|@!1    .?|@!1    ?=|@!1    =?|@!1    ?_|@!1    _?|@!1    ?0|@!1
?.>@!)    .?>@!)    ?=>@!)    =?>@!)    ?_>@!)    _?>@!)    ?0>@!)
?.>@!1    .?>@!1    ?=>@!1    =?>@!1    ?_>@!1    _?>@!1    ?0>@!1
```
And then there's a different version using conditional IP selection, where the first command can be chosen almost arbitrarily, and there is also a choice between `)` and `1` for some of those options:
```
"?#1!@    &?#1!@    '?#1!@    )?#1!@    *?#1!@    +?#1!@    -?#1!@    .?#1!@    
0?#1!@    1?#1!@    2?#1!@    3?#1!@    4?#1!@    5?#1!@    6?#1!@    7?#1!@    
8?#1!@    9?#1!@    =?#1!@    ^?#1!@    _?#1!@    {?#1!@    }?#1!@
"?#)!@    &?#)!@    '?#)!@              *?#)!@    +?#)!@    -?#)!@    
0?#)!@              2?#)!@              4?#)!@              6?#)!@    
8?#)!@                        ^?#)!@    _?#)!@    {?#)!@    }?#)!@
```
### `1110`: Nand
```
 ? $
@ # )
 ! <
```
The last complicated one. If you're still reading, you've almost made it. :) Let's look at `A = 0` first:
[![enter image description here](https://i.stack.imgur.com/55x6F.png)](https://i.stack.imgur.com/55x6F.png)
`?` reads `A` and then we hit `$`. This is a jump command (like Befunge's `#`) which skips the next instruction so that we don't terminate on the `@`. Instead the IP continues at `#`. However since `A` is `0`, this doesn't do anything. `)` increments it to `1` so that the IP continues on the bottom path where the `1` is printed. The `<` deflects the IP to the right where it wraps to the left corner and the program terminates.
Next, when the input is `(A, B) = (1, 0)` we get this situation:
[![enter image description here](https://i.stack.imgur.com/6w8Wp.png)](https://i.stack.imgur.com/6w8Wp.png)
It's essentially the same as before except that at the `#` we switch to IP `1` (green path), but since `B` is `0` we switch back to IP `0` when we hit `#` a second time (now blue path), where it prints `1` as before.
Finally, the `A = B = 1` case:
[![enter image description here](https://i.stack.imgur.com/CmZqg.png)](https://i.stack.imgur.com/CmZqg.png)
This time, when we `#` the second time, the current value is still `1` so that we don't change the IP again. The `<` reflects it and the third time we hit `?` we get a zero. Hence the IP wraps to the bottom left where `!` prints the zero and the program ends.
There are nine 7-byte solutions in total for this. The first alternative simply uses `1` instead of `)`:
```
?$@#1!<
```
Then there's two solutions that will do your head in with the amount of IP switching that's going on:
```
)?#_[!@    1?#_[!@
```
These actually blew my mind: the interesting part is that IP switching can be used as a deferred conditional. The language's IP-switching rules are such that the current IP makes another step before the switch happens. If that step happens to go through a corner, then the current value decides on which branch the IP will continue if we ever switch back to it. Exactly this happens when the input is `A = B = 1`. Although this is all consistent with how I designed the language, I was never aware of this implication of the spec, so it's nice when my language teaches me some new tricks :D.
Then there's a third solution whose amount of IP switching is even worse (although it doesn't make use of that deferred conditional effect):
```
>?1]#!@
```
And then there's another one:
```
?$@#)!<
```
And then there's these four equivalent solutions, which do use some non-conditional IP switching and instead implement all the logic via branches and corners: 
```
]<?<@!)    ]<?<@!1    ]|?<@!)    ]|?<@!1
```
### `1111`: True
```
 1 !
@ . .
 . .
```
You've earned yourself something simple for the end: set edge to `1`, print with `!`, terminate with `@`. :)
Of course, there's one alternative:
```
)!@
```
---
As usual, all control flow diagrams created with Timwi's [HexagonyColorer](https://github.com/Timwi/HexagonyColorer) and the memory diagram with his [EsotericIDE](https://github.com/Timwi/EsotericIDE).
[Answer]
# APL, ~~22~~ ~~20~~ 18 bytes
The true and false entries are complete programs, and the other 14 are functions. (Thanks to Adám.)
```
0000 false              0 (complete program)
0001 p and q            ∧
0010 p and not q        >
0011 p                  ⊣
0100 not p and q        <
0101 q                  ⊢
0110 xor                ≠
0111 p or q             ∨
1000 not p and not q    ⍱
1001 eq                 =
1010 not q              ~⊢
1011 p or not q         ≥
1100 not p              ~⊣
1101 not p or q         ≤
1110 not p or not q     ⍲
1111 true               1 (complete program)
```
[Try it here.](http://tryapl.org/?a=%u2191%28%7B0%7D%2C%u2227%2C%3E%2C%u22A3%2C%3C%2C%u22A2%2C%u2260%2C%u2228%2C%u2371%2C%3D%2C%28%7E%u22A2%29%2C%u2265%2C%28%7E%u22A3%29%2C%u2264%2C%u2372%2C%7B1%7D%29%u233F2%202%u22A4%AF1+%u23734&run)
[Answer]
# Chess/mediocre chess player in endgame, 70 pieces
Inspired by that domino answer, I decided another game should have this honor.
Note that I took a few rules for how the pieces move. Because I don't feel like studying the optimal moves for every situation, the rules for whites move is simple: Stay out of check, capture the highest ranking piece he can that turn, while losing as little material as possible, and stop a pawn from promoting, in that order of priority. If there are two spaces he can move to, with equal favourability, he can move to either (hence in these, if he can move to more than one square, they are the same colour). Note that white will capture with something even if it gets captured, if the piece it is attacking is higher value than the one lost. Values are here:`pawn<knight=bishop<rook<queen`
The input is whether a rook is present or not. Note that rooks are only labelled with names A and B when it matters: if the gate behaves the same when the rooks are switched, they are not labelled.
The output is the colour of the square white king ends on: White=1, black=0
Before the images, I want to apologise for poor images. I'm not much good at holding a camera steady.
False, 4:
[![False](https://i.stack.imgur.com/VzwTX.png)](https://i.stack.imgur.com/VzwTX.png)
AND, 4:
[![enter image description here](https://i.stack.imgur.com/u1eoR.png)](https://i.stack.imgur.com/u1eoR.png)
A and not B, 5 (I think I can get this down to three, but do not have board right now):
[![enter image description here](https://i.stack.imgur.com/olAC9.png)](https://i.stack.imgur.com/olAC9.png)
A, 4:
[![enter image description here](https://i.stack.imgur.com/Ps0Db.png)](https://i.stack.imgur.com/Ps0Db.png)
Not A and B,5 (I think I can get this down to three, but do not have board right now):
[![enter image description here](https://i.stack.imgur.com/y4pCN.png)](https://i.stack.imgur.com/y4pCN.png)
B, 4:
[![enter image description here](https://i.stack.imgur.com/81Xmb.png)](https://i.stack.imgur.com/81Xmb.png)
Xor,5 (I know a way to make it 4, but I don't have the board right now):
[![enter image description here](https://i.stack.imgur.com/gEpkj.png)](https://i.stack.imgur.com/gEpkj.png)
Or, 4:
[![enter image description here](https://i.stack.imgur.com/AZnE9.png)](https://i.stack.imgur.com/AZnE9.png)
Nor, 4:
[![enter image description here](https://i.stack.imgur.com/yANm3.png)](https://i.stack.imgur.com/yANm3.png)
Xnor, 5 (I know a way to make it 4, but I don't have the board right now):
[![enter image description here](https://i.stack.imgur.com/hdn1A.png)](https://i.stack.imgur.com/hdn1A.png)
Not B, 4:
[![enter image description here](https://i.stack.imgur.com/USfIs.png)](https://i.stack.imgur.com/USfIs.png)
B implies A, 5 (I think I can get this down to three, but do not have board right now):
[![enter image description here](https://i.stack.imgur.com/pjByc.png)](https://i.stack.imgur.com/pjByc.png)
Not A, 4:
[![enter image description here](https://i.stack.imgur.com/dvzhj.png)](https://i.stack.imgur.com/dvzhj.png)
A implies B, 5 (I think I can get this down to three, but do not have board right now):
[![enter image description here](https://i.stack.imgur.com/M9p0X.png)](https://i.stack.imgur.com/M9p0X.png)
Nand, 4:
[![enter image description here](https://i.stack.imgur.com/AfJNw.png)](https://i.stack.imgur.com/AfJNw.png)
True, 4:
[![enter image description here](https://i.stack.imgur.com/wE6fb.png)](https://i.stack.imgur.com/wE6fb.png)
[Answer]
# [Jelly](http://github.com/DennisMitchell/jelly), 19 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
0 0 0 0 ¤  1 byte  Empty niladic chain. Returns default argument 0.
0 0 0 1 &  1 byte  Bitwise AND.
0 0 1 0 >  1 byte  Greater than.
0 0 1 1    0 bytes Empty link. Returns left argument.
0 1 0 0 <  1 byte  Less than.
0 1 0 1 ị  1 byte  At-index (x,y -> [y][x]). Returns right argument.
0 1 1 0 ^  1 byte  Bitwise XOR.
0 1 1 1 |  1 byte  Bitwise OR.
1 0 0 0 |¬ 2 byte  Logical NOT of bitwise OR.
1 0 0 1 =  1 byte  Equals.
1 0 1 0 ¬} 2 bytes Logical NOT of right argument.
1 0 1 1 *  1 byte  Exponentiation.
1 1 0 0 ¬  1 byte  Logical NOT of left argument.
1 1 0 1 >¬ 2 bytes Logical NOT of greater than.
1 1 1 0 &¬ 2 bytes Logical NOT of bitwise AND.
1 1 1 1 !  1 byte  Factorial.
```
[Try it online!](http://jelly.tryitonline.net/#code=wqQKJgo-Cgo8CuG7iwpeCnwKfMKsCj0Kwqx9CioKwqwKPsKsCibCrAohCjAsMeG5lzLigbjFgC_igqwK4oG0UsOH4oKsRw&input=)
[Answer]
# [Bitwise Cyclic Tag](https://esolangs.org/wiki/Bitwise_Cyclic_Tag), 118 bits = 14.75 bytes
Bitwise Cyclic Tag is perhaps the simplest Turing-complete language ever devised. There is a program tape and a data tape, both consisting of a list of bits. The program tape is interpreted cyclically until the data tape is empty, as follows:
* `0`: delete the first bit from the data tape.
* `1x`: if the first bit of the data tape is 1, append the bit `x` to the data tape.
We initialize the data tape with a 1 followed by the two input bits (the 1 is necessary because there is no way to create a 1 if the data tape consists entirely of 0s), and we use the final deleted data bit as the gate’s output.
* 0,0,0,0 (`false`): `001`
* 0,0,0,1 (`and`): `1001001`
* 0,0,1,0 (`A and not B`): `0110100`
* 0,0,1,1 (`A`): `1001`
* 0,1,0,0 (`not A and B`): `0100`
* 0,1,0,1 (`B`): `0`
* 0,1,1,0 (`xor`): `0110110010`
* 0,1,1,1 (`or`): `0110`
* 1,0,0,0 (`nor`): `1101001000`
* 1,0,0,1 (`xnor`): `110101001100`
* 1,0,1,0 (`not B`): `1100100`
* 1,0,1,1 (`B implies A`): `110101101000`
* 1,1,0,0 (`not A`): `11010000`
* 1,1,0,1 (`A implies B`): `11010011001`
* 1,1,1,0 (`nand`): `10110100100010`
* 1,1,1,1 (`true`): `1100`
[Answer]
# NAND logic gates — 31 gates
As the creator of the [original](https://codegolf.stackexchange.com/questions/10845/7110) [series](https://codegolf.stackexchange.com/questions/12261/7110) [of](https://codegolf.stackexchange.com/questions/24983/7110) [NAND](https://codegolf.stackexchange.com/questions/25489/7110) [gate](https://codegolf.stackexchange.com/questions/26194/7110) [questions](https://codegolf.stackexchange.com/questions/26252/7110), I couldn't pass up the opportunity to use these gates to solve another logic gate problem.
[![enter image description here](https://i.stack.imgur.com/LR6LA.png)](https://i.stack.imgur.com/LR6LA.png)
In each of these diagrams, the top input is A while the bottom input is B.
[Answer]
## Python 2, 137 bytes
```
[].sort
min
int.__rshift__
round
range
{}.get
cmp
max
lambda a,b:a<1>b
lambda a,b:a==b
lambda a,b:b<1
pow
{0:1,1:0}.get
{0:1}.get
lambda a,b:a+b<2
slice
```
Takes inputs like `min(True,False)` (or as `min(1,0)`). Takes heavy advantage of outputs only needing to have the right Truthy-Falsey value. Whenever possible, uses a built-in to avoid a costly `lambda`. I used code to search for built-ins that work.
My favorite one is `{0:1}.get`, which I thought of by hand. The dictionary `{0:1}` maps the key `0` to the value `1`. Its `get` method takes a key and a default, outputting the value matching the key, or the default if there's no such key. So, the only way to output a `0` is as `{0:1}.get(1,0)`, with missing key `1` and default `0`. One can get other variants with different dictionaries, but only this one was the shortest.
```
built_in_names = list(__builtins__) 
object_names = ["int","(0)","(1)"] + \
["True","False","0L","1L","0j","1j"] + \
["str", "''", "'0'","'1'","'a'"] + \
["list", "[]", "[0]", "[1]","['']","[[]]","[{}]"] + \
["set","set()","{0}","{1}","{''}"] + \
["dict","{}","{0:0}","{0:1}","{1:0}","{1:1}","{0:0,1:0}", "{0:0,1:1}","{0:1,1:0}","{0:1,1:1}"] + \
["id"]
object_method_names = [object_name+"."+method_name 
for object_name in object_names 
for method_name in dir(eval(object_name))]
additional_func_names = [
"lambda a,b:0",
"lambda a,b:1",
"lambda a,b:a",
"lambda a,b:b",
"lambda a,b:b<1",
"lambda a,b:a<1",
"lambda a,b:a+b",
"lambda a,b:a*b",
"lambda a,b:a==b",
"lambda a,b:a-b",
"lambda a,b:a<=b",
"lambda a,b:a>=b", 
"lambda a,b:a>b", 
"lambda a,b:a<b", 
"lambda a,b:a<1>b", 
"lambda a,b:a+b<2"]
func_names = built_in_names + object_method_names + additional_func_names
t=True
f=False
cases = [(f,f),(f,t),(t,f),(t,t)]
def signature(func):
    table = [bool(func(x,y)) for x,y in cases]
    table_string = ''.join([str(int(val)) for val in table])
    return table_string
d={}
for func_name in func_names:
    try:
        func = eval(func_name) 
        result = signature(func)
        if result not in d or len(func_name)<len(d[result]):
            d[result]=func_name
    except:
        pass
total_length = sum(len(func) for sig,func in d.items())
print total_length
print
    
for sig in sorted(d):
    print d[sig]
```
[Answer]
# Go (game), 33 stones, 73 intersections
If domino and chess are acceptable, then this. It can't be too golfy on a full 19x19 Go board. So I used small rectangular boards. The input is whether the stones marked 1 and 2 are present. The output is whether black wins. It uses area scoring, 0.5 komi, situational superko, no suicide. All black to play. Some are given multiple solutions.
White wins (2, 1x5):
```
➊━━━➋
```
1 and 2 (3, 2x3):
```
➊◯➋
┗┷┛
```
1 and not 2 (2, 1x5):
```
╺➊━➁╸
```
1 (2, 1x5):
```
╺➊➁━╸ 
╺➊━━➁
➀━➁━╸
```
Not 1 and 2 (2, 1x5):
```
╺➋━➀╸
```
2 (2, 1x5):
```
╺➋➀━╸
```
1 xor 2 (2, 2x3):
```
➀┯➁
┗┷┛
```
1 or 2 (2, 1x5):
```
╺➊━➋╸
➀━━━➁
```
1 nor 2 (2, 1x4):
```
➊━━➋
╺➀➁╸
```
1 = 2 (2, 1x7):
```
╺━➀━➁━╸
```
Not 2 (2, 1x3):
```
➀➁╸
```
1 or not 2 (2, 1x4):
```
➀➁━╸
➀━➁╸
╺➊➁╸
➋➊━╸
➋━➊╸
```
Not 1 (2, 1x3)
```
➁➀╸
```
Not 1 or 2 (2, 1x4):
```
➁➀━╸
```
1 nand 2 (2, 1x3):
```
➊━➋
```
Black wins (2, 1x3):
```
➊➋╸
➀━➁
➊━➁
```
This page helped me a bit: <http://www.mathpuzzle.com/go.html>
Maybe someone could find a 2 stone solution for 1 and 2 on a 1x9 board...
[Answer]
# Javascript ES6, 124 bytes
```
a=>0
Math.min
parseInt
a=>a
a=>b=>a<b
a=>b=>b
a=>b=>a^b
Math.max
a=>b=>~a&~b
a=>b=>a==b
a=>b=>~b
Math.pow
a=>~a
a=>b=>a<=b
a=>b=>~a|~b
a=>1
```
I seriously hate lambdas right now.
[Answer]
# [Retina](https://github.com/m-ender/retina), ~~62~~ 39 bytes
23 bytes thanks to [@MartinEnder](https://codegolf.stackexchange.com/users/8478/martin-ender)!
```
0000 false              1 byte : 2
0001 p and q            2 bytes: 11
0010 p and not q        2 bytes: 10
0011 p                  2 bytes: ^1
0100 not p and q        2 bytes: 01
0101 q                  2 bytes: 1$
0110 xor                5 bytes: 01|10
0111 p or q             1 byte : 1
1000 not p and not q    2 bytes: 00
1001 xnor               5 bytes: (.)\1
1010 not q              2 bytes: 0$
1011 p or not q         5 bytes: ^1|0$
1100 not p              2 bytes: ^0
1101 not p or q         5 bytes: ^0|1$
1110 not p or not q     1 byte : 0
1111 true               0 bytes: 
```
Takes input as `PQ`.
Outputs an integer between `0` to `3`. `0` is falsey, others are truthy.
## Explanation
They are all just [regexes](https://en.wikipedia.org/wiki/Regular_expression).
For example, `01|10` just matches `01` or `10`.
In `0000`, `2` will never be in the input, so it never matches.
In `1111`, it matches the empty string, which there are `4`.
[Answer]
## [Stack Cats](https://github.com/m-ender/stackcats), 67 + 64 = 131 bytes
Note that the +64 is from applying the `-nm` flags to each program. `-n` indicates numeric I/O, and `-m` mirrors the source code across the last character - not all submissions need these flags technically, but for consistency and simplicity I'm scoring them all the same way.
```
-2 -2 -3 -3     !I                0 0 0 0     <I!+
-4 -4 -4  1     |!T*I             0 0 0 1     [>I=I_
-4 -4  3 -2     *I*_              0 0 1 0     :I*=I:
-2 -2  3  3     T*I               0 0 1 1     [<!>X
-2  1 -2 -2     _*T*I             0 1 0 0     *|!TI:
-2  1 -3  1     !-|_I             0 1 0 1     <!I!>X
-2  3  3 -2     ^T*I              0 1 1 0     ^:]<_I
-2  3  3  3     -_T*I             0 1 1 1     *I<-I!
 2 -3 -3 -3     -*|_I             1 0 0 0     ^{!:}I_
 2 -3 -3  2     _|*I              1 0 0 1     _|[<I!:
 1 -2  1 -2     :]I*:             1 0 1 0     _!:|]X
 1 -2  1  1     *I\<X             1 0 1 1     *>I>!I
 2  2 -3 -3     -*I               1 1 0 0     I^:!
 2  2 -3  2     _*I_              1 1 0 1     |I|^:!
 1  2  2 -1     |!:^I             1 1 1 0     -I*<*I
 1  1  1  1     *<X               1 1 1 1     +I+
```
`()` in Stack Cats checks whether an element is positive or nonpositive (i.e. 0 or negative), so we're using that for truthy/falsy respectively. The second column is just for interest, and lists the best gates with `0`/`1`s as outputs (with total score 90).
Input is delimiter-separated bits via STDIN. [Try it online!](http://stackcats.tryitonline.net/#code=XypUKkk&input=MCAw&args=LW5t)
---
Stack Cats is a reversible esoteric language, where programs have reflective symmetry. Given a snippet `f` (e.g. `>[[(!-)/`), the mirror image (e.g. `\(-!)]]<`) computes the inverse `f^-1`. As such, even length programs do nothing (or get stuck in an infinite loop), and the only non-trivial programs have odd length, computing `f g f^-1` where `g` is the centre operator.
Since half the source code is always redundant, it can be left out, and running the code with the `-m` flag indicates that the source code should be mirrored over the last character to retrieve the actual source code. For example, the program `*<X` is actually `*<X>*`, which is symmetrical.
Golfing in Stack Cats is highly unintuitive, so the above programs had to be found by brute force. Most of them are surprisingly complex, but I'll explain a few and add to this answer when I have time. For now, some explanations and alternative solutions for the `0`/`1` versions can be found on the Github repository [here](https://github.com/m-ender/stackcats/tree/master/examples/logic-gates).
[Answer]
# Minecraft, 89 blocks
In all of the following photos, blue blocks are for Input A and orange blocks are for Input B
## 16. TRUE gate - 1 blocks
[![enter image description here](https://i.stack.imgur.com/6G0qU.png)](https://i.stack.imgur.com/6G0qU.png)
## 15. NAND gate - 1x2x3 = 6 blocks
[![enter image description here](https://i.stack.imgur.com/17cA4.png)](https://i.stack.imgur.com/17cA4.png)
## 14. A=>B - 1x2x3 = 6 blocks[enter image description here](https://i.stack.imgur.com/UZGg5.png)
## 13. NOT A - 2 blocks [enter image description here](https://i.stack.imgur.com/GrXhV.png)
## 12. B=>A - 1x2x3 = 6 blocks[enter image description here](https://i.stack.imgur.com/jSAOi.png)
## 11. NOT B - 2 blocks [enter image description here](https://i.stack.imgur.com/OQ06g.png)
## 10. XNOR - 1x3x4 = 12 blocks [enter image description here](https://i.stack.imgur.com/wds7x.png)
## 9. NOR - 1x2x3 = 6 blocks[enter image description here](https://i.stack.imgur.com/zsGqS.png)
## 8. OR - 1 blocks [enter image description here](https://i.stack.imgur.com/TAcv9.png)
## 7. XOR - 1x3x4 = 12 blocks [enter image description here](https://i.stack.imgur.com/97s9z.png)
## 6. B - 1 blocks [enter image description here](https://i.stack.imgur.com/6pQ1a.png)
## 5. !A&B - 1x2x5 = 10 blocks [enter image description here](https://i.stack.imgur.com/aM7zx.png)
## 4. A - 1 blocks [enter image description here](https://i.stack.imgur.com/Hibbv.png)
## 3. A&!B - 1x2x5 = 10 blocks [enter image description here](https://i.stack.imgur.com/HPaH1.png)
## 2. AND - 2x2x3 = 12 blocks [enter image description here](https://i.stack.imgur.com/mbY6k.png)
## 1. FALSE- 1 blocks [enter image description here](https://i.stack.imgur.com/lsJTh.png)
[Answer]
## Haskell, ~~78~~ ~~76~~ 75 bytes
1. `_#_=2<1`
2. `&&`
3. `>`
4. `pure`
5. `<`
6. `_#b=b`
7. `/=`
8. `||`
9. `(not.).max`
10. `==`
11. `_#b=not b`
12. `>=`
13. `a#_=not a`
14. `<=`
15. `(not.).min`
16. `_#_=1<2`
Edit: -1 byte thanks to @cole.
[Answer]
# dc, 37 bytes
`dc` ("desk calculator") is a standard unix command, a stack-based postfix calculator. It lacks bit operations, and comparison operators can only be used to execute macros (which is not worth the bytes). Integer division makes up for some of that.
These scripts expect `0` and `1` values on the stack, and leave the result on the stack.
```
0,0,0,0 (false)              0
0,0,0,1 (and)                *         a*b
0,0,1,0                      -1+2/     (a-b+1)/2
0,0,1,1 (A)                  r         reverse a, b: a now on top
0,1,0,0                      -1-2/     (a-b-1)/2
0,1,0,1 (B)                            (0 bytes) do nothing: b on top
0,1,1,0 (xor)                -         a-b
0,1,1,1 (or)                 +         a+b                  
1,0,0,0 (nor)                +v1-      sqrt(a+b) -1
1,0,0,1 (xnor)               +1-       a+b-1
1,0,1,0 (not B)              1-        b-1
1,0,1,1 (if B then A)        -1+       a-b+1
1,1,0,0 (not A)              r1-       a-1
1,1,0,1 (if A then B)        -1-       a-b-1            
1,1,1,0 (nand)               *1-       a*b - 1
1,1,1,1 (true)               1
```
[Answer]
# C 34 bytes
```
#define g(n,a,b)((n-1)>>3-b-2*a)&1
```
Where n is the function number to use, but I think it would be refused so I propose this other one:
# C 244 bytes (using memory)
```
typedef int z[2][2];
z a={0,0,0,0};
z b={0,0,0,1};
z c={0,0,1,0};
z d={0,0,1,1};
z e={0,1,0,0};
z f={0,1,0,1};
z g={0,1,1,0};
z h={0,1,1,1};
z i={1,0,0,0};
z j={1,0,0,1};
z k={1,0,1,0};
z l={1,0,1,1};
z m={1,1,0,0};
z n={1,1,0,1};
z o={1,1,1,0};
z p={1,1,1,1};
```
it uses double indexed array. `n[0][1]` is `(A implies B)(0,1)`
# Forth 138 bytes
I just learned Forth. I suppose that's Ansi Forth compatible as it run also on gforth. 
```
: z create dup , 1+ does> @ -rot 3 swap - swap 2* - rshift 1 and ; 
0 
z a z b z c z d z e z f z g z h z i z j z k z l z m z n z o z p 
drop
```
Function z create a new function with the name provided then put the logic gate number from the top of stack to the new function address. It leaves the next (n+1) logic gate function in the stack for the next declaration. 
you can test it :  
**And A B** 
```
0 0 b . cr 
0 1 b . cr
1 0 b . cr 
1 1 b . cr   
```
( "." print top of stack "cr" is cariage return )
[Answer]
## Mathematica, 67 bytes
```
0>1&
And
#&&!#2&
#&
!#&&#2&
#2&
Xor
Or
Nor
Xnor
!#2&
#||!#2&
!#&
!#||#2&
Nand
1>0&
```
Each of these evaluates to a function, so you can use them like
```
#&&!#2&[True, False]
Xor[True, False]
```
Ah, if only integers were truthy/falsy in Mathematica, those four longer ones could have been shortened considerably.
[Answer]
# [Brachylog](https://github.com/JCumin/Brachylog), ~~36~~ 34 bytes
```
0000 false              \     Backtrack (always false)
0001 p and q            1.    Unify input and output with 1
0010 p and not q        >.    Input > Output
0011 p                  1     Unify input with 1
0100 not p and q        <.    Input < Output
0101 q                  ,1.   Unify output with 1
0110 xor                '.    Input and output cannot unify
0111 p or q             1;1.  Unify input with 1 or unify output with 1
1000 not p and not q    0.    Unify input and output with 0
1001 eq                 .     Unify input with output
1010 not q              ,0.   Unify output with 0
1011 p or not q         >=.   Input >= Output
1100 not p              0     Unify input with 0
1101 not p or q         <=.   Input <= Output
1110 not p or not q     0;0.  Unify input with 0 or unify output with 0
1111 true                     Empty program (always true)
```
This expects `0` as falsy value and `1` as truthy value. Returns `true` or `false`. p is `Input` and q is `Output`.
[Answer]
# MATL, ~~34~~ 23 bytes
I hope I got the order all right! Zero is falsey, non-zero is truthy. Each function takes two implicit inputs (although it may ignore some inputs). The first input is A, and the second is B. You can input `0`/`1` for true/false, or `T`/`F`.
Here is a [TryItOnline](http://matl.tryitonline.net/#code=PA&input=MAox) example for test case 3.
Saved 4 bytes by using `*` for `and`, and another 4 by using `>`/`<` instead of `~wY&`/`w~Y&` after I saw Dennis' answer!
```
1.  0,0,0,0 0 (ignores input, just returns a zero)
2.  0,0,0,1 * (and)
3.  0,0,1,0 < (not-A and B)
4.  0,0,1,1 D (A)
5.  0,1,0,0 > (not-B and A)
6.  0,1,0,1 xD (discard A, display B)
7.  0,1,1,0 Y~ (xor)
8.  0,1,1,1 + (or)
9.  1,0,0,0 +~ (not-or)
10. 1,0,0,1 = (A=B)
11. 1,0,1,0 x~ (not-B)
12. 1,0,1,1 <~ (not-B or A)
13. 1,1,0,0 ~ (not-A)
14. 1,1,0,1 ~+ (not-A or B)
15. 1,1,1,0 *~ (not(A and B))
16. 1,1,1,1 1 (just returns 1)
```
[Answer]
# Prolog, ~~147~~ 145 bytes
*Gained 2 bytes thanks to @SQB*
```
a(a,a).       % 0000 false
b(1,1).       % 0001 P and Q
c(1,0).       % 0010 P and not Q
d(1,_).       % 0011 P
e(0,1).       % 0100 not P and Q
f(_,1).       % 0101 Q
g(P,Q):-P\=Q. % 0110 P xor Q
h(1,_).       % 0111 P or Q
h(0,1).
i(0,0).       % 1000 not P and not Q
j(P,P).       % 1001 P == Q                 
k(_,0).       % 1010 not Q
m(P,Q):-P>=Q. % 1011 P or not Q
n(0,_).       % 1100 not P              
r(P,Q):-P=<Q. % 1101 not P or Q         
s(0,_).       % 1110 not P or not Q
s(1,0).
t(_,_).       % 1111 true
```
Query `x(P,Q).` with `x` being the appropriate letter and `P` and `Q` set to either 0 or 1.  
Returns `true` or `false`.
[SWISH example including tests](http://swish.swi-prolog.org/p/Codegolfing%2016%20gates.pl) - enter `runTest.` to run.
[Answer]
# NTFJ, 86 bytes
```
0000 false              ~
0001 p and q            |:|
0010 p and not q        :||:|
0011 p                  $
0100 not p and q        #{:||:|
0101 q                  #{$
0110 xor                :#{:#{:||#}:|||
0111 p or q             :|#{:||
1000 not p and not q    :|#{:||:|
1001 eq                 :#{:#{:||#}:|||:|
1010 not q              #{$:|
1011 p or not q         #{:||
1100 not p              $:|
1101 not p or q         :||
1110 not p or not q     |
1111 true               #
```
[Try it here!](http://conorobrien-foxx.github.io/NTFJ/) But read below first.
Input is implicit on stack. Result is let on stack. Add 16 bytes (one `*` to the end of each) if you want `0x00` or `0x01` to output representing 0 and 1. Add an additional 160 bytes if you want a `0` or a `1` printed. (Put `~~##~~~#{@` before each `*`.)
NTFJ's only binary operator is NAND, so each of these is written in NAND form.
Let's go through each of them.
## 0: false
```
~
```
`~` represents a false bit. Simple enough. Since input is implicit at the bottom of the stack, this is left at the top of it.
## 1: p and q
```
|:|
```
NTFJ operates on a stack. `:` is the command for duplicate. Observe that `p and q` ≡ `not (p nand q)` and that `not q = q nand q`.
```
Command | Stack
        | p q
   |    | (p nand q)
   :    | (p nand q) (p nand q)
   |    | (p nand q) nand (p nand q)
        | => not (p nand q)
        | => p and q
```
(Note, then, `:|`can be said to be *negation* and `|:|` can be said to be *conjunction*)
## 2: p and not q
```
:||:|
```
Observe that this just a negation, `:|` and a conjunction `|:|`.
```
Command | Stack
        | p q
  :|    | p (not q)
  |:|   | p and (not q)
```
## 3: p
```
$
```
`$` pops an item from the stack. So... yeah.
## 4: not p and q
```
#{:||:|
```
This is the same thing as 2, except with `#{` at the beginning. `#` pushes 1 (the true bit) and `{` rotates the stack left once. Simple enough.
## 5: q
```
#{$
```
Rotate left once, drop.
## 6: xor
```
:#{:#{:||#}:|||
```
Observe:
```
p xor q = (p and (not q)) or ((not p) and q)                ; by experimentation (trust me)
        = (not ((not p) nand q)) or (not (p nand (not q)))  ; by definition of nand
        = not (((not p) nand q) and (p nand (not q)))       ; by De Morgan's laws
        = ((not p) nand q) nand (p nand (not q))            ; by definition of nand
```
However, there is no way to duplicate the stack entirely. So, we're going to have to bring each of `p`, `q` to the top and duplicate it.
```
Command | Stack
        | p q
   :    | p q q
  #{    | q q p
   :    | q q p p
  #{    | q p p q
  :|    | q p p (not q)
   |    | q p (p nand (not q))
  #}    | (p nand (not q)) q p
  :|    | (p nand (not q)) q (not p)
   |    | (p nand (not q)) (q nand (not p))
   |    | (p nand (not q)) nand (q nand (not p))
```
And thus, we have our xor.
## 7: p or q
```
:|#{:||
```
Negate top, bring bottom to top, negate that, and nand them together. Basically, `p or q = (not p) nand (not q)`.
## 8: not p and not q
```
:|#{:||:|
```
This is simply the negation of 7. Easy.
## 9: eq
```
:#{:#{:||#}:|||:|
```
This is just [xnor](https://codegolf.stackexchange.com/users/20260/xnor), or not xor. Simple again.
## 10: not q
```
#{$:|
```
Negation of 5.
## 11: p or not q
```
#{:||
```
Negate p, nand. `(not p) nand q = not ((not p) and q) = p or (not q) (by De Morgan's laws)`.
## 12: not p
```
$:|
```
Drop, stop, and negate.
## 13: not p or q
```
:||
```
De Morgan's laws to save the day, again! Same process as 11, just negating `q` instead of `p`.
## 14: not p or not q
```
|
```
This is just a mimic nand.
## 15: true
```
#
```
`#` is the true bit.
[Answer]
# IA-32 machine code, 63 bytes
Hexdump of the code, with the disassembly:
```
0000  33 c0     xor eax, eax;
      c3        ret;
0001  91        xchg eax, ecx;
      23 c2     and eax, edx;
      c3        ret;
0010  3b d1     cmp edx, ecx;
      d6        _emit 0xd6;
      c3        ret;
0011  91        xchg eax, ecx;
      c3        ret;
0100  3b ca     cmp ecx, edx;
      d6        _emit 0xd6;
      c3        ret;
0101  92        xchg eax, edx;
      c3        ret;
0110  91        xchg eax, ecx;
      33 c2     xor eax, edx;
      c3        ret;
0111  8d 04 11  lea eax, [ecx + edx];
      c3        ret;
1000  91        xchg eax, ecx; // code provided by l4m2
      09 d0     or eax, edx;
      48        dec eax;
      c3        ret;
1001  3b ca     cmp ecx, edx;
      0f 94 c0  sete al;
      c3        ret;
1010  92        xchg eax, edx;
      48        dec eax;
      c3        ret;
1011  39 d1     cmp ecx, edx; // code provided by l4m2
      d6        _emit 0xd6;
      40        inc aex;
      c3        ret;
1100  91        xchg eax, ecx;
      48        dec eax;
      c3        ret;
1101  3b d1     cmp edx, ecx; // code inspired by l4m2
      d6        _emit 0xd6;
      40        inc aex;
      c3        ret;
1110  8d 44 11 fe   lea eax, [ecx+edx-2] // code provided by l4m2
      c3        ret;
1111  91        xchg eax, ecx;
      40        inc eax;
      c3        ret;
```
The code is longer than it could be, because it uses a standard coding convention: input in `ecx` and `edx`, and output in `al`. This may be expressed in C as
```
unsigned char __fastcall func(int, int);
```
It seems that MS Visual Studio doesn't understand the undocumented [`SALC`](http://www.rcollins.org/secrets/opcodes/SALC.html) opcode, so I had to use its code, instead of name.
Thanks you [l4m2](https://codegolf.stackexchange.com/users/76323/l4m2) for improving some of the code samples!
[Answer]
## [Labyrinth](https://github.com/mbuettner/labyrinth), 85 bytes
*Thanks to Sp3000 for saving 2 bytes.*
```
!@
??&!@
??~&!@
?!@
?~?&!@
??!@
??$!@
??|!@
??|#$!@
??$#$!@
?#?$!@
?#?$|!@
?#$!@
?#$?|!@
??&#$!@
1!@
```
All of these are full programs, reading two integers `0` or `1` from STDIN (using any non-digit separator), and printing the result as `0` or `1` to STDOUT.
[Try it online!](http://labyrinth.tryitonline.net/#code=PyM_JHwhQA&input=MSAx) (Not a test suite, so you'll have to try different programs and inputs manually.)
As for explanations, these are all rather straightforward. All programs are linear, and the commands in use do the following:
```
?   Read integer from STDIN and push.
!   Pop integer and write to STDOUT.
@   Terminate program.
&   Bitwise AND of top two stack items.
|   Bitwise OR of top two stack items.
$   Bitwise XOR of top two stack items.
~   Bitwise NOT of top stack item.
#   Push stack depth (which is always 1 when I use it in the above programs).
1   On an empty stack, this pushes 1.
```
Note that I'm using `#` is always used to combine it with `$`, i.e. to compute `XOR 1`, or in other words for logical negation. Only in a few cases was I able to use `~` instead, because the subsequent `&` discards all the unwanted bits from the resulting `-1` or `-2`.
[Answer]
# [Brainfuck](http://esolangs.org/wiki/Brainfuck), ~~184~~ ~~178~~ 174 bytes
Input/output uses U+0000 and U+0001.
```
0000 .
0001 ,[,[->+<]]>.
0010 ,[,-[+>+<]]>.
0011 ,.
0100 ,-[,[->+<]]>.
0101 ,,.
0110 ,>,[-<->]<[>>+<]>.
0111 ,-[,-[+>-<]]>+.
1000 ,-[,-[+>+<]]>.
1001 ,>,[-<->]<[>>-<]>+.
1010 ,,-[+>+<]>.
1011 ,-[,[->-<]]>+.
1100 ,-[+>+<]>.
1101 ,[,-[+>-<]]>+.
1110 ,[,[->-<]]>+.
1111 +.
```
[Answer]
# C, 268 bytes
```
#define c(a,b)0      // 0000 
#define d(a,b)a&b    // 0001 
#define e(a,b)a>b    // 0010 
#define f(a,b)a      // 0011 
#define g(a,b)a<b    // 0100 
#define h(a,b)b      // 0101 
#define i(a,b)a^b    // 0110 
#define j(a,b)a|b    // 0111 
#define k(a,b)!b>a   // 1000 
#define l(a,b)a==b   // 1001 
#define m(a,b)!b     // 1010 
#define n(a,b)!b|a   // 1011 
#define o(a,b)!a     // 1100 
#define p(a,b)!a|b   // 1101 
#define q(a,b)!b|!a  // 1110 
#define r(a,b)1      // 1111 
```
Macros seem shorter than functions.
[Answer]
## [Brian & Chuck](https://github.com/m-ender/brian-chuck), 183 bytes
*Thanks to Sp3000 for saving 4 bytes.*
Some of the programs contain an unprintable character. In particular, every `\x01` should be replaced with the `<SOH>` (0x01) control character:
```
0000
?
#>.
0001
,-?,-?>?\x01
#}>.
0010
,-?,?>?\x01
#}>.
0011
,?\x01+?
#>.
0100
,?,-?>?\x01
#}>.
0101
,,?\x01+?
#>.
0110
,?>},?>?_\x01
#}+{>?_}>.
0111
,\x01?,?>?
#{>.
1000
,?,?>?\x01
#}>.
1001
,-?>},?>?_\x01
#}+{>>?_}>.
1010
,,-?\x01+?
#>.
1011
,\x01?,-?>?
#{>.
1100
,-?\x01+?
#>.
1101
,\x01-?,?>?
#{>.
1110
,\x01-?,-?>?
#{>.
1111
?
#>+.
```
Input and output use [byte values](http://meta.codegolf.stackexchange.com/questions/4708/can-numeric-input-output-be-in-the-form-of-byte-values), so input should be two 0x00 or 0x01 bytes (without separator) and output will be one such byte. This is actually also the most sensible definition of truthy/falsy for B&C because the only control flow command `?` regards zeros as falsy and everything else truthy.
### Explanations
First a quick B&C primer:
* Every program consists of two Brainfuck-like instances, each written on its own line. We call the first one *Brian* and the second one *Chuck*. Execution begins on Brian.
* Each program's tape is the other program's source code, and each program's instruction pointer is the other program's tape head.
* Only Brian can use the `,` (input byte) command and only Chuck can use the `.` (output byte) command.
* Brainfuck's `[]` loop does not exist. Instead, the only control flow you have is `?` which switches control to the other instance iff the current value under the tape head is nonzero.
* In addition to `>` and `<`, there's `{` and `}` which are essentially equivalent to the Brainfuck snippets `[<]` and `[>]`, that is, they move the tape head to the next zero position in that direction. The main difference is that `{` can also be stopped at the left end of the tape, regardless of what value it has.
* For convenience, any `_`s in the source code are replaced with null-bytes (as these are very useful in nontrivial programs in order to catch `{` and `}`).
Note that in all programs, Chuck's tape begins with a `#`. This could really be anything. `?` works such that the tape head moves one cell before starting execution (so that the condition itself isn't executed if it happens to be a valid command). So we can't ever use the first cell of Chuck for code.
There are five classes of programs, which I'll explain in detail later. For now I'm listing them here in order of increasing complexity.
### `0000`, `1111`: Constant functions
```
?
#>.
```
```
?
#>+.
```
These are very simple. We switch to Chuck unconditionally. Chuck moves the tape head to the unused cell to the right and either prints it directly, or increments it first to print `1`.
### `0011`, `0101`, `1010`, `1100`: Functions depending on only one input
```
,?\x01+?
#>.
```
```
,,?\x01+?
#>.
```
```
,,-?\x01+?
#>.
```
```
,-?\x01+?
#>.
```
Depending on whether we start with `,` or `,,` we're working with `A` or `B`. Let's look at the first example `0011` (i.e. `A`). After reading the value, we use `?` as a conditional on that value. If `A = 1`, then this switches to Chuck, who moves the tape head to the right and prints the literally embedded `1`-byte. Otherwise, control remains on Brian. Here, the 1-byte is a no-op. Then we increment the input well with `+` to make sure it's non-zero and *then* switch to Chuck with `?`. This time, `>` moves to an unused cell to the right which is then printed as `0`.
In order to negated one of the values we simply decrement it with `-`. This turns `1` into `0` and `0` into `-1`, which is non-zero and hence truthy as far as `?` is concerned.
### `0001`, `0010`, `0100`, `1000`: Binary functions with one truthy result
```
,-?,-?>?\x01
#}>.
```
```
,-?,?>?\x01
#}>.
```
```
,?,-?>?\x01
#}>.
```
```
,?,?>?\x01
#}>.
```
This is an extension of the previous idea in order to work with two inputs. Let's look at the example of `1000` (NOR). We (potentially) read both inputs with `,?`. If either of those is `1`, the `?` switches to Chuck. He moves the tape head to the end with `}` (onto the empty cell after Brian's code), moves another cell with `>` (still zero) and prints it with `.`.
However, if both inputs are zero, then control is still with Brian. `>` then moves the tape head onto the `}` such that this command *isn't* executed when we switch to Chuck with `?`. Now all that Chuck does is `>.` which only moves onto the `1`-cell and prints that.
We can easily obtain the other three functions by negating one or both of the inputs as required.
### `0111`, `1011`, `1101`, `1110`: Binary functions with three truthy results
```
,\x01?,?>?
#{>.
```
```
,\x01?,-?>?
#{>.
```
```
,\x01-?,?>?
#{>.
```
```
,\x01-?,-?>?
#{>.
```
A minor modification of the previous idea in order to negated the *result* (i.e. print `0` when we've passed through all of Brian and `1` otherwise). Let's look at `0111` (OR) as an example. Note that the embedded `1`-byte is a no-op, so this still starts with `,?,?`. If either input is `1` we switch to Chuck, who moves the tape head back to the start with `{`. `>.` moves the tape head onto that `1`-byte and prints it.
If both inputs are zero then we remain with Brian, move the tape head onto `{` to skip it and then switch to Chuck. When he executes `>.` this time he moves onto the empty cell after Brian's code and prints the `0`. 
Again, we easily obtain the other functions by negating one or both inputs.
### `0110`, `1001`: Binary functions with two truthy results
```
,?>},?>?_\x01
#}+{>?_}>.
```
```
,-?>},?>?_\x01
#}+{>>?_}>.
```
This one is a bit trickier. The previous functions were reasonably simple because they can be [short-circuited](https://en.wikipedia.org/wiki/Short-circuit_evaluation) - the value of the first input can decide the output, and if it doesn't then we look at the other input. For these two functions, we always need to look at both inputs.
The basic idea is to use the first input to decide whether the second input choose between `0` and `1` or between `1` and `0`. Let's take `0110` (XOR) as an example:
Consider `A = 0`. In this case we want to output `B` as is. `,` reads `A`, `?` does nothing. `>` moves onto the next (nonzero) cell so that `}` brings us to the `_` on Chuck. Here, we read `B` with `,` and use `?` again. If `B` was `0` as well, we're *still* on Brian. `>` skips the `}` on Chuck and `?` switches so that the `>.` prints the `0` embedded in Brian's source code. If `B` was `1` on the other hand, Chuck does execute the `}` which moves into the `_` in Brian's code already, so the `>.` then prints the `1`-byte instead.
If `A = 1`, then we do switch to Chuck right away, who will execute `}+{>?`. What this does is move to the `_` in Brian's source code, turns it into a `1` as well with `+`, then moves back to the start `{` and skips Brian's `?` by moving one cell to the right with `>` before handing control back to him. This time, after Brian read's `B`, if `B = 0`, and Chuck uses `>.` the cell next to Brian's `?` will be `1` instead of `0`. Also, when `B = 1`, Chuck's `}` skips right over what to used to be a gap and moves all the way to the end of the tape, so that `>.` prints a zero instead. This way we're printing `not B`.
In order to implement equivalence, we simply negated `A` before using it as a condition. Note that due to this we also need to add another `>` to Chuck to skip that `-` as well when moving back to the start.
[Answer]
# ClojureScript, 88 84 76 74 bytes
`nil` and `false` are falsy, all other values are truthy. Booleans coerce to 0/1 for arithmetic and inequalities. Functions can take the wrong number of arguments.
```
0000   nil?            ; previously: (fn[]nil)
0001   and
0010   <
0011   true?           ; previously: (fn[x]x)
0100   >
0101   (fn[x y]y)
0110   not=
0111   or
1000   #(= 0(+ % %2))
1001   =
1010   #(not %2)
1011   <=
1100   not
1101   >=
1110   #(= 0(* % %2))
1111   /               ; previously: (fn[]4), inc
```
[Answer]
# [Brain-Flak](https://github.com/DJMcMayhem/Brain-Flak), ~~418~~, 316 bytes
[Try it online!](http://brain-flak.tryitonline.net/)
Let the inputs be the top two numbers on the stack at the start of the program (zero for false one for true) and the output be top of the stack at the end of the program (zero for false else for true).
### false, 4 bytes (Courtesy of [Leaky Nun](https://codegolf.stackexchange.com/users/48934/leaky-nun))
`(<>)`
### and, 36 bytes
`(({}{}[(())()])){{}{}(((<{}>)))}{}{}`
### A and not B, 40 bytes
`((({}){}{}[(())()])){{}{}(((<{}>)))}{}{}`
### A, 6 bytes
`({}<>)`
### not A and B, 38 bytes
`((({}){}{}[(())])){{}{}(((<{}>)))}{}{}`
### B, 2 bytes
`{}`
### xor, 34 bytes
`(({}{}[(())])){{}{}(((<{}>)))}{}{}`
### or, 6 bytes
`({}{})`
### nor, 34 bytes
`(({}{}<(())>)){{}{}(((<{}>)))}{}{}`
### xnor, 10 bytes
`({}{}[()])`
### not B, 34 bytes
`{}(({}<(())>)){{}{}(((<{}>)))}{}{}`
### B implies A, 14 bytes
`(({}){}{}[()])`
### not A, 34 bytes
`(({}<{}(())>)){{}{}(((<{}>)))}{}{}`
### A implies B, 16 bytes
`(({}){}{}[()()])`
### nand, 12 bytes
`({}{}[()()])`
### true, 6 bytes
`<>(())`
## Explanation
Since most of these are very similar I am not going to explain exactly how each of them works. I try my best to make it clear however how all of the sixteen work.
Firstly are the gates that return three of the same value (i.e. 2, 3, 5, 8, 9, 12, 14, and 15). These all follow the same pattern. First you convert the input into a two bit number with a as the twos place and B as the ones. This is done with this snippet `(({}){}{})`. You then subtract the value of the two bit input you want to isolate `({}[value])`. (In the actual code the subtraction and the conversion are done in one step to save bytes). This can be combined with a not if needed: `(({}<(())>)){{}{}(((<{}>)))}{}{}`.
Next up: and, nor, or, xor, and xnor. These work similarly to the ones above. In fact some of these are included above, however this method is shorter. The trick I used here is that these each correspond to a sum of A B. e.g. xor evaluates to true if A+B = 1 and false otherwise. First you add A B and subtract the relevant amount. Expressed as `({}{}[0,1,2 or 3])`. Then if necessary conduct a not
Next up: A, B, not A and not B. These are pretty much self explanatory. We start by removing the unnecessary value and then we either negate or finish.
Lastly are the two simpletons: true and false. For these we push the correct value to the off stack. The `<>` nilad returns zero so we can save two bytes by using the switch as the zero value.
Not the most efficient solution out there (perhaps the most efficient in Brain-Flak), but I had a good deal of fun writing these and I implore you to attempt to shorten these.
[Answer]
# [Binary lambda calculus](https://tromp.github.io/cl/cl.html), 216 bits = 27 bytes
Uses the [Church numerals](https://en.wikipedia.org/wiki/Church_encoding#Church_numerals) 0 = λx. λy. y, 1 = λx. x as booleans.
* 0,0,0,0 (`false`): `0000000010` = λa. λb. λx. λy. y
* 0,0,0,1 (`and`): `000001011000111010` = λa. λb. b (λx. a) b
* 0,0,1,0 (`A and not B`): `0000010111010000010` = λa. λb. a b (λx. λy. y)
* 0,0,1,1 (`A`): `0000110` = λa. λb. a
* 0,1,0,0 (`not A and B`): `00011000001110` = λa. a (λx. λy. a)
* 0,1,0,1 (`B`): `000010` = λa. λb. b
* 0,1,1,0 (`xor`): `00011000011000110` = λa. a (λx. x (λy. x))
* 0,1,1,1 (`or`): `00011000110` = λa. a (λx. a)
* 1,0,0,0 (`nor`): `00000101011101010000010` = λa. λb. a b b (λx. λy. y)
* 1,0,0,1 (`xnor`): `0001011000110000110110` = λa. a (λx. a) (λb. b a)
* 1,0,1,0 (`not B`): `0000011000110` = λa. λb. b (λx. b)
* 1,0,1,1 (`B implies A`): `00000110110` = λa. λb. b a
* 1,1,0,0 (`not A`): `000001110001110` = λa. λb. a (λx. a)
* 1,1,0,1 (`A implies B`): `0010` = λa. a
* 1,1,1,0 (`nand`): `000001100111000110` = λa. λb. b (a (λx. b))
* 1,1,1,1 (`true`): `00000010` = λa. λb. λx. x
# Binary lambda calculus, 292 bits = 36.5 bytes
Uses the [Church booleans](https://en.wikipedia.org/wiki/Church_encoding#Church_Booleans) true = λx. λy. x, false = λx. λy. y.
* 0,0,0,0 (`false`): `0000000010` = λa. λb. λx. λy. y
* 0,0,0,1 (`and`): `000001011011010` = λa. λb. b a b
* 0,0,1,0 (`A and not B`): `0000010110000010110` = λa. λb. b (λx. λy. y) a
* 0,0,1,1 (`A`): `0000110` = λa. λb. a
* 0,1,0,0 (`not A and B`): `000110000010` = λa. a (λx. λy. y)
* 0,1,0,1 (`B`): `000010` = λa. λb. b
* 0,1,1,0 (`xor`): `0000010111001011000001011010` = λa. λb. a (b (λx. λy. y) a) b
* 0,1,1,1 (`or`): `00011010` = λa. a a
* 1,0,0,0 (`nor`): `00000000010111101001011111010110` = λa. λb. b (λx. λy. y) (a b (λx. λy. x))
* 1,0,0,1 (`xnor`): `00000101110100101101100000110` = λa. λb. a b (b a (λx. λy. x))
* 1,0,1,0 (`not B`): `000000000101111010110` = λa. λb. λx. λy. b y x
* 1,0,1,1 (`B implies A`): `00000101101100000110` = λa. λb. b a (λx. λy. x)
* 1,1,0,0 (`not A`): `0000000001011111010110` = λa. λb. λx. λy. a y x
* 1,1,0,1 (`A implies B`): `00000101110100000110` = λa. λb. a b (λx. λy. x)
* 1,1,1,0 (`nand`): `000000000101111001011111010110110` = λa. λb. b (a (λx. λy. y) b) (λx. λy. x)
* 1,1,1,1 (`true`): `00000000110` = λa. λb. λx. λy. x
[Answer]
## [ProgFk](https://esolangs.org/wiki/ProgFk), ~~18.5~~ 17.5 bytes
As ProgFk's instructions are specified in nibbles, the below code is given in hexadecimal, one logic gate per line and with spaces in between the bytes.
```
3
E1
DE 2D
<empty>
DE 1
1
E3
E2
E2 D
E3 D
1D
DE 2
D
DE 1D
E1 D
4
```
### Explanation
[ProgFk](https://esolangs.org/wiki/ProgFk) is a tape-based esolang (similar to Brainfuck) where each cell is a bit and instructions are given as nibbles (4 bytes). Instructions operate on the cell pointed to by the instruction pointer. Input is given in the first and second cells (with `A` and `B` being the first and second cells respectively), and the instruction pointer starts at the first cell. Output is stored in the first cell.
Each instruction used is explained below.
```
1   Increment the instruction pointer.
2   Decrement the instruction pointer.
3   Set the current bit to 0.
4   Set the current bit to 1.
D   Perform a NOT on the current bit.
E   The next instruction is an extended instruction.
Extended instructions:
1   Set the current bit to the current bit AND the next bit.
2   Set the current bit to the current bit OR the next bit.
3   Set the current bit to the current bit XOR the next bit.
6   Swap the current bit and the next bit.
```
*Saved a byte thanks to @LeakyNun!*
]