Classical Propositional Logic: Formulas and Truth

We show that \(((p\wedge q)\to r)\vee\neg q\) is a formula by building it with the clauses of Definition 7.2.

1. \(p\), \(q\) and \(r\) are formulas, by clause 1.
2. \((p\wedge q)\) is a formula, by clause 3 applied to \(p\) and \(q\).
3. \(((p\wedge q)\to r)\) is a formula, by clause 3 applied to \((p\wedge q)\) and \(r\).
4. \(\neg q\) is a formula, by clause 2 applied to \(q\).
5. \((((p\wedge q)\to r)\vee\neg q)\) is a formula, by clause 3 applied to the formulas of steps 3 and 4.

The last formula is written with one pair of parentheses fewer at the outside; Convention 7.5 below allows this. Figure 1 shows the same construction as a tree, read from the bottom up.

We use Definition 7.2 together with Convention 7.5.

1. \(\neg\neg p\to p\). A formula. Negation has narrow scope, so the two negations apply only to the first \(p\): the string means \((\neg\neg p)\to p\). The main connective is \(\to\).
2. \(p\,\neg\!\wedge q\). Not a formula. The clauses never put \(\neg\) between a formula and a binary connective.
3. \((p\to q)\vee\neg(r\wedge p)\). A formula with main connective \(\vee\). Its immediate subformulas are \(p\to q\) and \(\neg(r\wedge p)\).
4. \(p\vee q\wedge r\). Not a formula: two binary connectives without parentheses to group them.
5. \(\neg(p\to(q\to p))\). A formula. Here the parentheses after \(\neg\) are needed, so the negation applies to the whole implication, and the main connective is \(\neg\).
6. \((p\wedge q))\). Not a formula. In every formula the left and right parentheses come in matching pairs, because clause 3 adds them in pairs; this string has one more right parenthesis than left ones.

A practical test for the main connective: it is the one connective that is not inside any pair of parentheses. If there is none outside all parentheses and the formula starts with \(\neg\), the main connective is that \(\neg\).

Dictionary of Definition 7.7.

1. It is raining but it is not cold. "But" joins the two parts, and logic only keeps the "and": \(r\wedge\neg c\).
2. If it is raining, I take my umbrella. \(r\to u\).
3. I take my umbrella only if it is raining. This says: whenever I take my umbrella, it is raining. So \(u\to r\). Compare with sentence 2, which is \(r\to u\).
4. I take my umbrella if it is raining. "\(B\) if \(A\)" is "if \(A\) then \(B\)": \(r\to u\), the same as sentence 2.
5. I walk to campus unless it is raining. If it is not raining, I walk: \(\neg r\to w\).
6. It is neither raining nor cold. \(\neg r\wedge\neg c\).
7. It is not both raining and cold. The "not" applies to the conjunction: \(\neg(r\wedge c)\). This is weaker than sentence 6: it allows rain without cold.
8. If it is cold and raining, then I take my umbrella and I do not walk to campus. The main connective is "if ... then". The antecedent is \(c\wedge r\), the consequent is \(u\wedge\neg w\). Both need parentheses: \((c\wedge r)\to(u\wedge\neg w)\).

Fix a natural number \(n\) and use the dictionary \(e\): \(n\) is even, \(f\): \(n\) is divisible by \(4\), \(t\): \(n\) is prime.

1. Being divisible by 4 is sufficient for being even. \(f\to e\).
2. Being even is necessary for being divisible by 4. Again \(f\to e\): a necessary condition is the consequent.
3. \(n\) is divisible by 4 only if \(n\) is even. Once more \(f\to e\). Sentences 1 to 3 are three ways to say the same thing.
4. If \(n\) is even and prime, then \(n\) is not divisible by 4. \((e\wedge t)\to\neg f\).
5. \(n\) is even if and only if \(n\) is divisible by 4. \(e\leftrightarrow f\). This one is false for \(n=6\); translation does not care whether a sentence is true.

It is raining and it is cold or I take my umbrella.

The English sentence does not say how to group its parts, and there are two candidates:

• \((r\wedge c)\vee u\): either it is raining and cold, or I take my umbrella. This is satisfied on a sunny day on which I happen to take my umbrella.
• \(r\wedge(c\vee u)\): it is raining, and it is cold or I take my umbrella. On a sunny day this is not satisfied, whatever I take.

Spoken English uses pauses and word order to separate the two readings ("either it is raining and cold, or ..."; "it is raining, and either ..."). A formula has to choose one, and the parentheses record the choice. When a sentence is ambiguous, say which reading you translate.

Same dictionary. For the way back, read the main connective first, then fill in the parts.

1. \((r\vee c)\to\neg w\): If it is raining or cold, I do not walk to campus.
2. \(\neg(w\wedge\neg u)\): It is not the case that I walk to campus without my umbrella. A smoother version: I do not walk to campus without my umbrella.
3. \(w\to(u\vee\neg r)\): If I walk to campus, then I take my umbrella or it is not raining.
4. \(\neg r\to\neg u\): If it is not raining, I do not take my umbrella. Equivalently: I take my umbrella only if it is raining. Compare sentence 3 of Example 7.10.

Let \(\varphi=(p\wedge\neg q)\to(q\vee p)\).

Length. Each line applies one clause of Definition 7.14 to the outermost connective that is still unevaluated:

Check by counting: the symbols are \(p,\wedge,\neg,q,\to,q,\vee,p\).

Connectives. In the same way \(\mathit{conn}(\varphi)=4\): the connectives are \(\wedge\), \(\neg\), \(\to\), \(\vee\).

Rank. \(\mathit{rank}(\neg q)=1\), so \(\mathit{rank}(p\wedge\neg q)=\max\{0,1\}+1=2\). \(\mathit{rank}(q\vee p)=\max\{0,0\}+1=1\). Hence \(\mathit{rank}(\varphi)=\max\{2,1\}+1=3\).

Subformulas. \(\mathit{sub}(\varphi)=\{p,\ q,\ \neg q,\ p\wedge\neg q,\ q\vee p,\ \varphi\}\), six formulas. The parse tree has eight nodes, but \(p\) and \(q\) each occur twice.

Occurring primitive propositions. \(\mathit{occ}(\varphi)=\{p,q\}\).

Claim: every formula has at least as many connectives as distinct primitive propositions, \(\mathit{conn}(\varphi)\ge|\mathit{occ}(\varphi)|\).

This is false, and one formula is enough to show it: for \(\varphi=p\) we have \(\mathit{conn}(p)=0\) and \(|\mathit{occ}(p)|=1\). An induction proof would fail already at the base case.

Corrected claim: \(\mathit{conn}(\varphi)\ge|\mathit{occ}(\varphi)|-1\) for every \(\varphi\).

To refute a statement about all formulas, give one formula for which it fails. To prove it, give an induction.

Let \(\varphi=(p\wedge\neg q)\to(q\vee r)\) and let \(v\) be a valuation with \(v(p)=\mathrm T\), \(v(q)=\mathrm F\), \(v(r)=\mathrm F\). Each line applies Definition 7.22 or Table 1 once:

So \([\![\varphi]\!]_v=\mathrm F\). The antecedent is true and the consequent is false: this is the one row in which an implication fails.

If we change only \(v(r)\) to \(\mathrm T\), the consequent becomes \(\mathrm F\vee\mathrm T=\mathrm T\) and the value of \(\varphi\) becomes \(\mathrm T\to\mathrm T=\mathrm T\).

Dictionary: \(r\): It is raining. \(c\): It is cold. \(u\): I take my umbrella. \(w\): I walk to campus. A situation is a valuation. Suppose today it is raining, it is not cold, I take my umbrella and I do not walk: \(v(r)=\mathrm T\), \(v(c)=\mathrm F\), \(v(u)=\mathrm T\), \(v(w)=\mathrm F\).

1. It is raining but not cold, \(r\wedge\neg c\): \(\mathrm T\wedge\neg\mathrm F=\mathrm T\wedge\mathrm T=\mathrm T\).
2. I take my umbrella only if it is raining, \(u\to r\): \(\mathrm T\to\mathrm T=\mathrm T\).
3. I walk to campus unless it is raining, \(\neg r\to w\): \(\neg\mathrm T\to\mathrm F=\mathrm F\to\mathrm F=\mathrm T\). It is raining, so the sentence makes no claim about today, and it is true.
4. If it is cold and raining, I take my umbrella and do not walk, \((c\wedge r)\to(u\wedge\neg w)\): the antecedent is \(\mathrm F\wedge\mathrm T=\mathrm F\), so the implication is \(\mathrm T\) without looking at the consequent.
5. It is not both raining and cold, \(\neg(r\wedge c)\): \(\neg(\mathrm T\wedge\mathrm F)=\neg\mathrm F=\mathrm T\).
6. If it is raining or cold, I walk to campus, \((r\vee c)\to w\): \(\mathrm T\to\mathrm F=\mathrm F\).

Sentence 4 shows a useful shortcut: an implication with a false antecedent is true, and a disjunction with one true part is true, so sometimes half of a formula does not need to be computed.

The truth table of \(\neg(p\wedge q)\to(\neg p\vee\neg q)\):

The first column after the bar is computed from \(p\) and \(q\) by the table of \(\wedge\); the second negates it, and so on. The last column is \(\mathrm T\) in every row, so the formula is true under every valuation.

Some books write the same computation more compactly, with each value under the connective that produces it in one long line. The entries are the same; only the layout differs.

The truth table of \((p\to q)\to(q\to p)\):

The formula is false in exactly one row: \(p\) false and \(q\) true. In that row \(p\to q\) is true (false antecedent) and \(q\to p\) is false. In words: the converse of a true implication can be false. A true \(p\to q\) does not give \(q\to p\).

The truth table of \(((p\vee q)\wedge\neg r)\to p\) has \(2^3=8\) rows:

In the first four rows \(p\) is true, so the implication is true whatever the antecedent is. Only the last four rows need work, and among them only the row \(p=\mathrm F\), \(q=\mathrm T\), \(r=\mathrm F\) makes the antecedent true. There the formula is false.

On Monday we translated neither \(A\) nor \(B\) both as \(\neg A\wedge\neg B\) and as \(\neg(A\vee B)\). With \(r\) and \(c\) for the two statements, the claim is that \(\neg(r\vee c)\leftrightarrow(\neg r\wedge\neg c)\) is a tautology:

The column of \(\leftrightarrow\) is \(\mathrm T\) exactly where the two columns it joins agree, and they agree in every row. So the two translations have the same truth value in every situation.

Same dictionary as in Example 7.24.

• Either it is raining or it is not raining, \(r\vee\neg r\): a tautology. It tells us nothing about the weather.
• If it is raining and cold, then it is raining, \((r\wedge c)\to r\): a tautology. If the antecedent is true, then \(r\) is true.
• If it is raining, then it is raining and cold, \(r\to(r\wedge c)\): contingent. It is false when \(r=\mathrm T\) and \(c=\mathrm F\).
• It is raining and it is not raining, \(r\wedge\neg r\): a contradiction.

(a) \((p\to q)\to(q\to p)\). For the whole implication to be false we need \(p\to q=\mathrm T\) and \(q\to p=\mathrm F\). The second condition forces \(q=\mathrm T\) and \(p=\mathrm F\). Check the first: \(\mathrm F\to\mathrm T=\mathrm T\). So the valuation with \(p=\mathrm F\), \(q=\mathrm T\) makes the formula false, and it is not a tautology. This is the row found in Example 7.28.

(b) \((p\to(q\to r))\to((p\to q)\to(p\to r))\). Suppose some valuation makes it false.

1. The consequent \((p\to q)\to(p\to r)\) must be \(\mathrm F\) and the antecedent \(p\to(q\to r)\) must be \(\mathrm T\).
2. For the consequent to be false: \(p\to q=\mathrm T\) and \(p\to r=\mathrm F\). The second forces \(p=\mathrm T\), \(r=\mathrm F\). Then the first forces \(q=\mathrm T\).
3. Now the antecedent is \(\mathrm T\to(\mathrm T\to\mathrm F)=\mathrm T\to\mathrm F=\mathrm F\). But step 1 needed it to be \(\mathrm T\).

Every choice was forced, and we reached a contradiction. So no valuation makes the formula false, and it is a tautology. This took one line of values instead of eight rows.