Phil 2250 10JUN26

Shared on June 10, 2026

Logic 2 – Proof Techniques in Predicate Logic

Overview

A lecture that reviews quantifier rules in predicate logic, explains why the rules preserve truth, and demonstrates derivation strategies. The speaker emphasizes the importance of keeping the main logical operator in focus, the role of constants versus variables, and the necessary conditions for the more complex rules (Universal Introduction and Existential Elimination). Practical examples illustrate how to construct derivations for typical arguments.

Key Concepts

Existential Introduction (∃I) Replaces a constant with a variable and adds an existential quantifier. Must be the main logical operator of the derived sentence.

Truth Preservation of ∃I Constants refer to existing objects; introducing an existential asserts that “at least one” object exists.

Universal Introduction (∀I) Replaces a constant with a variable that is arbitrary (not assumed in an open assumption and not present in the final sentence). Conditions:

Constant not in any open assumption.

Constant not in the derived sentence.

Existential Elimination (∃E) Uses an existential premise to assume an arbitrary constant and derive a conclusion that does not mention that constant. Conditions:

New constant not in any open assumption.

New constant not already in the premise.

Conclusion cannot contain that constant.

Rule Application Order Rules must be applied such that the derived sentence’s main logical operator matches the rule (e.g., cannot apply ∃I to a conjunction).

Derivation Strategy Start with the goal, identify its main operator, and work backward using the most suitable rule (∃I, ∀I, ∀E, →I/E, ∨I/E, etc.). Keep track of variables and constants carefully to avoid violating conditions.

Detailed Notes

1.Existential Introduction*

Example: From G(B) (B has property G) conclude ∃x G(x).

The constant B is replaced by a variable x.

Truth‑preserving because B exists by virtue of being a constant.

2.Main Logical Operator Matters*

If a sentence is a conjunction, applying ∃I only to one conjunct is invalid; the resulting sentence would still have a conjunction as the main operator.

3.Derivation Example – From Two Premises to an Existential Conclusion*

Premises: ∀x Fx → Gx, ∀x Gx → Bx.

Goal: ∃x (Fx ∧ Bx).

Steps:

Use →I to derive Fx → Gx. 2. Use ∃I on the consequent Gx to obtain ∃x Gx. 3. Apply ∀E to obtain Gx for a particular x. 4. Combine with Fx via ∧I, then ∃I again.

Universal Introduction

Can only introduce ∀x φ(x) when the constant chosen (to be replaced by x) is not tied to any open assumption and does not appear in the final formula.

Violating this leads to invalid arguments (e.g., inferring “Everyone wears a cape” from “Batman wears a cape”).

Existential Elimination

Illustrated with an argument about Batman:

Premise: ∃x (Town(x) ∧ Scared(x)).

Cannot assume a constant already in use (e.g., Batman) as the witness because it may introduce extra information.

Must introduce a fresh constant (e.g., c) and derive a conclusion that does not mention c.

Derivation Practice

Emphasized that derivations in predicate logic are more involved than propositional logic due to quantifiers.

Recommended systematic checking of conditions for each rule, especially in complex proofs.

Use of Replacement Rules

Not used in early derivations to ensure skill in pure quantifier manipulation.

Replacement rules are introduced later to simplify complex expressions (e.g., moving negations inside quantifiers).

Examples of Complex Derivations

Proof that ∀x (Fx → Gx) ⊢ ∃x (Fx ∧ Gx) requires:

Assume arbitrary a. 2. From ∀x (Fx → Gx) get Fa → Ga via ∀E. 3. Assume Fa. 4. Derive Ga using →E. 5. Conclude Fa ∧ Ga via ∧I. 6. Introduce ∃I to obtain the final conclusion.