FOL 13 · Flashcards
Setup
Uses the Spaced Repetition community plugin (same as the Propositional Logic deck).
Question::Answerper line;?on its own line for multi-line answers.
Predicates & quantifiers
What is a predicate?::A statement with variables that is neither true nor false until the variables get values or are quantified. Two ways to turn a predicate into a proposition?::Assign values to all variables, or quantify them. Is “x > 3” a proposition?::No — x is free. What is the domain of discourse?::The set of values a variable may take; a quantified statement has no meaning without it. ∀x P(x) is false when…?::At least one x makes P(x) false — a counterexample. ∃x P(x) is false when…?::P(x) is false for every x in the domain. ∀x P(x) over {a, b, c} as a proposition?::P(a) ∧ P(b) ∧ P(c) ∃x P(x) over {a, b, c} as a proposition?::P(a) ∨ P(b) ∨ P(c) Expand ∀x<0 (x² > 0)::∀x (x < 0 → x² > 0) Expand ∃y>0 (y² = 2)::∃y (y > 0 ∧ y² = 2)
Equivalences
Does ∀ distribute over ∧?::Yes: ∀x(P ∧ Q) ≡ ∀xP ∧ ∀xQ Does ∀ distribute over ∨?::No: ∀x(P ∨ Q) ≢ ∀xP ∨ ∀xQ (only ∀xP ∨ ∀xQ ⇒ ∀x(P ∨ Q)) Does ∃ distribute over ∨?::Yes: ∃x(P ∨ Q) ≡ ∃xP ∨ ∃xQ Does ∃ distribute over ∧?::No: only ∃x(P ∧ Q) ⇒ ∃xP ∧ ∃xQ Mnemonic for distribution?::”∀ loves ∧, ∃ loves ∨” Standard counter-model for non-equivalences?::Domain {a, b}, P = (T, F), Q = (F, T) ∀x(P(x) → A) ≡ ? (x not free in A)::∃x P(x) → A — the quantifier flips ∀x(A → P(x)) ≡ ? (x not free in A)::A → ∀x P(x)
Negation
¬∀x P(x) ≡ ?::∃x ¬P(x) ¬∃x P(x) ≡ ?::∀x ¬P(x) Negation of “All S are P”?::Some S is not P: ∃x(S(x) ∧ ¬P(x)) Negation of “Some S are P”?::No S is P: ∀x(S(x) → ¬P(x)) Negation of “No S is P”?::Some S is P: ∃x(S(x) ∧ P(x)) ¬∀x∃y P(x,y) ≡ ?::∃x∀y ¬P(x,y) ¬∃x∀y P(x,y) ≡ ?::∀x∃y ¬P(x,y)
Translation
“All S are P” in FOL?::∀x(S(x) → P(x)) “Some S are P” in FOL?::∃x(S(x) ∧ P(x)) Which connective pairs with ∀, and which with ∃?::∀ with →, ∃ with ∧ (“All-Arrow, Some-and”) Why not ∀x(S(x) ∧ P(x)) for “All S are P”?::It claims everything in the domain is an S. Why not ∃x(S(x) → P(x)) for “Some S are P”?::It’s true as soon as anything is not an S — almost always true. “None of my friends are perfect”?::¬∃x(F(x) ∧ P(x)) ≡ ∀x(F(x) → ¬P(x)) “Not all rainy days are cold”?::∃d(Rainy(d) ∧ ¬Cold(d)) “Gold and silver ornaments are precious”?::∀x((G(x) ∨ S(x)) → P(x)) — “and” in the subject becomes ∨. “Only S are P”?::∀x(P(x) → S(x)) “Some boys are taller than all girls”?::∃x(boy(x) ∧ ∀y(girl(y) → taller(x, y))) “Every teacher is liked by some student”?::∀x(teacher(x) → ∃y(student(y) ∧ likes(y, x)))
Nested quantifiers
Does order matter for ∀x∀y?::No. Does order matter for ∃x∃y?::No. Does order matter for ∀x∃y vs ∃y∀x?::Yes. Which implies which: ∃y∀x P or ∀x∃y P?::∃y∀x P ⇒ ∀x∃y P (not the converse). ∀x∃y (x + y = 0) over reals?::True (y = −x). ∃y∀x (x + y = 0) over reals?::False. ∃y∀x (x·y = 0) over reals?::True (y = 0). “Exactly one x has P”?::∃x(P(x) ∧ ∀y(P(y) → y = x)), written ∃!x P(x) “At most one x has P”?::∀x∀y((P(x) ∧ P(y)) → x = y) “At least two x have P”?::∃x∃y(x ≠ y ∧ P(x) ∧ P(y))
Resolution
Literal?::A variable or its negation. Clause?::A disjunction of literals. Resolvent of (L ∨ C₁) and (¬L ∨ C₂)?::C₁ ∨ C₂ What does the empty clause □ mean?::Contradiction — derived ⇒ the argument is valid. How do you prove validity by resolution? ? Convert premises to clauses, add the NEGATED conclusion, resolve until you derive the empty clause □. Can you resolve on two complementary pairs at once?::No — exactly one pair per step. “Neither s nor t” as clauses?::Two clauses: ¬s and ¬t.
Inference
Universal Instantiation?::∀x P(x) ∴ P(c) for any c Universal Generalization?::P(c) for an ARBITRARY c ∴ ∀x P(x) Existential Instantiation?::∃x P(x) ∴ P(c) for some NEW constant c Existential Generalization?::P(c) ∴ ∃x P(x) Universal Modus Ponens?::∀x(P(x) → Q(x)), P(c) ∴ Q(c) Universal Modus Tollens?::∀x(P(x) → Q(x)), ¬Q(c) ∴ ¬P(c) Can you get ∃x(P ∧ Q) from ∃xP and ∃xQ?::No — EI needs a fresh constant each time (c and d may differ). “Every CS major takes DM. Ria takes DM. ∴ Ria is a CS major.” Valid?::No — affirming the conclusion.
Extras
Free vs bound variable?::Bound = inside the scope of a quantifier on it; free = not. Free variables mean it’s not a proposition. Scope of ∀x in ∀x P(x) ∨ Q(x)?::Only P(x) — the x in Q(x) is free. Is FOL validity decidable?::No — undecidable, but semi-decidable. Unary predicate on an n-element domain: number of interpretations?::2ⁿ Binary predicate on an n-element domain: number of interpretations?::2^(n²)
Prev ← FOL 12 Practice Problems · Next → FOL 14 Memory Tricks and Traps