logical operation (thing)

A function {0,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²⁰=2 logical "operations" with no inputs; these are called the constants 0 and 1.

There are 2²¹=4 logical operations with 1 input: these are X, ~X, 0 and 1.

There are 2²²=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.

0. 0000: the constant 0
1. 0001: X NOR Y
2. 0010: ~(Y->X)
3. 0011: ~X
4. 0100: ~(X→Y)
5. 0101: ~Y
6. 0110: X XOR Y
7. 0111: X NAND Y
8. 1000: X AND Y
9. 1001: X = Y (or ~(X XOR Y))
10. 1010: Y
11. 1011: X→Y
12. 1100: X
13. 1101: Y→X
14. 1110: X OR Y
15. 1111: the constant 1