A function {,1}^{k}→{0,1}. Being a *function*, a logical operation depends *only* on the truth values of its inputs (and not, say, on context). See material implication for some, uhmm, immaterial implications of this.

There are 2^{2k} different logical operations with k inputs. To see this, note that the truth table of the logical operation has 2^{k} rows, and in each row we can pick one of 2 outputs.

There are 2^{20}=2 logical "operations" with no inputs; these are called the constants 0 and 1.

There are 2^{21}=4 logical operations with 1 input: these are X, ~X, 0 and 1.

There are 2^{22}=16 logical operations with 2 inputs. We can read them off by examining the binary representations of 0..15, using them to fill in the rows of a truth table. For instance, 13 gives

X Y X@Y
1 1 1
1 0 1
0 1 0
0 0 1

Here is the complete list ordered by this binary representation. Note the pleasing (albeit expected)

symmetry between the first & second halves; other symmetries are out there, too.

- 0000: the constant 0
- 0001: X NOR Y
- 0010: ~(Y->X)
- 0011: ~X
- 0100: ~(X→Y)
- 0101: ~Y
- 0110: X XOR Y
- 0111: X NAND Y
- 1000: X AND Y
- 1001: X = Y (or ~(X XOR Y))
- 1010: Y
- 1011: X→Y
- 1100: X
- 1101: Y→X
- 1110: X OR Y
- 1111: the constant 1