Complex formulas

We are now in the position to give truth-values to our more complex formulas, based on the values of the atomic formulas. Again, everything is relativized to a certain structure, since that is how we can assign truth-values to the atomic ones.

In particular, this is done by invoking the concept of a truth-function. A truth-function is just a function that takes one or more truth-values, and outputs a single truth-value. The meaning of our connectives are truth-functions in this sense. They operate on the values of their constituent formulas, and output another truth-value.

There are several ways to formulate this idea. First, one may specify these truth-values in terms of truth ($T$) and falsity ($F$), and a function $v: \mathsf{FORM}_{\mathcal{L}_0} \to \{T, F\}$ for any formula $X$, $Y$, like this:

1. $v(\neg X)=T$ if, and only if, $v(X)=F$;

2. $v(X \wedge Y)=T$ if, and only if, $v(X)=T$ and $v(Y)=T$;

3. $v(X \vee Y)=T$ if, and only if, $v(X)=T$ or $v(Y)=T$ (or both);

4. $v(X \rightarrow Y)=T$ if, and only if, if $v(X)=T$, then $v(Y)=T$.

Now usually, these are represented in truth-tables, which are really just tables representing the above truth-function, $v$, by listing all its input-output pairs one by one. In particular:

You should read these as follows: in any structure $\mathbf{S}$, if $X$ is true in $\mathbf{S}$ and $Y$ is true in $\mathbf{S}$, then $X \wedge Y$ is true in $\mathbf{S}$. If $X$ is true in $\mathbf{S}$ and $Y$ is false in $\mathbf{S}$, then $X \wedge Y$ is is false in $\mathbf{S}$, and so on, for each line of each truth-table.

There are other ways to specify these same truth-functions. One is to arithmetize the relation between the input(s) and the output using $1$ for true and $0$ for false. This looks nice for some connectives, but less nice for others. Thus:

1. $v'(\neg X)=1-v'(X)$;

2. $v'(X \wedge Y)=v'(X)\times v'(Y)=\text{MAX}(v'(X),v'(Y))$;

3. $v'(X \vee Y)=1-((1-v'(X)) \times (1-v'(Y)))=\text{MIN}(v'(X), v'(Y))$;

4. $v'(X \rightarrow Y)=1 – (v'(X) \times (1-v'(Y))$.

We can check if the four tables in Figure 4.2 match our tables in Figure 4.1 by computing the right side with our equations. And indeed, they do match!

Finally, we can put the above ideas in line with our previous results, and specify it as such:

1. $\mathbf{S} \models \neg X$ if, and only if, $\mathbf{S} \not\models X$;

2. $\mathbf{S} \models (X \wedge Y)$ if, and only if, $\mathbf{S} \models X$ and $\mathbf{S}\models Y$;

3. $\mathbf{S} \models (X \vee Y)$ if, and only if, $\mathbf{S} \models X$ or $\mathbf{S}\models Y$ (or both);

4. $\mathbf{S} \models (X \rightarrow Y)$ if, and only if, if $\mathbf{S} \models X$, then $\mathbf{S} \models Y$.

Here is some helpful information as to how to read the above specifications. On the left hand side of the ‘if, and only if’ connective, you always find more complex formulas, while on the right hand side, you always find less complex formulas. Reading from left to right, you can determine what the truth-value of the less complex formula must be if the more complex formula is true. For example, $X$ must be false in a structure if $\neg X$ is true in that structure. Reading from right to left, you can determine the value of the more complex formula if the conditions on the right side hold for less complex ones. So if $X$ and $Y$ are both true in $\mathbf{S}$, $X \wedge Y$ will also be true.

It is important that these specifications allow one to determine both truth and falsity for any complex formula depending on the truth or falsity of some simpler formulas, and vice versa, though this may not be apparent at first.

Suppose $\mathbf{S} \not\models X \vee Y$, i.e., it is false in $\mathbf{S}$. Now it is specified what simpler formulas need to be true in order for $X \vee Y$ to be true. So how do we determine what needs to happen for it to be false in $\mathbf{S}$? Well, all we have to do is negate the right hand side, and see what’s left. In particular:

$\mathbf{S} \not\models X \vee Y$ if, and only if, it is not the case that [$\mathbf{S} \models X$ or $\mathbf{S}\models Y$ (or both)].

Now this states that $\mathbf{S} \not\models X \vee Y$ if neither $X$ nor $Y$ is true in $\mathbf{S}$, since all three other possibilities would make it true. And indeed, this is just what the truth-table says!

Similarly, but from the other way around, suppose $\mathbf{S} \not\models X$ and $\mathbf{S} \models Y$. Well, since $\mathbf{S} \models X \wedge Y$ if, and only if, $\mathbf{S} \models X$ and $\mathbf{S} \models Y$, we have:

$\mathbf{S} \not\models X \wedge Y$ if, and only if, it is not the case that [$\mathbf{S} \models X$ and $\mathbf{S} \models Y$].

If it is not the case that [$\mathbf{S} \models X$ and $\mathbf{S} \models Y$], then either $X$ or $Y$ or both are false in $\mathbf{S}$. So in particular, if $\mathbf{S} \not\models X$ and $\mathbf{S} \models Y$, then $\mathbf{S} \not\models X \wedge Y$.

One way to think about this is by simply noting that $\not\models$ is just the negation of $\models$. So if the definition specifies when something is modeled, then it will not be modeled precisely when that specification is not met. That is, once the left side of the biconditional is negated, the right side needs to be too. This is very much akin to multiplying by $-1$ in an equation. It is a very fundamental fact that goes for every biconditional; if you negate both sides of a true biconditional, you get a true biconditional.

From now on, we will be using this type of specification to talk about the values of complex formulas. At times, we may refer back to truth-tables as a helpful reference for those who already know how truth-tables work. Don’t worry if you are not familar with truth-tables. They do not give any more information than what can already be found in our style of specification.

Computing with complex formulas

Let’s turn back the wheel of time to the beginning of this book, where we specified the language of arithmetic expressions $\mathcal{L}_{AE}$. You may remember how we emphasized that the syntactic trees for those expressions give you an order of computation, based on how the parentheses are configured in the formula. If you forgot, go back to Part 1 to refresh your memory. In fact, the situation is the same with the expressions of $\mathcal{L}_0$, except instead of $+$, $–$ and $\times$, we have our connectives, and instead of numbers, we have atomic formulas which themselves require computation. And formulas are either true or false. But it’s the same.

Once again, take a structure $\mathbf{S}=\langle\mathbf{D}, I\rangle$ with the domain $\mathbf{D}=\{\mathbf{a}, \mathbf{b}, \mathbf{c}, \mathbf{d}\}$, and an interpretation function $I$ such that:

1. $I(a)=\mathbf{a}$, $I(b)=\mathbf{b}$, $I(c)=\mathbf{c}$;

2. 1. $I(P)=\{\mathbf{a}, \mathbf{d}\}$;

   2. $I(Q)=\{\langle\mathbf{a}, \mathbf{c}\rangle, \langle\mathbf{d}, \mathbf{a}\rangle, \langle\mathbf{a}, \mathbf{d}\rangle\}$;

   3. $I(R)=\{\langle\mathbf{a}, \mathbf{b}, \mathbf{c}\rangle, \langle\mathbf{b}, \mathbf{c}, \mathbf{b}\rangle, \langle\mathbf{b}, \mathbf{b}, \mathbf{b}\rangle\}$.

We already know a bunch about what truth-values various formulas get in the structure $\mathbf{S}$. Now, we can go on to talk about the values of more complex formulas, built out of our connectives.

Suppose you want to find out whether $(P(a) \vee P(c)) \wedge Q(a, c)$ is true in $\mathbf{S}$. Let’s quickly draw up a syntax tree for this formula:

As with the example regarding $\mathcal{L}_{AE}$, we start from the leaves of our tree (remember that it is upside down). Now in general, you would first have to compute whether $P(a)$, $P(c)$, and $Q(a, c)$ are true in $\mathbf{S}$, but we will not revisit this issue, since this was already done above.

We had the following facts:

1. $\mathbf{S} \models P(a)$;

2. $\mathbf{S} \not\models P(c)$;

3. $\mathbf{S} \models Q(a, c)$.

We can substitute these values for the relevant formulas in our tree. Thus:

Now given how the connective $\vee$ was defined above, we can compute from $T \vee F$ the value $T$, since $\mathbf{S} \models X \vee Y$ if $\mathbf{S} \models X$, even if $\mathbf{S} \not\models Y$. So we have:

Substituting again, we have: $$T \wedge T$$ Invoking the rule for the connective $\wedge$, we get $T$ as the final value, so $$\mathbf{S} \models (P(a) \vee P(c)) \wedge Q(a, c).$$

Note that this is a handy way to compute the values of formulas, but you should not confuse things like $T \vee F$ for formulas of the language, since they are not. In general, what we are doing in this computation is systematically replacing our formulas with their values in $\mathbf{S}$. In other words, it is just a compact representation of something more verbose (see immediately below).

There are several ways of going about computing the values of formulas. In presentation, it may look something like this:

Take the formula $(P(a) \vee P(c)) \wedge Q(a, c)$. By our previous results, $\mathbf{S} \models P(a)$, $\mathbf{S} \not\models P(c)$, and $\mathbf{S}\models Q(a, c)$. By definition of $\vee$, $\mathbf{S} \models P(a) \vee P(c)$, since $\mathbf{S} \models P(a)$. Then, by definition of $\wedge$, $\mathbf{S} \models (P(a) \vee P(c)) \wedge Q(a, c)$, since $\mathbf{S} \models P(a) \vee P(c)$, and $\mathbf{S} \models Q(a,c)$. This is what we wanted to show.

In fact, if you really want to go wild, you can use the equations above, and produce something like this: $$(1 -((1-1) \times (1-0))) \times 1=1$$

Now $1-1=0$, $1-0=1$, so we get $0 \times 1$, which is $0$, which we subtract from $1$, which gets us $1$, which we multiply by $1$ to get $1$. Or true.

This is not a thing we will be doing going further.

Computing from formulas up

We do not always have to consider how exactly the atomic formulas are specified in each case. Instead, we can talk more abstractly about assigning some truth-value to some specific formula $X$ of the language, and some other truth-value to some specific formula $Y$ of the language (and so on), and then see what truth-values one gets in a structure if we combine them in various ways. Indeed, doing this is equivalent to doing propositional or sentential logic, and specifically, drawing up more general truth-tables. Again, this you may already be familiar with.

For example, suppose $X$ is any formula, and $Y$ is any formula, and consider the formula $X \wedge \neg Y$. We do not know what these variables stand for (other than that they are formulas), so we cannot specify an exact structure for them, in which they may be true or false. But what we can do is assume that there is a certain structure in which, say $X$ is true and $Y$ is false, and then consider whether $X \wedge \neg Y$ is true or false as a result in a structure.

Actually, what we are considering here is not just one structure but many; all those in which $X$ is true and $Y$ is false (for each possible choice of formula for the variables $X$ and $Y$). But by abstracting away from the specifics, we do not need to worry about this.

Now the question is: is $X \wedge \neg Y$ true if $X$ is true and $Y$ is false in a structure? You might already see that in such a case, $X \wedge \neg Y$ is, in fact, true. Here is how it would go:

Suppose there is a structure $\mathbf{S}$ such that $\mathbf{S} \models X$ but $\mathbf{S} \not\models Y$. By the above definition, $\mathbf{S} \models \neg Y$ provided $\mathbf{S} \not\models Y$, so $\mathbf{S} \models \neg Y$. Then, again, by definition, $\mathbf{S} \models X \wedge \neg Y$, provided $\mathbf{S} \models X$ and $\mathbf{S} \models \neg Y$, which we already know, so $\mathbf{S} \models X \wedge \neg Y$

This reasoning is the exact same as the following vertical fragment of a generalized truth-table:

Putting it all together

We are now in the position to formulate our whole semantics in one fell swoop. This is usually done in more advanced works at the very beginning (or not at all). You shall now be able to read those definitions with confidence.

Congratulations, this concludes the semantics of $\mathcal{L}_0$.