Using First-Order Logic
Assertions and Queries in First-Order Logic
1. Assertions
•In FOL, TELL(KB, sentence) is used to add a sentence to the knowledge base (KB).
•These sentences are known as assertions.
•Example:
•TELL(KB, King(John)) → Adds the fact "John is a king".
•TELL(KB, Person(Richard)) → Adds the fact "Richard is a person".
•TELL(KB, ∀x King(x) ⇒ Person(x)) → Adds the rule "All kings are persons".
2. Queries
•We can ask whether a sentence is entailed by the KB using ASK.
•Example:
•ASK(KB, King(John)) → Returns true, as it was added.
•ASK(KB, Person(John)) → Returns true because John is a King, and all Kings are Persons (by rule).
3. Quantified Queries
•Example: ASK(KB, ∃x Person(x))
•Meaning: "Is there any x such that x is a person?"
•Answer: true, but doesn't give who.
4. Variable Binding with ASKVARS
•Use ASKVARS(KB, Person(x)) to get specific values of x.
•Output: {x/John}, {x/Richard} → These are called substitutions or bindings.
II. The Kinship Domain
1. Objects & Predicates
•The domain here is people.
•We describe relationships and attributes using predicates.
Unary Predicates: These describe properties of individuals.
•Male(x) — x is a male.
•Female(x) — x is a female.
Binary Predicates: These describe relationships between two people.
•Parent(x, y) — x is a parent of y.
•Sibling(x, y) — x and y are siblings.
•Spouse(x, y) — x is married to y.
•Others: Brother, Sister, Child, Husband, Wife, Grandparent, etc.
2. Definitions Using First-Order Logic (FOL)
Mother
Formula:
∀m, c : Mother(c) = m ⇔ Female(m) ∧ Parent(m, c)
Explanation:
A person m is the mother of c if and only if m is female and is a parent of c. This defines the
Mother function using two simpler predicates: Female and Parent.
Husband
Formula:
∀w, h : Husband(h, w) ⇔ Male(h) ∧ Spouse(h, w)
Explanation:
A person h is the husband of w if and only if h is male and is the spouse of w. It defines "husband" as a
gendered role in marriage.
Parent & Child Relationship
Formula:
∀p, c :Parent(p, c) ⇔ Child(c, p)
Explanation:
This defines that Parent and Child are inverse relations. If p is a parent of c, then c is a child of p.
Grandparent
Formula:
∀g, c :Grandparent(g, c) ⇔ ∃p Parent(g, p) ∧ Parent(p, c)
Explanation:
A person g is a grandparent of c if there exists a person p such that g is a parent of p, and p is a parent of c.
This expresses indirect relationships using transitive logic.
Sibling
Formula:
∀x, y : Sibling(x, y) ⇔ x ≠ y ∧ ∃p Parent(p, x) ∧ Parent(p, y)
Explanation:
Two people x and y are siblings if they are not the same person, and they share at least one parent.
This rules out self-siblinghood and emphasizes shared parenthood.
3. Axioms vs Theorems
•Axioms: These are basic facts or definitions we assume as true in the domain. Example: The
definition of Sibling or Parent.
•Theorems: These are logically entailed from axioms. We derive them using rules of inference.
Example Theorem:
∀x, y: Sibling(x, y) ⇔ Sibling(y, x)
Explanation: Siblinghood is a symmetric relation. If x is a sibling of y, then y must also be a sibling
of x.
III. Numbers in First-Order Logic
1. Core Concepts
•Constant symbol: 0 — represents the number zero.
•Function symbol: S(n) — successor function, gives next number.
•Predicate: NatNum(n) — true if n is a natural number.
2. Axioms for Natural Numbers
•NatNum(0) — Zero is a natural number.
•∀n NatNum(n) ⇒ NatNum(S(n)) — If n is a natural number, its successor is also a
natural number.
This defines the set of natural numbers recursively:
•0
•S(0) → 1
•S(S(0)) → 2
•and so on...
3. Constraints on Successor Function
•∀n 0 ≠ S(n) — Zero is not the successor of any number.
•∀m, n m ≠ n ⇒ S(m) ≠ S(n) — The successor function is injective, meaning no two
different numbers can have the same successor.
These constraints ensure a clear, ordered structure to natural numbers.
4. Recursive Definition of Addition
•Base Case:
∀m NatNum(m) ⇒ +(0, m) = m
→ Adding 0 to any number m gives m.
•Recursive Case:
∀m, n NatNum(m) ∧ NatNum(n) ⇒ +(S(m), n) = S(+(m, n))
→ To add S(m) to n, first add m to n, then take the successor of that result.
5. Syntactic Sugar
•Writing S(n) as n + 1 makes expressions easier to read.
•Example:
(m + 1) + n = (m + n) + 1
→ Addition is associative in this recursive structure.
This recursive definition lets us later build multiplication (as repeated addition), exponentiation
(as repeated multiplication), and other arithmetic operations.
IV. Sets in First-Order Logic
1. Vocabulary and Operators
•Predicate: Set(s) — true if s is a set.
•Membership: x ∈ s — x is an element of s.
•Subset: s1 ⊆ s2 — s1 is a subset of s2.
•Functions:
•s1 ∪ s2 — union of two sets.
•s1 ∩ s2 — intersection.
•{x|s} — set formed by adding x to set s.
2. Set Axioms and Meanings
Set Definition
∀s Set(s) ⇔ (s = { }) ∨ (∃x, s2 Set(s2) ∧ s = {x|s2})
→ A set is either empty, or built by adding an element to an existing set.
Empty Set
¬∃x, s {x|s} = { }
→ You can't form the empty set by adding an element.
Idempotency (No duplicates)
∀x, s x ∈ s ⇔ s = {x|s}
→ Adding an element that's already present doesn't change the set.
Membership Rule
∀x, s x ∈ s ⇔ ∃y, s2 (s = {y|s2} ∧ (x = y ∨ x ∈ s2))
→ x is a member of a set if it was either just added, or was already in the set.
Subset
∀s1, s2 s1 ⊆ s2 ⇔ (∀x x ∈ s1 ⇒ x ∈ s2)
→ All elements of s1 are in s2.
Set Equality
∀s1, s2 s1 = s2 ⇔ (s1 ⊆ s2 ∧ s2 ⊆ s1)
→ Two sets are equal if they contain exactly the same elements.
Intersection
∀x, s1, s2 x ∈ (s1 ∩ s2) ⇔ (x ∈ s1 ∧ x ∈ s2)
→ An element is in the intersection if it's in both sets.
Union
∀x, s1, s2 x ∈ (s1 ∪ s2) ⇔ (x ∈ s1 ∨ x ∈ s2)
→ An element is in the union if it's in at least one of the sets.
V. Lists in First-Order Logic
1. Core Concepts
•Predicate: List(l) — true if l is a list.
•Constant: Nil — represents the empty list.
Functions:
•Cons(x, l) — creates a new list by adding x at the front of l.
•Append(l1, l2) — joins two lists.
•First(l) — gets the first item in the list.
•Rest(l) — gets the list minus the first element.
Predicate:
•Find(x, l) — true if x is found in list l.
2. Syntax Sugar Examples
•Cons(x, Nil) is written as [x] → list with one element.
•Cons(A, Cons(B, Cons(C, Nil))) is written as [A, B, C].
This makes lists easier to read and write.
3. Explanation: Lists vs Sets
•Lists are ordered: [1, 2] ≠ [2, 1]
•Lists can contain duplicates: [1, 1] is valid
•Sets are unordered and don’t allow duplicates