Lecture 1: Boolean Functions

Boolean values

There are two Boolean values, TRUE and FALSE. For convenience, we will denote these values as \(1\) and \(0\). Boolean values are often also called bits. We will use Boolean values to encode information.

Basic Boolean operations

Basic Boolean operations are functions that take one or two Boolean values as input and output a Boolean value. We will focus the following operations:

\[ {\mathrm{\scriptstyle NOT}}(x) := \begin{cases} 1 & \text{ if $x=1$,}\\ 0 & \text{ otherwise.} \end{cases} \] \[ {\mathrm{\scriptstyle AND}}(x,y) := \begin{cases} 1 & \text{ if $x=1$ and $y=1$,}\\ 0 & \text{ otherwise.} \end{cases} \] \[ {\mathrm{\scriptstyle OR}}(x,y) := \begin{cases} 1 & \text{ if $x=1$ or $y=1$,}\\ 0 & \text{ otherwise.} \end{cases} \] The following notation is common: \[ \neg x \text{ for } {\mathrm{\scriptstyle NOT}}(x),\] \[ x \land y \text{ for } {\mathrm{\scriptstyle AND}}(x,y),\] \[ x \lor y \text{ for } {\mathrm{\scriptstyle OR}}(x,y).\]

Truth table

We can represent the Boolean operations NOT, AND, OR by the following truth table.

\[ \begin{array}{ll|ccc} x & y & {\mathrm{\scriptstyle NOT}}(x) & {\mathrm{\scriptstyle AND}}(x,y) & {\mathrm{\scriptstyle OR}}(x,y) \\ \hline 0 & 0 & 1 & 0 & 0\\ 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 & 1 \\ \end{array} \]

De Morgan’s Laws

There are redundancies among the operations NOT, AND, OR. In particular, we can write AND in terms of NOT, OR. Similarly, OR can be expressed in terms of NOT, AND. \[ \neg (x\land y) = \neg x \lor \neg y, \] \[ \neg (x\lor y) = \neg x \land \neg y. \] We can check that these identities hold by looking at the above truth table.

Boolean functions

An \(n\)-bit Boolean function \(f\) is a function that take \(n\) Boolean values as input and outputs a Boolean value, i.e., \[ f{\colon}\{0,1\}^n \to \{0,1\} .\]

Boolean function can express interesting algorithmic questions: \[ {\mathrm{\scriptstyle PRIMES}}_n(x) := \begin{cases} 1 & \text{ if $x$ is (the binary encoding of) a prime number,}\\ 0 &\text{ otherwise}. \end{cases} \] \[ {\mathrm{\scriptstyle RIEMANN}}_n(x) := \begin{cases} 1 & \text{ if $x$ is (the binary encoding of) a proof of the Riemann hypothesis},\\ 0 & \text{ otherwise.} \end{cases} \] (The Riemann hypothesis is an important open question in mathematics. If you resolve the hypothesis, you get a Millennium Prize.)

We will try to understand whether these kind of functions can be expressed by a small number of basic Boolean operations. (It turns out that both functions above can be expressed by a number of basic Boolean operations that is polynomial in \(n\).)