0% found this document useful (0 votes)
96 views16 pages

Using First-Order Logic

The document explains the use of First-Order Logic (FOL) for assertions and queries, detailing how to add facts to a knowledge base and ask questions about them. It covers the kinship domain, defining relationships using predicates, and discusses axioms and theorems in FOL. Additionally, it addresses numbers, sets, and lists in FOL, including their definitions, operations, and properties.

Uploaded by

Nidhi Rao
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
96 views16 pages

Using First-Order Logic

The document explains the use of First-Order Logic (FOL) for assertions and queries, detailing how to add facts to a knowledge base and ask questions about them. It covers the kinship domain, defining relationships using predicates, and discusses axioms and theorems in FOL. Additionally, it addresses numbers, sets, and lists in FOL, including their definitions, operations, and properties.

Uploaded by

Nidhi Rao
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 16

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

You might also like