FOL vs Propositional Logic:

 Propositional Logic: Deals with propositions as a whole and logical

connectives.

 First-Order Logic (FOL): Extends propositional logic by adding the

ability to quantify over variables and express relationships between
entities. FOL is more powerful and expressive compared to
propositional logic, especially in the case of complex relationships,
facts, and reasoning.

Examples:

 Propositional Logic Example:

o P: "John is studying."

o Q: "John is at the university."

o P ∧ Q: "John is studying and John is at the university."

 First-Order Logic Example:

o Student(John): "John is a student."

o Studying(John, AI): "John is studying AI."

o At(John, University): "John is at the university."

o ∀x (Student(x) → Studying(x, AI) ∧ At(x, University)): "All

students are studying AI and are at the university."

While propositional logic can handle basic truth conditions between simple
propositions, first-order logic can handle more complex relations,
conditions, and quantifications, allowing us to express facts in much greater
detail.

First-order logic (FOL):

First-order logic (FOL), also known as predicate logic, is an extension of

propositional logic that allows us to express statements about objects, their
properties, and their relationships in a formal way. It provides a framework
for reasoning about the world and is commonly used in artificial intelligence,
computer science, and mathematics.
1. Components of First-Order Logic

 Constants: These are specific objects in the domain of discourse. For

example, John, Alice, and Paris could be constants.

 Variables: These represent arbitrary objects in the domain. For

example, x, y, z.

 Predicates: These represent properties or relations between objects.

Predicates can be thought of as functions that take arguments and
return true or false. For example, Likes(John, IceCream) or
Married(Alice, Bob) are predicates.

 Functions: Functions take arguments and return a specific object. For

example, FatherOf(x) could return the father of x.

 Quantifiers:

holds for all elements in the domain. Example: ∀x (Human(x) →

o Universal Quantifier (∀): States that a property or relationship

Mortal(x)) means "All humans are mortal."

element for which a property or relationship holds. Example: ∃x

o Existential Quantifier (∃): States that there exists at least one

(Human(x) ∧ Rich(x)) means "There exists someone who is both

human and rich."

2. Syntax of First-Order Logic

The syntax of FOL consists of well-formed formulas (WFF) that follow these
rules:

 Atomic Formulas: These are simple statements like Likes(John,

IceCream) or Married(Alice, Bob).

 Logical Connectives: FOL uses logical operators like negation (¬),

conjunction (∧), disjunction (∨), implication (→), and biconditional (↔)
to build more complex statements.

existence. For example, ∀x (Human(x) → Mortal(x)) or ∃x (Likes(x,

 Quantified Formulas: Quantifiers are used to express generality or

IceCream)).

3. Semantics of First-Order Logic

The semantics of FOL define the meanings of the symbols and formulas in
the context of a particular interpretation:
  Interpretation: An interpretation consists of a domain (set of objects)
and an assignment of meanings to the constants, predicates, and
functions.

 Satisfaction: A formula is said to be satisfied by an interpretation if it

evaluates to true under that interpretation.

For example:

 The formula ∀x (Human(x) → Mortal(x)) is satisfied if, for every object

in the domain, if the object is a human, it is also mortal.

5. Use Cases of First-Order Logic

 Knowledge Representation: FOL is widely used in AI to represent

knowledge about the world, such as facts about people, relationships,
and objects. It is also used to express rules that govern reasoning.

 Automated Reasoning: FOL provides a foundation for automated

theorem proving, where a computer can prove the truth of statements
based on a set of axioms or premises.

6. Example Problem

Problem:
Given the following facts and rules:

1. ∀x (Human(x) → Mortal(x))

2. Human(John)

3. Human(Mary)

4. ∀x (HasLegs(x) → CanWalk(x))

5. HasLegs(John)

Prove that John can walk.

Solution:

1. From Fact 2, Human(John) is true.

2. From Fact 1, ∀x (Human(x) → Mortal(x)), we know John is mortal, but

this is not directly related to the question.

3. From Fact 5, HasLegs(John) is true.

4. Using Modus Ponens on Facts 4 and 5, since HasLegs(John) is true, we
can conclude that John can walk.

Thus, John can walk.

7. Conclusion

First-Order Logic is a powerful framework for representing knowledge and

reasoning in AI. It allows us to model real-world situations involving
objects, relationships, and functions. By understanding and applying FOL,
you can solve complex problems in knowledge representation, automated
reasoning, and AI systems.

In preparation for your exam, make sure you understand the basic syntax
and semantics of FOL, how to use quantifiers, and how to apply inference
rules like Modus Ponens** and Universal Instantiation.

1. Example: All humans are mortal.

 FOL Translation:

o ∀x (Human(x) → Mortal(x))

o This reads as: "For all x, if x is a human, then x is mortal."

2. Example: Socrates is a human.

 FOL Translation:

o Human(Socrates)

o This reads as: "Socrates is a human."

3. Example: Some birds can fly.

 FOL Translation:

o ∃x (Bird(x) ∧ CanFly(x))

o This reads as: "There exists an x such that x is a bird and x can
fly."

4. Example: No student in this class is absent.

 FOL Translation:

o ∀x (Student(x) → ¬Absent(x))

o This reads as: "For all x, if x is a student, then x is not absent."

5. Example: Every professor teaches at least one course.

 FOL Translation:

o ∀x (Professor(x) → ∃y (Course(y) ∧ Teaches(x, y)))

o This reads as: "For all x, if x is a professor, then there exists a y

such that y is a course and x teaches y."

6. Example: If it is raining, then the ground will be wet.

 FOL Translation:

o Raining → Wet(Ground)

o This reads as: "If it is raining, then the ground is wet."

7. Example: Alice is friends with Bob.

 FOL Translation:

o ∃x ∃y (Friend(x, y) ∧ Name(x, "Alice") ∧ Name(y, "Bob"))

o This reads as: "There exist x and y such that x and y are friends,
x's name is Alice, and y's name is Bob."

8. Example: All cars have wheels.

 FOL Translation:

o ∀x (Car(x) → ∃y (Wheel(y) ∧ Has(x, y)))

o This reads as: "For all x, if x is a car, then there exists a y such
that y is a wheel and x has y."

9. Example: John is taller than Mary.

 FOL Translation:

o TallerThan(John, Mary)

o This reads as: "John is taller than Mary."

10. Example: If it is a weekend, then I am free.

 FOL Translation:

o Weekend → Free(I)

o This reads as: "If it is a weekend, then I am free."

11. Example: Only students who pass the exam are eligible for a
scholarship.

 FOL Translation:

o ∀x (Student(x) ∧ Pass(x, Exam) → EligibleForScholarship(x))

o This reads as: "For all x, if x is a student and x passes the exam,
then x is eligible for a scholarship."

12. Example: Some students like math.

 FOL Translation:

o ∃x (Student(x) ∧ Likes(x, Math))

o This reads as: "There exists an x such that x is a student and x

likes math."

13. Example: Bob is the only person who can solve this problem.

 FOL Translation:

o ∀x (CanSolve(x, Problem) → x = Bob)

o This reads as: "For all x, if x can solve the problem, then x is
Bob."

14. Example: There is a book in the library that was written by

George Orwell.

 FOL Translation:

o ∃x (Book(x) ∧ WrittenBy(x, "George Orwell") ∧ InLibrary(x))

o This reads as: "There exists an x such that x is a book, x was

written by George Orwell, and x is in the library."

**Modus Ponens is a fundamental rule of inference in classical logic. It allows you to infer the truth
of a conclusion based on a conditional statement and the truth of the antecedent (the "if" part) of
that statement. It is often referred to as the law of detachment.

The Structure of Modus Ponens:

 Premise 1: If P, then Q (P → Q)
 Premise 2: P is true.

 Conclusion: Therefore, Q is true.