Phil 2250 15JUN26
Shared on June 15, 2026
Partial Decision Procedure and Truth Functional Expansions in Predicate Logic
Overview
The lecture explains how, although full predicate logic (PL) is undecidable, a partial decision procedure exists for a large and useful fragment. It also introduces truth functional expansions, a systematic method for transforming quantified formulas into finite propositional formulas that can be evaluated with truth tables. Finally, the talk touches on Tarski’s formal notion of truth and the role of satisfaction in defining truth for PL.
Key Concepts
Concept | Definition / Significance |
|---|---|
Undecidability of PL | No algorithm can decide the truth of all PL sentences. |
Partial Decision Procedure | An algorithm that can decide Q‑true, Q‑false, or Q‑indeterminate for certain classes of sentences. |
Bernays–Schönfinkel Class | Sentences that are existential–universal (∃∀) with only unary predicates and no function symbols. |
Q‑true / Q‑false / Q‑indeterminate | Quantificational truth status: true in all interpretations, false in all, or varies. |
Truth Functional Expansion | Replace each quantifier with a finite disjunction/conjunction over a chosen set of constants, turning the formula into an atomic PL sentence (no remaining quantifiers). |
Truth Table Analysis | Evaluate the expanded sentence on all valuations of the atomic predicates; from the table derive Q‑status. |
T‑sentences | For a language ℒ, “ p is true iff p” (in ℒ). These capture the truth conditions of every sentence. |
Satisfaction | A recursive notion that tells whether a formula (not necessarily a sentence) holds in a given interpretation under a variable assignment. |
Variable Assignment | Mapping from variables to elements of the universe; needed to interpret open formulas. |
Detailed Notes
1. Decidability Landscape
PL is undecidable – no algorithm can decide every sentence.
- Partial decision procedure (Bernays & Schönfinkel, 1928):
- Works for sentences that are ∃∃…∀∃… (no function symbols, only unary predicates).
- Relies on the fact that for such sentences, truth can be decided by checking interpretations with at most 2 k elements, where k is the number of distinct unary predicates.
2. Truth Functional Expansions
1.Choose a finite set of constants*
- Must include any constants already in the sentence.
- Add enough new constants to reach the required universe size (e.g., 2 k).
- Replace quantifiers
- ∀x φ(x) → φ(a) ∧ φ(b) ∧ … over chosen constants.
- ∃x φ(x) → φ(a) ∨ φ(b) ∨ …
- Result: An atomic PL sentence (no quantifiers), still potentially involving predicates and constants.
Example
Sentence: ∀x F(x)
Expansion with constants a, b: F(a) ∧ F(b)
3. Using Truth Tables
- Construct a truth table for the expanded sentence, treating each atomic predicate–constant pair as an independent Boolean variable.
- Q‑true: all rows make the formula true.
- Q‑false: all rows make it false.
- Q‑indeterminate: some rows true, some false.
Practical Tips
- When the expanded sentence is long, use shortened truth tables that only record rows needed to determine Q‑status.
- For single‑place predicates, a universe of 2 k constants suffices; larger universes yield the same results.
4. Limitations
- Truth functional expansions do not provide a decision procedure for sentences containing multi‑place predicates (e.g., R(x, y)).
- They also cannot decide semantic properties like consistency or entailment for arbitrary sets of sentences.
5. Tarski’s Theory of Truth
- T‑sentence schema: “
pis true iffp” for every sentence p of the language.
- Adequacy: A definition of truth for a language must be able to derive all its T‑sentences.
- Satisfaction vs. Truth
- Satisfaction is defined recursively for every formula (open or closed).
- A sentence is true on an interpretation iff every variable assignment satisfies it.
- This avoids assigning truth values to predicates themselves (predicates have no truth value; they are satisfied or not).
Recursive Satisfaction Rules (simplified)
- Atomic:
P(t₁,…,tₙ)is satisfied iff the tuple of denotations of the terms lies in the extension of P.
- Negation:
¬φsatisfied iff φ is not satisfied.
- Conjunction:
φ ∧ ψsatisfied iff both φ and ψ are satisfied.
- Disjunction / Conditional / Biconditional – analogous.
- Existential:
∃x φ(x)satisfied iff there is some element in the universe such that φ(x) is satisfied under an assignment that maps x to that element.
- Universal:
∀x φ(x)satisfied iff for every element in the universe, φ(x) is satisfied under an assignment that maps x to that element.
6. Practical Takeaways for the Course
- Expand any PL sentence that fits the Bernays–Schönfinkel class to a finite set of constants.
- Construct a truth table for the expansion; read off Q‑status immediately.
- Remember the method fails for sentences with multi‑place predicates.
- Use the concept of satisfaction when working with open formulas or when you need a formal semantics.
- Tarski’s framework underlies the entire semantic treatment of PL and explains why truth is defined relative to an interpretation.
Note: Non‑logical content (e.g., discussions about plushies or sports) was omitted to keep the summary focused on the lecture material.