11. First-Order Logic 1 Flashcards
What is First-Order Logic (FOL)?
A logical system that extends propositional logic by introducing objects, properties, relations, and functions.
How does FOL improve upon propositional logic?
It allows the representation of objects, properties, and relationships, making it more expressive.
What are the four key components of FOL?
- Objects (individual entities) 2. Properties (distinguishing characteristics) 3. Relations (connections between objects) 4. Functions (mapping inputs to outputs).
What is an example of an object in FOL?
Human1, RR1 (a robot), Sq11 (a square).
What is an example of a property in FOL?
Red(RR1) (RR1 is red), Robot(RR1) (RR1 is a robot).
What is an example of a relation in FOL?
Same-type(RR1, RB2) (RR1 and RB2 are of the same type).
What is an example of a function in FOL?
Location(RR1, Step0) = Sq11 (At step 0, RR1 is in square 11).
What are the basic logical connectives in FOL?
∧ (AND), ∨ (OR), → (IMPLIES), ¬ (NOT), ⇔ (BICONDITIONAL), = (EQUALITY).
What are the two types of quantifiers in FOL?
Existential quantifier (∃) and Universal quantifier (∀).
What does the existential quantifier (∃) mean?
It states that a property or relation holds for at least one object. Example: ∃x: Square(x) ∧ Unsafe(x) means “There is at least one unsafe square.”
What does the universal quantifier (∀) mean?
It states that a property or relation holds for all objects in the domain. Example: ∀x: Robot(x) → HasBattery(x) means “All robots have a battery.”
What is a common mistake when using existential quantifiers?
Using implication (→) instead of conjunction (∧). Example: ∃x: Square(x) → Free(x) incorrectly means “There exists an object such that if it is a square, then it is free.” Instead, use ∃x: Square(x) ∧ Free(x).
What is a common mistake when using universal quantifiers?
Using them for absolute statements when context is needed. Example: ∀x: Unsafe(x) incorrectly implies every object in the world is unsafe.
What happens if you switch the order of universal quantifiers?
The meaning remains unchanged: ∀x ∀y: P(x, y) ≡ ∀y ∀x: P(x, y).
What happens if you switch the order of existential quantifiers?
The meaning remains unchanged: ∃x ∃y: P(x, y) ≡ ∃y ∃x: P(x, y).
What happens if you switch the order of a universal and existential quantifier?
It changes the meaning. ∀x ∃y: Loves(x, y) means “Everyone loves someone,” while ∃y ∀x: Loves(x, y) means “There is someone who is loved by everyone.”
How does FOL handle equality?
FOL allows explicit equality statements such as x = y or x ≠ y to distinguish objects.
How can you translate “Every gardener likes the sun” into FOL?
∀x: Gardener(x) → Likes(x, Sun).
How can you translate “No purple mushroom is poisonous” into FOL?
∀x: (Mushroom(x) ∧ Purple(x)) → ¬Poisonous(x) or ¬∃x: (Mushroom(x) ∧ Purple(x) ∧ Poisonous(x)).
How can you express “There are exactly two purple mushrooms” in FOL?
∃x ∃y: (Mushroom(x) ∧ Purple(x) ∧ Mushroom(y) ∧ Purple(y) ∧ (x ≠ y)) ∧ ∀z: (Mushroom(z) ∧ Purple(z)) → (z = x ∨ z = y).
