Propositional Logic Reasoning

Overview: Styles of reasoning

We cover three:

• Using truth tables
• Using equivalences
• Using inference rules

First two today. These two are simple and familiar, but impractical for proving complicated things. Third one in next two classes. It is more difficult initially, but more useful in the long run.

There are other styles, but most are variations or combinations of these.

For now, we will not mix proof styles. In practice, mixing proof styles makes sense, but it interferes with our current purpose of learning the techniques.

Reasoning with truth tables

• E.g., is (a ∧ b) → c equivalent to (a → c) ∧ (b → c)?
• E.g., show ¬(a ∧ b) is equivalent to ¬a ∨ ¬b. (One of DeMorgan's Laws.)
• E.g., is (a → (a ∨ b)) a tautology, i.e., always true?
• How many rows and columns used in those proofs?
• E.g., a ∧ b is stronger than a ∨ b (and, a ∨ b is weaker than a ∧ b)

Counter-example

• How to prove something isn't a tautology?
• An example truth assignment (row of truth table) that falsifies the formula
• Don't need full truth table, just an appropriate row
• E.g., counter-example for a ∨ (¬ a ∧ b)?
• The reasoning steps: "What truth assignments might falsify the ∨ ..."

Aside: Normal forms

• Disjunctive Normal Form
  • disjunction of conjunctions — or of ands
  • Example — (a ∧ b ∧ ¬ c) ∨ (¬ a ∧ c)
  • Example — "true if this row or this row or …" — Read off true rows of truth table — e.g., a ⊕ b
• Conjunctive Normal Form
  • conjunction of disjunctions — and of ors
  • Example — (a ∨ b ∨ ¬ c) ∧ (¬ a ∨ c)
  • Example — "true if not this row and not this row and …" — Read off false rows of truth table, negating each, use DeMorgan. — e.g., a ⊕ b
• One common use: Minimizing formulas with Karnaugh Maps (cf. ELEC 220).

Reminder: Metavariables vs. propositions

• Propositions (a, b, …) are parts of formulas
• Metavariables (φ, ψ, …) range over formulas
• Example — can state commutativity as φ ∨ ψ ≡ ψ ∨ φ

Reasoning with equivalences

Replacing subformulas based on "replacing equals with equals"

• A familiar numeric example: ((a + b) + 0) × (1 × c) = a × c + b × c
• Similar logic example: ((a ∨ b) ∨ false) ∧ (true ∧ c) = (a ∧ c) ∨ (b ∧ c)
• The similarity is very fundamental — Boolean algebra
• Some useful identities
  • Which identities are "given" is somewhat arbitrary, but for homeworks, use this set
  • Soundness — Don't want to use incorrect/inconsistent identities. How can we prove them correct?
  • Completeness — Which identities sufficient?
• Only useful for proving equivalences — but, can often reword problems as equivalences, e.g., tautologies

Again, for now, we will not mix proof styles.