SI242: Interpretation, and evaluation and truth tables intro

Interpretations and Evaluation

Continuing our analogy to algebra, you should expect that we will want to take a formua, assign values to its variables, and evaluate the formula. And, indeed, that's what we will look at next.

An assignment of true/false values to the propositional variables in a formula is called an interpretation. We often represent an interpretation as a function that maps variables to their true/false values under the interpretation.

Interpretation is an important concept that we will be revisiting frequently. The name comes from the following kind of thinking: Let $F$ be the formula $b \Rightarrow c$. If we think of the meanings of $b$ and $c$ as being $b:=$"I am eating lima beans" and $c:=$"hell has frozen over", then "I am eating lima beans" is false (thankfully!) and (to the best of my knowledge) "hell has frozen over" is false, so we get the "interpretation" $(b,c)=(false,false)$. On the other hand, if we think of the meanings of $b$ and $c$ as being $b:=$"tennis is better than pickel ball" and $c:=$"pickel ball is cool", we get the "interpretation" $(b,c) = (true,false)$. So while "interpretation" technically is not about "meanings" of variables, just the true/false values we assign them, the motivation or history of the term comes from attaching meanings to variables.

The most fundamental thing we do with formulas is evaluate them for a given interpretation. Operationally, the easiest way to think about evaluation is to take the expression tree for the formula in question, annotate the variable nodes with the true/false value they get in the interpretation, and then work your way up the tree annotating each non-variable node with value you get by applying the operator at that node to the true/false values from the node's children.

example of evaluation
Evaluating $a \oplus b \Rightarrow \neg c$ under the interpretation $(a,b,c)=$(true,false,true).

ACTIVITY

Evaluate $a \oplus b \Rightarrow \neg a$ under the interpretation $a=false,b=true$.
Evaluate $\neg(a \vee b) \wedge (c \vee b)$ under the interpretation $a=false,b=false,c=true$.
Find an interpretation under which ¬a⇒b⇒b evaluates to false.

A formal definition of evaluation

Hopefully the process for evaluating a formula is intuitive. However, if we want to prove things about evaluation we ought to be able to give a formal definition to evaluation. The key to doing this is to realize that, by the definition of propositional formula, a formula $F$ comes in only three possible forms: 1) a variable, 2) $\neg(A)$ for formula $A$, or 3) $(A)\mbox{op}(B)$ for formulas $A$ and $B$. So to completely define what "evaluation" means, we need only specify what to do in each of these cases.

Let $F$ be a propositional formula in the variables $x_1,\ldots,x_n$, and let $I$ be an interpretation (i.e. $I:=\{x_1=b_1,\ldots,x_n=b_n\}$, where "$b_j$" is the true/false value $x_j$ has been assigned). The evaluation of $F$ under $I$, denoted $eval(F,I)$ is

if $F$ is the variable $x_j$, then the evaluation is $b_j$
if $F$ is $\neg(A)$, then the evaluation is $\neg z$, where $z = eval(A,I)$
if $F$ is $(A)\mbox{op}(B)$, then the evaluation is $y\ \mbox{op}\ z$, where $y = eval(A,I)$ and $z = eval(B,I)$
$F$ can't be anything else!

Note: The variables $x_1,x_2,\ldots,x_n$ and the variables $y$ and $z$ are all regular old propositional variables - i.e. variables that take on true/false values. There are the subscripts on the "$x_i$" variables and we use the "..."s because the definition needs to make sense for formulas with any number of variables. If $F$ has two variables the definition needs to fit that. If $F$ has 2,000 variables the definition needs to fit that too. So we use $n$ to represent the number of variables in $F$, and call those variables $x_1, x_2,\ldots, x_n$. Variables $y$ and $z$ are just temporary variables we use to denote the result of sub-problems we solve during the evaluation process. The $b_1, b_2, \ldots b_n$ are a bit different. They are just names we give to the constant true/false values each $x_i$ variable is assigned during the process.

Hopefully you see that this definition is, in fact, a description of more or less the process you were going through informally before. It shows why we evaluate the tree from the bottom up: because to evaluate $\neg(...)$, for example, we first have to have evaluated the "$(...)$" part which, in the expression tree, would be the stuff below the $\neg$ node. This definition is, in fact, an algorithm for evaluation.

Example: Evaluate $F := (x_1) \oplus (\neg(x_2))$ under interpretation $I:=\{x_1=\underbrace{true}_{b_1},x_2=\underbrace{false}_{b_2}\}$ by following the defintion.
Since $F$ is an $\oplus$ of two things, we are in the Rule 3 case. So we evaluate the left side, $(x_1)$, and call the result $y$. $$y=\text{eval}(x_1,I) = true$$ Then we evaluate the left side,$(\neg(x_2))$, and call the result $z$. $$z=\text{eval}(~(x_2),I) =true$$ Finally, we return $y\oplus z$: $$ y\oplus z = true \oplus true = false. $$ If we connect this back to the tree, this means we evaluated the left child of the $\oplus$ node, then the right child, and only then did we get the result for the $\oplus$ node itself. This is our bottom-up evaluation of the expression tree!

Connecting propositional formulas and boolean functions: Truth tables! [We will push this into next week.]

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$

Important: Truth tables are kind of a big deal!