Up to now, we've been stressing that all we're doing is looking at the syntactic structure of logical statements. Indeed, our translations from English to propositional logic were very rule-based and our theorems and proofs were about the structure of well-formed formulas. The idea of the separation between syntax and semantics was first due to Gottlob Frege in 1879, who was motivated to construct a logical system to formalize the notion of mathematical proof. His hope was, in a sense, to remove the notion of intuition from mathematical proof. We'll see a bit more later on how such a proof system might work, but for now, we'll finally begin to impart some meaning onto formulas and begin talking about truth in the semantic sense.
Definition 4.1. A truth valuation (or simply, valuation) is a function $t : \mathcal P \to \{F,T\}$ from the set of propositional variables $\mathcal P$ to the set $\{F,T\}$. A truth valuation $t$ assigns a value of either $F$ or $T$ to every propositional variable in $\mathcal P$.
Suppose we have a truth valuation $t$.
A valuation is also called an interpretation or a model. Philosophically, these terms imply some observation or experience. In other words, we can see valuations as a description of our universe. Then what can be considered an alternative valuation? If we're talking about two different interpretations, that's easy to explain, but what if we want to consider an alternative valuation for something like a physical constant. In this case, we simply view alternative valuations as an entirely different universe. From this perspective, the structure and meaning of logical statements doesn't change, but the semantics which model our understanding of the world do.
For instance, by mixing two classic idioms together, we get a perfectly valid logical statement "If pigs fly, then I will eat my hat". This statement is logically valid in every possible universe and it's a perfectly fine argument. However, whether this statement models something true will depend on whether or not pigs fly and whether or not I made good on my threat to eat my hat in our particular universe.
Now, observe that the valuation $t$ is a function from propositional variables to truth values. We haven't yet defined how to interpret the connectives under a valuation, even though our definition of valuations implies this. If we were being more careful and more formal about how we define the semantics of propositional logic, we would explicitly define a meaning function that tells us exactly how to interpret each connective. However, you may already be familiar with the notion of truth tables, so instead, we will "define" the meaning of each connective via its truth table under a particular valuation $t$.
Definition 4.2. First, we'll consider the unary connective $\neg$.
| $\varphi$ | $(\neg \varphi)$ |
|---|---|
| $T$ | $F$ |
| $F$ | $T$ |
As expected, negation negates the truth value of the formula it is acting upon. Next, we consider the three binary connectives.
| $\alpha$ | $\beta$ | $\quad$ | $(\alpha \wedge \beta)$ | $(\alpha \vee \beta)$ | $(\alpha \rightarrow \beta)$ |
|---|---|---|---|---|---|
| $F$ | $F$ | $F$ | $F$ | $T$ | |
| $F$ | $T$ | $F$ | $T$ | $T$ | |
| $T$ | $F$ | $F$ | $T$ | $F$ | |
| $T$ | $T$ | $T$ | $T$ | $T$ |
Note that a particular valuation corresponds to a single row in the truth table. Also observe that the meaning of the connectives doesn't change depending on a particular valuation, which is why it would be more "correct" to separate the meaning of the connectives from the notion of a valuation.
Example 4.3. Now that we know how to interpret the connectives in a formula, we can build truth tables to evaluate them. Let's consider the formula $((\neg p) \rightarrow (q \wedge r))$.
| $p$ | $q$ | $r$ | $\quad$ | $(\neg p)$ | $(q \wedge r)$ | $((\neg p) \rightarrow (q \wedge r))$ |
|---|---|---|---|---|---|---|
| $T$ | $T$ | $T$ | $F$ | $T$ | $T$ | |
| $T$ | $T$ | $F$ | $F$ | $F$ | $T$ | |
| $T$ | $F$ | $T$ | $F$ | $F$ | $T$ | |
| $T$ | $F$ | $F$ | $F$ | $F$ | $T$ | |
| $F$ | $T$ | $T$ | $T$ | $T$ | $T$ | |
| $F$ | $T$ | $F$ | $T$ | $F$ | $F$ | |
| $F$ | $F$ | $T$ | $T$ | $F$ | $F$ | |
| $F$ | $F$ | $F$ | $T$ | $F$ | $F$ |
We can prove things about the semantics of propostitional formulas as well. For instance, we would like to know for sure that a formula under a valuation $t$ will always result in an evaluation of either $T$ or $F$.
Theorem 4.4. Let $t : \mathcal P \to \{T,F\}$ be a valuation and let $\varphi$ be a well-formed formula. Then $\varphi^t \in \{F,T\}$.
Proof. We will show this via structural induction on $\varphi$.
Base case: $\varphi = p$ for some propositional variable $p \in \mathcal P$. Then $\varphi^t = t(p) \in \{F,T\}$, as desired.
Induction step: Let $\alpha$ and $\beta$ be well-formed formulas. For our induction hypothesis, we assume that $\alpha^t, \beta^t \in \{F,T\}$.
First, if $\varphi = (\neg \alpha)$ then, $$ \varphi^t = (\neg \alpha)^t = \begin{cases} F & \text{if $\alpha^t = T$,} \\ T & \text{if $\alpha^t = F$,} \end{cases} $$ and therefore $\varphi^t \in \{F,T\}$.
Next, if $\varphi = (\alpha \vee \beta)$, then, $$ \varphi^t = (\alpha \vee \beta)^t = \begin{cases} F & \text{if $\alpha^t = \beta^t = F$,} \\ T & \text{otherwise,} \end{cases} $$ and therefore $\varphi^t \in \{F,T\}$.
Next, if $\varphi = (\alpha \wedge \beta)$, then, $$ \varphi^t = (\alpha \wedge \beta)^t = \begin{cases} T & \text{if $\alpha^t = \beta^t = T$,} \\ F & \text{otherwise,} \end{cases} $$ and therefore $\varphi^t \in \{F,T\}$.
Finally, if $\varphi = (\alpha \rightarrow \beta)$, then, $$ \varphi^t = (\alpha \vee \beta)^t = \begin{cases} T & \text{if $\alpha^t = F$ or $\beta^t = T$,} \\ F & \text{otherwise,} \end{cases} $$ and therefore $\varphi^t \in \{F,T\}$.
Thus, by the principle of structural induction, $\varphi^t \in \{F,T\}$. $$\tag*{$\Box$}$$
Now, we would like to consider the possible outcomes of propositional formulas under various valuations. There are a few special cases, which we will define here.
Definition 4.5. A formula $\varphi$ is a tautology if for every valuation $t$, we have $\varphi^t = T$. A formula $\varphi$ is a contradiction if for every valuation $t$, we have $\varphi^t = F$. A formula $\varphi$ is satisfiable if there exists a valuation $t$ such that $\varphi^t = T$.
The formula $(p \vee (\neg p))$ is a classic example of a tautology, while the formula $(p \wedge (\neg p))$ is a classic example of a contradiction.
How do we determine whether a formula is a tautology, or a contradiction, or is satisfiable? One easy way is to look at its truth table.
Example 4.6. Let's consider the formula $((p \vee q) \vee ((\neg p) \wedge (\neg q)))$, which has the following truth table.
| $p$ | $q$ | $(p \vee q)$ | $((\neg p) \wedge (\neg q))$ | $((p \vee q) \vee ((\neg p) \wedge (\neg q)))$ |
|---|---|---|---|---|
| $T$ | $T$ | $T$ | $F$ | $T$ |
| $T$ | $F$ | $T$ | $F$ | $T$ |
| $F$ | $T$ | $T$ | $F$ | $T$ |
| $F$ | $F$ | $F$ | $T$ | $T$ |
Here, we can see in the final column that our formula evaluates to $T$ for every valuation. Therefore, it is a tautology. One can apply the definitions for satisfiable and contradiction similarly.
This seems like a pretty straightforward method, but there is a flaw: if our formula contains $n$ variables, then we have up to $2^n$ possible valuations to examine. Clearly, this approach becomes infeasible very quickly. So a natural follow-up question would be: is there a more efficient way of determining this?
This turns out to be the literal million dollar question known as the P vs. NP problem. Satisfiability of a boolean formula turns out to be the central problem in the class of NP-complete problems. At the moment, we have no known proofs for any algorithms that have a better running time than our brute-force method, but it hasn't been shown yet that none exist. The million dollars refers to the fact that it is one of the seven Millennium Prize Problems, the prize being $1 million USD.
However, there are strategies other than constructing an entire truth table. One such method is to partially evaluate an expression, setting one propositional variable at a time. For this to work, we need some ways to simplify formulas, based on partial valuations. One can verify these expressions via truth tables. \begin{align*} (\neg T) & \equiv F & (p \wedge T) & \equiv p & (p \vee T) & \equiv T & (p \rightarrow T) & \equiv T\\ (\neg F) & \equiv T & (p \wedge F) & \equiv F & (p \vee F) & \equiv p & (p \rightarrow F) & \equiv (\neg p)\\ & & (p \wedge p) & \equiv p & (p \vee p) & \equiv p & (T \rightarrow p) & \equiv p\\ & & & & & & (F \rightarrow p) & \equiv T\\ & & & & & & (p \rightarrow p) & \equiv T \end{align*}
Example 4.7. To see this in action, let's take a look at our example from above, the formula $((\neg p) \rightarrow (q \wedge r))$.
The result of this sort of reasoning results in the following tree structure.
Just as we can examine the truth table of a particular formula to determine whether it is a tautology, satisfiable, or a contradiction, for the valuation tree, we simply need to examine its leaves. Here, since there is a leaf that evaluates to $T$, we can conclude that our formula is satisfiable.
Now, it seems like this is a much more efficient way of checking the results of formulas without going through every valuation. However, it turns out that in the worst case, we may not do any better than constructing a truth table after all. In the worst case, we may need to explore every branch of the tree to the very end, which means we examine every possible valuation. The reason the valuation tree method can sometimes be faster is if we're lucky and happen to examine an assignment of a variable that rules out an entire branch early on.