In the first class, I talked very vaguely about the notion of semantic truth, where the truth of a statement was defined relative to some set of experiences or observations and whether or not our new statement contradicted any of those. We now have the background knowledge to make this idea that I handwaved about more concrete.
Definition 6.1. Let $\Sigma$ denote a set of well-formed formulas. We say that a truth valuation $t$ satisfies $\Sigma$ if for every $\varphi \in \Sigma$, we have $\varphi^t = T$. In other words, a set $\Sigma$ is satisfiable if and only if there is some valuation $t$ such that $\Sigma^t = T$.
Example 6.2. Let $\Sigma = \{((p \rightarrow q) \vee r), ((p \vee q) \vee s)\}$. We will show that $\Sigma$ is satisfiable. Let $t$ be a valuation with $t(q) = T$. Then $(p \rightarrow q)^t = T$ and therefore $((p \rightarrow q) \vee r)^t = T$. We also have $(p \vee q)^t = T$ and therefore $((p \vee q) \vee s)^t = T$. Therefore, $t$ satsifies $\Sigma$.
Alternatively, we could have written up the truth table for both formulas and tried to find a row where both formulas evaluated to true. We can take the same approach to show that $\Sigma$ is not satisfiable. In that case, we can either argue or come up with a truth table to show that no valuation will satisfy $\Sigma$.
The notion of satisfiability seems pretty simple. After all, we just have to check the satisfiability of a bunch of formulas instead of just one. However, this will be important for the following notion.
Definition 6.3. Let $\Sigma$ be a set of well-formed formulas and let $\varphi$ be a well-formed formula. We say that $\Sigma$ (semantically) entails $\varphi$ if whenever $\Sigma^t = T$ for some truth valuation $t$, it follows that $\varphi^t = T$. Here, we call $\Sigma$ the premises and $\varphi$ the conclusion and we denote entailment by $\Sigma \vDash \varphi$.
I mentioned previously that a valuation can also be called a model. Similarly, here we can say that $\Sigma$ models $\varphi$.
But here, we can see what it means for $\varphi$ to be "true" in the sense that I alluded to back in the very first lecture. We can take $\Sigma$ to be our "model" or what we know to be "true". Then $\varphi$ is "true" if it is true whenever $\Sigma$ is true. This gives us a few ways to prove an entailment $\Sigma \vDash \varphi$ holds.
This means that $\varphi$ isn't true if it contradicts $\Sigma$. In other words, if there is a valuation that makes $\Sigma$ true but $\varphi$ false, then the entailment does not hold.
Example 6.4. We will show that $\{(\neg(p \wedge q)), (p \rightarrow q)\} \models (\neg p).$ Consider the following truth table.
| $p$ | $q$ | $(\neg(p \wedge q))$ | $(p \rightarrow q)$ | $(\neg p)$ | |
|---|---|---|---|---|---|
| T | T | F | T | F | |
| T | F | T | F | F | |
| F | T | T | T | T | |
| F | F | T | T | T |
Observe that for every valuation where $\{(\neg(p \wedge q)),(p \rightarrow q)\}$ is satisfied, $(\neg p)$ is also true. Therefore, $\{(\neg(p \wedge q)), (p \rightarrow q)\} \models (\neg p)$.
From this, we can also show that $\{(\neg(p \wedge q)), (p \rightarrow q)\} \not\models (q \rightarrow p)$. To see this, observe that for $t(p) = F,t(q) = T$, we have $\{(\neg(p \wedge q)),(p \rightarrow q)\}$ satisfied, but $(q \rightarrow p)^t = F$.
Example 6.5. We will show that $\{(p \rightarrow q),(q \rightarrow r)\} \models (p \rightarrow r)$. We will prove this by contradiction. Assume that the entailment does not hold. This means there exists a valuation $t$ such that $(p \rightarrow q)^t = T$, $(q \rightarrow r)^t = T$, and $(p \rightarrow r)^t = F$.
Since $(p \rightarrow r)^t = F$, we must have $t(p) = T$ and $t(r) = F$. Then since $(p \rightarrow q)^t = T$, we must have $t(q) = T$. However, since $(q \rightarrow r)^t = T$ and $t(r) = F$, we must have $t(q) = F$, which is a contradiction. Therefore, our assumption was false and the entailment holds.
This all seems fairly straightforward, until we get to some less obvious entailments. One easy way to keep track of what entailment means is to think of it like an implication: If $\Sigma$ is satisfied under $t$, then $\varphi$ is satisfied under $t$.
For instance, what happens when we take $\Sigma = \emptyset$? What does it mean for $\varphi$ if $\emptyset \models \varphi$ holds? Here, we have to start thinking carefully about the definitions of satisfaction and entailment. If satisfaction means that every formula in $\emptyset$ is satisfied under a valuation $t$, then when is $\emptyset$ satisfied? It turns out that under our definitions, $\emptyset$ is satisfied by every valuation $t$. Then this must mean that $\varphi$ is also satisfied under every valuation $t$, which makes $\varphi$ a tautology. Philosophically speaking, we can think of a tautology as some kind of universal truth (or, if valuations are parallel universes, a truth that spans every universe).
We can ask a similar question about contradictions: If $\varphi$ is a contradiction and we have an entailment $\Sigma \models \varphi$, what does this say about $\varphi$? Again, we have to think through our definitions. If it is the case that $\Sigma \models \varphi$ and $\varphi$ is never satisfied, then $\Sigma$ can never be satisfied either. In a sense, $\Sigma$ contains a contradiction (though not necessarily contained in one formula like we've been working with so far). Again, there is an interesting philosophical interpretation, which is: what happens when your universe contains a contradiction? According to the idea of semantic entailment, it means anything and everything could be true.
Now, we've been working in the world of semantics where things have meaning and we can use our intuition to come up with logical equivalences. However, it's time to get pulled back into the cold, mechanical world of syntax and answer a question I've been alluding to since the beginning of the course: how can we prove to ourselves that our understanding of truth is valid?
Let's revisit the idea of proof. By now, we're familiar with the idea of proving things, as we've been doing in this class and as you've had to do in various math courses. But what is a proof? One classic answer is due to the Rt. Hon. Jean Chrétien, 20th Prime Minister of Canada:
A proof is a proof. What kind of a proof? It's a proof. A proof is a proof, and when you have a good proof, it's because it's proven.
As I've mentioned before, as far as we're currently concerned, proof has nothing to do with any notion of truth. It is simply a mechanical manipulation of formulas according to a given set of rules. We call this set of rules a proof system. Proof systems are formalizations of notions of proof.
Definition 6.6. A proof is a sequence of formulas, beginning with a set of formulas $\Sigma$ called the premises, a sequence of transformations of formulas based on a set of inference rules, and ending with a formula $\varphi$ called the conclusion. We write $\Sigma \vdash \varphi$ if we can find a proof that begins with $\Sigma$ and ends with $\varphi$. We say $\Sigma$ proves $\varphi$ or $\Sigma$ yields $\varphi$.
Inference rules are rules of the form $$\frac{\alpha_1 \quad \alpha_2 \quad \cdots \quad \alpha_n}{\beta}$$ where $\alpha_1, \alpha_2, \dots, \alpha_n, \beta$ are formulas. According to this rule, we may infer $\beta$ if $\alpha_1, \dots, \alpha_n$ have appeared previously before. You'll see a lot more of these types of rules if you ever get into programming language theory and type theory and take CS 442. Keep in mind that such rules are purely syntactic. It may be tempting, but we need to resist the urge to read meaning into these rules, especially since there will be some rules that may not quite conform to our understanding of semantics.
Now, the notation that we use for "proves" looks suspiciously like the notation that we use for "entails". The obvious question is how are these two things related? And in fact, this is a much more formal way of putting the questions that I asked at the beginning of the course.
First, we should note that I mentioned that there are proof systems. In this course, we will be using the proof system called natural deduction. This means that we will be concerned with the above questions regarding proof with respect to natural deduction only. Of course, we can always ask the same questions for other proof systems.
Natural deduction was proposed by Gerhard Gentzen in 1934. He was primarily interested in proofs for number theory. The idea behind natural deduction is that it is intended to resemble how mathematicians think about proof. This is in contrast to Frege's system, which I mentioned before. We call those kinds of proof systems Hilbert systems, after David Hilbert. The problem with Hilbert systems (for us and Gentzen, at least; it was clearly quite popular with logicians at the time) was that it only used two connectives: $\neg, \rightarrow$. As we saw earlier, it is definitely possible to express any formula you wish with only those two connectives. Another proof system that is sometimes taught in other offerings of CS 245 is resolution, which is used in automated theorem proving and the rules are geared towards that purpose.
Generally speaking, there are two broad types of rules. If $\square$ is a connective, then we have
Conjunction has one introduction rule and two elimination rules. If we have $\alpha$ and $\beta$, we can conclude $(\alpha \wedge \beta)$: $$\frac{\alpha \quad \beta}{(\alpha \wedge \beta)}\wedge\!i$$ Then, if we have $\alpha \wedge \beta$, we can eliminate either side: $$\frac{(\alpha \wedge \beta)}{\alpha}\wedge\!e \quad \frac{(\alpha \wedge \beta)}{\beta}\wedge\!e$$
This is enough to let us see a simple example of a proof for the commutativity of $\wedge$.
Example 6.7. We will show $\{(p \wedge q)\} \vdash (q \wedge p)$.
| 1 | $(p \wedge q)$ | premise |
| 2 | $p$ | $\wedge e$ 1 |
| 3 | $q$ | $\wedge e$ 1 |
| 4 | $(q \wedge p)$ | $\wedge i$ 3,2 |
Let's take note of a few things. First, inference rules can make use of any formula that has already been written down. The application of each rule refers to the lines it makes use of. Next, observe that because of this rule about using things that are already written down, we can write down any premises we're given for free at the very beginning. Finally, the final line of the proof must be the formula that we want to prove.
Let's take a look at another example.
Example 6.8. We will show $\{((p \wedge q) \wedge r)\} \vdash (q \wedge r)$.
| 1 | $((p \wedge q) \wedge r)$ | premise |
| 2 | $(p \wedge q)$ | $\wedge e$ 1 |
| 3 | $r$ | $\wedge e$ 1 |
| 4 | $q$ | $\wedge e$ 2 |
| 5 | $(q \wedge r)$ | $\wedge i$ 4,3 |
Here, we make things a bit more complicated by putting the $q$ inside of a subformula. Observe that we need to follow the inference rules strictly: inference rules can only be applied to entire formulas. We cannot just extract the $q$ to use without first applying a rule that lets us acquire the subformula $(p \wedge q)$ as a formula.