Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is First-Order Logic (FOL) in Artificial Intelligence?
2.1.
Example
3.
Syntax and Notations of First-Order Logic
3.1.
Predicates
3.2.
Variables
3.3.
Constants 
3.4.
Quantifiers
3.5.
Logical Connectives
4.
Quantifiers in First-Order Logic
4.1.
Universal Quantifier (∀): 
4.2.
Existential Quantifier (∃):
5.
Rules of Inference in First-Order Logic
5.1.
1. Modus Ponens 
5.2.
2. Modus Tollens  
5.3.
3. Universal Instantiation 
5.4.
4. Universal Generalization  
5.5.
5. Existential Instantiation
5.6.
6. Existential Generalisation 
6.
Unification in First-Order Logic
6.1.
Conditions for Unification
6.2.
Pseudocode of Unification
6.3.
Example
6.3.1.
Comparison
6.3.2.
Substitution Variable
6.3.3.
Unifying Variables
6.3.4.
Applying Substitutions
6.3.5.
Unified Expression
7.
Resolution in First-Order-Logic
7.1.
Steps for Resolution
7.2.
Example
7.3.
Steps to Resolve
8.
First-Order Logic VS Propositional Logic
9.
Frequently Asked Questions
9.1.
How does First-Order Logic apply to knowledge representation? 
9.2.
What are the limitations of First-Order Logic? 
9.3.
How does First-Order Logic apply to knowledge representation? 
10.
Conclusion
Last Updated: Mar 27, 2024
Easy

First-Order Logic in Artificial Intelligence

Author Pallavi singh
2 upvotes
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

First-Order Logic (FOL) is a logical way of allowing us to use statements to express relationships between things. It goes beyond fundamental logic by allowing us to talk about individual items by using variables and quantifiers. Based on what we already know, First-Order Logic helps us discover new knowledge or facts about a family. First-Order Logic is widely used in the field of Artificial Intelligence as a critical tool for tackling real-world issues.

First-Order Logic in Artificial Intelligence

Let's talk about First-Order Logic in Artificial Intelligence in brief.          

What is First-Order Logic (FOL) in Artificial Intelligence?

First-Order Logic, also known as First-Order Predicate Calculus or First-Order Predicate Logic, adds quantifiers, variables, and predicates to propositional logic.

Imagine having a magical language that allows you to explain and understand things in a very structured manner. In Artificial Intelligence, this magical language is known as First-Order Logic.

Simple statements may be used for conveying information about items and their characteristics. In this language. You may say, "All dogs bark," or "Every bird can fly." These statements serve as building blocks for understanding how things function in the real world.

First-Order Logic also enables you to discuss the relationships between objects. You can say something like, "If you study hard, then you will get good marks," or "If it's sunny, then I will not go for a movie". These statements can help you in making logical relationships between various types of information.

We may use FOL to connect all of these statements and infer new information.

For example, if we know that all dogs bark and come across a new dog, we may assume that this animal will bark similarly.

Example

Consider the following simple family scenario:

Define the Predicates:

Parent(x, y): Indicates that x is the parent of y.

Statements addressing the family:

Parent(Ram, Riya): Ram is Riya's father.

Parent (Riya, Aarav): Riya is Aarav's mother.

By using First Order Logic, we can conclude.

Parent(Ram, Aarav):

Because Ram is the father of Riya (Parent(Ram, Riya)) and Riya is the mother of Peter (Parent(Riya, Aarav)), we can infer that Ram is also the father of Aarav.

In this brief example, we used First-Order Logic to conclude that Ram is Aarav's father based on the statements provided.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Syntax and Notations of First-Order Logic

Let’s discuss the syntax and notations of First-Order Logic.

Predicates

Predicates are symbols that represent the attributes or connections of things. They are used to construct assertions about things and their properties. For instance, "human(x)" may be a predicate indicating that "x is a human."

Variables

Variables are placeholders in logical statements that allow us to refer to undefined objects. They help in the creation of general statements that may be applied to any object. In the predicate "human(x)," for example, "x" is a variable that represents any human.

Constants 

In First-Order Logic (FOL), a constant is a unique name of a certain item. It is like providing a label for the item in the logical statements.

Notation: Constants are represented using lowercase letters, numerals, or other symbols. For example: "x," "y," "z," "1," "2," etc.

Let’s say x is a constant, and Human(x) is the statement. So, in this, we are using the constant x to represent Humans.

Quantifiers

Quantifiers, namely universal () and existential (), allow us to make general statements about groups of items. The universal quantifier () means that a statement applies to all objects in the particular domain, whereas the existential quantifier denotes that there is at least one item in the particular domain.

Logical Connectives

Logical connectives are basic symbols in logic that are used to combine or transform simple statements to produce more sophisticated logical expressions. These connectives enable us to think about the links between propositions and serve as the foundation for logical arguments and expressions. 

The following are examples of popular logical connectives:

1. AND (^): Denotes a conjunction. 

It is represented by the symbol "^" and is only true when both declarations connected by it are true. 

As an example:

Statement 1: "The weather is nice today."

Statement 2: "I'm going to see a movie."

"I'll go to the movies today ^ the weather is nice." is the Logical Expression

Only if both declarations 1 and 2 are true will the expression be true.

 

2. OR (∨): Denotes disjunction.

It is represented by the symbol "∨" and is true if at least one of the connected statements is true. 

As an example:

Statement 1: "Stop" 

Statement 2: "I will shoot"

 "Stop ∨ I will shoot" is the Logical Expression

If either statement 1 or statement 2 (or both) is true, the expression is true.
 

3. NOT (¬): Denotes negation. It is represented by the symbol "¬" and reverses a proposition's truth value. As an example:

Statement: "The sky is blue"

"¬The sky is blue." is the Logical Expression

If the sky is not blue, the term is correct.
 

4. IMPLIES (→):  This symbol represents implication. It represents a conditional connection between two propositions and is symbolised by the symbol "→". As an example:

Statement 1: "If I study hard, I will get good grades."

Statement 2: "I studied very hard for the exam."

          "If I study hard → I will get good grades" is the Logical Expression

Quantifiers in First-Order Logic

In First-Order Logic, quantifiers allow us to discuss collections of objects, qualities, or relationships as a group. They help us in expressing our thoughts on whether particular statements apply to all members of a group or apply to particular members that fit a specified requirement.

Assume you're discussing a large group of items, such as all the animals at a zoo or all the students in a class. In First-Order Logic, quantifiers help you talk about these groupings.

Types of Quantifiers

Universal Quantifier (∀): 

The Universal Quantifier is a logic concept that allows you to make statements about each and every individual member in a group. It's equivalent to stating "for all" or "for every". It states a condition that holds true for every member of a set or collection in mathematical and logical terms.

Statement: "In every classroom, all students have notebooks."

Meaning: This statement conveys that within every classroom, each and every student has a notebook.

Existential Quantifier (∃):

The Existential Quantifier (∃) is a key idea in logic that allows you to say that at least one member in a group or domain meets a certain condition. In other words, it's the same as stating "there is" or "there exists" in daily speech. It states the presence of at least one member who fits a specific requirement in logical terms.

For Example, "There is a garden in the neighbourhood with colourful flowers."

Consider a neighbourhood that has a variety of gardens. When we apply the Existential Quantifier (∃), we mean that among all of these gardens, at least one stands out because of its gorgeous flowers. We may not know which garden it is, but we are certain that it exists.

Rules of Inference in First-Order Logic

Let’s discuss the rules that are to be followed in First-Order Logic:

Rules of Inference in First-Order Logic

1. Modus Ponens 

If you have a statement, "P implies Q" (P → Q), and you also know that "P" is true, then you can correctly conclude that "Q" is true.
Example: 

Given: If it's raining (P), then I'll take an umbrella (Q).

Statement 1: It's raining (P).

Conclusion: I'll take an umbrella (Q).

2. Modus Tollens  

If you have a statement "P implies Q", and you also know that "Q" is not true (¬Q), then you can infer that "P" is not true (¬P).
Example:

Given: If I study hard (P), then I'll pass the exam (Q).

Given: I didn't pass the exam (¬Q).

Conclusion: I didn't study hard (¬P).

3. Universal Instantiation 

If you have a statement that says something is true for all instances, like "For all x, P(x)," and you have a specific individual "a," you can conclude that "P(a)" is true.
Example:

Given: All dogs (∀x Dog(x)) bark (P(x)).

Conclusion: Fido barks (Dog(Fido) → Bark(Fido)).

4. Universal Generalization  

If you have a statement that's true for a specific individual "a," like "P(a)," you can generalise it to say that it's true for all instances, or "For all x, P(x)."
Example:

Statement: "Riya aced the Science test."

Conclusion: "All students as good as Riya aced the Science test."

Explanation: Starting with the Statement that "Riya aced the Science test," we can apply Universal Generalization to make a broader statement. The conclusion "All students as good as Riya aced the Science test" depicts that any student who possesses the same level of skill as Riya also aced the Science test. This demonstrates how Universal Generalization allows us to generalise from a specific case to a more general statement that applies to a group with similar attributes.

5. Existential Instantiation

If you have a statement that says something exists, like "There exists an x such that P(x)," and you introduce a new variable "a," you can conclude that "P(a)" is true.
Example:

Given Statement: "At least one student in the class speaks German.”

Inference: "Jerry is a student in the class who speaks German."

The initial statement indicates that there's a student in the class who knows how to speak German. Applying Existential Instantiation, we can pinpoint a specific individual, Jerry, who fulfils this condition. This showcases how Existential Instantiation helps us identify particular instances that satisfy the requirement mentioned in the given statement.

6. Existential Generalisation 

If you have a statement that's true for a specific individual "a," like "P(a)," you can generalise it to say that something exists for all instances, or "There exists an x such that P(x)."
Example:

Given Statement: "One student scored the highest marks in the exam."

Statement: "There exists a student who scored the highest marks in the exam."

Explanation: Let's say there are 20 students in the class. The given statement asserts that among these 20 students, there's at least one who achieved the highest marks. 

By using Existential Generalisation, we can conclude that out of the entire group of students, there exists at least one student who indeed secured the top marks in the exam.

Unification in First-Order Logic

Unification in First-Order Logic deals with finding a common substitution for variables in different terms to make them match. The goal of unification is to make two expressions identical by assigning values to variables in a way that preserves their meanings. It involves substituting terms for variables in a way that the resulting expressions match.

Conditions for Unification

  1. The predicate symbol must be the same.
  2. The number of arguments in both expressions must be identical.
  3. If two similar variables are present in the same expression, then unification fails.

Pseudocode of Unification

function unify(expression1, expression2):
	if expression1 is the same as expression2:
		return "SUCCESS" 
		
	if expression1 is a variable: 
		return substitute(expression1, expression2) 
		
	if expression2 is a variable: 
		return substitute(expression2, expression1) 
		
	if both expressions are terms and not equal:
		return "FAILURE" 
		
	if both expressions are functions or predicates with matching name and arity: 
		for each corresponding argument (arg1, arg2): 
			result <- unify(arg1, arg2) 
		
		if result is "FAILURE": 
			return "FAILURE"
		
	return "SUCCESS"
		
 function substitute(variable, expression): 
 	if variable occurs in expression: 
 		return "FAILURE" 
	else: 
 		return {variable / expression}


Explanation: The provided pseudocode describes the process of unification in First-Order Logic using simplified code. It checks for identical expressions, handles cases involving variables, terms, functions, and predicates, and ensures consistency in variable substitutions. The substitute function handles variable replacements and checks for valid substitutions.

Example

Consider the following phrases, which must be unified:

"Eats(x, Apple)" is an expression.

"Eats(Riya, y)" is an expression.

The following is an explanation of the unification process:

Comparison

Expression A ("Eats(x, Apple)") is compared to Expression B ("Eats(Riya, y)"

Substitution Variable

We can see that Expression A's first parameter is a variable "x," and the second argument is a constant "Apple."

The first parameter in Expression B is a constant "Riya," while the second argument is a variable "y."

Unifying Variables

We unify the variable "x" in Expression A with "Riya" in Expression B. This results in the substitution: x = Riya.

We also unify the variable "y" in Expression B with the constant "Apple." This gives us the substitution: y = Apple.

Applying Substitutions

After substitutions, Expression A becomes "Eats(Riya, Apple)."

Expression B remains the same: "Eats(Riya, Apple)."

Unified Expression

Both expressions are now identical: "Eats(John, Apple)."

Unification is successful, and the unified expression is "Eats(Riya, Apple)."

Resolution in First-Order-Logic

In First-Order Logic (FOL), resolution is a fundamental inference method for theorem proving and logical reasoning. It's very beneficial for showing the truth of statements through contradiction. The resolution principle helps in the generation of new clauses from old ones, resulting in the resolution of difficult logical issues. 

Steps for Resolution

1. Conversion to Clausal Form: The statements in FOL are transformed into clausal form, where each statement becomes a collection of literals (positive or negated atomic formulas) joined together by logical disjunction (OR).
 

2. Application of Negation Normal Form (NNF): If necessary, statements are converted into Negation Normal Form, ensuring negations only relate to atomic formulas.
 

3. Resolution Process: Selection of Clause Pair: Two clauses are chosen for resolution. These clauses generally contain a pair of complementary literals (one positive, one negated).

Literal Resolution: Complementary literals are identified within the selected clauses.

Resolution Step: By merging the chosen clauses and removing the resolved literals, a new clause is created. This new clause is a disjunction of the remaining literals.
 

4. Iterative Iteration: The resolution rule is iteratively applied to yield new clauses. If an empty clause (contradiction) emerges, the original statements are shown to be inconsistent, thus substantiating the theorem.

Example

Consider the following situation with a family and their relationships. Based on the facts provided, we wish to prove that "John is Sarah's grandfather."

Given facts: 

John is Alice's father.

Sarah's mother is Alice.

Goal: Demonstrate that "John is Sarah's grandfather."

Steps to Resolve

Clausal Form Conversion:

Fact 1: "Father(John, Alice)" transforms into "Father(John, Alice) True.

Fact 2: "Mother(Alice, Sarah)" transforms into "Mother(Alice, Sarah) True.

Process of Resolution:

Choose "Father(John, Alice) True" and "Mother(Alice, Sarah) True."

Determine the complementary literals "Father(John, Alice)" and "Father(John, Alice)."

The resolved clause is "True True," which is shortened to "True."

Conclusion: 

The resolution method returns "True," indicating that the objective "John is the grandfather of Sarah" is correct based on the information provided. 

First-Order Logic VS Propositional Logic

Basis

First-Order Logic (FOL)

Propositional Logic

 

Definition

FOL is a formal logic that extends propositional logic by allowing variables, quantifiers, functions, and relations. It enables the representation of complex relationships and structured knowledge. Propositional logic is a formal logic that deals with propositions, where propositions are atomic statements that can be either true or false. It focuses on truth values and logical connectives.

 

Variables

FOL uses variables to represent varying entities, objects, and properties. It introduces the concept of quantified variables. Propositional logic lacks variables; it only deals with atomic propositions.

 

Quantifiers

FOL employs quantifiers, such as universal (∀) and existential (∃), to express generalities and existence over variables. Propositional logic lacks quantifiers; it cannot express statements about all or some entities.

 

Predicates and Functions

FOL accommodates predicates (relations) and functions to model complex properties and relationships among entities. Propositional logic does not have predicates or functions; it deals with atomic propositions only.

 

Expressive Power

FOL is more expressive due to its ability to represent intricate relationships, quantified statements, and complex structures. Propositional logic is less expressive and is limited to representing simple propositions and truth values.

 

Deductive Reasoning

FOL supports deductive reasoning about objects, properties, and relations. It offers more sophisticated inference methods like resolution. Propositional logic allows for deduction but has simpler inference methods like modus ponens.

 

Applications

FOL is widely used in AI, robotics, databases, natural language processing, and knowledge representation due to its ability to model complex scenarios and relationships. Propositional logic finds application in basic logic puzzles, automated reasoning, and fundamental knowledge representation.

 

Frequently Asked Questions

How does First-Order Logic apply to knowledge representation? 

First-Order Logic helps computers store and manage knowledge by using a language that describes relationships, facts, and rules. It's like a smart filing system that lets computers understand and use information effectively.

What are the limitations of First-Order Logic? 

First-Order Logic struggles with uncertainty, handling large-scale reasoning, and capturing context-dependent knowledge. It can become complex for certain problems, and its representations might not be ideal for dealing with vague or probabilistic information.

How does First-Order Logic apply to knowledge representation? 

First-Order Logic helps computers organise and understand knowledge by using a structured language to represent relationships, facts, and rules. It's like a blueprint that lets computers reason and make smart decisions based on the information they have.

Conclusion

First-Order Logic (FOL) is like a language for computers to understand and talk about complex ideas. It's great because it lets us use variables, talk about groups of things, and say things about them. We can use it to solve puzzles, teach computers about the world, and make them smarter. While FOL can do a lot, it's also a bit tricky and can sometimes take a lot of computer power. But as we learn more, FOL keeps getting better and helps computers understand our world in smarter ways.

You can read these articles to learn more.


Refer to our Guided Path to upskill yourself in DSACompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. For placement preparations, you must look at the problemsinterview experiences, and interview bundles.

We wish you Good Luck!

Happy Learning!

Previous article
Hidden Markov Model in Machine Learning
Next article
Asymmetric Key Cryptography
Live masterclass