An instruction in which the quantity being operated on and the results of the operation can each have two values, following the rules of symbolic logic. Logical operations include AND, OR, NAND, XOR, and NOR.

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 22k different logical operations with k inputs. To see this, note that the truth table of the logical operation has 2k rows, and in each row we can pick one of 2 outputs.

There are 220=2 logical "operations" with no inputs; these are called the constants 0 and 1.

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

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

Log in or register to write something here or to contact authors.