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