Phil 2250 11JUN20

Shared on June 11, 2026

Lecture on Predicate‑Logic Derivations

Overview

The instructor guided students through systematic use of predicate‑logic inference rules, emphasizing the importance of correct constant choices, scope management, and the application of quantifier rules. The session mixed explanations of theory with step‑by‑step derivations of example arguments, illustrating common pitfalls and efficient strategies.

Key Concepts

Quantifier Negation

¬∃x φ(x) ⇔ ∀x ¬φ(x)

¬∀x φ(x) ⇔ ∃x ¬φ(x)

Existential Elimination (∃E)

Assume a witness a for ∃x φ(x).

Derive conclusion ψ without referring to a in any open assumption.

a must not appear in any open assumption or the final conclusion.

Universal Introduction (∀I)

From a derivation of φ(x) that contains no assumptions involving x, infer ∀x φ(x).

The chosen constant for x must not appear in any open assumption.

Identity (Equality) Rules

Identity Elimination (EqE): From t₁ = t₂ and a formula containing t₁, replace it with t₂.

Identity Introduction (EqI): t = t.

Conditional Introduction (→I) and Conditional Elimination (→E) (Modus Ponens).

Hypothetical Syllogism (HS): From P→Q and Q→R, infer P→R.

Transposition (Contrapositive): From P→Q infer ¬Q→¬P.

Replacement Rules for predicates and functions, ensuring proper handling of bound variables.

Detailed Notes

1.Quantifier Manipulation*

Demonstrated transforming nested quantifiers with negations, ensuring each application alters only the targeted sub‑formula.

Emphasized the one‑rule‑per‑line rule in formal derivations.

2.Existential Elimination in Practice*

Example: From ∃x (Ux ∧ Wx) and Ux, derive Wx.

Steps:

Assume a such that Ua ∧ Wa. 2. Use ∧E to obtain Ua and Wa. 3. Apply EqE to replace a with the specific individual when needed. 4. Conclude with the desired formula, dropping the assumption.

2.Universal Introduction*

Showed deriving ∀x (Ux ∧ Wx) from ∀x Ux and ∀x Wx by combining them with ∧I and then introducing the universal quantifier.

Highlighted that no constant used in the derivation may appear in the final formula.

4.Identity Rules*

Example: From equality x = y and a predicate P(x), deduce P(y).

Demonstrated the importance of keeping identity assumptions isolated to avoid unintended variable capture.

Conditional and Hypothetical Reasoning

Constructed implications using →I by assuming antecedents and deriving consequents.

Applied HS to chain implications efficiently.

Showed transposition to handle contrapositive arguments, crucial for proofs involving negated consequents.

Common Pitfalls

Incorrect Constant Choice: Choosing a constant already in an open assumption violates ∃E or ∀I.

Scope Errors: Mixing bound and free variables when applying replacement or substitution.

Negation Placement: Misapplying quantifier negation can reverse the intended logical direction.

Worked Example Overview

Premise: ∃x(Ux ∧ Wx)

Goal: ∃x(Ux ∧ Wx) (trivial, but illustrates steps)

Derivation:

∃E → assume a: Ua ∧ Wa

∧E → Ua, Wa

∧I → Ua ∧ Wa

∃I → ∃x(Ux ∧ Wx)

Practice Tips

Plan Ahead: Decide which rule will close the proof and ensure constants meet the criteria.

Check Open Assumptions: Before applying ∃E or ∀I, confirm no forbidden constants appear.

Use Replacement Wisely: Transform predicates only when it simplifies the derivation, not to force a particular shape.

Take‑Away

Mastery of predicate‑logic derivations hinges on a disciplined application of inference rules, careful handling of constants, and a clear strategy for moving from assumptions to conclusions. Regular practice with varied examples consolidates understanding and reduces common errors.

Browse all public notes