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.

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!

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.

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

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.

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.

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.

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]

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.

x86 machine code (48 47 bytes)

Played really straight; assumes input in ax and bx, output goes in ax.

Gate    Hex      Assembly
====    ====     ========
0000    31C0     xor ax,ax

0001    21D8     and ax,bx

0010    F7D3     not bx
        21D8     and ax,bx

0011             (nothing to do)

0100    F7D0     not ax
        21D8     and ax,bx

0101    89D8     mov ax,bx

0110    31D8     xor ax,bx

0111    09D8     or ax,bx

1000    09D8     or ax,bx
        F7D0     not ax

1001    B80100   mov ax,0x1

1010    F7D3     not bx
        89D8     mov ax,bx

1011    F7D3     not bx
        09D8     or ax,bx

1100    F7D0     not ax

1101    F7D0     not ax
        09D8     or ax,bx

1110    21D8     and ax,bx
        F7D0     not ax

1111    31C0     xor ax,ax
        F7D0     not ax

Labyrinth, 85 bytes

Thanks to Sp3000 for saving 2 bytes.

!@
??&!@
??~&!@
?!@
?~?&!@
??!@
??$!@
??|!@
1??|-!@
1??$-!@
?#?-!@
?#?$|!@
1?-!@
1?$?|!@
1??&-!@
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.)

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)

ClojureScript, 88 84 76 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   inc             ; previously: (fn[]4)

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

NAND logic gates — 30 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.

What's interesting about this solution is that there are four different gates that require zero NAND gates to implement — just ground wires or constants.

While this is not technically a program or function, it sizes up with the other solutions quite nicely regardless.

Haskell, 78 76 bytes

1. _#_=2<1
2. &&
3. >
4. a#_=a (or const)
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

Java 8, 251 240 bytes

Removed 11 bytes thanks to Frozn!

interface a{a[]A={(a,b)->1<0,(a,b)->a&b,(a,b)->a&!b,(a,b)->a,(a,b)->!a&b,(a,b)->b,(a,b)->a^b,(a,b)->a|b,(a,b)->!a&!b,(a,b)->!(a^b),(a,b)->!b,(a,b)->b?a:true,(a,b)->!a,(a,b)->a?b:true,(a,b)->!a|!b,(a,b)->1>0};boolean b(boolean B,boolean c);}

This is WAY shorter than my prediction(s) :)

Ungolfed:

interface a{
    a[] A = {
        (a, b) -> 1 < 0,        // 1
        (a, b) -> a & b,        // 2
        (a, b) -> a & !b,       // 3
        (a, b) -> a,            // 4
        (a, b) -> !a & b,       // 5
        (a, b) -> b,            // 6
        (a, b) -> a ^ b,        // 7
        (a, b) -> a | b,        // 8
        (a, b) -> !a & !b,      // 9
        (a, b) -> !(a ^ b),     // 10
        (a, b) -> !b,           // 11
        (a, b) -> b ? a : true, // 12
        (a, b) -> !a,           // 13
        (a, b) -> a ? b : true, // 14
        (a, b) -> !a | !b,      // 15
        (a, b) -> 1 > 0         // 16
    };

    boolean b(boolean B, boolean c);
}

Java 5 (probably), 1029 1018 bytes

interface a{a[]A={new a(){public boolean b(boolean a,boolean B){return 1<0;}},new a(){public boolean b(boolean a,boolean B){return a&B;}},new a(){public boolean b(boolean a,boolean B){return a&!B;}},new a(){public boolean b(boolean a,boolean B){return a;}},new a(){public boolean b(boolean a,boolean B){return!a&B;}},new a(){public boolean b(boolean a,boolean B){return B;}},new a(){public boolean b(boolean a,boolean B){return a^B;}},new a(){public boolean b(boolean a,boolean B){return a|B;}},new a(){public boolean b(boolean a,boolean B){return!a&!B;}},new a(){public boolean b(boolean a,boolean B){return!(a^B);}},new a(){public boolean b(boolean a,boolean B){return!B;}},new a(){public boolean b(boolean a,boolean B){return B?a:true;}},new a(){public boolean b(boolean a,boolean B){return!a;}},new a(){public boolean b(boolean a,boolean B){return a?B:true;}},new a(){public boolean b(boolean a,boolean B){return!a|!B;}},new a(){public boolean b(boolean a,boolean B){return 1>0;}}};boolean b(boolean B,boolean c);}

Am I seriously supposed to state that a method that overrides an interface method is public?

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.

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

05AB1E, 31 27 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    +0Q        # (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

TI-Basic, 108 bytes

*Could be 66 bytes if Input : is accepted versus Prompt P,Q: and then P and Q would be X and Y.

0000 false            1 0
0001 p and q          7 Prompt P,Q:PQ
0010 p and not q      8 Prompt P,Q:Pnot(Q
0011 p                6 Prompt P,Q:P
0100 not p and q      8 Prompt P,Q:Qnot(P
0101 q                6 Prompt P,Q:Q
0110 xor              8 Prompt P,Q:P-Q
0111 p or q           8 Prompt P,Q:P+Q
1000 not p and not q  9 Prompt P,Q:not(P+Q
1001 eq               8 Prompt P,Q:P=Q
1010 not q            7 Prompt P,Q:not(Q
1011 p or not q       8 Prompt P,Q:P≥Q
1100 not p            7 Prompt P,Q:not(P
1101 not p or q       8 Prompt P,Q:Q≤P
1110 not p or not q   8 Prompt P,Q:not(PQ
1111 true             1 1

Actually, 27 bytes

These programs take input as A\nB (with \n representing a newline), which leaves B on top of the stack, with A below.

é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)
^Y  (A xnor B: xor, boolean negate)
@XY (not B: discard A, boolean negate B)
>Y  (if B then A: greater-than, boolean negate)
XY  (not A: discard B, boolean negate)
<Y  (if A then B: less-than, boolean negate)
*Y  (A nand B: multiply, boolean negate)
é1  (true: clear stack, push 1)

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.

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.

IA-32 machine code, 67 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;
      48        dec eax;
      4a        dec edx;
      23 c2     and eax, edx;
      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  3b ca     cmp ecx, edx;
      0f 93 c0  setnc al;
      c3        ret;

1100  91        xchg eax, ecx;
      48        dec eax;
      c3        ret;

1101  3b d1     cmp edx, ecx;
      0f 93 c0  setnc al;
      c3        ret;

1110  85 ca     test ecx, edx;
      0f 94 c0  setz al;
      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.

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

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!

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!

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

CJam, 25 24 23

These can all be used as function bodies which will take the top two values on the stack as inputs. 0 is false and 1 is true. Output is left as the top value on the stack.

0  "false";
&  "bitwise and";
>  "greater than";
;  "pop top element on stack";
<  "less than";
\; "swap top two elements and pop A";
^  "bitwise xor";
|  "bitwise or";
|! "bitwise or, then not";
=  "equality";
\;! "swap top two elements, pop A and return not B";
# "exponent - only returns false if A is false and B is true";
;! "pop B and not A";
>! "greater than, not - only returns false if A is true and B is false";
&! "nand";
1  "true;

Note that the first and last 'functions' will leave the input on the stack if used as functions, but can also be used as complete programs.