First Order Logic in AI
Table of Content:
- What is First Order Logic in Artificial intelligence?
- What are the First-Order logic?
- Syntax of First-Order logic.
- Atomic sentences.
- Complex sentences.
- Quantifiers in First-order logic.
- Universal Quantifier.
- Existential Quantifier.
- Properties of Quantifiers.
- Examples of First-Order Logic using quantifiers.
Content Highlight:
First-Order Logic (FOL) in Artificial Intelligence is a formal system used to represent and reason about the properties and relationships of objects. Unlike propositional logic, which deals with simple, true or false statements, FOL includes quantifiers and predicates, allowing for more complex expressions. FOL enables the representation of statements like "All humans are mortal" using variables, constants, functions, and quantifiers (e.g., ∀x (Human(x) → Mortal(x))). It is foundational for knowledge representation, enabling AI systems to perform sophisticated reasoning, infer new information, and solve problems in a wide range of domains.
What is First Order Logic in Artificial intelligence?
First Order Logic (FOL) in Artificial Intelligence is a formal system used to represent and reason about the properties and relationships of objects. Unlike propositional logic, which deals with simple, true or false statements, FOL includes quantifiers and predicates, allowing for more complex expressions. FOL enables the representation of statements like "All humans are mortal" using variables, constants, functions, and quantifiers (e.g., ∀x (Human(x) → Mortal(x))). It is foundational for knowledge representation, enabling AI systems to perform sophisticated reasoning, infer new information, and solve problems in a wide range of domains. Consider the following sentence, which cannot be represented using Propositional Logic (PL):
- "Some humans are intelligent", or
- "Sachin likes cricket."
What are the First-Order logic?
First-Order Logic (FOL):
- First-Order Logic is a method of knowledge representation in artificial intelligence, extending beyond propositional logic.
- FOL is expressive enough to represent natural language statements concisely.
- Also known as Predicate Logic or First-Order Predicate Logic, it is a powerful language that can describe objects and the relationships between them.
- Unlike propositional logic, FOL assumes the world contains:
- Objects: Examples include A, B, people, numbers, colors, theories, squares, pits, wumpus, etc.
- Relations: Unary relations such as "is red," "is round," or n-ary relations like "is the sister of," "is adjacent to," "has color," "comes between," etc.
- Functions: Examples include "father of," "best friend of," "third inning of," "end of," etc.
- Similar to natural language, FOL consists of two main parts:
- Syntax: The rules that define the structure of sentences.
- Semantics: The meaning of the sentences.
Syntax of First-Order logic:
The syntax of First-Order Logic (FOL) specifies which combinations of symbols form valid logical expressions. The fundamental syntactic elements of FOL are symbols, which allow us to write statements in a concise, shorthand notation.
| Constant: | 1, 2, A, John, Mumbai, cat,.... |
|---|---|
| Variables: | x, y, z, a, b,.... |
| Predicates: | Brother, Father, >,.... |
| Functions: | sqrt, LeftLegOf, .... |
| Connectives: | ∧, v, ¬, ⇒, ⇔ |
| Equality: | == |
| Quantifier: | ∀, ∃ |
Atomic sentences:
Atomic sentences are the simplest expressions in First-Order Logic (FOL). They are created by combining a predicate symbol with a sequence of terms enclosed in parentheses.
We can represent atomic sentences in the format: Predicate(term1, term2, ..., term n).
Examples:
- Ravi and Ajay are brothers: Brothers(Ravi, Ajay)
- Chinky is a cat: Cat(Chinky)
Complex Sentences:
Complex sentences are formed by combining atomic sentences using connectives.
First-Order Logic (FOL) statements can be divided into two parts:
- Subject: The main part of the statement.
- Predicate: A relation that connects two atoms in a statement.
Consider the statement: "x is an integer." It consists of two parts: the first part, "x," is the subject of the statement, and the second part, "is an integer," is the predicate.
Quantifiers in First-order logic:
- A quantifier in First-Order Logic is a language element that introduces quantification, specifying the quantity of objects in the universe of discourse.
- Quantifiers determine the range and scope of variables in logical expressions. There are two main types of quantifiers:
- Universal Quantifier: Denoted by symbols like "∀" (for all, everyone, everything), it asserts that a statement holds for all elements in the domain.
- Existential Quantifier: Denoted by symbols like "∃" (for some, at least one), it asserts that there exists at least one element in the domain for which the statement holds.
Universal Quantifier:
The universal quantifier, denoted by the symbol "∀", is used in logical representation to indicate that a statement holds true for every instance of a particular thing or for everything within its scope.
In the universal quantifier, we use the implication "→". For a variable x, "∀x" is read as:
- For all x
- For each x
- For every x
Example:
All man drink coffee. Let the variable x represent a cat. In the universe of discourse (UOD), the statement "all x" can be represented as:
∀x man(x) → drink (x, coffee).
It is read as: "For all x, where x is a person who drinks coffee."
Existential Quantifier:
Existential quantifiers are a type of quantifier that express that a statement within its scope is true for at least one instance of something.
It is denoted by the logical operator "∃", which resembles an inverted E. When used with a predicate variable, it is called an existential quantifier.
Note: In existential quantification, we always use the AND or conjunction symbol "∧".
- There exists a 'x.'
- For some 'x.'
- For at least one 'x.'
Example:
Some boys are intelligent.
∃x: boys(x) ∧ intelligent(x)
It is read as: "There are some x where x is a boy who is intelligent."
Points to remember:
- The main connective for universal quantifier ∀ is implication →.
- The main connective for existential quantifier ∃ is and ∧.
Properties of Quantifiers:
- In universal quantification, ∀x∀y is similar to ∀y∀x.
- In existential quantification, ∃x∃y is similar to ∃y∃x.
- ∃x∀y is not similar to ∀y∃x.
Examples of First-Order Logic (FOL) using quantifiers:
- All birds fly.
Predicate: fly(x)
Representation: ∀x bird(x) → fly(x) - Every man respects his parent.
Predicate: respects(x, y)
Representation: ∀x man(x) → respects(x, parent) - Some boys play cricket.
Predicate: play(x, y)
Representation: ∃x boys(x) → play(x, cricket) - Not all students like both Mathematics and Science.
Predicate: like(x, y)
Representation: ¬∀x [student(x) → like(x, Mathematics) ∧ like(x, Science)] - Only one student failed in Mathematics.
Predicate: failed(x, y)
Representation: ∃x [student(x) → failed(x, Mathematics) ∧ ∀y [¬(x==y) ∧ student(y) → ¬failed(x, Mathematics)]]
Free and Bound Variables:
Free Variable: A variable is considered a free variable in a formula if it appears outside the scope of any quantifier.
Example: In ∀x ∃y [P(x, y, z)], z is a free variable.
Bound Variable: A variable is considered a bound variable in a formula if it appears within the scope of a quantifier.
Example: In ∀x [A(x) ∧ B(y)], both x and y are bound variables.