Connecting propositional formulas and boolean functions: Truth tables!

Recall our definition of "boolean functions": a function whose inputs are boolean-valued, and output is a boolean value.

Let $F$ be a propositional formula in the variables $x_1,\ldots,x_n$. The boolean function defined by $F$ is the function $f_F$ that maps $n$ boolean values to a single boolean value according to the rule $f_F(b_1,\ldots,b_n) = eval(F,\{x_1=b_1,\ldots,x_n=b_n\})$.

This means that whenever we have a formula, we can always think of it as a function. This connection is really important. One immediate result is this: we have already discussed that a boolean function can be competely described by a table (we called it the "truth table" for the function), since there are only a finite number of input combinations. So if we have a formula $F$, that motivates us to consider the truth table for $F$, i.e. the truth table for the boolean function $F$ defines. Here are some examples:

$F_1 := \neg(a \vee b)$ Truth table for $F_1$ $F_2 := a\wedge b \vee \neg a \wedge \neg b$ Truth table for $F_2$
$F_3 := a \oplus b \Rightarrow a$ Truth table for $F_3$ $F_4 := a \oplus b \Rightarrow (a\vee c)$ Truth table for $F_4$

ACTIVITY

  1. Write down the truth table for $(a \Rightarrow b) \Rightarrow a$.
  2. Write down the truth table for $a \oplus \neg(b \oplus c)$.
  3. Why would you refuse to write a truth table for $(a \wedge e \oplus \neg b \wedge c) \Rightarrow (b \oplus d \Leftrightarrow e)$?
  4. Given $F_1$ from above, write down an interpretation (assignment of values to variables) for which $F_1$ evaluates to true.
  5. Given $F_2$ from above, write down an interpretation (assignment of values to variables) for which $F_2$ evaluates to false.
  6. How many different assignments of values to variables are there for which $F_3$ evaluates to true?
  7. Given $F_4$ from above, write down an interpretation (assignment of values to variables) for which $\neg F_4$ evaluates to true.
  8. (This one is harder!) Let $f$ be the function defined by $F_4$, and let $g_1$ be the function defined by $x \wedge y$, let $g_2$ be the function defined by $x \oplus y$, and let $g_3$ be the function defined by $x \Rightarrow y$. Find values for $x$ and $y$ for which the function $f(g_1(x,y),g_2(x,y),g_3(x,y))$ returns false.
  9. Consider the boolean function G1 given by the following truth table: Find a propositional formula that defines G1.
  10. Consider the boolean function G2 given by the following truth table: Find a propositional formula that defines G2.
  11. There is a useful boolean function called "ite", which stands for "if-then-else". The way ite works is this: the value of ite(x,y,z) is y when x is true, and z when x is false. So, for example, $\text{ite}(\text{true,false,true}) = \text{false}$ because the first argument ("x") is true, so we return the second argument ("y"), which is false. On the other hand, $\text{ite}(\text{false,false,true}) = \text{true}$ because the first argument ("x") is false, so we return the third argument ("z"), which is true. Your job: Write the truth table for the ite function.

Important: Truth tables are kind of a big deal!

Connecting propositional formulas and boolean functions: defining formulas

We see from the previous section that every propositional formula defines a boolean function. The last few activity problems asked you to go the other direction: starting with a boolean function, it asked you to find a propositional formula that defines that function. It was possible for G1 and G2, but is it always possible? Can we do this for any boolen function?

If $f$ is a boolean function of $n$ inputs, then there is a propositional formula $F$ in the variables $x_1,\ldots,x_n$ such that $f_F$ is that function.
This theorem is a big deal! With this theorem and the definition from the previous section, we have the following:
Every propositional formula defines a boolean function, and every boolean function is defined by a propositional formula.
We shouldn't take this for granted! In other contexts, analogous statements are not true. For example, what about functions that take a single real number as input and produce a single real number as output? Is it true that each of these is defined by a formula? Perhaps we are given a function $f$ and it is indeed defined by a formula, like: $$ f(x) = 3x^2 - \sin(x -1) + e^{-x} $$ But do all functions with a single real input and a single real output have such formulas? The answer is "no"! So we should be excited that for boolean functions and propositional functions, the answer is "yes"!
This is our first non-trivial proof. There are aspects of this proof that will make more sense after a little more experience. None the less, we will present the proof here, and refer back to it as we learn more and can understand it better. One thing we will have to address is the question of what it means for two functions to actually be the same? You understand something of functions from years of high school and college math classes, but you may never have addressed this question. It is actually easy: two functions are the same if they have the same domains and, for any element from the domain, they produce the same outputs.

How could we go about convincing someone that for any boolean function, no matter how weird, there is always a propositional formula that defines that function? Well ... if I had a specific function in mind (like G1 from the previous activity), how would you prove to me that there is propositional formula that defines that function? You would produce such a formula, of course! What about G2? Same thing. So:

This suggests that what we really need is a process, an algorithm, that takes any boolean function and produces a propositional formula that defines that function, i.e. a formula that proves the theorem for that particular function. If we had such an algorithm (and we were confident that it worked!), we could be sure that for any boolean function anyone could ever dream up, there is indeed a propositional formula defining that function. After all, just run the algorithm.

helper function $l(\cdot,\cdot)$ helper function $c(\cdot)$
If $i$ is a number in the range $1,\ldots,n$, where the
function $f$ we are interested in has $n$ inputs, and
$b$ is a boolean value:

$l(i,b) = \left\{ \begin{array}{c,l} x_i & \mbox{if $b =$ true}\\ \neg x_i & \mbox{if $b =$ false}\\ \end{array} \right.$

If $r$ is row $\begin{array}{cccccc} x_1 & x_2 & \ldots & x_n & f &\\ \hline \vdots &\vdots & \vdots & \vdots &\\ b_1 & b_2 & \ldots & b_n & b \end{array} $ in the truth table for $f$ then:

$c(r) = l(1,b_1) \wedge l(2,b_2) \wedge \cdots \wedge l(n,b_n)$

Algorithm
Input: the truth table $T$ for boolean function $f$ with $n$ inputs
Output: a propositional formula $F$ in $x_1,\ldots,x_n$ that defines function $f$

  1. if all rows of $T$ have output value false, return $F := (x_1 \wedge \neg x_1)\wedge x_2 \wedge \cdots \wedge x_n$ ← this formula contains variables $x_1,\ldots,x_n$ and is false for all interpretations
  2. if $r_{i_1},r_{i_2},\ldots,r_{i_k}$ are the rows of $T$ that have output value true, return $F := c(r_{i_1}) \vee c(r_{i_2}) \vee \cdots \vee c(r_{i_k})$

Example: Let's try this algorithm out on an example. Suppose the input table $T$ is

Step 1 doesn't apply, so we go on to Step 2. The rows of $T$ that have output value true are row 1, row 3 and row 4. So ...
row 1: $c($ falsefalsetrue $) = \neg x_1 \wedge \neg x_2$.
row 3: $c($ truefalsetrue $) = x_1 \wedge \neg x_2$.
row 4: $c($ truetruetrue $) = x_1 \wedge x_2$.

and, finally, the output $c(r_{i_1}) \vee c(r_{i_2}) \vee \cdots \vee c(r_{i_k})$ is $F := (\neg x_1 \wedge \neg x_2) \vee (x_1 \wedge \neg x_2) \vee (x_1 \wedge x_2)$.

Hopefully what you see is that the formula literally says that the variable assignments have to match one of the truth table rows with a true output value.

To finish off this proof, we need to show that this algorithm always works, i.e. that the returned formula $F$ always defines the function $f$ whose truth table we gave as input. We will put that off and address it later. Hopefully, after our worked example, your intuition for why the algorithm works is pretty strong anyway.

It's important to note that formula produced by the algorithm from the Theorem is not the only formula defining the input function. There are many such formulas. In fact, the formula produced by the algorithm is seldom a very concise, simple or interesting defining formula. However, it's enough to show that a formula exists!

ACTIVITY

  1. Given a function $f$ with truth table

    write down the formula the algorithm from the proof would produce for $f$.
  2. Give a more concise defining formula for function $f$ from the previous problem.

Equivalent formulas

In the previous activity, you should have seen that $\neg x_1 \wedge x_2 \vee x_1 \wedge \neg x_2$ and $x_1 \oplus x_2$ both define the same boolean function $f$. In this sense, the two formulas are interchangable. Next we formalize this concept in the definition of equivalent formulas.

Formulas $F_1$ and $F_2$ are equivalent if, for every interpretation of the combined variables of $F_1$ and $F_2$, both formulas evaluate to the same thing.

Suppose that $F_1 := a \Rightarrow \neg b$ and $F_2 := b \Rightarrow \neg a$. We can prove whether they are the same for a given interpretation, say $a =$ false and $b =$ false, by evaluating them both, and checking that the answer is the same. This would be "proof by calculation", which we described earlier. To prove that $F_1$ an $F_2$ are equivalent, however, requires doing this for all possible interpretations. 
      a=false, b=false ... E1 is true, E2 is true ✓
      a=false, b=true  ... E1 is true, E2 is true ✓
      a=true, b=false  ... E1 is true, E2 is true ✓
      a=true, b=false  ... E1 is true, E2 is true ✓
      a=true, b=true   ... E1 is true, E2 is true ✓
This approach (i.e. explicitly & separately checking all possible cases of something) is called proof by exhaustion. Presumably you won't need me to explain why! Of course, another way of looking at this is to say that $F_1$ and $F_2$ are equivalent if their truth tables are the same.

Important! When proving a statement "X is Y", you have to look at the definition of Y and show that X satisfies all points of that definition. In this case the definition of "equivalent formulas" requires that "for each interpretation" the formulas "have the same values". We verified that is indeed the case by looking at all possible interpretations, so we are allowed to call $F_1$ and $F_2$ "equivalent".
Christopher W Brown