Lesson 1

A truth table is one of the simplest and most natural ways to define a Boolean function. For example, to define a Boolean function \(f \in B_{3}\), it is enough to specify its values at all points.

For this toy example, the truth table of \(f\) is just the last column of the table above: \(\texttt{01010010}\). That is, the truth table of a function from \(B_{n}\) is just a bit string of length \(2^{n}\).

This way of defining is not always convenient. For example, when defining some condition in a program, we almost never use a truth table. Moreover, a truth table has \(2^{n}\) rows, which quickly becomes impractical as \(n\) grows. Below, we consider several other natural ways to define a Boolean function.