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.

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.

Statements

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

  • Statements: “6 is odd.”, “It is raining.”
  • Not statements: “x is odd.” (depends on x), “Is it raining?” (a question), “She is happy.” (not objectively T/F)

We use variables \(p, q, r, \dots\) to represent statements. See logical-connectives for \(\land, \lor, \sim\).

Truth tables

A truth table shows the truth value of a statement form for every combination of truth values of its variables. If a statement form has \(n\) variables, its truth table has \(2^n\) rows.

Build truth tables in standard form (all combinations covered systematically, e.g. T/T/T, T/T/F, T/F/T, …) so your work is easy to check.

Inclusive vs. exclusive or

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

Exclusive or (\(\oplus\), “one or the other but not both”) is common in English (“Would you like red or white wine?”) but is a different connective:

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

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

Order of operations

  1. \(\sim\) first.
  2. \(\land\) and \(\lor\) equal second — use parentheses to disambiguate; otherwise left to right.

E.g. \((p \land q) \lor \sim(r \lor p) \land s\) means \(((p \land q) \lor (\sim(r \lor p))) \land s\).

Logical equivalence

Two statement forms are logically equivalent (\(\equiv\)) if they have the same truth value for every combination of inputs — shown via a truth table or the laws of logical equivalence (see logical-equivalence-laws). To show they are not equivalent (\(\not\equiv\)), find one combination of truth values where they differ.

De Morgan’s Laws (see logical-equivalence-laws for the full table):

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

In-class activities

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

  • Translate to symbolic form: (1) “It is not cold but it is snowing.” (2) “It is neither snowing nor cold, but it is sunny.”
  • Translate to English: (1) \(\sim q \land p\). (2) \((p \land q) \lor r\).
  • Are “It is not cold but it is snowing” and “It is snowing and it is not cold” equivalent statements?

Activity 2: Construct a truth table for \((p \land \sim q) \lor (q \land r)\).

Activity 3: Show that \(\sim(p \lor q) \not\equiv \sim p \lor \sim q\).

Activity 4: Write a statement logically equivalent to the negation of “5 is divisible by 2 and 6 is divisible by 2.”

Activity 5: Use the laws of logical equivalence to prove:

  • Q2: \((p \land \sim q) \land (\sim p \lor q) \equiv \mathbf{c}\) (a contradiction).
  • Q3: \(\sim p \lor (p \land q) \equiv \sim p \lor q\).

Activity 6 (carries into Lecture 3):

    1. Use a truth table to show \(\sim((\sim p \land q) \lor (\sim p \land \sim q)) \equiv p\).
    1. Use the laws of logical equivalence to show the same.

See also