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

## 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$$.