Phil 2250 09JUN26

Shared on June 9, 2026

Lecture Notes on Quantificational Logic

Overview

This lecture covered the syntax and semantics of first‑order logic (FOL) with a focus on:

Reading and simplifying negated existentials and universal sentences

Understanding q‑truth (truth in every interpretation) and q‑false (false in every interpretation)

Quantifier order and its effect on sentence meaning

Quantificational equivalence and consistency

Quantificational entailment and validity

Illustrative examples and common pitfalls

The instructor interleaved examples from natural language and formal logic, occasionally reflecting on the difficulty of parsing complex sentences and the importance of methodical interpretation.

Key Concepts

Concept	Definition	Example
Negated Existential	`¬∃x P(x)` is equivalent to `∀x ¬P(x)`	“There is no student who fails the exam” → “Every student passes the exam”
Double Negation	`¬¬φ` is equivalent to `φ`	“It is not true that it is not raining” → “It is raining”
Q‑Truth / Q‑False	A sentence is q‑true if it is true in every interpretation; q‑false if false in every interpretation	`∀x (P(x) → P(x))` is q‑true; `∃x P(x) → P(x)` is not q‑true
Quantifier Scope	Order of `∀` and `∃` changes meaning	`∃x ∀y (P(x) ∧ Q(y))` vs `∀y ∃x (P(x) ∧ Q(y))`
Quantificational Equivalence	Two sentences that have the same truth value in every interpretation	`∀x (P(x) → Q(x))` ≡ `¬∃x (P(x) ∧ ¬Q(x))`
Consistency / Inconsistency	A set of sentences is consistent if there is an interpretation making all true; otherwise inconsistent	`{∃x P(x), ∀x ¬P(x)}` is inconsistent
Entailment / Validity	Γ ⊨ φ iff every interpretation that makes all sentences in Γ true also makes φ true	`{∀x P(x)} ⊨ ∃x P(x)` is valid

Detailed Notes

1. Simplifying Negated Existential Statements

Convert ¬∃x P(x) → ∀x ¬P(x) to avoid nested negations.

Example: “If everything is (f), then nothing is (g)” becomes “For all (x), if (f(x)) then not (g(x))”.

2. Double Negation in FOL

The class of q‑true sentences often relies on eliminating double negations.

Example: ¬¬∃x P(x) simplifies to ∃x P(x); this reduces complexity during evaluation.

3. Evaluating q‑Truth and q‑False

Q‑True: Evaluate all possible interpretations; if the sentence holds in each, it is q‑true.

Q‑False: If the sentence is false in every interpretation, it is q‑false.

Example: ∀x (f(x) ∨ g(x)) is q‑true because the antecedent f(x) guarantees at least one truth value.

4. Quantifier Order Matters

The lecture emphasized that moving an existential outside of a consequent can change meaning.

∃x ∀y (P(x) → Q(y)) ≠ ∀y ∃x (P(x) → Q(y)).

Demonstrated with a concrete counterexample using domain {1,2} and predicates defined on parity.

5. Demonstrating Quantificational Equivalence

Use logical equivalences such as:

¬∃x (P(x) ∧ ¬Q(x)) ↔ ∀x (P(x) → Q(x))

∃x (P(x) ∧ Q(x)) ↔ ¬∀x (¬P(x) ∨ ¬Q(x))

Proof strategy: Assume one side true and deduce the other; then assume false and deduce false.

6. Consistency Checks

Consistent Example: ∃x P(x) and ∀x (P(x) → Q(x)) can both be true if there is at least one (x) with (P(x)).

Inconsistent Example: ∃x P(x) and ∀x ¬P(x) cannot coexist in any interpretation.

Procedure: Construct an interpretation that satisfies all premises or show that such construction is impossible.

7. Entailment & Validity

To prove entailment: use general reasoning—show that if all premises are true, the conclusion must be true.

To prove non‑entailment: provide a counter‑interpretation where premises are true but conclusion is false.

Example: {∀x (f(x) → g(x)), ∀x (h(x) → g(x))} does not entail {∃x (h(x) ∧ f(x))}—counterexample with empty domain or predicates.

8. Reading Complex Sentences

Break sentences into nested sub‑sentences; evaluate from innermost outward.

Use equivalence transformations (e.g., material implication → disjunction) to clarify meaning.

Example: ∃x (P(x) → ∀y Q(y)) is always true because you can choose an (x) that does not satisfy (P(x)).

9. Common Pitfalls

Misreading the scope of quantifiers, especially in nested implications.

Confusing material conditional with causal conditional; in FOL, A → B is equivalent to ¬A ∨ B.

Ignoring the distinction between q‑truth and truth under a specific interpretation.

Summary

The lecture systematically guided through the mechanics of translating, simplifying, and interpreting first‑order logical sentences. By practicing quantifier manipulation, consistency checks, and entailment proofs, students gain the tools to analyze complex logical arguments rigorously.

Browse all public notes