Lecture 2 — Logical Form and Logical Equivalence

lecture
discrete-math
logic
propositional-logic

Pre-work: Video 001 (Logical Form), Video 002 (Logical Equivalence). See logical-connectives and logical-equivalence-laws for the reference definitions/tables this lecture builds on.

Logic is the study of reasoning. What the language of symbolic logic is for is worth keeping in view, because the rest of the logic block is in service of it. Symbolic logic will help us to:

Learning goals

  1. Appreciate the difficulties in translating between English and mathematics.
  2. Understand the logical connectives \(\sim\) (not), \(\land\) (and), \(\lor\) (or).
  3. Construct a truth table for a statement form in standard form.
  4. Use a truth table to establish logical equivalence of two statement forms.
  5. Apply logical equivalence laws to establish logical equivalence of two statement forms.

Common questions

  • Can we use other symbols for “not”? Yes — common symbols for not include \(\sim\) and \(\neg\). This course writes \(\sim\).
  • How do we work out the number of variables and the number of rows in a truth table — for \((p \land q) \land (q \land r)\), are there 2 variables, 3 or 4? Each unique letter is a variable, so here there are 3 variables \(p, q, r\), and the truth table has \(2^3 = 8\) rows. The repeated \(q\) does not count twice.
  • Do we need to memorise the laws of logical equivalence? No. The laws are given on the examination formula page (see formula-sheet).

Statements

A statement (or proposition) is a sentence that is either true or false, but not both.

  • Statements: “6 is odd.” — a statement, and false. “It is raining.” — also a statement; it could be either true or false, and not knowing the value doesn’t stop it having one.
  • Not statements: “\(x\) is odd.” (depends on the unspecified \(x\)), “Is it raining?” (a question), “She is happy.” (not objectively true or false).

We use variables \(p, q, r, \dots\) to represent statements, and the connectives and \(\land\), or \(\lor\), not \(\sim\) to combine them. See logical-connectives.

Worked: translating between English and symbols

Let \(p\) = “it is cold”, \(q\) = “it is snowing”, \(r\) = “it is sunny”.

Into symbolic form:

English Symbolic Note
It is not cold but it is snowing. \(\sim p \land q\) “but” is \(\land\) — the contrast it carries in English is invisible to logic
It is neither snowing nor cold, but it is sunny. \(\sim(q \lor p) \land r \;\equiv\; (\sim q \,\land\sim p) \land r\) “neither … nor” is the negation of an “or” statement; the second form is the De Morgan rewrite of the first

Into English:

Symbolic English
\(\sim q \land p\) It is not snowing and it is cold.
\((p \land q) \lor r\) It is cold and snowing, or it is sunny.

The \(\lor\) in the second one is the inclusive or — a day that is cold, snowing and sunny satisfies it.

Are these equivalent statements? (1) “It is not cold but it is snowing.” (2) “It is snowing and it is not cold.”

Yes — by the commutative law. Symbolically \(\sim p \land q \equiv q \,\land\sim p\). The English word order carries an emphasis the logic does not.

Truth tables

A truth table shows the truth value of a statement form for all possible truth values of its statement variables. With \(n\) variables it has \(2^n\) rows. You should know the truth tables for \(\land\), \(\lor\) and \(\sim\) by heart.

Build them in standard form, so that you are sure you have covered all combinations and it is easy for someone to check your work — the fixed row order is drawn out as a figure in logical-connectives.

Inclusive and exclusive or

\(\lor\) means inclusive or: \(p \lor q\) is true when \(p\) is true, or \(q\) is true, or both.

Sometimes English “or” means “one or the other but not both” — exclusive or, written \(\oplus\) (XOR):

\[p \oplus q \;\equiv\; (p \lor q) \land \big(\sim(p \land q)\big)\]

Setting \(p \oplus q\) between \(p \land q\) and \(p \lor q\) makes the two differences visible:

\(p\) \(q\) \(p \land q\) \(p \oplus q\) \(p \lor q\)
T T T F T
T F F T T
F T F T T
F F F F F

\[p \oplus q \;\not\equiv\; p \lor q \qquad\qquad p \oplus q \;\not\equiv\; p \land q\]

Examples from common English usage: “Would you like red or white wine?” is exclusive and “Would you like milk or sugar with your tea?” is inclusive. Only context distinguishes them — which is precisely learning goal 1.

Order of operations

  1. \(\sim\) first.
  2. \(\land\) and \(\lor\) equal second — use parentheses to specify; if no parentheses, work from left to right.

Worked. Take the statement form \((p \land q) \lor \sim (r \lor p) \land s\). This means

\[\big((p \land q) \lor (\sim (r \lor p))\big) \land s\]

\(\sim\) takes only \((r \lor p)\); the remaining \(\lor\) and \(\land\) are then equal in precedence, so they resolve left to right.

Worked: constructing a truth table

Construct a truth table for \((p \,\land\sim q) \lor (q \land r)\).

There are two ways to lay this out: give each sub-expression its own column (\(\sim q\), then \(p \,\land\sim q\), then \(q \land r\), then the whole thing), or work all at once, writing each column of values directly beneath the part of the expression it evaluates. The figure below uses the column-by-column layout, because a single column can then be checked in isolation.

Figure 1: The truth table for (p ∧ ~q) ∨ (q ∧ r), laid out column by column. The evaluation order is numbered ①②③ beneath — ~q first, then p ∧ ~q, then q ∧ r — and the outlined last column is the final answer. Laid out this way, any one column can be checked in isolation.

Logical equivalence

Given two statement forms, you can show that they are logically equivalent (\(\equiv\)) using a truth table or the laws of logical equivalence. To show that two statement forms are not logically equivalent (\(\not\equiv\)), you need to find a set of truth values for the variables for which the two statement forms have opposite truth values.

Worked: a non-equivalence from one row

Show that \(\sim(p \lor q) \;\not\equiv\; \sim p \lor \sim q\).

Take \(p\) false and \(q\) true:

  • LHS: \(p \lor q\) is \(\mathrm{F} \lor \mathrm{T} = \mathrm{T}\), so \(\sim(p \lor q)\) is false.
  • RHS: \(\sim p \,\lor\sim q\) is \(\mathrm{T} \lor \mathrm{F} = \mathrm{T}\), so it is true.

They differ on this assignment, so they are not logically equivalent. One row is a complete answer — there is no need to fill in the other three.

De Morgan’s Laws

Important logical equivalences for the negations of statements involving “and” and “or”:

\[\sim(p \land q) \equiv \sim p \lor \sim q \qquad\qquad \sim(p \lor q) \equiv \sim p \land \sim q\]

Both halves get negated and the connective flips. The non-equivalence above is what happens when you flip the sign but forget the connective.

Worked: negating an “and” statement

Write down a statement which is logically equivalent to the NEGATION of: “5 is divisible by 2 and 6 is divisible by 2.”

5 is not divisible by 2 or 6 is not divisible by 2.

(The original is \(p \land q\) with \(p\) = “5 is divisible by 2” and \(q\) = “6 is divisible by 2”, so its negation is \(\sim p \,\lor\sim q\). As it happens the negation is true and the original false, but that is not what was asked — the question is about form.)

The laws of logical equivalence

The full table is in logical-equivalence-laws; it is the one on the examination formula page. Two definitions used throughout it:

  • a tautology \(\mathbf{t}\) is a statement that is always true;
  • a contradiction \(\mathbf{c}\) is a statement that is always false.

Worked: two proofs with the laws

Show that \((p \,\land\sim q) \land (\sim p \lor q) \equiv \mathbf{c}\).

\[ \begin{aligned} (p \,\land\sim q) \land (\sim p \lor q) &\equiv (p \,\land\sim q) \;\land\; \sim(p \,\land\sim q) && \text{by De Morgan's law and the double negative law} \\ &\equiv r \,\land\sim r \quad \text{where } r = (p \,\land\sim q) \\ &\equiv \mathbf{c} && \text{by the negation law} \end{aligned} \]

The move that makes it short is recognising \(\sim p \lor q\) as \(\sim(p \,\land\sim q)\) — a whole compound expression standing in for the single letter the law is written with.

Show that \(\sim p \lor (p \land q) \;\equiv\; \sim p \lor q\).

\[ \begin{aligned} \sim p \lor (p \land q) &\equiv (\sim p \lor p) \land (\sim p \lor q) && \text{by the distributive law} \\ &\equiv \mathbf{t} \land (\sim p \lor q) && \text{by the negation law} \\ &\equiv \sim p \lor q && \text{by the identity law} \end{aligned} \]

Worked: one equivalence, by truth table and by the laws

(a) Use a truth table to show that \(\sim\big((\sim p \land q) \lor (\sim p \,\land\sim q)\big) \equiv p\).

\(p\) \(q\) \(\sim p\) \(\sim q\) \(\sim p \land q\) \(\sim p \,\land\sim q\) \((\sim p \land q) \lor (\sim p \,\land\sim q)\) \(\sim\big(\cdots\big)\)
T T F F F F F T
T F F T F F F T
F T T F T F T F
F F T T F T T F

The first column and the last column are identical, so \(\sim\big((\sim p \land q) \lor (\sim p \,\land\sim q)\big) \equiv p\). Marking the two columns that have to match — with a \(\ast\) beneath each — and then stating the verdict in words is how to finish a truth-table equivalence proof. The table alone does not say what it has shown.

(b) Use the laws of logical equivalence to show the same.

There are two complete chains, one six steps and one four. Both are drawn side by side as a figure in logical-equivalence-laws; the short one comes from noticing that \(\sim p\) is a common factor of the two disjuncts and pulling it out with the distributive law before doing anything else.

See also