Phil 2250 08June26
Shared on June 9, 2026
Logic 101 – Symbolic Logic and Semantics Lecture
Overview
The lecture covers the transition from sentential logic (SL) to predicate logic (PL), focusing on how to evaluate validity, truth‑functional status, and quantificational (Q) status of arguments and sentences. It explains the role of counter‑examples (interpretations) in establishing invalidity, the limitations of truth tables in PL, and the necessity of general reasoning for Q‑truth questions.
Key Concepts
- Truth‑functional Validity (SL)
- An argument is valid iff no truth‑value assignment makes all premises true and the conclusion false.
- Counter‑example: a row in a truth table.
- Quantificational (Q) Validity (PL)
- An argument is Q‑valid iff no interpretation (universe + predicate meanings) makes all premises true and the conclusion false.
- Counter‑example: an interpretation that satisfies premises and falsifies the conclusion.
- Interpretation / Symbolization Key
- Choose a universe of discourse (UD), assign meanings to predicates, and interpret constants.
- Must be verifiable by the audience; use common objects (e.g., natural numbers, birds, TV shows).
- Truth Tables vs. Truth Trees
- Truth tables work for SL (finite, mechanical).
- Truth trees can be used for PL but are not decision procedures; they may fail to close.
- Undecidability of PL
- No algorithm can determine Q‑truth status for all PL sentences (Church’s theorem).
- Requires human‑guided reasoning or proofs.
- Law of the Induction (Lohmann–Hygd) Theorem
- If a PL sentence is true in some interpretation, it can be made true in an interpretation whose UD is the set of positive integers.
- Encourages using ℕ or ℤ⁺ as a standard UD.
Detailed Notes
- From SL to PL
- SL only handles sentences with propositional variables and connectives.
- PL introduces quantifiers (∀, ∃) and predicates with arity > 0.
- Many SL techniques (truth tables) fail because predicates cannot be assigned truth values independently of their arguments.
- Checking Validity
- SL: Build full truth table; find a counter‑example row.
- PL: Construct an interpretation where premises hold and conclusion fails.
- Example: For all x, B(x) → C(x); ∃x(C(x) ∧ D(x)); ∃x D(x). Interpretation with UD = {1,2}, B(1)=B(2)=True, C(1)=True, C(2)=False, D(1)=True, D(2)=False yields premises true, conclusion false.
- Q‑Truth / Q‑Falsity / Q‑Indeterminacy
- Q‑True: True in every interpretation.
- Q‑False: False in every interpretation.
- Q‑Indeterminate: True in some, false in others.
- Example: “∀x (P(x) ∨ ¬P(x))” is Q‑True; “∃x P(x)” can be Q‑indeterminate.
- Constructing Counter‑Examples
- Pick a UD that is easy to describe (natural numbers, birds, TV shows).
- Assign predicates to make premises true and conclusion false.
- Use “empty set” or “universal set” tricks when appropriate.
- Verify by checking each quantified statement under the chosen UD.
- General Reasoning (Proofs) vs. Counter‑Examples
- Proofs are analogous to full truth tables: show a statement holds in every interpretation.
- Counter‑examples are analogous to short truth tables: show a statement fails in some interpretation.
- Practical Advice for Students
- Always provide verifiable interpretations (e.g., ℕ, ℤ⁺, set of birds).
- Avoid personal references (“my friend”) unless the professor can verify.
- Use natural language clarity when constructing interpretations.
- Practice reading PL sentences to identify the main logical operator and the role of each quantifier.
- Homework & Exercises
- Apply counter‑example technique to sentences in chapter 8 (problem sets 1–3).
- Use general reasoning to show sentences are Q‑false.
- Read and analyze the provided examples in the textbook to strengthen intuition.
“The set of positive integers is always a safe choice when constructing interpretations.” – Professor’s note on the Law of Induction theorem.
This lecture equips students with the foundational tools for evaluating logical arguments in predicate logic, emphasizing the shift from mechanical truth‑tables to interpretation‑based reasoning and highlighting the theoretical limits of algorithmic decision procedures in PL.