Truth values and boolean functions
From Learning Logic for Computer Science
Contents
Truth values
From a very simple perspective, a statement can be true or false. These are the two truth values one works with in propositional and first-order logic.
For simplicity, false is identified with the natural number \(0\), true with the natural number \(1\).
Boolean functions
Boolean functions are functions that map truth values or tuples of truth values to truth values. More precisely, an \(n\)-ary boolean function is a function \(\{0,1\}^n \to \{0,1\}\). The name is due to George Boole, who was the first to take an algebraic approach to logic.[1]
Nullary boolean functions
Since there are exactly two truth values, there are two nullary boolean functions.
Unary boolean functions
Besides the two constant unary boolean functions and the identity function, there is only one more unary function, the function neg, which inverts each truth value: \(\text{neg} \colon \{0,1\} \to \{0,1\}\) is defined by \(\text{neg}(b) = 1 - b\) for every \(b \in \{0,1\}\).
Binary boolean functions
In total, there are \(2^4\) different functions. Some of them are used fairly often:
| \(x_0\) | \(x_1\) | \(\text{or}(x_0, x_1)\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
| \(x_0\) | \(x_1\) | \(\text{and}(x_0, x_1)\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
| \(x_0\) | \(x_1\) | \(\text{nor}(x_0, x_1)\) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
| \(x_0\) | \(x_1\) | \(\text{nand}(x_0, x_1)\) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
| \(x_0\) | \(x_1\) | \(\text{cond}(x_0, x_1)\) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
| \(x_0\) | \(x_1\) | \(\text{bicond}(x_0, x_1)\) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
| \(x_0\) | \(x_1\) | \(\text{xor}(x_0, x_1)\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Boolean functions with any number of arguments
Some of the binary boolean functions are extended to variable arity, that is, they have a multiple arity:
- \(\text{And}(x_0, \dots, x_{n-1}) = 1\) iff \(x_0 = x_1 = \dots = x_{n-1} = 1\). In particular, \(\text{And}() = 1\).
- \(\text{Or}(x_0, \dots, x_{n-1}) = 0\) iff \(x_0 = x_1 = \dots = x_{n-1} = 0\). In particular, \(\text{Or}() = 0\).
- \(\text{Xor}(x_0, \dots, x_{n-1}) = 1\) iff there exists some \(i<n\) such that \(x_i = 1\) and \(x_j = 0\) for all \(j<n\) with \(j \neq i\). In particular, \(\text{Xor}() = 0\).
- \(\text{Parity}(x_0, \dots, x_{n-1}) = 1\) iff the number of \(i < n\) such that \(x_i = 1\) is odd. In particular, \(\text{Parity}() = 0\).