Chapter 7 - First-Order Logic

7.1 Expert System

Definition

• An expert system utilizes knowledge base and inference engine to emulate the decision-making ability of a human expert

Components

• User Interface: Handles queries from users and provides advice
• Inference Engine: Processes queries and generates answers
• Knowledge Base: Contains facts and rules in a specific domain
  • Collections of facts and rules
  • We can first-order logic!
• Expert: Provides domain knowledge
• Knowledge Engineer: Extracts knowledge from experts

Knowledge Base

• Contains facts and rules in a specific domain
• Extracted from a human expert by a knowledge engineer
• Can be stored in several forms:

1. Inference Rules (If-Then Statements)

IF the collateral is satisfactory AND
the applicant is able to the loan payments AND
the applicant has a good financial situation
THEN
the loan is approved.

2. Decision Tree

• Internal node = question
• Leaf node = label/class

Inference Engine

• Accepts queries from users
• Searches for matched facts in the knowledge base
• Generates appropriate answers
• Performs inference according to ==rules of inference==

Modus Ponens (Rule of Inference)

• Rule: "P implies Q. P is true. Therefore, Q must also be true."

• Notation: p → q, p, ∴ q

• Based on propositional logic

7.2 First-Order Logic (FOL)

Describe objects and their relations

Definition

• Also called predicate logic
• Collection of formal systems
• Extends propositional logic by additionally covering:
  • Predicates — Relations among objects
  • Quantifiers

7.3 Syntax for FOL

Basic Elements

1. Constant Symbols

• Specific objects such as:
  • Person names (Tom)
  • Particular objects (a specific apple)

2. Variable Symbols

• Countably infinite set of unknowns
• Examples: $x, y, a, b, \dots$

3. Function Symbols

• Takes n-tuples of terms (constants, variables, or functions)
• Returns another term
• Notation: f → an object

4. Predicate Symbols

Return either true or false (boolean function), relation among objects

• n-ary predicate defined as a function from tuples of n terms to True/False
• Notation: p → True/False

5. Connective Symbols

• ∨ (or)
• ∧ (and)
• $\to$ (implies)
• ↔ (equivalent)
• ¬ (not)

6. Quantifier Symbols

• $\forall$ (for all/universal quantifier)
• $\exists$ (there exists/existential quantifier)
• Allows statements about entire or some collections of objects rather than enumerating objects by name

7. Equality Symbol

• = (equality)

7.4 Logical Sentences

Atomic Logical Sentences

• Simplest structure in FOL
• A predicate applied to a set of terms
• Format: $Predicate(term_1, term_2, \dots, term_n)$
• Where $term_i$ can be variable or constant

Example 7.1

FOL: $\text{Brother(John, Richard)}$

• Brother(x, y): predicate "x is a brother of y" ← อันนี้ต้องกำหนดมาให้นะ
• Richard and John: constants
• Translation: "John is a brother of Richard"

Example 7.2

FOL: $\text{>(Length(LeftLegOf(Richard)), Length(LeftLegOf(John)))}$

• Length(a): function returning the length of a
• LeftLegOf(b): function returning the left leg of b
• >(x, y): predicate "x is longer than y"
• Richard and John: constants
• Translation: "The length of left leg of Richard is longer than length of left leg of John"

Compound Logical Sentences

• Constructed from multiple atomic sentences using connectives (∨, ∧, ¬, →, ↔)

Example 7.3

FOL:
$\text{Owns(John, Car1) ∧ Owns(John, Car2)}$

• Owns(x, y): predicate "x owns y"
• John, Car1, Car2: constants
• Translation: "John owns Car1 and Car2" or "John owns Car1 and John owns Car2"

7.5 Truth in FOL

Key Concepts

• Sentences are true with respect to a model and an interpretation
• Model: Contains objects and relations among objects
• Interpretation: Specifies referents for:
  • Constant symbols → objects
  • Predicate symbols → relations
  • Function symbols → functional relations → objects

Truth Condition

• An atomic sentence predicate(term1, ..., termn) is true
• If and only if the objects referred by term1, ..., termn are in the relation referred by the predicate

Example 7.4

Given: $P(x)$ be predicate $x=x^2$, domain is all integers

1. $P(0)$:
   • True ($0 = 0^2$) → $P(0)$ is true.
2. $P(1)$:
   • True ($1 = 1^2$) → $P(1)$ is true.
3. $P(2)$:
   • False ($2 \ne 2^2$) → $P(2)$ is false.

Example 7.5

Given: $Q(x, y)$ be predicate "$x + y = x - y$", domain is all integers

1. $Q(0, 0)$:
   • True ($0 + 0 = 0 - 0$)
2. $Q(1, 1)$:
   • False ($1 + 1 \ne 1 - 1$)
3. $Q(2, 0)$:
   • True ($2 + 0 = 2 - 0$)

7.6 Quantifiers in FOL

7.6.1 Universal Quantification ($\forall$)

Basic Form

• Used to describe situations/things true about all objects in the domain
• $\forall x P$ is true if and only if $P$ is true with x being each possible object in the model

Example

• "Everyone is smart" → $\forall x (Smart(x))$
• If domain = {John, Richard}, then equivalent to: Smart(John) ∧ Smart(Richard)

Universal Quantification with Conditions

• Pattern: $\forall x (\text{Condition(x)} \to \text{Property(x)})$

• Example: "Everyone studying at SIIT is smart"
  $\forall x (\text{StudyAt(x, SIIT)} → \text{Smart(x)})$

• Equivalent to: $(\text{StudyAt(John, SIIT)} → \text{Smart(John)}) ∧ (\text{StudyAt(Richard, SIIT)} → \text{Smart(Richard)})$

Common Mistake

• Wrong: $\color{red}$
• This means: "Everyone is studying at SIIT AND everyone is smart"
• Not the intended meaning

คือถ้าเป็น For All ให้ใช้ Implies ($\to$) ในการเชื่อมเด้อออออออ

7.6.2 Existential Quantification ($\exists$)

Basic Form

• Used to state properties of some objects without naming them
• $\exists x P$ is true if and only if $P$ is true for at least one object in the domain

Example

• "Someone is smart" → $\exists x (\text{Smart(x)})$
• If domain = {John, Richard}, then equivalent to: $\text{Smart(John)} ∨ \text{Smart(Richard)}$`

Existential Quantification with Conditions

• Pattern: $∃x (\text{Condition(x)} ∧ \text{Property(x)})$

• Example: "Someone studying at SIIT is smart"
  $∃x (\text{StudyAt(x, SIIT)} ∧ \text{Smart(x)})$

• Equivalent to: $(\text{StudyAt(John, SIIT)} ∧ \text{Smart(John)}) ∨ (\text{StudyAt(Richard, SIIT)} ∧ \text{Smart(Richard)})$

Common Mistake

• Wrong:
  $\color{red} ∃x (\text{StudyAt(x, SIIT)} → \text{Smart(x)})$
• This means: "There exists someone who is smart OR does not study at SIIT"
• Not the intended meaning

คือถ้าเป็น For some ให้ใช้ And ($∧$) ในการเชื่อมเด้อออออออ

7.6.3 Negation of Quantifiers

De Morgan's Rules

• $\forall x \, (\lnot P) \equiv \lnot (\exists x \, P)$
• $\lnot \forall x \, (\lnot P) \equiv \exists x \, (P)$
• $\forall x \, (P) \equiv \lnot (\exists x \, \lnot P)$
• $\exists x \, (P) \equiv \lnot (\forall x \, \lnot P)$

Additional Rules

• $\lnot (\forall x \, P) \equiv \exists x \, (\lnot P)$
• $\lnot (\exists x \, P) \equiv \forall x \, (\lnot P)$

Example 7.6

Given: ICT(x) = "x is an ICT student", ITS336(x) = "x is enrolling in ITS336"

1. "Every ICT student is enrolling in ITS336"
   $∀x (ICT(x) → ITS336(x))$
2. "Some ICT students are enrolling in ITS336"
   $∃x (ICT(x) ∧ ITS336(x))$
3. "There are some non ICT students who are enrolling in ITS336"
   $∃x (¬ICT(x) ∧ ITS336(x))$
4. "There are some ICT students who are not enrolling in ITS336"
   $∃x (ICT(x) ∧ ¬ITS336(x))$

7.7 Nested Quantifiers

Definition

• Multiple quantifiers in a single statement
• Can be thought of as nested loops

Programming Analogy

def check_all(Dx, Dy, P):
	for x in Dx:
		for y in Dy:
			if not P(x,y):
		return False
	return True

Combinations with Same Quantifiers

Both Universal

• $∀x∀y (\text{P(x, y)}) ≡ ∀y∀x (\text{P(x, y)})$
• P(x, y) is true for all pairs of x and y
• Order doesn't matter

Both Existential

• $∃x∃y (\text{P(x, y)}) ≡ ∃y∃x (\text{P(x, y)})$
• P(x, y) is true for at least one pair of x and y
• Order doesn't matter

Mixed Quantifiers (Order Matters!)

Universal then Existential

• $∀x∃y (\text{P(x, y)})$
• For every x, there is at least one y such that P(x, y) is true
• The value of y does not have to be the same for all x

Existential then Universal

• $∃x∀y (\text{P(x, y)})$
• There is at least one x such that P(x, y) is true for every y

Example 7.7

• Question: "There is at least one y such that P(x, y) is true for every x"
• Answer: $∃y∀x (P(x, y))$

Example 7.8

Let ParentOf(x, y) be the predicate '$x$ is a parent of $y$', and Female(x) be the predicate ‘x is a female.' The domain and is the set of all creatures in the world. Translate the following FOL sentence into plain English.

• FOL: ∀y ∃x (Person(y) → (ParentOf(x, y) ∧ Female(x)))
• Equivalent: ∀y (Person(y) → ∃x (ParentOf(x, y) ∧ Female(x)))
• Translation: "Every person has a female parent" or "For every person, there exists a female who is their parent"
  • (LONG) For every creature $y$, if $y$ is a person, there exists at least one $x$ such that $x$ is a parent of $y$ and $x$ is a female.

Example 7.9

Let Student(x) mean "a is a student in the class" and Friend(x, y) mean "x is a friend of y". The domain of x and y is all people. Translate the following English sentence into a logical sentence:

• English: "Every student in the class has at least one friend"
• FOL: $∀x (\text{ Student(x)} → ∃y \text{ Friend(x, y)})$

7.8 Equality

Definition

• Sometimes needed in FOL statements to address identity relation
• term1 = term2 is true under a given interpretation
• If and only if term1 and term2 refer to the same object

Example 7.10

FOL: ∃x∃y (Owns(Mickey, x) ∧ Dog(x) ∧ Owns(Mickey, y) ∧ Dog(y) ∧ ¬(x = y))

• Owns(x, y): predicate "x owns y"
• Dog(x): predicate "x is a dog"
• Translation: "Mickey owns at least two dogs"
• Inequality $¬(x = y)$ ensures x and y are distinct
  • ถ้าไม่มีตัวนี้อยู่ จะเกิดสถานการณ์แบบนี้ได้เลยล่ะ

Example 7.11

FOL: $∀x∃y∀z (\text{Married(x, y)} ∧ (\text{Married(x, z)} → (y = z)))$

Equivalent: $∀x (∃y (Married(x, y) ∧ ∀z (Married(x, z) → (y = z))))$

Translation: "Everyone is married to exactly one person"

• First part: x is married to y
• Second part: y is the unique spouse of x

Example 7.12

Given: L(x, y) = "x loves y", domain is all people

1. "Everybody loves Kitty"
   • $∀x L(x, Kitty)$
2. "Everybody loves somebody"
   • $∀x ∃y L(x, y)$
3. "There is somebody whom everybody loves"
   • $∃y ∀x L(x, y)$
4. "Everyone has someone who loves them"
   • $∀x ∃y L(y, x)$
5. "Everyone loves himself or herself"
   • $∀x L(x, x)$
6. "There is someone who loves no one besides himself or herself"
   • $∃x ∀y (L(x, y) → (x = y))$
7. "Everyone loves everyone except himself/herself"
   • $∀x ∀y ((x ≠ y) → L(x, y))$
   • หรือ ๆ $∀x ∀y ((x ≠ y) → L(x, y) ∧ (x=y)\to ¬L(x,y))$
8. "Kitty loves exactly two people"
   • $∃x ∃y (L(Kitty, x) ∧ L(Kitty, y) ∧ (x ≠ y) ∧ ∀z (L(Kitty, z) → (z = x ∨ z = y)))$
9. "At least one people do not love Kitty"
   • $∃x ¬L(x, Kitty)$
10. "Nobody loves everybody"
    • ¬ (At least one person loves everybody)
    • $∀x ∃y ¬L(x, y)$ or
    • $¬∃x ∀y L(x, y)$

Example 7.13

Given: Lent(x, y) = "x lent some money to y"

1. $Lent(Piglet, Pooh)$
   • "Piglet lent some money to Pooh"
2. ¬(∀x Lent(Pooh, x))
   • "Pooh did not lend money to everyone" or "It is not the case that Pooh lent money to everyone"
   • Cholwich: There exists at least one creature that Pooh did not lend some money to.
3. ∃x∃y (Lent(x, Piglet) ∧ Lent(y, Piglet) ∧ ¬(x = y))
   • "At least two people lent money to Piglet"
4. ∃x (Lent(x, Piglet) ∧ ∀y (Lent(y, Piglet) → (x = y)))
   • "Exactly one person lent money to Piglet"
5. ∀x∀y ((Lent(x, Piglet) ∧ Lent(y, Piglet)) → (x = y))
   • "At most one person lent money to Piglet"