Day 1: semantic consequence \(\Gamma\models\varphi\). Day 2: logical equivalence and adequate sets of connectives. Day 3: deductions from assumptions and \(\Gamma\vdash\varphi\).
By the end of this week you will be able to:
Today we define when a formula follows from a set of formulas by truth alone. We learn how to decide this, and how to prove general facts about it from the definition.
| \(p\) | \(q\) | \(\neg p\) | \(p \wedge q\) | \(p \vee q\) | \(p \to q\) |
|---|---|---|---|---|---|
| T | T | F | T | T | T |
| T | F | F | F | T | F |
| F | T | T | F | T | T |
| F | F | T | F | F | T |
Last week we asked whether one formula is true under a valuation. In mathematics, and in everyday reasoning, we usually start from several assumptions at once. So we now look at sets of formulas.
Let \(\Gamma\) be a set of formulas. A valuation \(v\) satisfies \(\Gamma\) if \([\![\psi]\!]_v=\mathrm T\) for every \(\psi\in\Gamma\). The set \(\Gamma\) is satisfiable if some valuation satisfies it, and unsatisfiable otherwise.
An argument is good when its conclusion cannot be false while its premises are true. Valuations make the word "cannot" precise: there is no valuation that makes the premises true and the conclusion false.
Let \(\Gamma\) be a set of formulas and \(\varphi\) a formula. We say that \(\Gamma\) entails \(\varphi\), or that \(\varphi\) is a semantic consequence of \(\Gamma\), and write \(\Gamma\models\varphi\), if every valuation that satisfies \(\Gamma\) also makes \(\varphi\) true:
\[\Gamma\models\varphi\quad\text{iff}\quad\text{for every valuation }v:\ \text{if }v\text{ satisfies }\Gamma, \text{ then }[\![\varphi]\!]_v=\mathrm T.\]We write \(\Gamma\not\models\varphi\) if this fails. Then there is a valuation \(v\) that satisfies \(\Gamma\) with \([\![\varphi]\!]_v=\mathrm F\). Such a \(v\) is called a counterexample.
We use a few short forms. We write \(\psi_1,\dots,\psi_n\models\varphi\) for \(\{\psi_1,\dots,\psi_n\}\models\varphi\), and \(\Gamma,\psi\models\varphi\) for \(\Gamma\cup\{\psi\}\models\varphi\). For \(\Gamma=\varnothing\) we write \(\models\varphi\). This agrees with the notation for tautologies: every valuation satisfies \(\varnothing\), so \(\varnothing\models\varphi\) says that \([\![\varphi]\!]_v=\mathrm T\) for every \(v\).
Claim: \(p,\ p\to q\models q\). Here \(\Gamma=\{p,\ p\to q\}\). We build one table with a column for each formula of \(\Gamma\) and a column for the conclusion \(q\):
| \(p\) | \(q\) | \(p\) | \(p \to q\) | \(q\) |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | T | F | F |
| F | T | F | T | T |
| F | F | F | T | F |
Only the first row satisfies \(\Gamma\), and in this row \(q\) is \(\mathrm T\). So the claim holds. The other rows do not matter, whatever the value of \(q\) is there.
The search is usually faster, because \(\varphi=\mathrm F\) and the formulas of \(\Gamma\) force many values at once.
Forms (a) and (c) are valid patterns of reasoning. Forms (b) and (d) are common mistakes: each looks like a valid form, but a single valuation shows that it is not.
Self-check only. Nothing here counts towards your grade.
For each claim, choose whether it holds or fails. If it fails, also give a counterexample: a valuation that makes every formula on the left true and the formula on the right false. The check computes the values under your valuation, so every correct counterexample is accepted.
Claim: \(p,\neg p\models q\). No valuation satisfies \(\{p,\neg p\}\). So the condition "every valuation that satisfies \(\Gamma\) makes \(q\) true" has no case to check, and it holds. The same reasoning shows that an unsatisfiable set \(\Gamma\) entails every formula.
The converse is also true. Suppose \(\Gamma\) entails every formula. Then \(\Gamma\models p\) and \(\Gamma\models\neg p\). A valuation that satisfies \(\Gamma\) would make both \(p\) and \(\neg p\) true, which is impossible. So \(\Gamma\) is unsatisfiable.
Next we prove four general facts. Each proof only unfolds Definitions 8.1 and 8.3 and uses the clauses for the truth value of a formula.
Let \(\Gamma,\Delta\) be sets of formulas and \(\varphi,\psi\) formulas.
Proof. (a) If \(v\) satisfies \(\Gamma\), then \(v\) makes every member of \(\Gamma\) true, and \(\varphi\) is a member.
(b) Let \(v\) satisfy \(\Delta\). Every member of \(\Gamma\) is a member of \(\Delta\), so \(v\) also satisfies \(\Gamma\). Since \(\Gamma\models\varphi\), \([\![\varphi]\!]_v=\mathrm T\).
(c) Let \(v\) satisfy \(\Gamma\). Then \([\![\varphi]\!]_v=\mathrm T\) and \([\![\varphi\to\psi]\!]_v=\mathrm T\). By the clause for \(\to\), \([\![\varphi]\!]_v=\mathrm F\) or \([\![\psi]\!]_v=\mathrm T\). The first is false, so \([\![\psi]\!]_v=\mathrm T\).
(d) (\(\Rightarrow\)) Suppose \(\Gamma\cup\{\varphi\}\models\psi\), and let \(v\) satisfy \(\Gamma\). If \([\![\varphi]\!]_v=\mathrm F\), then \([\![\varphi\to\psi]\!]_v=\mathrm T\) by the clause for \(\to\). If \([\![\varphi]\!]_v=\mathrm T\), then \(v\) satisfies \(\Gamma\cup\{\varphi\}\), so \([\![\psi]\!]_v=\mathrm T\), and again \([\![\varphi\to\psi]\!]_v=\mathrm T\).
(\(\Leftarrow\)) Suppose \(\Gamma\models\varphi\to\psi\), and let \(v\) satisfy \(\Gamma\cup\{\varphi\}\). Then \(v\) satisfies \(\Gamma\), so \([\![\varphi\to\psi]\!]_v=\mathrm T\), and also \([\![\varphi]\!]_v=\mathrm T\). As in (c), \([\![\psi]\!]_v=\mathrm T\). □
Part (d) moves a formula from the left of \(\models\) into the antecedent of an implication, and back. If we use it \(n\) times, starting from the empty set, we get
\[\psi_1,\dots,\psi_n\models\varphi\quad\text{iff}\quad\models\psi_1\to(\psi_2\to(\cdots\to(\psi_n\to\varphi)\cdots)).\]So for a finite set of assumptions, entailment is the same as a tautology. On Day 3 we meet a second relation, \(\vdash\). The statement for \(\vdash\) that corresponds to (d) is called the Deduction Theorem.
Is \((p\to q)\to((q\to r)\to(p\to r))\) a tautology? Apply Proposition 8.7(d) three times:
\[\models(p\to q)\to((q\to r)\to(p\to r))\iff p\to q\models(q\to r)\to(p\to r)\iff p\to q,\ q\to r\models p\to r \iff p\to q,\ q\to r,\ p\models r.\]The last claim is easy. Let \(v\) satisfy the three assumptions. Then \(v(p)=\mathrm T\); from \(p\to q\), \(v(q)=\mathrm T\); from \(q\to r\), \(v(r)=\mathrm T\). So the formula is a tautology, and we did not need its eight-row truth table.
Let \(p_0,p_1,p_2,\dots\) be distinct primitive propositions, and let
\[\Gamma=\{p_0\}\cup\{p_n\to p_{n+1}: n\in\mathbb N\}=\{p_0,\ p_0\to p_1,\ p_1\to p_2,\ \dots\}.\]Claim: \(\Gamma\models p_n\) for every \(n\). We use induction on \(n\). Let \(v\) satisfy \(\Gamma\). For \(n=0\): \(p_0\in\Gamma\), so \(v(p_0)=\mathrm T\). Step: if \(v(p_n)=\mathrm T\), then since \([\![p_n\to p_{n+1}]\!]_v=\mathrm T\), the clause for \(\to\) gives \(v(p_{n+1})=\mathrm T\).
On the other hand, let \(q\) be a primitive proposition different from all \(p_n\). The valuation with \(v(p_n)=\mathrm T\) for every \(n\) and \(v(q)=\mathrm F\) satisfies \(\Gamma\), so \(\Gamma\not\models q\).
A truth table cannot be used here, since infinitely many primitive propositions occur in \(\Gamma\). The definition still works: we reason about an arbitrary valuation.
Self-check only. Nothing here counts towards your grade.
Let \(\Gamma=\{p\vee q,\ q\to r\}\). For each formula \(\varphi\), decide whether \(\Gamma\models\varphi\). Hint: first find all valuations of \(p,q,r\) that satisfy \(\Gamma\).
If \(v(q)=\mathrm T\), then \(q\to r\) forces \(v(r)=\mathrm T\), and \(p\) can be anything. If \(v(q)=\mathrm F\), then \(p\vee q\) forces \(v(p)=\mathrm T\), and \(r\) can be anything. So exactly four valuations satisfy \(\Gamma\) (values of \(p,q,r\)): \(\mathrm{TTT}\), \(\mathrm{FTT}\), \(\mathrm{TFT}\), \(\mathrm{TFF}\). A formula is a consequence iff it is true in all four.
Today we compare formulas by their truth values, and we ask which sets of connectives are enough to express every formula.
| \(p\) | \(q\) | \(p \leftrightarrow q\) | \(p \mid q\) | \(p \downarrow q\) |
|---|---|---|---|---|
| T | T | T | F | F |
| T | F | F | T | F |
| F | T | F | T | F |
| F | F | T | T | T |
The formulas \(p\wedge q\) and \(q\wedge p\) are different strings of symbols, but they say the same thing: under every valuation they have the same truth value. We give this a name.
Two formulas \(\varphi\) and \(\psi\) are logically equivalent, written \(\varphi\approx\psi\), if \(\models\varphi\leftrightarrow\psi\). Since \(\varphi\leftrightarrow\psi\) is true exactly when both sides have the same value, this means:
\[\varphi\approx\psi\quad\text{iff}\quad[\![\varphi]\!]_v=[\![\psi]\!]_v\ \text{ for every valuation }v.\]Like \(\models\), the symbol \(\approx\) belongs to the metalanguage. We write \(\varphi\not\approx\psi\) when the formulas are not equivalent; then some valuation gives them different values.
| \(p\) | \(q\) | \(\neg p\) | \(\neg p \vee q\) | \(p \to q\) |
|---|---|---|---|---|
| T | T | F | T | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
In terms of Day 1, \(\varphi\approx\psi\) holds exactly when \(\varphi\models\psi\) and \(\psi\models\varphi\): each formula is true wherever the other one is.
For all formulas \(\varphi,\psi,\chi\): \(\varphi\approx\varphi\) (reflexive); if \(\varphi\approx\psi\) then \(\psi\approx\varphi\) (symmetric); if \(\varphi\approx\psi\) and \(\psi\approx\chi\) then \(\varphi\approx\chi\) (transitive).
Proof. Each property of \(\approx\) comes from the same property of equality of truth values. Let \(v\) be any valuation. Clearly \([\![\varphi]\!]_v=[\![\varphi]\!]_v\). If \([\![\varphi]\!]_v=[\![\psi]\!]_v\), then \([\![\psi]\!]_v=[\![\varphi]\!]_v\). If \([\![\varphi]\!]_v=[\![\psi]\!]_v\) and \([\![\psi]\!]_v=[\![\chi]\!]_v\), then \([\![\varphi]\!]_v=[\![\chi]\!]_v\). Since \(v\) was arbitrary, the three properties hold. □
An equivalence relation splits a set into classes. Here each class collects the formulas that have the same truth value under every valuation. For example, every formula whose only primitive proposition is \(p\) is in one of exactly four classes, one for each of the four ways a truth value can depend on \(p\) (Figure 1).
Table 1 lists equivalences that we use all the time. Each line is a pair of formula schemes. Each can be checked with a truth table in which \(\varphi,\psi,\chi\) are treated like primitive propositions, so each holds for all formulas \(\varphi,\psi,\chi\).
| Name | Equivalence |
|---|---|
| Double negation | \(\neg\neg\varphi\approx\varphi\) |
| De Morgan | \(\neg(\varphi\wedge\psi)\approx\neg\varphi\vee\neg\psi\qquad \neg(\varphi\vee\psi)\approx\neg\varphi\wedge\neg\psi\) |
| Implication | \(\varphi\to\psi\approx\neg\varphi\vee\psi\qquad \varphi\to\psi\approx\neg(\varphi\wedge\neg\psi)\) |
| Negated implication | \(\neg(\varphi\to\psi)\approx\varphi\wedge\neg\psi\) |
| Contraposition | \(\varphi\to\psi\approx\neg\psi\to\neg\varphi\) |
| Exportation | \((\varphi\wedge\psi)\to\chi\approx\varphi\to(\psi\to\chi)\) |
| Commutativity | \(\varphi\wedge\psi\approx\psi\wedge\varphi\qquad \varphi\vee\psi\approx\psi\vee\varphi\) |
| Associativity | \((\varphi\wedge\psi)\wedge\chi\approx\varphi\wedge(\psi\wedge\chi)\qquad (\varphi\vee\psi)\vee\chi\approx\varphi\vee(\psi\vee\chi)\) |
| Distributivity | \(\varphi\wedge(\psi\vee\chi)\approx(\varphi\wedge\psi)\vee(\varphi\wedge\chi) \qquad\varphi\vee(\psi\wedge\chi)\approx(\varphi\vee\psi)\wedge(\varphi\vee\chi)\) |
To use these equivalences inside bigger formulas, we need one more fact: replacing a part of a formula by an equivalent part gives an equivalent formula.
If \(\varphi\approx\varphi'\) and \(\psi\approx\psi'\), then \(\neg\varphi\approx\neg\varphi'\), \(\varphi\wedge\psi\approx\varphi'\wedge\psi'\), \(\varphi\vee\psi\approx\varphi'\vee\psi'\) and \(\varphi\to\psi\approx\varphi'\to\psi'\).
Proof. Let \(v\) be a valuation. Then \([\![\varphi]\!]_v=[\![\varphi']\!]_v\) and \([\![\psi]\!]_v=[\![\psi']\!]_v\). The value of \(\neg\varphi\) is computed from the value of \(\varphi\) by the truth table of \(\neg\), and the value of \(\neg\varphi'\) from the same value by the same table, so they are equal. In the same way, \(\varphi\wedge\psi\) and \(\varphi'\wedge\psi'\) get their values from the same pair of values by the table of \(\wedge\); the same holds for \(\vee\) and \(\to\). □
Using Proposition 8.13 again and again, one can replace a subformula anywhere inside a formula. This fact is called the Substitution Theorem. Below we only need Proposition 8.13 itself.
Each step replaces one part by an equivalent part (Proposition 8.13), and transitivity (Proposition 8.12) joins the steps. In English, (b) says: if \(\varphi\) gives \(\chi\) and \(\psi\) gives \(\chi\), then "\(\varphi\) or \(\psi\)" gives \(\chi\). This is proof by cases.
Self-check only. Nothing here counts towards your grade.
For each pair, decide whether the two formulas are logically equivalent.
Our language \(\mathcal L(\neg,\wedge,\vee,\to)\) has four connectives. Do we need all of them? If every formula has an equivalent formula that uses fewer connectives, then nothing is lost by dropping the others.
A set \(A\) of connectives is adequate if for every formula \(\varphi\in\mathcal L(\neg,\wedge,\vee,\to)\) there is a formula \(\varphi'\in\mathcal L(A)\) with \(\varphi'\approx\varphi\).
For example, \(\{\neg,\wedge,\vee,\to\}\) is adequate: take \(\varphi'=\varphi\). For \(A=\{\neg,\wedge\}\), the formula \(p\to q\) has the equivalent \(\neg(p\wedge\neg q)\in\mathcal L(\neg,\wedge)\) (Table 1). One example is not enough, though: adequacy is a claim about every formula.
For every formula \(\varphi\in\mathcal L(\neg,\wedge,\vee,\to)\) there is a formula \(\varphi'\in\mathcal L(\neg,\wedge)\) such that \(\varphi'\approx\varphi\).
Proof. By structural induction on \(\varphi\).
Base case. \(\varphi=p\) is a primitive proposition. Then \(p\in\mathcal L(\neg,\wedge)\), so we take \(p'=p\).
Step for \(\neg\). Suppose \(\varphi'\in\mathcal L(\neg,\wedge)\) and \(\varphi'\approx\varphi\). Then \(\neg\varphi'\in\mathcal L(\neg,\wedge)\), and \(\neg\varphi'\approx\neg\varphi\) by Proposition 8.13. So \((\neg\varphi)'=\neg\varphi'\) works.
Step for \(\wedge\). Suppose \(\varphi'\approx\varphi\) and \(\psi'\approx\psi\) with \(\varphi',\psi'\in\mathcal L(\neg,\wedge)\). Then \(\varphi'\wedge\psi'\in\mathcal L(\neg,\wedge)\) and \(\varphi'\wedge\psi'\approx\varphi\wedge\psi\) by Proposition 8.13.
Step for \(\to\). With \(\varphi',\psi'\) as before, we claim \(\neg(\varphi'\wedge\neg\psi')\approx\varphi\to\psi\). Under every valuation \(\varphi'\) has the value of \(\varphi\) and \(\psi'\) the value of \(\psi\), so we only need the four rows for the values of \(\varphi\) and \(\psi\):
| \(\varphi\) | \(\psi\) | \(\varphi \to \psi\) | \(\varphi'\) | \(\psi'\) | \(\neg \psi'\) | \(\varphi' \wedge \neg \psi'\) | \(\neg (\varphi' \wedge \neg \psi')\) |
|---|---|---|---|---|---|---|---|
| T | T | T | T | T | F | F | T |
| T | F | F | T | F | T | T | F |
| F | T | T | F | T | F | F | T |
| F | F | T | F | F | T | F | T |
The two marked columns, for \(\varphi\to\psi\) and \(\neg(\varphi'\wedge\neg\psi')\), agree in every row, and \(\neg(\varphi'\wedge\neg\psi')\in\mathcal L(\neg,\wedge)\).
Step for \(\vee\). In the same way we claim \(\neg(\neg\varphi'\wedge\neg\psi')\approx\varphi\vee\psi\):
| \(\varphi\) | \(\psi\) | \(\varphi \vee \psi\) | \(\varphi'\) | \(\psi'\) | \(\neg \varphi'\) | \(\neg \psi'\) | \(\neg \varphi' \wedge \neg \psi'\) | \(\neg (\neg \varphi' \wedge \neg \psi')\) |
|---|---|---|---|---|---|---|---|---|
| T | T | T | T | T | F | F | F | T |
| T | F | T | T | F | F | T | F | T |
| F | T | T | F | T | T | F | F | T |
| F | F | F | F | F | T | T | T | F |
Again the two marked columns agree, and \(\neg(\neg\varphi'\wedge\neg\psi')\in\mathcal L(\neg,\wedge)\). This completes the induction. □
The proof does more than show that \(\varphi'\) exists. It is a recipe: it builds \(\varphi'\) from the formulas \(p'\) for the primitive propositions, one connective at a time, using
\[\begin{gathered}p'=p,\qquad(\neg\varphi)'=\neg\varphi',\qquad(\varphi\wedge\psi)'=\varphi'\wedge\psi',\\ (\varphi\to\psi)'=\neg(\varphi'\wedge\neg\psi'),\qquad(\varphi\vee\psi)'=\neg(\neg\varphi'\wedge\neg\psi').\end{gathered}\]Let \(\varphi=(p\vee q)\to\neg r\). We work from the inside out:
Check: \(\varphi'\) is false iff \(\neg(\neg p\wedge\neg q)\wedge\neg\neg r\) is true, that is, iff \(p\vee q\) is true and \(r\) is true. And \(\varphi\) is false iff \(p\vee q\) is true and \(\neg r\) is false, that is, the same condition. So \(\varphi'\approx\varphi\).
The recipe does not give the shortest answer. For example \(\neg(\neg(\neg p\wedge\neg q)\wedge r)\) is also equivalent to \(\varphi\), by double negation.
Once we know that \(\{\neg,\wedge\}\) is adequate, other sets are easier. It is enough to express \(\neg\) and \(\wedge\).
Let \(A\) be a set of connectives. Suppose that for all formulas \(\varphi,\psi\in\mathcal L(A)\) there are formulas \(N(\varphi)\) and \(K(\varphi,\psi)\) in \(\mathcal L(A)\) with
\[N(\varphi)\approx\neg\varphi\qquad\text{and}\qquad K(\varphi,\psi)\approx\varphi\wedge\psi.\]Then \(A\) is adequate.
Proof. Let \(\theta\in\mathcal L(\neg,\wedge,\vee,\to)\). By Theorem 8.16 there is \(\theta_1\in\mathcal L(\neg,\wedge)\) with \(\theta_1\approx\theta\). We show by structural induction on \(\mathcal L(\neg,\wedge)\) that every \(\chi\in\mathcal L(\neg,\wedge)\) has some \(\chi^*\in\mathcal L(A)\) with \(\chi^*\approx\chi\).
Then \(\theta_1^*\in\mathcal L(A)\) and \(\theta_1^*\approx\theta_1\approx\theta\), by transitivity. □
In practice we give \(N\) and \(K\) as formula schemes and check each with a four-row truth table, as in the next three examples.
Take \(N(\varphi)=\neg\varphi\) and \(K(\varphi,\psi)=\neg(\neg\varphi\vee\neg\psi)\). The first needs no check. For the second:
| \(\varphi\) | \(\psi\) | \(\neg \varphi\) | \(\neg \psi\) | \(\neg \varphi \vee \neg \psi\) | \(\neg (\neg \varphi \vee \neg \psi)\) | \(\varphi \wedge \psi\) |
|---|---|---|---|---|---|---|
| T | T | F | F | F | T | T |
| T | F | F | T | T | F | F |
| F | T | T | F | T | F | F |
| F | F | T | T | T | F | F |
The two marked columns agree, so \(K(\varphi,\psi)\approx\varphi\wedge\psi\). By Proposition 8.18, \(\{\neg,\vee\}\) is adequate. (This is De Morgan's law used backwards.)
Take \(N(\varphi)=\neg\varphi\) and \(K(\varphi,\psi)=\neg(\varphi\to\neg\psi)\):
| \(\varphi\) | \(\psi\) | \(\neg \psi\) | \(\varphi \to \neg \psi\) | \(\neg (\varphi \to \neg \psi)\) | \(\varphi \wedge \psi\) |
|---|---|---|---|---|---|
| T | T | F | F | T | T |
| T | F | T | T | F | F |
| F | T | F | T | F | F |
| F | F | T | T | F | F |
So \(\{\neg,\to\}\) is adequate.
Now \(A=\{\mid\}\) has a single connective. We need \(N(\varphi)\) and \(K(\varphi,\psi)\) that use only \(\mid\). Since \(\varphi\mid\varphi\) is "not both \(\varphi\) and \(\varphi\)", it should be \(\neg\varphi\). And \(\varphi\wedge\psi\) is the negation of \(\varphi\mid\psi\), so we negate with the same trick:
\[N(\varphi)=\varphi\mid\varphi,\qquad K(\varphi,\psi)=(\varphi\mid\psi)\mid(\varphi\mid\psi).\]| \(\varphi\) | \(\psi\) | \(\varphi \mid \varphi\) | \(\neg \varphi\) | \(\varphi \mid \psi\) | \((\varphi \mid \psi) \mid (\varphi \mid \psi)\) | \(\varphi \wedge \psi\) |
|---|---|---|---|---|---|---|
| T | T | F | F | F | T | T |
| T | F | F | F | T | F | F |
| F | T | T | T | T | F | F |
| F | F | T | T | T | F | F |
The column of \(\varphi\mid\varphi\) agrees with the column of \(\neg\varphi\), and the column of \((\varphi\mid\psi)\mid(\varphi\mid\psi)\) agrees with the column of \(\varphi\wedge\psi\). So \(\{\mid\}\) is adequate: every formula can be written with the Sheffer stroke alone. The set \(\{\downarrow\}\) is treated in Exercise 4 below.
Self-check only. Nothing here counts towards your grade.
Write a formula that is equivalent to the given one and uses only the allowed connectives. The check compares truth values under all valuations, so every correct formula is accepted.
Typing formulas: use the buttons, or the keyboard: ~ for \(\neg\),
& for \(\wedge\), \/ for \(\vee\), -> for \(\to\),
<-> for \(\leftrightarrow\), | for the stroke \(\mid\). Use the button for
\(\downarrow\). Primitive propositions are small letters such as \(p,q,r\). As in our convention, only the
outermost parentheses may be left out: write \((p\wedge q)\to r\), not \(p\wedge q\to r\).
One possible answer for each part. Other equivalent formulas are also correct.
To show that \(A\) is adequate, we exhibit formulas. To show that \(A\) is not adequate, we must show that some formula has no equivalent in \(\mathcal L(A)\) at all. Trying many formulas and failing proves nothing, since there are infinitely many formulas in \(\mathcal L(A)\). The standard method has three steps:
Let \(v_{\mathrm T}\) be the valuation with \(v_{\mathrm T}(p)=\mathrm T\) for every primitive proposition \(p\).
Claim. \([\![\varphi]\!]_{v_{\mathrm T}}=\mathrm T\) for every \(\varphi\in\mathcal L(\vee,\to)\).
Proof of the claim, by structural induction on \(\varphi\).
Conclusion. Suppose some \(\varphi\in\mathcal L(\vee,\to)\) satisfies \(\varphi\approx\neg p\). Then \([\![\varphi]\!]_{v_{\mathrm T}}=[\![\neg p]\!]_{v_{\mathrm T}}=\mathrm F\), which contradicts the claim. So \(\neg p\) has no equivalent in \(\mathcal L(\vee,\to)\), and \(\{\vee,\to\}\) is not adequate.
The step for \(\wedge\) works in the same way (\(\mathrm T\wedge\mathrm T=\mathrm T\)). So even \(\{\wedge,\vee,\to\}\) is not adequate: without \(\neg\) we cannot turn true into false.
Every formula of \(\mathcal L(\neg)\) has the form \(\neg\neg\cdots\neg s\) for one primitive proposition \(s\). Formally, by structural induction: a primitive proposition \(s\) contains exactly one primitive proposition, and \(\neg\varphi\) contains the same primitive propositions as \(\varphi\). So every \(\varphi\in\mathcal L(\neg)\) contains exactly one primitive proposition \(s\), and its value depends only on \(v(s)\).
Suppose \(\varphi\approx p\wedge q\) with \(\varphi\in\mathcal L(\neg)\), and let \(s\) be its primitive proposition. We find two valuations that agree on \(s\) but give \(p\wedge q\) different values.
In both cases \([\![\varphi]\!]_{v_1}=[\![\varphi]\!]_{v_2}\), since \(v_1(s)=v_2(s)\). But \([\![p\wedge q]\!]_{v_1}=\mathrm T\) and \([\![p\wedge q]\!]_{v_2}=\mathrm F\). This contradicts \(\varphi\approx p\wedge q\). So \(\{\neg\}\) is not adequate.
Today we define deductions from a set of assumptions, list the axioms for each connective, and write our first deductions in Fitch notation.
On Day 1, \(\Gamma\models\varphi\) was defined through valuations: it talks about all possible assignments of truth values. Now we take a different approach. We fix some basic formulas and one rule of reasoning, and we say that \(\varphi\) can be deduced from \(\Gamma\) if there is a finite list of steps from \(\Gamma\) to \(\varphi\). Truth values play no role in this definition.
We work in the language \(\mathcal L(\neg,\wedge,\vee,\to)\). For each connective we fix a few axiom schemes that say how it behaves, and we use a single rule of inference.
An axiom is any instance of one of the following nine schemes.
| Connective | Name | Axiom scheme |
|---|---|---|
| Implication | (L1) | \(\varphi \to (\psi \to \varphi)\) |
| (L2) | \((\varphi \to (\psi \to \chi)) \to ((\varphi \to \psi) \to (\varphi \to \chi))\) | |
| Negation | (L3) | \((\neg \psi \to \neg \varphi) \to (\varphi \to \psi)\) |
| Conjunction | (L4) | \((\varphi \wedge \psi) \to \varphi\) |
| (L5) | \((\varphi \wedge \psi) \to \psi\) | |
| (L6) | \(\varphi \to (\psi \to (\varphi \wedge \psi))\) | |
| Disjunction | (L7) | \(\varphi \to (\varphi \vee \psi)\) |
| (L8) | \(\psi \to (\varphi \vee \psi)\) | |
| (L9) | \((\varphi \to \chi) \to ((\psi \to \chi) \to ((\varphi \vee \psi) \to \chi))\) |
There is one rule of inference, modus ponens (MP): from \(\varphi\) and \(\varphi\to\psi\), infer \(\psi\).
Each axiom says something we accept about one connective.
The symbol \(\leftrightarrow\) is still an abbreviation, so it needs no axioms of its own. Every axiom is a tautology, which can be checked with a truth table. This will matter later, when we compare \(\vdash\) with \(\models\).
To check whether a formula is an instance of a scheme, compare main connectives first, then the parts. The same Greek letter must be replaced by the same formula everywhere.
Let \(\Gamma\) be a set of formulas. A deduction from \(\Gamma\) is a finite sequence of formulas \(\varphi_1,\dots,\varphi_n\) such that for each \(1\le i\le n\), either
It is a deduction of \(\varphi\) if \(\varphi_n=\varphi\). We write \(\Gamma\vdash\varphi\) if there is a deduction of \(\varphi\) from \(\Gamma\). The members of \(\Gamma\) are called assumptions. For \(\Gamma=\varnothing\) we write \(\vdash\varphi\): a deduction without assumptions.
We use the same short forms as for \(\models\): \(\psi_1,\dots,\psi_n\vdash\varphi\) means \(\{\psi_1,\dots,\psi_n\}\vdash\varphi\). Two remarks on the definition:
We write deductions in Fitch notation (Figure 2):
Definition 8.26 allows a member of \(\Gamma\) at any line, not only at the top. Moving such a line up does not break anything: an assumption line cites no other line, and every line still comes after the lines it cites (the numbers in the MP justifications change, but the order does not). So we can always put the assumptions first. An assumption may also stay unused, and a line may be cited many times.
There are no assumptions, so the bar is at the top.
Line 2 is the instance of (L2) with \(\varphi:=\varphi\), \(\psi:=\varphi\to\varphi\) and \(\chi:=\varphi\). Line 3: line 2 is line 1 followed by \(\to\) and line 3. Line 5: line 3 is line 4 followed by \(\to\) and line 5. Since all our axioms are schemes, the same deduction works for every formula \(\varphi\), for example \(\varphi:=p\).
The deduction is short but not obvious. The idea: (L2) followed by MP twice removes an antecedent in the form \(\varphi\to\cdots\), and the two instances of (L1) supply exactly what (L2) needs.
Axiom (L6) turns the two assumptions into their conjunction with two applications of MP. Since the line numbers in a justification can come in any order, line 5 cites line 2 (\(\psi\)) and line 4 (\(\psi\to(\varphi\wedge\psi)\)).
Lines 2 to 5 take the conjunction apart with (L5) and (L4). Lines 6 to 8 put the parts together again, in the other order, as in Example 8.28. Note line 6: it is (L6) with \(\varphi:=\psi\) and \(\psi:=\varphi\), so the letters swap.
(L1) followed by MP adds any antecedent \(\psi\) in front of a formula we already have. We will use this move often.
Planning, backwards from the goal. The goal \(\varphi\to\chi\) is not an assumption and not an axiom, so it must come from MP: we need some \(\alpha\) and \(\alpha\to(\varphi\to\chi)\). Axiom (L2) ends in \((\varphi\to\psi)\to(\varphi\to\chi)\), and \(\varphi\to\psi\) is an assumption. So we aim for \((\varphi\to\psi)\to(\varphi\to\chi)\). By (L2) and MP, this follows from \(\varphi\to(\psi\to\chi)\). And that follows from the assumption \(\psi\to\chi\) by (L1) and MP, as in Example 8.30. Now we write the lines forwards:
The only axiom with \(\neg\) is (L3), and its consequent is \(\varphi\to\psi\), exactly the goal. So we need its antecedent \(\neg\psi\to\neg\varphi\), which we get from \(\neg\varphi\) as in Example 8.30.
In words: from \(\neg\varphi\), every implication with antecedent \(\varphi\) can be deduced.
We use (L9), proof by cases, with \(\chi:=\psi\vee\varphi\). We need \(\varphi\to(\psi\vee\varphi)\) and \(\psi\to(\psi\vee\varphi)\).
Line 2 is (L8) with \(\varphi:=\psi\), \(\psi:=\varphi\); line 3 is (L7) with the same replacement. Line 4 is (L9) with \(\chi:=\psi\vee\varphi\) and the letters \(\varphi,\psi\) unchanged. Lines 5 to 7 apply MP three times, once for each antecedent of line 4.
Lines 3 and 4 take \(\varphi\) out of the conjunction. Lines 5 and 6 turn the first assumption into \(\varphi\to\psi\) with (L3). Line 7 combines the two.
Self-check only. Nothing here counts towards your grade.
The formulas below form a deduction of \(r\wedge p\) from \(\Gamma=\{p,\ p\to q,\ q\to r\}\). For each line, choose the justification. For MP, also enter the two line numbers, in either order.
Line 6 is (L6) with \(\varphi:=r\) and \(\psi:=p\). Lines 4 and 5 use the assumptions as implications; lines 7 and 8 use MP with (L6) as in Example 8.28.
Deductions can be joined together. This gives some general facts about \(\vdash\). Compare them with Proposition 8.7(a) to (c) for \(\models\).
Let \(\Gamma,\Delta\) be sets of formulas and \(\varphi,\psi\) formulas.
Proof. (a) The one-line sequence \(\varphi\) is a deduction from \(\Gamma\): its only line is justified by (assump.).
(b) Take a deduction of \(\varphi\) from \(\Gamma\). Each line is an axiom, a member of \(\Gamma\) (and so of \(\Delta\)), or follows from earlier lines by MP. So the same sequence is a deduction from \(\Delta\).
(c) Take a deduction \(\varphi_1,\dots,\varphi_n\) of \(\varphi\) from \(\Gamma\), and a deduction \(\chi_1,\dots,\chi_m\) of \(\varphi\to\psi\) from \(\Gamma\). Write the first, then the second, then \(\psi\):
\[\varphi_1,\ \dots,\ \varphi_n,\ \chi_1,\ \dots,\ \chi_m,\ \psi.\]Lines \(1\) to \(n\) are justified as before. Line \(n+i\) is \(\chi_i\); if it was justified by MP from lines \(j,k\) of the second deduction, it is now justified by MP from lines \(n+j,n+k\), which are still earlier. The last line follows by MP from line \(n\) (\(\varphi\)) and line \(n+m\) (\(\varphi\to\psi\)). □
In the same way we can turn the pattern of Example 8.31 into a general rule.
If \(\Gamma\vdash\varphi\to\psi\) and \(\Gamma\vdash\psi\to\chi\), then \(\Gamma\vdash\varphi\to\chi\).
Proof. Write a deduction of \(\varphi\to\psi\) from \(\Gamma\) (\(n\) lines), then a deduction of \(\psi\to\chi\) from \(\Gamma\) (\(m\) lines, with MP line numbers raised by \(n\), as in the proof of Proposition 8.35(c)). Then add the last five lines of Example 8.31:
| \(n+m+1\) | \((\psi\to\chi)\to(\varphi\to(\psi\to\chi))\) | (L1) |
| \(n+m+2\) | \(\varphi\to(\psi\to\chi)\) | (\(n+m,\ n+m+1\) MP) |
| \(n+m+3\) | \((\varphi\to(\psi\to\chi))\to((\varphi\to\psi)\to(\varphi\to\chi))\) | (L2) |
| \(n+m+4\) | \((\varphi\to\psi)\to(\varphi\to\chi)\) | (\(n+m+2,\ n+m+3\) MP) |
| \(n+m+5\) | \(\varphi\to\chi\) | (\(n,\ n+m+4\) MP) |
Line \(n\) is \(\varphi\to\psi\) and line \(n+m\) is \(\psi\to\chi\). □
This rule is called hypothetical syllogism (HS). Results like Propositions 8.35 and 8.36 are statements about deductions. They tell us that a deduction exists without writing it out.
Short proof. By (L4), \(\vdash(\varphi\wedge\psi)\to\varphi\). By (L7), \(\vdash\varphi\to(\varphi\vee\psi)\). By Proposition 8.36 with \(\Gamma=\varnothing\), \(\vdash(\varphi\wedge\psi)\to(\varphi\vee\psi)\).
The deduction itself. Following the proof of Proposition 8.36 with \(n=m=1\):
Self-check only. Nothing here counts towards your grade.
Write a deduction for each claim. Type one formula per line and choose its justification. The check tests every line against Definition 8.26, so every correct deduction is accepted, also one that differs from the solution. Type formulas as in Exercise 4.
Hint: (L6) gives \(p\to(q\to(p\wedge q))\). Then use (L2) to deal with the \(q\) inside, and get \(p\to q\) from \(q\) as in Example 8.30.
(a)
(b)
(c)
In (c), line 3 is (L2) with \(\varphi:=p\), \(\psi:=q\), \(\chi:=p\wedge q\).
In Example 8.32 we showed \(\neg\varphi\vdash\varphi\to\psi\). Can we conclude \(\vdash\neg\varphi\to(\varphi\to\psi)\), with no assumptions? For \(\models\), Proposition 8.7(d) moves a formula from the left side into an antecedent. The corresponding statement for \(\vdash\) is the Deduction Theorem: \(\Gamma\cup\{\varphi\}\vdash\psi\) if and only if \(\Gamma\vdash\varphi\to\psi\). We prove it next week. Until then, show a claim \(\Gamma\vdash\varphi\) only by writing a deduction, or with Propositions 8.35 and 8.36.
For each claim, decide whether it holds. If it holds, prove it, for example by assuming that a valuation satisfies the left side and makes the right side false, and reaching a contradiction. If it fails, give a counterexample and check it. Each part is worth 3 points.
A student claims that the following is a deduction of \(r\wedge p\) from \(\Gamma=\{p\to q,\ q\to r,\ r\}\):
Write a deduction for each claim in Fitch notation. Use only (assump.), the axioms (L1) to (L9) and MP, and write the justifications as in the notes, for example (L6) or (1,2 MP). Write every line: do not cite Proposition 8.36 or earlier examples. Put the assumptions first. Use "Add line" for more lines.
Prove each statement directly from Definitions 8.1 and 8.3. Here \(\Gamma\) is any set of formulas and \(\varphi,\psi\) are any formulas.
In this question \(\leftrightarrow\) is a connective of its own: \(\varphi\leftrightarrow\psi\) is true exactly when \(\varphi\) and \(\psi\) have the same truth value. Let \(v_1,v_2,v_3,v_4\) be the four valuations that give \(p\) and \(q\) the four combinations of truth values and give every other primitive proposition the value \(\mathrm T\). For a formula \(\varphi\), let \(t(\varphi)\) be the number of \(i\in\{1,2,3,4\}\) with \([\![\varphi]\!]_{v_i}=\mathrm T\).