Golf all the 16 logic gates with 2 inputs and 1 output!

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 1

Dominoes, 122,000 bytes or 72 tiles

The byte count is the size of the saved file which is 0.122 MB.

Domino computing was the inspiration. I have tested all of these up to symmetry (and beyond!) via a virtual-reality Steam game called Tabletop Simulator.

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

Gates

• false, 1
  • 
• and, 6 4
  • 
• A and not B, 4 3
  • 
• A, 1
  • 
• not A and B, 4 3
  • 
• B, 1
  • 
• xor, 15 11
  • 
• or, 1
  • 
• nor, 3 2
  • 
• xnor, 17 13
  • 
• not B, 2
  • 
• B implies A, 7 6
  • 
• not A, 2
  • 
• A implies B, 7 6
  • 
• nand, 16 15
  • 
  • true, 1
  • 

---

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. 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.

After building these with physical dominoes, it was ruled on meta that valid solutions should be digital. So I recreated these gates in Tabletop Simulator. 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 2

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! 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 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. 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:

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:

# 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):

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:

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):

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.

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.

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:

Let's first consider the case where both inputs are 0:

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?

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:

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.

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.

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:

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:

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:

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:

? 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:

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:

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 and the memory diagram with his EsotericIDE.

Answer 3

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.

Answer 4

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:

AND, 4:

A and not B, 5 (I think I can get this down to three, but do not have board right now):

A, 4:

Not A and B,5 (I think I can get this down to three, but do not have board right now):

B, 4:

Xor,5 (I know a way to make it 4, but I don't have the board right now):

Or, 4:

Nor, 4:

Xnor, 5 (I know a way to make it 4, but I don't have the board right now):

Not B, 4:

B implies A, 5 (I think I can get this down to three, but do not have board right now):

Not A, 4:

A implies B, 5 (I think I can get this down to three, but do not have board right now):

Nand, 4:

True, 4:

Answer 5

Jelly, 19 bytes

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!

Answer 6

NAND logic gates — 31 gates

As the creator of the original series of NAND gate questions, I couldn't pass up the opportunity to use these gates to solve another logic gate problem.

In each of these diagrams, the top input is A while the bottom input is B.

Answer 7

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 8

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 9

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 10

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 11

Retina, 62 39 bytes

23 bytes thanks to @MartinEnder!

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.

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 12

Stack Cats, 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/1s as outputs (with total score 90).

Input is delimiter-separated bits via STDIN. Try it online!

---

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.

Answer 13

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 14

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

15. NAND gate - 1x2x3 = 6 blocks

14. A=>B - 1x2x3 = 6 blocks

13. NOT A - 2 blocks

12. B=>A - 1x2x3 = 6 blocks

11. NOT B - 2 blocks

10. XNOR - 1x3x4 = 12 blocks

9. NOR - 1x2x3 = 6 blocks

8. OR - 1 blocks

7. XOR - 1x3x4 = 12 blocks

6. B - 1 blocks

5. !A&B - 1x2x5 = 10 blocks

4. A - 1 blocks

3. A&!B - 1x2x5 = 10 blocks

2. AND - 2x2x3 = 12 blocks

1. FALSE- 1 blocks

Answer 15

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 16

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 - enter runTest. to run.

Answer 17

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! 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, 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 18

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 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 19

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 20

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! (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 21

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 22

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 opcode, so I had to use its code, instead of name.

Thanks you l4m2 for improving some of the code samples!

Answer 23

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 24

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 25

Actually, 24 bytes

These programs take input as A\nB (with \n representing a newline), which leaves B on top of the stack, with A below. False is represented by 0, and True is represented by any positive integer.

é0  (false: clear stack, push 0)
*   (and: multiply)
<   (A and not B: less-than)
X   (A: discard B)
>   (B and not A: greater-than)
@X  (B: discard A)
^   (A xor B: xor)
|   (A or B: or)
|Y  (A nor B: or, boolean negate)
=   (A xnor B: equals)
@XY (not B: discard A, boolean negate B)
≤   (if B then A: less-than-or-equal)
XY  (not A: discard B, boolean negate)
≥   (if A then B: greater-than-or-equal)
*Y  (A nand B: multiply, boolean negate)
é1  (true: clear stack, push 1)

Thanks to Leaky Nun for 3 bytes

Answer 26

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 27

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, 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 - 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 28

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 29

Brain-Flak, 418, 316 bytes

Try it online!

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)

(<>)

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 30

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 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!

Answer 31

C, 144 bytes

This builds on @Emmanuel's idea to use the function number as the array of bits containing the required output. However, it adds some preprocessor abuse to actually define those 16 freestanding functions required by the question. It is also this preprocessor abuse that makes this the shortest C answer to date.

#define z(n)(a,b){return (n>>3-b-2*a)&1;}
a z(0)b z(1)c z(2)d z(3)e z(4)f z(5)g z(6)h z(7)i z(8)j z(9)k z(10)l z(11)m z(12)n z(13)o z(14)p z(15)

Using the preprocessor, the token sequence a z(0) expands to

a (a,b){return (0>>3-b-2*a)&1;}

which is the required free-standing function a(a,b) returning false. The other functions are defined analogously.

Test the code with

#include <stdio.h>

#define z(n)(a,b){return (n>>3-b-2*a)&1;}
a z(0)b z(1)c z(2)d z(3)e z(4)f z(5)g z(6)h z(7)i z(8)j z(9)k z(10)l z(11)m z(12)n z(13)o z(14)p z(15)

void showFunction(int(*function)(int,int)) {
    printf("%d %d %d %d\n", function(0,0), function(0,1), function(1,0), function(1,1));
}

int main() {
    showFunction(a);
    showFunction(b);
    showFunction(c);
    showFunction(d);
    showFunction(e);
    showFunction(f);
    showFunction(g);
    showFunction(h);
    showFunction(i);
    showFunction(j);
    showFunction(k);
    showFunction(l);
    showFunction(m);
    showFunction(n);
    showFunction(o);
    showFunction(p);
}

Answer 32

Cubically, 317 304 295 269 257 219 187 128 119 110 bytes

^{-13, 11, 12 thanks to TehPers
-~200 realizing output must be truthy, not 1
-66 thanks to language updates}

0000 false              %
0001 p and q            $:$·7%
0010 p and not q        $?7{$=%}!%7
0011 p                  $%7
0100 not p and q        $?7%0!$%7
0101 q                  $$%7
0110 xor                $:$⊕7%
0111 p or q             $:$|7%
1000 not p and not q    $?7{%&}$?7{%&}%1
1001 eq                 $:$=%
1010 not q              $$!7B%0
1011 p or not q         $?7B$!7B%0
1100 not p              $=%
1101 not p or q         $!7B$?7B%0
1110 not p or not q     $!7B$!7B%0
1111 true               %1

0000, 2 bytes - TIO

%0

Simply prints the sum of the UP face, which is initialized to all zero's. Prints zero.

0001, 24 11 8 7 6 bytes - TIO

$:$·7%
$          read input
 7         set notepad to input
   $       read input
    ·7     set notepad to notepad AND input
      %    print notepad as integer

Older version:

$!7{%0&}$!7{%0&}R3D1R1%0
$                            read input
 !7{...}                     if falsy
    %0                        print 0th face sum (0)
      &                       exit
        $                    read input
         !7{...}             if falsy
            %0&               print 0th face sum (0) and exit
                R3D1R1       get the 0th face sum to 1
                      %0     print as integer (1)

Credit to TehPers for the shortened algorithm to get the 0th face sum to 1; before today it had been about 12 bytes.

0010, 24 13 12 11 bytes - TIO

$?7{$=%}!%7
$            read input
 ?7{...}     if truthy
    $         read input
     =        compare to previous
      %      print result
        !    otherwise
         %7  print input (falsy)

0011, 16 3 bytes - TIO

$%7
$    read input
 %7  and print it

0100, 24 12 11 9 bytes - TIO

$?7%0!$%7
$           read input (into 7th face)
 ?7         if 7th face truthy
   %0        print 0
     !      otherwise
      $      read input
       %7   print input

I don't actually have any idea how this works...

0101, 17 4 bytes - TIO

$$%7
$$    read input, discard, read input
  %7  and print

0110, 21 8 7 6 bytes - TIO

$:7$⊕7%
$         read input
 :7       set notepad to input
   $      read input
    ⊕7    set notepad to notepad XOR input
      %   print notepad

Old version:

$:7$=7R3D1R1?6-0!+0%6
$:7                    read input, set notepad to input
   $=7                 read input, compare with previous input, store result in notepad
      R3D1R1           get 0th face sum to 1
            ?6-0!+0    swap result
            ?6         if notepad is truthy (implicit curly-braces)
              -0        subtract one from notepad
                !      else
                 +0     add one to notepad
                   %6  print notepad

0111, 30 8 7 6 bytes - TIO

$:$|7%
$        read input
 :       set notepad to input
  $      read input
   |7    set notepad to notepad OR input
     %   print notepad

Old version:

R3D1R1$?7{%0&}$?7{%0&}R3D3R1%0
R3D1R1                          get 0th face sum to 1
      $                         read input
       ?7{...}                  if truthy
          %0&                    print 1 and exit
              $?7{%0&}          read input - if truthy, print 1 and exit
                      R3D3R1    get 0th face sum to 0
                            %0  print 0

1000, 24 18 bytes - TIO

Pretty much the same as the other 24-byte gates.

1001, 8 7 bytes - TIO

$:$=%
$:       read input, set notepad to input
  $=     read input, compare to previous
    %    print comparison result

1010, 17 7 bytes - TIO

$$!7B%0
$$        read input, discard, read again
  ?7.     if truthy
    B      get top face to nonzero
      %0  print top face sum

1011, 24 18 10 bytes - TIO

$?7B$!7B%0
$           read input
 ?7.        if truthy
   B         get top face sum to truthy
    $       read input
     !7.    if falsy
       B     get top face sum to truthy
        %0  print top face sum

Old version:

$?7{%1&}$!7{%1&}%0
$                    read input
 ?7{...}             if truthy
    %1                print 9
      &              exit
        $            read input
         !7{...}     if falsy
            %1&       print 9 and exit
                %0   print 0

1100, 13 5 4 bytes - TIO

$=%
$      read input
 =     set notepad to (input == 0)
  %    print notepad

Old version:

$!7{R3D1R1}%0
$               read input
 !7{......}     if falsy
    R3D1R1       get 0th face sum to 1
           %0   print 0th face (1 if input was falsy, 0 if input was truthy)

1101, 24 10 bytes - TIO

$!7B$?7B%0
$           read input
 !7.        if falsy
   B         get top face sum to truthy
    $       read input
     ?7.    if truthy
       B     get top face sum to truthy
        %0  print top face sum

1110, 24 10 bytes - TIO

Pretty much the same as 1101, but the second if-statement is an if falsy.

1111, 8 4 2 bytes - TIO

%1  print face sum of left face (9)

Old versions:

=6%6
=6    set notepad to (0 == 0)
  %6  print notepad

and...

R3D1R1%0
R3D1R1    get 0th face sum to 1
      %0  print 1

Answer 33

05AB1E, 31 27 26 bytes

First input is p.
Second input is q.

0000 false              0          # ignore input, output 0 (false)
0001 p and q            &          # p and q
0010 p and not q        s±&        # (not q) and p
0011 p                  ¹          # p
0100 not p and q        ±&         # (not p) and q
0101 q                  ²          # q
0110 xor                ^          # p xor q
0111 p or q             ~          # p or q
1000 not p and not q    +_         # (p + q) == 0
1001 eq                 Q          # p == q
1010 not q              ²_         # not q
1011 p or not q         s_~        # (not q) or p
1100 not p              _          # not p
1101 not p or q         _~         # (not p) or q
1110 not p or not q     +2‹        # (p + q) < 2
1111 true               1          # ignore input, output 1 (true)

Saved 4 bytes thanks to Adnan
Saved 1 byte thanks to Magic Octopus Urn

Answer 34

TI-Basic, 108 66 bytes

With no arguments, Input gets input into X and Y.

0000 false            1 0
0001 and              4 Input :XY
0010 x and not y      5 Input :Xnot(Y
0011 x                3 Input :X
0100 not x and y      5 Input :Ynot(X
0101 y                3 Input :Y
0110 xor              5 Input :X-Y
0111 or               5 Input :X+Y
1000 nor              6 Input :not(X+Y
1001 xnor             5 Input :X=Y
1010 not y            4 Input :not(Y
1011 x or not y       5 Input :X≥Y
1100 not x            4 Input :not(X
1101 not x or y       5 Input :Y≤X
1110 nand             5 Input :not(XY
1111 true             1 1

Answer 35

Python, 58*16 = 928 bytes

This defines all 16 logic gates, so it can be used for each of the implementations. Since the rules state that the functions programs/functions must be implemented separately, the score is multiplied by 16.

[(lambda i:lambda a,b:i>>(a*2+b)&1)(i) for i in range(16)]

Demo here.

Answer 36

Forth-83, 43 37 bytes

These are all complete programs. The inputs begin on the stack, and the result of each program is the top value of the stack afterwards. Not all of these programs are stack-safe. I wish there was a shorter way to NOT (1+ is shorter.)

Note: -1 is TRUE in this language (and many older languages,) because a bitwise NOT of 0 is -1. Any non-zero value is truthy.

0000    0
0001    *
0010    <
0011    DROP
0100    >
0101    
0110    -
0111    +
1000    + 1+
1001    =
1010    1+
1011    > 1+
1100    DROP 1+
1101    < 1+
1110    * 1+
1111    1

Test code:

Replace DROP on line 2 with your program of choice. This program runs the above programs for each combination of inputs and prints whether it was interpreted to be true or false (some of the truthy values are different, but this test program shows that they are still interpreted as true.) Any occurrence of NOT must be replaced with INVERT for this interpreter, because this isn't a Forth‑83 interpreter. The new lines here are for readability, and can be replaced with spaces.

Try it online

: f 
DROP
IF -1 . ELSE 0 . THEN ;

0 0 f
0 -1 f
-1 0 f
-1 -1 f

Answer 37

Stackylogic, 106 105 bytes (non-competing)

Sort of what this language is made for.

It was made after the challenge, so non-competing

• 1 moves the pointer down one, and removes itself

• 0 moves the pointer up one, and removes itself

• ? is substituted for a bit from input, which is executed as above.

• < just denotes the start of the pointer

0000 false              2 bytes:0<

0001 p and q            4 bytes:?<
                                ?

0010 p and not q        7 bytes:1?<
                                ?
                                0

0011 p                  2 bytes:?<

0100 not p and q        6 bytes:?
                                ?<
                                0

0101 q                  6 bytes:?
                                ?<
                                ?

0110 xor               11 bytes:?
                                ?<
                                11
                                ?
                                0

0111 p or q             4 bytes:?
                                ?<

1000 not p and not q   11 bytes:1
                                ?
                                0?<
                                1
                                0

1001 xnor              11 bytes:1
                                ?
                                0?<
                                1
                                ?

1010 not q              9 bytes:11
                                ??<
                                00

1011 p or not q         7 bytes:1
                                ?
                                0?<

1100 not p              6 bytes:1
                                ?<
                                0

1101 not p or q         6 bytes:1
                                ?<
                                ?

1110 not p or not q    11 bytes:1
                                ?<
                                11
                                ?
                                0

1111 true               2 bytes: 1<

Answer 38

Binary lambda calculus, 216 bits = 27 bytes

Uses the 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 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 39

PowerShell, 231 bytes

These are all full scripts, with arguments passed as either Boolean values ($true or $false) or integers (0 or 1 for false and true, respectively) on the command line.

1. 0000 is pretty simple, by which I mean it's completely blank. Null coerces to $false.

2. 0001 multiplies the two values together; $true coerces to 1, $false to 0.

   $args[0]*$args[1]
   

3. 0010 inverts B by subtracting 1 from it, then does the same as the previous. The integer -1 coerces to $true.

   $args[0]*($args[1]-1)
   

4. 0011 just returns A.

   $args[0]
   

5. 0100 does the same as #3, just flipped.

   ($args[0]-1)*$args[1]
   

6. 0101 just returns B.

   $args[1]
   

7. 0110 subtracts B from A, again using the fact that any nonzero value becomes $true.

   $args[0]-$args[1]
   

8. 0111 adds the two arguments together.

   $args[0]+$args[1]
   

9. 1000 adds the two and makes sure the result is still zero.

   $args[0]+$args[1]-eq0
   

10. 1001 makes sure the values are the same.

    $args[0]-eq$args[1]
    

11. 1010 subtracts 1 from B.

    $args[1]-1
    

12. 1011 shifts B to the left, adds A, and subtracts two. If the result is zero, we found the one unacceptable configuration.

    $args[1]*2+$args[0]-2
    

13. 1100 inverts A with the same trick as #11.

    $args[0]-1
    

14. 1101 is the same as #12 but with the arguments flipped.

    $args[0]*2+$args[1]-2
    

15. 1110 does "and" and then inverts it.

    $args[0]*$args[1]-1
    

16. 1111 is just $true.

    1
    

Answer 40

Husk, 24 bytes

μ0     take two arguments, return 0
&      and
<      second argument is less than first
¹      return first of two arguments
>      second argument is greater than first
μ⁰     take two arguments, return the last one
≠      arguments are not equal
|      or
¬|     not or
=      arguments are equal
μ¬⁰    take two arguments, return the negation of the last one
≤      second argument is less or equal than the first
¬¹     negate the first of two arguments
≥      second argument is greater or equal than the first
¬&     not and
μ1     take two arguments, return 1

Try it online! (this test suite calls each function with each combination of inputs)

Answer 41

Alumin, 34 bytes

Try it online!

0 -> b
1 -> g
2 -> c
3 -> k
4 -> rc
5 -> hw
6 -> ahe
7 -> a
8 -> aze
9 -> e
10 -> we
11 -> cha
12 -> dce
13 -> chyc
14 -> tze
15 -> ade

Input is through the top of the stack, and output is through STDOUT or STDERR.

Explanations

0: false

b

This pushes the modulus of the top two members. Anything mod 0 raises an error. 0 % 1 and 1 % 1 are both zero, so this suffices.

1: and

g

This is division: anything divided by 0 raises an error, 0 / 1 is zero, and 1 / 1 is 1. t also works, being multiplication, and so does v, minimum.

2: and-not

c

Numbers in Alumin are truthy iff they are positive (1 or greater). So, subtraction works nicely here:

0 - 0 = 0    (FALSEY)
0 - 1 = -1   (FALSEY)
1 - 0 = 1    (TRUTHY)
1 - 1 = 0    (FALSEY)

3: a

k

k simply pops the top member of the stack, leaving the first argument intact.

4: not-and

yc

Swap, then subtract.

5: B

hw

Create a stack using the first member of the stack. yk (swap then pop) also works.

6: xor

ahe

This adds the two arguments together and checks for equality with one. That is, this is true if only one of its arguments is one.

7: or

a

This adds the two arguments, and is only zero when both of its arguments are zero.

8: nor

aze

This checks if the sum is zero.

9: xnor

e

This checks for equality.

10: not B

we

w pops the TOS and creates a stack using the top TOS elements. When B is zero, this will create a stack with 0 elements; thus, the top two members are always equal, both being nil. When there is one element on the stack (when B is one), it will be 0 or 1, which is always unequal to nil.

11: then-if

cha

c subtracts, and ha adds 1. This is only false for values less than 0, thus is only false for (0, 1). See this table:

0, 0 -> [1] (0)
0, 1 -> [0] (-1)
1, 0 -> [2] (1)
1, 1 -> [1] (0)

12: not A

dce

dc replaces the TOS with 0, and e checks for equality of A with 0, which negates it.

13: if-then

chyc

This performs subtractions, then computes one minus that. This inverts #11:

0, 0 -> [1]
0, 1 -> [2]
1, 0 -> [0]
1, 1 -> [1]

14: nand

tze

Multiplies (t), then checks for equality with 0.

15: true

ade

a adds them so that only one value is on the stack. de checks if its equal to itself, which is always true.

Appendix A: Brute force over A⁴

Where A is the list of symbols:

[a...z] \ {i, j, q, p, o, n, x}

The alphabet is all of the commands of Alumin without the above characters. i and j are STDIN input (unnecessary, since all input is present), q and p are loop delineators (unnecessary since it would always leave a false value on the top of the stack), o and n are output commands, and x is nondeterministic. (If we could assume x would yield a float from 0 to 1 non-inclusive, it could shorten up many snippets, but as it stands, since there is a chance of it returning a falsey value, it cannot be used.)

The following table shows arrays of all possible solutions for each number of the same length.

0 -> ["b", "d", "f", "h", "l", "m", "r", "s", "y", "z"]
1 -> ["g", "t", "v", "w"]
2 -> ["c"]
3 -> ["k"]
4 -> ["rc", "yc"]
5 -> ["hw", "rk", "yk"]
6 -> ["ahe", "ale", "cdt", "eze", "zee"]
7 -> ["a", "u"]
8 -> ["aze", "dae", "lte", "uze"]
9 -> ["e"]
10 -> ["we"]
11 -> ["cha", "cla", "hcc", "whv", "zea", "zeu"]
12 -> ["dce", "hbe", "kze", "lee", "lge", "rwe", "ywe", "zte", "zve"]
13 -> ["chrc", "chyc", "clrc", "clyc", "drea", "dreu", "drue", "harc", "hayc", "hrca", "rcha", "rcla", "rhcc", "rwhv", "rzea", "rzeu", "ycha", "ycla", "yhcc", "ywhv", "yzea", "yzeu"]
14 -> ["tze", "vze"]
15 -> ["ade", "aha", "ahu", "ake", "akh", "ala", "alu", "awe", "awh", "cde", "chu", "cke", "ckh", "clu", "dea", "deu", "ede", "eha", "ehu", "eke", "ekh", "ela", "elu", "ewe", "ewh", "fhf", "flf", "haa", "hau", "hdw", "hua", "huu", "kde", "kha", "khu", "kke", "kkh", "kla", "klu", "kwe", "kwh", "laa", "lau", "lcc", "lhw", "lua", "luu", "tde", "tha", "thu", "tke", "tkh", "tla", "tlu", "twe", "twh", "ude", "uha", "uhu", "uke", "ukh", "ula", "ulu", "uwe", "uwh", "vde", "vha", "vhu", "vke", "vkh", "vla", "vlu", "vwe", "vwh", "wde", "whu", "wke", "wkh", "zwe", "zwh"]

This was generated using the following ruby program:

#!/usr/bin/ruby
require_relative 'alumin'

def alu(prog, inputs = [])
    inst = Alumin.new prog
    inst.stack.push *inputs
    inst.run rescue return nil
    return nil if inst.stack.size > 1
    return inst.stack[-1]
end


$truthy = "ddzycudzeaghe"
def tru(prog)
    bin = ""
    fp = prog + $truthy
    # p fp
    [[0,0],[0,1],[1,0],[1,1]].each { |arr|
        begin
            res = alu(fp, arr)
            bin += res.to_s
        rescue
            return nil
        end
    }
    bin.to_i(2)
end

max_len = 5

iter = "a"

hash = {}
(0..15).each { |e| hash[e] = [] }
while iter.size != max_len
    unless /[ijqponx]/ === iter
        res = tru(iter)
        if hash[res] && (hash[res].first.nil? || hash[res].first.size == iter.size)
            hash[res] << iter.dup
        end
    end
    iter.next!
end

(0..15).each { |e|
    puts "#{e} -> #{hash[e]}"
}

Answer 42

Japt, 26 bytes

0000 False:              Empty program outputs `undefined`
0001 A&B  : ×     r*1    Reduce by multiply, starting with 1
0010 A&!B : r>           Reduce by greater than
0011 A    : g            Get element at index 0
0100 !A&B : r<           Reduce by less than
0101 B    : o            Pop from the end
0110 A^B  : r^           Reduce by xor
0111 A|B  : d            Some
1000 !A&!B: ev           Map with not, then Every
1001 A==B : r¥    r==    Reduce by equal
1010 !B   : Ìv    gJ v   Take last item, apply not
1011 A|!B : r¨    r>=    Reduce by greater or equal
1100 !A   : v v          Pop first item, apply not
1101 !A|B : r§    r<=    Reduce by less or equal
1110 !A|!B: dv           Map with not, then Some
1111 True : 1

Try it online: False A&B A&!B A !A&B B A^B A|B !A&!B A==B !B A|!B !A !A|B !A|!B True

The input is an array of two values A and B, each being 0 or 1.

Number.v is somewhat abused here. It originally means to return 1 if the given number is divisible by 2, otherwise 0. When it is applied to 0 and 1, the result is 1 and 0 respectively, effectively being not of itself.

It's a shame that I couldn't find any 2-byte solution for !A, while I have one for !B.

Answer 43

Pyramid Scheme, 325 bytes

I've added A and B to the code to indicate where the inputs are (always A left of B); these are not included in the bytecount. All 16 assume A and B both exist and are either 0 or 1.

False, 15 bytes:

   ^
  /!\
 ^---
A-B

Try it online!

A and B, 10 bytes:

  ^
 /*\
A---B

Try it online!

A and not B, 23 bytes:

  ^
 /*\
A---^
   /!\
  B---

Try it online!

A, 10 bytes:

  ^
 /[\
A---B

Try it online!

Not A and B, 24 bytes:

   ^
  /*\
 ^---B
/!\
---A

Try it online!

B, 10 bytes:

  ^
 /]\
A---B

Try it online!

A xor B, 20 bytes:

   ^
  / \
 /<=>\
A-----B

Try it online!

A or B, 10 bytes:

  ^
 /+\
A---B

Try it online!

Neither A nor B, 23 bytes:

 ^
/!\
---^
  /+\
 A---B

Try it online!

A xnor B, 10 bytes:

  ^
 /=\
A---B

Try it online!

Not B, 23 bytes:

 ^
/!\
---^
  /]\
 A---B

Try it online!

B implies A, 35 bytes:

    ^
   /=\
  ^---^
 /*\ ^-
A---B-

Try it online!

Not A, 23 btyes:

 ^
/!\
---^
  /[\
 A---B

Try it online!

A implies B, 28 bytes:

  ^
 /=\
^---^
-^ /*\
 -A---B

Try it online!

A nand B, 23 bytes:

 ^
/!\
---^
  /*\
 A---B

Try it online!

True, 28 bytes:

   ^
  /]\
 ^---^
A-B /1\
    ---

Try it online!

There are some possibly cheaty ways I could work that bytecount down, like simply detaching one or both inputs, but I've stayed away from those. Both inputs are accepted, and any necessary ignoring is handled by the code.

Answer 44

MarioLANG, 265 263 bytes

This is going to be a fairly long answer since this is a 2D language. Trailing newlines are significant wherever they appear.

Note that these programs were written and tested on Try it Online!. There are some things that can be done on the Ruby interpreter but not in TIO's. See Martin Ender's answer for the code golfed further making use of that.

False (2 bytes)

:
​

Outputs the initial value of the first cell, which is 0.

A and B (15 14 bytes)

;-
=[
+<;
:=:
​

Takes in A and check if it's 0. If it is, it outputs 0 and ends. Otherwise, it takes in B and outputs it.

A and not B (25 bytes)

;-
=[
 <;
 =-
++[<:
:===
​

Check if A is 1. If it is, outputs 0 and ends. Otherwise, takes in B and check if it's 1. If it is, outputs 0, if it isn't, outputs 1.

A (4 bytes)

;
:
​

Takes in A and outputs it.

not A and B (14 13 bytes)

;
=[
-<;
:=:
​

Takes in A and checks if it's 0. If it is, takes in B outputs it. Otherwise, outputs 0.

B (6 bytes)

;
;
:
​

Takes in A, then B, then outputs B.

A xor B (34 bytes)

;);[!(
====#:
+![(<
:#=="
 >-:
 "=

Takes in A and B. If B is 1, output NOT A. If B is 0, output A.

A or B (13 bytes)

;
=[
:<;:
 ==

If A is 1, output A. Otherwise, output B.

A nor B (23 bytes)

;
=[
 <;
-=[
:-<+:
 ===

If A is 1, output (0). Otherwise, output NOT B.

A xnor B (27 bytes)

;
)
;
[!(
=#=[
(<-<+
:":=:
​

Takes in A and B. If B is 0, output NOT A. Otherwise, output A.

not B (18 bytes)

;;
==[
:-<+:
 ===

Takes in B. If B is 0, add 1 and output. Otherwise, subtract 1 and output. This same construct is used for negation in the other gates.

B implies A (23 bytes)

;
=[
 <;
 =[
:-<+:
 ===

If A is 1, output 1. Otherwise, output NOT B.

not A (17 bytes)

;
==[
:-<+:
 ===

Same as the NOT B answer, except only takes the first the input, not the second.

A implies B (16 bytes)

;-
=[
+<;
+=:
:
​

If A is 0, output 1. Otherwise, output B.

A nand B (24 bytes)

;-
=[
+<;
+=[
:-<+:
 ===

If A is 0, output 1. Otherwise, output NOT B.

True (3 bytes)

+
:
​

Increments the first cell and outputs it, giving 1.

Answer 45

Fourier, 94 bytes

Fourier uses 0 for falsey and 1 truthy. Many thanks to @LeakyNun for golfing help.

False, 1 bytes

o

Outputs the value of the accumulator (0), then takes input.

Try it online!

AND, 4 bytes

I*Io

Multiplies the two numbers together.

Try it online!

a AND NOT b, 6 bytes

I*1-Io

Similar to above, except the second input is subtracted from one, simulating a NOT.

Try it online!

a, 2 bytes

Io

Only outputs the first input.

Try it online!

NOT a AND b, 6 bytes

1-I+Io

Pretty mich the same as a AND NOT b.

Try it online!

b, 3 bytes

IIo

Outputs the second input.

Try it online!

XOR, 6 bytes

I+I=1o

Checks if the sum of the inputs is equal to one.

Try it online!

OR, 6 bytes

I+I>0o

Similar to AND, this checks to see if the sum of the inputs is greater than zero.

Try it online!

NOR, 6 bytes

I+I<1o

Just a reverse of the OR.

Try it online!

XNOR, 8 bytes

1-I+I=1o

Adds a NOT in front of the XOR gate.

Try it online!

NOT b, 5 bytes

I1-Io

Puts a NOT in front of the second input.

Try it online!

b implies a, 13 bytes

1-IoI{1}{@1o}

Outputs NOT a then, if b equals 1, clears the screen and outputs 1.

Try it online!

NOT a, 4 bytes

1-Io

Pretty much NOT b, just slightly different.

Try it online!

a implies b, 16 bytes

I~A1-IoA{0}{@1o}

Stores the first input in the variable A, then outputs the value of NOT b. If a is 0, the program clears the screen and outputs 1.

Try it online!

NAND, 6 bytes

I+I<2o

Again, just the inverse of the AND program.

Try it online!

True, 2 bytes

1o

Outputs 1 and ignores the inputs.

Try it online!

Answer 46

Chip, 67 bytes (non-competing, language too recent)

A and B are inputs, a is output.

1. 0000 Empty code produces false

2. 0001 ] is an AND gate

    A
   B]a
   

3. 0010 \ is a switch, where if the top/bottom is false, then left and right are connected

    B
   A\a
   

4. 0011

   Aa
   

5. 0100

    A
   B\a
   

6. 0101

   Ba
   

7. 0110 } is an XOR gate

    A
   B}a
   

8. 0111 juxtaposition implicitly OR's

   AaB
   

9. 1000 ~ is a NOT gates, and ) is an OR gate

    A
   B)~a
   

10. 1001

     A
    B}~a
    

11. 1010

    B~a
    

12. 1011 multiple identical outputs are implicitly OR'd

    A~aB
    

13. 1100

    A~a
    

14. 1101

    B~aA
    

15. 1110 ÷ is a right-to-left NOT gate

    A~a÷B
    

16. 1111 * is always-true

    *a
    

Try it online! Use ASCII 0, 1, 2, and 3 as input, since their low 2 bits are 00, 01, 10, and 11. The extra code of e*f maps the output back to ASCII 0 and 1. You can add a -v flag to see the actual binary in STDERR for the input and output.

Answer 47

SmileBASIC, 221 bytes

0     'false
A*B   'and
A>B   'a and not b
A     'a
A<B   'b and not a
B     'b
A-B   'xor
A+B   'or
A+B<1 'nor
A==B  'xnor
!B    'not b
A>=B  'b implies a
!A    'not a
B>=A  'a implies b
A+B<2 'nand
1     'true 

Add INPUT A,B? before each expression.

Other short expressions that didn't make the list (due to being longer, or the same length with not as nice output):

A/B  'divide by 0 error
A!=B 'a xor b, replaced by A-B
A*!B 'a and not b
A>>B 'a and not b, replaced by A>B
A+!B 'b implies a, replaced by A>=B
A-!B 'a xnor b, replaced by A==B
A||B 'a or b, replaced by A+B
A&&B 'a and b, replaced by A*B

Answer 48

Cubix, 103 bytes

Assuming inputs as 0 for False and 1 for True:

0000    .O@
0001    OI<\a@
0010    OU@a(I<\
0011    .IO@
0100    OU@aI(I/
0101    OIu@
0110    OI<\c@
0111    OI<\b@
1000    OU@(IIb/
1001    OU@+(I<\    
1010    OI<\(@
1011    OI<\P@
1100    .I(O@
1101    OU@PsI<\
1110    OU@(aI<\
1111    .1O@

Definitely a lot more that can be golfed here.

Answer 49

Excel: 84B

0
=a1*b3
=a1>b3
=a1
=a1<b3
=b3
=a1-b3
=a1+b3
=a1+b3=0
=a1=b3
=1-b3
=a1>=b3
=1-a1
=a1<=b3
=a1*b3<1
1

Answer 50

R, 50 bytes

 1. F
 2. &
 3. >
 4. print
 5. <
 6. "[<-"
 7. !=
 8. |
 9. <!
10. ==
11. !"[<-"
12. ^
13. function(a,b)!a
14. <=
15. !all
16. T

All functions (except 1 and 16 full programs), some infix, a and b taking values in (F,T). 4, 6 and 11 are R specific (TIO link below). I wish I had a good answer also for 13...

Try it online!

Answer 51

Flobnar, 68 bytes

Programs containing & require the -d flag.

1 (0)

0@

2 (A&B)

&
*@

3 (A&!B)

&
`@

4 (A)

&@

5 (!A&B)

!
*@
&

6 (B)

&
|@&

7 (A^B)

&
-@

8 (A|B)

&
+@

9 (A!|B)

&
+!@

10 (A!^B)

&
-!@

11 (!B)

&
|!@&

12 (A|!B)

&
+@
!

13 (!A)

&!@

14 (!A|B)

&
`!@

15 (A!&B)

&
*!@

16 (1)

1@

Answer 52

TI-BASIC, 106 bytes

0000. 0 (1 byte)
0001.*Prompt A:prod(∟A (7 bytes)
0010. Prompt A,B:A>B (8 bytes)
0011. Prompt A,B:A (6 bytes)
0100. Prompt A,B:A<B (8 bytes)
0101. Prompt A,B:B (6 bytes)
0110. Prompt A,B:A xor B (8 bytes)
0111.*Prompt A:sum(∟A (7 bytes)
1000.*Prompt A:not(sum(∟A (8 bytes)
1001. Prompt A,B:A=B (8 bytes)
1010. Prompt A,B:not(B (7 bytes)
1011. Prompt A,B:A≥B (8 bytes)
1100. Prompt A,B:not(A (7 bytes)
1101. Prompt A,B:A≤B (8 bytes)
1110.*Prompt A:not(prod(∟A (8 bytes)
1111. 1 (1 byte)

Starred numbers take input as a list. Answering on my phone again :P

Answer 53

Julia, 65 63 bytes

x\y=0>1
&
>
x\y=x
<
x\y=y
$
|
x\y=!x>y
==
x\y=!y
^
x\y=!x
<=
x\y=!x|!y
x\y=0<1

Try it online!

Answer 54

J, 27 bytes

Some credits to the official page.

0000 false              0:
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 xnor               =
1010 not q              1-]
1011 p or not q         >:
1100 not p              1-[
1101 not p or q         !
1110 not p or not q     *:
1111 true               1:

I am still not sure which values are truthy/falsey in J.

If -1 is truthy, xor can be golfed to - (subtraction).

Answer 55

Python, 215 bytes

lambda a,b:0
int.__mul__
lambda a,b:a>b
lambda a,b:a
lambda a,b:a<b
lambda a,b:b
int.__xor__
int.__or__
lambda a,b:not a|b
lambda a,b:a==b
lambda a,b:1-b
lambda a,b:a>=b
lambda a,b:1-a
lambda a,b:a<=b
lambda a,b:1-a*b
lambda a,b:1

Ideone it!

Answer 56

Pyke, 22 bytes

0000 false              0 
0001 p and q            &
0010 p and not q        >
0011 p                  Kz
0100 not p and q        <
0101 q                  Q
0110 xor                N
0111 p or q             |
1000 not p and not q    |!
1001 eq                 q
1010 not q              !
1011 p or not q         !&
1100 not p              K!
1101 not p or q         !|
1110 not p or not q     &!
1111 true               1

Answer 57

Brainfuck, 1757 bytes

This is my first golfing solution, please be gentle. :)

Inputs may be '0' (ASCII 48) or '1' (ASCII 49). Inputs are entered as AB (eg. 01 or 11). Truthy output values are 'T' (ASCII 84) or 'F' (ASCII 70).

1.

>+++++++[-<++++++++++>]>+++++++[-<++++++++++++>],>,<<<.

2.

>+++++++[-<++++++++++>]>+++++++[-<++++++++++++>],>,>++++++[-<<-------->>]++++++[-<-------->]<<[->>+<<]>[->+<]>--[<]<<<.

3.

>+++++++[-<++++++++++>]>+++++++[-<++++++++++++>],>,>++++++[-<<-------->>]++++++[-<-------->]+<[->-<]>[<+>-]<<[->>+<<]>[->+<]>--[<]<<<.

4.

>+++++++[-<++++++++++>]>+++++++[-<++++++++++++>],>,[-]++++++[-<-------->]+<[<.>->-<]>[<<<.>>>->]<<

5.

>+++++++[-<++++++++++>]>+++++++[-<++++++++++++>],>,>++++++[-<<-------->>]++++++[-<-------->]+<<[->>-<<]>>[<<+>>-]<<[->>+<<]>[->+<]>--[<]<<<.

6.

>+++++++[-<++++++++++>]>+++++++[-<++++++++++++>],,>[-]++++++[-<-------->]+<[<.>->-<]>[<<<.>>>->]<<

7.

>+++++++[-<++++++++++>]>+++++++[-<++++++++++++>],>,>++++++[-<<-------->>]++++++[-<-------->]<<[->>+<<]>[->+<]>-[<]<<<.

8.

>+++++++[-<++++++++++++>]>+++++++[-<++++++++++>],>,>++++++[-<<-------->>]++++++[-<-------->]<<[->>+<<]>[->+<]>[<]<<<.

9.

>+++++++[-<++++++++++>]>+++++++[-<++++++++++++>],>,>++++++[-<<-------->>]++++++[-<-------->]<<[->>+<<]>[->+<]>[<]<<<.

10.

>+++++++[-<++++++++++++>]>+++++++[-<++++++++++>],>,>++++++[-<<-------->>]++++++[-<-------->]<<[->>+<<]>[->+<]>-[<]<<<.

11.

>+++++++[-<++++++++++++>]>+++++++[-<++++++++++>],,>[-]++++++[-<-------->]+<[<.>->-<]>[<<<.>>>->]<<

12.

>+++++++[-<++++++++++++>]>+++++++[-<++++++++++>],>,>++++++[-<<-------->>]++++++[-<-------->]+<<[->>-<<]>>[<<+>>-]<<[->>+<<]>[->+<]>--[<]<<<.

13.

>+++++++[-<++++++++++++>]>+++++++[-<++++++++++>],>,[-]++++++[-<-------->]+<[<.>->-<]>[<<<.>>>->]<<

14.

>+++++++[-<++++++++++++>]>+++++++[-<++++++++++>],>,>++++++[-<<-------->>]++++++[-<-------->]+<[->-<]>[<+>-]<<[->>+<<]>[->+<]>--[<]<<<.

15.

>+++++++[-<++++++++++++>]>+++++++[-<++++++++++>],>,>++++++[-<<-------->>]++++++[-<-------->]<<[->>+<<]>[->+<]>--[<]<<<.

16.

>+++++++[-<++++++++++>]>+++++++[-<++++++++++++>],>,<<.

Answer 58

Yup, 109 + 80 = 189 bytes

+80 bytes for 16 -x 0 flags. For removing the imaginary parts.

0000 false           0#
0001 and             *|0*|--e#
0010 A and not B     **-#
0011 A               *#
0100 not A and B     0**--#
0101 B               **#
0110 xor             **-:|~|0~--e#
0111 or              *0*--#
1000 nor             0e*0*---#
1001 xnor            0e**-:|~|0~--e-#
1010 not B           *0e*-#
1011 B implies A     **|-#
1100 not A           0e*-#
1101 A implies B     0e**--
1110                 0e00e--*0*---#
1111 true            0e#

Try it online!

Answer 59

Java 8, 165 bytes

x->y->1<0;
x->y->x&y;
x->y->!y&x;
x->y->x;
x->y->!x&y;
x->y->y;
x->y->x!=y;
x->y->x|y;
x->y->!(x|y);
x->y->x==y;
x->y->!y;
x->y->!y|x;
x->y->!x;
x->y->!x|y;
x->y->!x|!y;
x->y->1>0;

Verify it! (Click "Compile" > Click "Execute")

Answer 60

MarioLANG, 176 132 bytes

These solutions were all tested in Ruby interpreter and make substantial use of the implementation-specific feature that > and < can move Mario in mid-air, avoiding the need for ground tiles in many cases.

MarioLANG's only conditional is [ which skips the next command if the current cell is zero. Therefore all non-zero values are truthy and zero is falsy. I'm making use of this to shorten the code substantially by occasionally outputting -1 as truthy.

0000 (1 byte)

:

0001 (7 bytes)

;[;
==:

0010 (12 bytes)

;
[
>;
:-
 :

0011 (3 bytes)

;
:

0100 (9 bytes)

;-[;
===:

0101 (5 bytes)

;;
=:

0110 (12 bytes)

;
[
>;
;-
::

0111 (10 bytes)

;
[
>:
;
:

1000 (13 bytes)

;
[
>-
;:
-
:

1001 (13 bytes)

;
[
>;
;:
-
:

1010 (7 bytes)

;;-
==:

1011 (12 bytes)

;
[
>:
;
-
:

1100 (5 bytes)

;-
=:

1101 (11 bytes)

;
[
>;
+:
:

1110 (9 bytes)

;[;-
===:

1111 (3 bytes)

+
:

Answer 61

Coconut, 88 bytes

0000 [].sort
0001 (*)
0010 (>)
0011 round
0100 (<)
0101 range
0110 (^)
0111 (|)
1000 (not)..(|)
1001 (==)
1010 (a,b)->b<1
1011 pow
1100 (a,b)->a<1
1101 (<=)
1110 (not)..(*)
1111 slice

Coconut is an extension of Python. Every valid program in Python is also valid in Coconut.

Credits to xnor for some of the functions.

Answer 62

C, 164 Bytes

#define r (a,b){return
c r 0;}d r a&b;}e r a>b;}f r a;}g r a<b;}h r b;}i r a^b;}j r a|b;}k r !b>a;}l r a==b;}m r !b;}n r !b|a;}o r !a;}p r !a|b;}q r !b|!a;}s r 1;}

Answer 63

Pyramid*, 112 bytes

The programs, in order (each separated by a =):

0000 (false):

0<

0001 (and):

?<
?

0010 (A and not B):

0?<
?
1

0011 (A):

?<

0100 (B and not A):

?
?<
0

0101 (B):

?
?<
?

0110 (xor):

?
0
1?<
?
0

0111 (or):

?
?<

1000 (nor):

1
?
00
?<
0

1001 (xnor):

1
?
0?<
1
?

1010 (not B):

1
?
00
?<
11
?
0

1011 (B implies A):

1
?
0?<

1100 (not A):

1
?<
0

1101 (A implies B):

1
?<
?

1110 (nand):

1
?<
11
?
0

1111 (true):

1<

*Technically, all of this can be done using regular Stackylogic.

Answer 64

Logicode, 282 bytes

All logic gates in order:

out 0
circ g(a,b)->a&b
circ g(a,b)->a&(!b)
circ g(a)->a
circ g(a,b)->(!a)&b
circ g(a,b)->b
circ g(a,b)->(!(a&b))&(a|b)
circ g(a,b)->a|b
circ g(a,b)->!(a|b)
circ g(a,b)->!((!(a&b))&(a|b))
circ g(a,b)->!b
circ g(a,b)->(!a)|b
circ g(a)->!a
circ g(a,b)->a|(!b)
circ g(a,b)->!(a,b)
out 1

Logicode is basically a code version of Logisim.

Check the Github repo (in the link) for more information.

Answer 65

NOR gates, 42 gates

Exprimed in pseudocode, NOR gates are -

0000 0
0001 (a-a)-(b-b)
0010 (a-a)-b
0011 a
0100 a-(b-b)
0101 b
0110 (a-b-a)-(a-a-b)-(a-b)
0111 (a-b)-(a-b)
1000 a-b
1001 (a-b-a)-(a-a-b)
1010 b-b
1011 (a-b-a)-(a-b-a)
1100 a-a
1101 (b-a-b)-(b-a-b)
1110 (a-a)-(b-b)-((a-a)-(b-b))
1111 1

Answer 66

Java 8, tested in Java 7 and written over directly, 565 bytes

This is mainly as a proof of concept, because I wanted to make a program for this where every gate could be written by only changing a number. It's not nearly as short as some of the other answers, but I felt like posting it here regardless.

interface G{int g(boolean a,boolean b);G[]g={(a,b)->0&(1<<((a?0:2)+(b?0:1))),(a,b)->1&(1<<((a?0:2)+(b?0:1))),(a,b)->2&(1<<((a?0:2)+(b?0:1))),(a,b)->3&(1<<((a?0:2)+(b?0:1))),(a,b)->4&(1<<((a?0:2)+(b?0:1))),(a,b)->5&(1<<((a?0:2)+(b?0:1))),(a,b)->6&(1<<((a?0:2)+(b?0:1))),(a,b)->7&(1<<((a?0:2)+(b?0:1))),(a,b)->8&(1<<((a?0:2)+(b?0:1))),(a,b)->9&(1<<((a?0:2)+(b?0:1))),(a,b)->10&(1<<((a?0:2)+(b?0:1))),(a,b)->11&(1<<((a?0:2)+(b?0:1))),(a,b)->12&(1<<((a?0:2)+(b?0:1))),(a,b)->13&(1<<((a?0:2)+(b?0:1))),(a,b)->14&(1<<((a?0:2)+(b?0:1))),(a,b)->15&(1<<((a?0:2)+(b?0:1)))};}

Behold this disgusting mess. Ungolfed:

interface G{
    int g(boolean a, boolean b);
    G[] g = {
        (a, b) -> 0 & (1 << ((a ? 0 : 2) + (b ? 0 : 1))),
        (a, b) -> 1 & (1 << ((a ? 0 : 2) + (b ? 0 : 1))),
        (a, b) -> 2 & (1 << ((a ? 0 : 2) + (b ? 0 : 1))),
        (a, b) -> 3 & (1 << ((a ? 0 : 2) + (b ? 0 : 1))),
        (a, b) -> 4 & (1 << ((a ? 0 : 2) + (b ? 0 : 1))),
        (a, b) -> 5 & (1 << ((a ? 0 : 2) + (b ? 0 : 1))),
        (a, b) -> 6 & (1 << ((a ? 0 : 2) + (b ? 0 : 1))),
        (a, b) -> 7 & (1 << ((a ? 0 : 2) + (b ? 0 : 1))),
        (a, b) -> 8 & (1 << ((a ? 0 : 2) + (b ? 0 : 1))),
        (a, b) -> 9 & (1 << ((a ? 0 : 2) + (b ? 0 : 1))),
        (a, b) -> 10 & (1 << ((a ? 0 : 2) + (b ? 0 : 1))),
        (a, b) -> 11 & (1 << ((a ? 0 : 2) + (b ? 0 : 1))),
        (a, b) -> 12 & (1 << ((a ? 0 : 2) + (b ? 0 : 1))),
        (a, b) -> 13 & (1 << ((a ? 0 : 2) + (b ? 0 : 1))),
        (a, b) -> 14 & (1 << ((a ? 0 : 2) + (b ? 0 : 1))),
        (a, b) -> 15 & (1 << ((a ? 0 : 2) + (b ? 0 : 1)))
               // ^ this number + 1 is the logic gate being programmed
    };
}

Answer 67

BitCycle, 140 134 bytes (non-competing)

BitCycle is a language that operates on bits, which makes it good for this challenge. However, it's a 2D language and doesn't have any boolean operators, which makes it less good for this challenge.

false, 2 bytes

0!

and, 11 bytes

 !+
?=/!
?^

A and not B, 11 bytes

 !+
?=/!
?~

A, 2 bytes

?!

not A and B, 14 11 bytes

+~
!=
?^
?^

B, 3 bytes

??!

xor, 13 10 bytes

?v
?v!
!=~

or, 12 bytes

?v
/=/!
!
?^

nor, 13 bytes

?\!+
?\
 ~=/!

xnor, 11 bytes

?v
~=\!
!?^

not B, 6 bytes

 !?
?~

B implies A, 13 bytes

?v
?=\!
  +~

not A, 5 bytes

 !
?~

A implies B, 9 bytes

?=\!
?/+~

nand, 13 bytes

!~
?+
~\\
!?^

true, 2 bytes

1!

General explanation

Bits move around the playfield, interacting with various devices. If they exit the playfield, they are destroyed. Here are the devices used in the following programs:

• ! - send bits to output
• ? - get bits from input. Multiple instances of ? are assigned to inputs top-to-bottom, left-to-right. So in these programs, the topmost ? is the A input and the bottommost is B.
• > < ^ v - redirect bits unconditionally
• / and \ - reflect the first bit they encounter, pass all subsequent bits straight through
• = - pass first bit straight through; if first bit was 0, send all subsequent bits west; if first bit was 1 send all subsequent bits east
• + - 0 turns left, 1 turns right
• ~ - bit turns right; a negated copy is generated and turns left

If you want in-depth explanation for specific gate(s), leave a comment and I'll add it.

Answer 68

Ruby, 246 bytes, non-competing

Not really golfed, and somewhat boring. But I can't leave this question without a Ruby answer.

1    ->a,b{0[a+a+b]}
2    ->a,b{1[a+a+b]}
3    ->a,b{2[a+a+b]}
4    ->a,b{3[a+a+b]}
5    ->a,b{4[a+a+b]}
6    ->a,b{5[a+a+b]}
7    ->a,b{6[a+a+b]}
8    ->a,b{7[a+a+b]}
9    ->a,b{8[a+a+b]}
10   ->a,b{9[a+a+b]}
11   ->a,b{10[a+a+b]}
12   ->a,b{11[a+a+b]}
13   ->a,b{12[a+a+b]}
14   ->a,b{13[a+a+b]}
15   ->a,b{14[a+a+b]}
16   ->a,b{15[a+a+b]}

A lot of improvements are possible, for example rewriting the first function as ->a,b{} but even assuming the function body is 1 byte for each answer, the minimum byte count is 64.

Based on the python non-competing lambda, this could be written as:

->n{->a,b{n[a+a+b]}}

Answer 69

Pyth, 33 bytes

0000: 0
0001: &E
0010: <E
0011: Q
0100: >E
0101: E 
0110: xE
0111: |E
1000: !|E
1001: qE
1010: !E 
1011: !>E
1100: !
1101: !<E
1110: !&E
1111: 1

Mind the trailing spaces! Test here, putting each program in the Code box.

Answer 70

Excel VBA, 114 Bytes

Series of binary Boolean operators which give the individually specified commented to the right of the function. All take input, if any, as A from [A1] and B from [B1] on the ActiveSheet object

Interestingly, despite the presence of OR, AND, NOT, XOR and IMP operators, using any of these directly is actually longer than using math.

?0          ' 0,0,0,0 (false)
?[A1*B1]    ' 0,0,0,1 (and)
?[A1>B1]    ' 0,0,1,0 (A and not B)
?[A1]       ' 0,0,1,1 (A)
?[A1<B1]    ' 0,1,0,0 (not A and B)
?[B1]       ' 0,1,0,1 (B)
?[A1-B1]    ' 0,1,1,0 (xor)
?[A1+B1]    ' 0,1,1,1 (or)
?[A1+B1=0]  ' 1,0,0,0 (nor)
?[A1=B1]    ' 1,0,0,1 (xnor)
?[1-B1]     ' 1,0,1,0 (not B)
?[A1>=B1]   ' 1,0,1,1 (B implies A)
?[1-A1]     ' 1,1,0,0 (not A)
?[A1<=B1]   ' 1,1,0,1 (A implies B)
?1>[A1*B1]  ' 1,1,1,0 (nand)
?1          ' 1,1,1,1 (true)

Uncommented Version

^{For Byte Counting}

?0
?[A1*B1]
?[A1>B1]
?[A1]
?[A1<B1]
?[B1]
?[A1-B1]
?[A1+B1]
?[A1+B1=0]
?[A1=B1]
?[1-B1]
?[A1>=B1]
?[1-A1]
?[A1<=B1]
?1>[A1*B1]
?1

Answer 71

Implicit, 35 28 bytes

0000 false              #      push length of stack
0001 p and q            *      2 implicit int inputs, multiply
0010 p and not q        <      2 implicit int inputs, less than
0011 p                  $      read input
0100 not p and q        >      2 implicit int inputs, greater than
0101 q                  $$     read input twice
0110 xor                ·      2 implicit int inputs, XOR
0111 p or q             +      2 implicit int inputs, add
1000 not p and not q    ñ$ñ=   implicit input NOT-equals self, input not-equals self, equality
1001 eq                 =      2 implicit int inputs, equality
1010 not q              $$ñ    read two integers, second NOT-equals self
1011 p or not q         $$ñ+   read two integers, second NOT-equals self, add
1100 not p              ñ      implicit input, NOT-equals self
1101 not p or q         ñ$+    implicit input NOT-equals self, read input, add
1110 not p or not q     *ñ     2 implicit int inputs, multiply, logical-NOT
1111 true               1      push 1

All of these rely on implicit output.

Links: 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

Answer 72

Add++, 135 bytes

D,0000,,0
D,0001,@@,&
D,0010,@@,!$&
D,0011,@,
D,0100,@@,$!&
D,0101,@@,
D,0110,@@,Bx
D,0111,@@,Bo
D,1000,@@,Bo!
D,1001,@@,Bx!
D,1010,@@,!
D,1011,@@,!Bo
D,1100,@,!
D,1101,@@,!&!
D,1110,@@,&!
D,1111,,1

The byte count assumes single byte names, such as a or b

How they work

0000

D,0000,,     - Create a niladic function
          0  - Return 0

0001

D,0001,@@,   - Create a dyadic function
          &  - Return A and B

0010

D,0010,@@,   - Create a dyadic function
          !  - NOT B
          $  - Swap
          &  - Return A and NOT B

0011

D,0011,@,    - Create a monadic function
             - Return A

0100

D,0100,@@,   - Create a dyadic function
          $  - Swap
          !  - NOT A
          &  - Return NOT A and B

0101

D,0101,@@,   - Create a dyadic function
             - Return B

0110

D,0110,@@,   - Create a dyadic function
          Bx - Return A xor B

0111

D,0111,@@,   - Create a dyadic function
          Bo - Return A or B

1000

D,1000,@@,   - Create a dyadic function
          Bo - A or B
          !  - Return NOT A or NOT B

1001

D,1001,@@,   - Create a dyadic function
          Bx - A xor B
          !  - Return NOT A xor NOT B

1010

D,1010,@@,   - Create a dyadic function
          !  - Return NOT B

1011

D,1011,@@,   - Create a dyadic function
          !  - NOT B
          Bo - Return A or NOT B

1100

D,1100,@,    - Create a monadic function
         !   - Return NOT A

1101

D,1101,@@,   - Create a dyadic function
          !  - NOT B
          &  - A and NOT B
          !  - Return NOT A and B

1110

D,1110,@@,   - Create a dyadic function
          &  - A and B
          !  - Return NOT A and NOT B

1111

D,1111,,     - Create a niladic function
        1    - Return 1

Answer 73

Pyth - 75 bytes

False

0

And

AQ&GH

A and not B

AQ&G!H

A

AQG

Not A and B

AQ&!GH

B

AQH

XOR

AQxGH

OR

AQ+GH

NOR

AQ!+GH

XNOR

AQ!xGH

Not B

AQ!H

B implies A

AQ!&!GH

not A

AQ!G

A implies b

AQ!&G!H

nand

AQ!&GH

True

1

Answer 74

Pyt, 46 bytes

0000   0
0001   ←←∧
0010   ←←¬∧
0011   ←
0100   ←¬←∧
0101   ←ŕ←
0110   ←←⊻
0111   ←←∨
1000   ←←⊽
1001   ←←⊙
1010   ←ŕ←¬
1011   ←¬←⊼
1100   ←¬
1101   ←←¬⊼
1110   ←←⊼
1111   1

Answer 75

C (gcc), 144 143 bytes

#define Q(R,S)R(a,b){return S>>a+a+b&1;}
Q(A,0)Q(B,8)Q(C,4)Q(D,12)Q(E,2)Q(F,10)Q(G,6)Q(H,14)Q(I,1)Q(J,9)Q(K,5)Q(L,13)Q(M,3)Q(N,11)Q(O,7)Q(P,15)

Try it online!

Ungolfed / expanded with comments

A(a,b){return 0>>a+a+b&1;}  // false
B(a,b){return 8>>a+a+b&1;}  // and
C(a,b){return 4>>a+a+b&1;}  // A and not B
D(a,b){return 12>>a+a+b&1;} // A
E(a,b){return 2>>a+a+b&1;}  // not A
F(a,b){return 10>>a+a+b&1;} // B
G(a,b){return 6>>a+a+b&1;}  // xor
H(a,b){return 14>>a+a+b&1;} // or
I(a,b){return 1>>a+a+b&1;}  // nor
J(a,b){return 9>>a+a+b&1;}  // xnor
K(a,b){return 5>>a+a+b&1;}  // not B
L(a,b){return 13>>a+a+b&1;} // B implies A
M(a,b){return 3>>a+a+b&1;}  // not A
N(a,b){return 11>>a+a+b&1;} // A implies B
O(a,b){return 7>>a+a+b&1;}  // nand
P(a,b){return 15>>a+a+b&1;} // true

Answer 76

Jelly, 17 bytes

Gate Name        L Code
---- ----------- - ----
0000 FALSE       1 0
0001 AND         1 &
0010 A AND NOT B 1 >
0011 A           0 
0100 NOT A AND B 1 <
0101 B           1 ⁹
0110 XOR         1 ^
0111 OR          1 |
1000 NOR         2 |C
1001 XNOR        1 ⁼
1010 NOT B       1 %
1011 B IMPLIES A 1 :
1100 NOT A       1 C
1101 A IMPLIES B 1 ọ
1110 NAND        2 &C
1111 TRUE        1 1

Test suite.

Answer 77

Ceylon, 143 bytes

value u=[for(i in 0:16)(Boolean a,Boolean b)=>[false,a&&b,a&&!b,a,!a&&b,b,a!=b,a||b,!a&&!b,a==b,!b,a||!b,!a,!a||b,!a||!b,true][i]else nothing];

Normally you would write it this way:

alias B => Boolean;

B(B, B)[] t = [
    (B a, B b) => false,
    (B a, B b) => a&&b,
    (B a, B b) => a&&!b,
    (B a, B b) => a,
    (B a, B b) => b&&!a,
    (B a, B b) => b,
    (B a, B b) => a!=b,
    (B a, B b) => a||b,
    (B a, B b) => !a&&!b,
    (B a, B b) => a==b,
    (B a, B b) => !b,
    (B a, B b) => a||!b,
    (B a, B b) => !a,
    (B a, B b) => b||!a,
    (B a, B b) => !a||!b,
    (B a, B b) => true
];

This alias + variable definition of length 284 (if removing unneeded whitespace) defines t as a sequence of 16 functions, each with two Boolean parameters and a Boolean return value.

xnor is just equality, xor is inequality for booleans. nand and nor were transformed via DeMorgan's rules, as this is shorter than !(a&&b) or !(a||b). A implies B is written in the "not A or B" form.

We added the alias to not have to write Boolean each time – this is worth from three usages. Normally you would have written [B(B, B)*] (or [B(B, B)+]) for the type of t, but the "traditional" syntax with the [] at the end is one byte shorter. (We could also have written B(B, B)[16] to indicate it's a sequence of length 16, but that would have been even longer, and wouldn't work for the next versions anyways.)

Unfortunately, we here have to repeat the parameter types and names each time.

If we are just interested in all the expressions (and don't necessary need functions), then this works too:

alias B => Boolean;

B[] z(B a,B b) => [
    false,
    a&&b,
    a&&!b,
    a,
    !a&&b,
    b,
    a!=b,
    a||b,
    !a&&!b,
    a==b,
    !b,
    a||!b,
    !a,
    !a||b,
    !a||!b,
    true
];

This (golfed length 113) is a function z which returns a sequence of 16 Boolean values (the results of each of the gates in order). (This is not much more than the 78 bytes for just the expressions and commas.) We can convert it into the same type as the first one (sequence of functions) by adding this one-liner:

B(B,B)[] w = [for (i in 0:16) (B a, B b) => z(a,b)[i] else nothing];

(The else nothing is needed because the Ceylon compiler is unable to figure out that i is always in the range of valid indexes for z. Alternatively, we could change the type to B?(B,B) (i.e. returning an optional boolean), but then the caller would have to worry about nulls.)

z and w together come to 172 bytes. Of course, we can merge those two together to save a tiny bit more:

alias B=>Boolean;
B(B,B)[] y = [for (i in 0:16)
  (B a, B b) => [
    false,
    a&&b,
    a&&!b,
    a,
    !a&&b,
    b,
    a!=b,
    a||b,
    !a&&!b,
    a==b,
    !b,
    a||!b,
    !a,
    !a||b,
    !a||!b,
    true
  ][i] else nothing];

This is 150 bytes (after removing whitespace), less than double of the plain expressions (+ commas) of 76.

If we can use a private declaration (inside a function or class) instead of a shared one, we don't need to write down the type (use the value keyword instead, for type inference), and then can get rid of the alias (as we only have two Boolean left):

value u = [for (i in 0:16)
    (Boolean a, Boolean b) => [
        false,
        a&&b,
        a&&!b,
        a,
        !a&&b,
        b,
        a!=b,
        a||b,
        !a&&!b,
        a==b,
        !b,
        a||!b,
        !a,
        !a||b,
        !a||!b,
        true
      ][i] else nothing];

This (with whitespace removal) is the 143 bytes declaration from the top of the post.

Try it online!

Answer 78

Charcoal, 31 bytes

Charcoal's default input is two 0 or 1 digits separated by a space or newline and default output is - for 1 and empty for 0. Requiring 0 or 1 output would add 12 bytes; the first program would become 0 and most other programs would need an initial Ｉ. The exceptions would be N (becomes θ), Ｉη (becomes η) and ¹ (becomes 1).

0 0 0 0         0 bytes  Empty output.
0 0 0 1   ∧ＮＮ   3 bytes  Logical And.
0 0 1 0   ›     1 byte   Greater than.
0 0 1 1   Ｎ     1 byte   First input.
0 1 0 0   ‹     1 byte   Less than.
0 1 0 1   Ｉη    2 bytes  Second input as a boolean.
0 1 1 0   ¬⁼    2 bytes  Not equal.
0 1 1 1   ∨ＮＮ   3 bytes  Logical Or.
1 0 0 0   ¬∨ＮＮ  4 bytes  Logical Nor.
1 0 0 1   ⁼     1 byte   Equals.
1 0 1 0   ¬Ｉη   3 bytes  Logical Not of second input as a boolean.
1 0 1 1   Ｘ     1 byte   Exponentiate.
1 1 0 0   ¬Ｎ    2 bytes  Logical Not of first input.
1 1 0 1   ¬›    2 bytes  Not greater than.
1 1 1 0   ¬∧ＮＮ  4 bytes  Logical Nand.
1 1 1 1   ¹     1 byte  Prints `-`.

Answer 79

Java, 695 bytes

class L{boolean f(){return false;}boolean d(boolean... x){return a(x)==t()?b(x):f();}boolean q(boolean...x){return d(a(x),n(b(x)));}boolean n(boolean x){return x==t()?f():t();}boolean a(boolean... x){return x[0];}boolean w(boolean...x){return d(n(a(x)),b(x));}boolean b(boolean...x){return x[1];}boolean x(boolean...x){return d(o(x),n(d(x)));}boolean o(boolean...x){return n(d(n(a(x)),n(b(x))));}boolean s(boolean...x){return n(o(x));}boolean r(boolean...x){return n(x(x));}boolean l(boolean...x){return n(b(x));}boolean j(boolean...x){return n(w(x));}boolean c(boolean...x){return n(a(x));}boolean v(boolean...x){return n(q(x));}boolean m(boolean...x){return n(d(x));}boolean t(){return !f();}}

Ungolfed

public class LogicGate
{
    public static boolean f(boolean... x)
    {
        return false;
    }

    public static boolean and(boolean... x)
    {
        return a(x)==t() ? b(x) : f();
    }

    public static boolean aandnotb(boolean... x)
    {
        return and( a(x), not(b(x)) );
    }

    private static boolean not(boolean x)
    {
        return x==t()?f():t();
    }

    public static boolean a(boolean... x)
    {
        return x[0];
    }

    public static boolean notaandb(boolean... x)
    {
        return and( not(a(x)), b(x));
    }

    public static boolean b(boolean... x)
    {
        return x[1];
    }

    public static boolean xor(boolean... x)
    {
        return and( or(x), not(and(x)) );
    }

    public static boolean or(boolean... x)
    {
        return not( and( not(a(x)), not(b(x))) );//see de morgan's law
    }

    public static boolean nor(boolean... x)
    {
        return not(or(x));
    }

    public static boolean xnor(boolean... x)//it is understandable when written nxor. See https://en.wikipedia.org/wiki/XNOR_gate
    {
        return not(xor(x));
    }

    public static boolean notb(boolean... x)
    {
        return not(b(x));
    }

    public static boolean bimpliesa(boolean... x) //A ⇒ B is true only in the case that either A is false o B is true.
    {
        return not(notaandb(x)) ;// == o( n(b(x)), a(x));
    }

    public static boolean nota(boolean... x)
    {
        return not(a(x));
    }

    public static boolean aimpliesb(boolean... x)
    {
        return not(aandnotb(x));
    }

    public static boolean nand(boolean... x)
    {
        return not( and(x) );
    }

    public static boolean t(boolean... x)
    {
        return !f();
    }
}

Test case to try above code.

Answer 80

Sesos, 56 55 bytes (non-competing)

; shared by all programs, counted for each
set numin,set numout

; 0,0,0,0, 1 byte
put
; 0,0,0,1, 3 bytes
get,jmp,get,fwd 1,jnz,rwd 1,put
; 0,0,1,0, 4 bytes
get,fwd 1,get,sub 1,jmp,rwd 1,jnz,fwd 2,put
; 0,0,1,1, 1 byte
get,put
; 0,1,0,0, 4 bytes
get,sub 1,fwd 1,get,jmp,rwd 1,jnz,fwd 2,put
; 0,1,0,1, 2 bytes
get,get,put
; 0,1,1,0, 5 bytes
get,fwd 1,get,jmp,rwd 1,sub 1,fwd 1,sub 1,jnz,rwd 1,put
; 0,1,1,1, 5 bytes
get,fwd 1,get,jmp,rwd 1,add 1,fwd 1,sub 1,jnz,rwd 1,put
; 1,0,0,0, 5 bytes
add 1,fwd 1,get,jmp,rwd 1,jnz,get,jmp,rwd 1,jnz,rwd 1,put
; 1,0,0,1, 7 bytes
get,fwd 1,get,jmp,rwd 1,sub 1,fwd 1,sub 1,jnz,add 1,rwd 1,jmp,fwd 1,jnz,fwd 1,put
; 1,0,1,0, 2 bytes
get,get,sub 1,put
; 1,0,1,1, 4 bytes
add 2,fwd 1,get,fwd 1,get,jmp,rwd 1,jnz,fwd 1,sub 1,put
; 1,1,0,0, 2 bytes
get,sub 1,put
; 1,1,0,1, 5 bytes
get,sub 1,fwd 1,get,jmp,rwd 1,sub 1,fwd 1,sub 1,jnz,rwd 1,put
; 1,1,1,0, 4 bytes
get,fwd 1,get,jmp,rwd 1,jnz,fwd 2,sub 1,put
; 1,1,1,1, 1 byte
add 1,put

Input is 0 or 1, output is zero (falsy) or non-zero (truthy).

Thanks to @MartinEnder for golfing off 1 byte!

Answer 81

Golfscript, 36 bytes

0000 ;
0001 ~*
0010 ~>
0011 ~;
0100 ~<
0101 ~\;
0110 ~^
0111 ~|
1000 ~*!
1001 ~=
1010 ~\;!
1011 ~?
1100 ~;!
1101 ~>!
1110 ~*!
1111 

Online interpreter.

Answer 82

Wise, 46 bytes (not-competing)

False

^:^

And

&

A and not B

?~&

A

?:^|

not A and B

~&

B

:^|

Xor

^

Or

|

Nor

|~

Xnor

^~

Not B

:^|~

B implies A

~&~

Not A

?:^^~

A implies B

?~&~

Nand

~?~&

True

^:~^

Answer 83

RProgN, 52 Bytes Non-Competing

0000    [ [ 0   # Pop A and B off reg, push 0 (Falsey)
0001    &       # Push Logical And of A AND B
0010    ! &     # Invert B, Logical AND
0011    [       # Pop B
0100    \ ! &   # Push B under A, Invert A, Logical AND.
0101    \ [     # Push B under A, pop A.
0110    == !    # Pop and And B and push truthy if they're equal. Logical not the output.
0111    |       # Logical Or of A OR B
1000    | !     # Logical Or of A OR B, Inverted.
1001    ==      # Pop and And B and push truthy if they're equal, falsy if they're not.
1010    \ [ !   # Flip B under A, Pop A, Pop B and return it's logical Not.
1011    ! |     # Pop B and push its logical Not, Logical Or of A OR (NOT B)
1100    [ !     # Pop B, pop A then Push the not value of A
1101    \ ! |   # Swap B under A, Pop A and Push it's logical Not, Push the Logical Or of A OR B
1110    & !     # Push Logical And of A AND B, pop and push the logical not.
1111    [ [ 1   # Push A and B off reg, Push 1 (Truthy)

ALL of these are full programs. Four digits behind and text after and including the # are all for commentary.