Unit II - Topic 2 - First order Predicate logic
Predicate
Meaning: “The part of a sentence containing a verb
and stating something about the subject “
Predicate Logic
Predicate logic is an extension of Propositional logic. It adds the
concept of predicates and quantifiers to better capture the meaning of
statements that cannot be adequately expressed by propositional logic.
Unit II - Topic 2 - First order Predicate logic
Predicate logic is also known as First-order logic (FOL) . It is a
foundational framework used in mathematics, philosophy, linguistics,
and computer science. In artificial intelligence (AI), FOL is important
for knowledge representation, automated reasoning, and NLP.
FOL extends propositional logic by incorporating quantifiers and
predicates, making it more expressive.
The key components include:
Constants: Represent specific objects (Example: , Alice, 2,
NewYork).
Variables: Stand for unspecified objects (Example: , x, y, z).
Predicates: Define properties or relationships (Example: ,
Likes(Alice, Bob) indicates Alice likes Bob).
Unit II - Topic 2 - First order Predicate logic
Functions: Map objects to other objects (Example: , MotherOf(x)
denotes the mother of x).
Quantifiers: Define the scope of variables:
(Example: , ∀x (Person(x) → Mortal(x)) means "All persons
o Universal Quantifier (∀): Applies a predicate to all elements
are mortal").
one element (Example: , ∃x (Person(x) ∧ Likes(x, IceCream))
o Existential Quantifier (∃): Specifies the existence of at least
means "Someone likes ice cream").
Logical Connectives: Include conjunction (∧), disjunction (∨),
implication (→), biconditional (↔), and negation (¬).
Unit II - Topic 2 - First order Predicate logic
Syntax and Semantics of First-Order Logic
FOL's syntax defines how to construct valid expressions, while
semantics assigns meaning to them. An interpretation provides a
domain of discourse and assigns meaning to constants, functions, and
predicates.
For example, in the domain of natural numbers, the predicate
GreaterThan(x, y) holds if x is greater than y.
Given x = 5 and y = 3, GreaterThan(5, 3) is true.
Applications of First-Order Logic in AI
FOL is widely used in AI for:
Knowledge Representation: Encoding relationships and properties,
such as in medical diagnosis systems where predicates define
symptoms and diseases.
Unit II - Topic 2 - First order Predicate logic
Automated Theorem Proving: Verifying software correctness and
proving mathematical theorems.
Natural Language Processing (NLP): Structuring and
understanding language for tasks like machine translation and
question answering.
Expert Systems: Encoding knowledge to infer decisions, such as
legal rule-based AI.
Semantic Web: Enhancing intelligent web search by defining
relationships between resources.
Example: Logical Reasoning with FOL
∀x (Cat(x) → Mammal(x)) (All cats are mammals)
Consider the following statements:
∀x (Mammal(x) → Animal(x)) (All mammals are animals)
Cat(Tom) (Tom is a cat)
From these, we can infer:
Unit II - Topic 2 - First order Predicate logic
Mammal(Tom) (Tom is a mammal)
Animal(Tom) (Tom is an animal)
This demonstrates how FOL enables logical reasoning to derive new
knowledge from given facts.
Advanced Concepts in FOL
Unification: Finding substitutions that make two expressions
identical, used in automated reasoning.
Resolution: A rule of inference for theorem proving, used to derive
contradictions and validate statements.
Model Checking: Verifying system correctness against
specifications, applied in software and hardware verification.
Logic Programming: Used in languages like Prolog for declarative
AI applications in NLP and expert systems.
Unit II - Topic 2 - First order Predicate logic
Challenges and Limitations
Despite its strengths, FOL has challenges:
Computational Complexity: Reasoning with large knowledge bases
can be expensive.
Expressiveness vs. Decide-ability: While powerful, FOL is
undecidable, meaning not all statements can be resolved
algorithmically.
Handling Uncertainty: FOL lacks probabilistic reasoning, requiring
extensions like fuzzy logic or probabilistic logic.
Unit II - Topic 2 - First order Predicate logic
Consider the statement, “x is greater than 3″. It has two parts. The
first part, the variable x , is the subject of the statement. The second
part, “is greater than 3”, is the predicate.
Predicate refers to a property that the subject of the statement can have.
The statement “x is greater than 3″ can be denoted by P(x)
where
P denotes the predicate “is greater than 3” and
x is the variable.
Unit II - Topic 2 - First order Predicate logic
The predicate P can be considered as a function. It tells the truth value
of the statement P(x) at x. Once a value has been assigned to the
variable x, the statement P(x) becomes a proposition and has a truth
or false (tf) value.
In general, a statement involving n variables
x1, x2, x3,.. , xn
can be denoted by
P(x1, x2, x3,.. , xn).
Here
P
is also referred to as n-place predicate or a n-ary predicate
Unit II - Topic 2 - First order Predicate logic
Example 1:
Let P(x) denote the statement “x > 10″. What are the truth values of
P(11) and P(5) ?
Solution:
P(11) is equivalent to the statement 11 > 10, which is True.
P(5) is equivalent to the statement 5 > 10, which is False.
Unit II - Topic 2 - First order Predicate logic
Example 2:
Let R(x,y) denote the statement “x = y + 1 “. What is the truth value of
the propositions R(1,3) and R(2,1) ?
Solution:
R(1,3) is the statement 1 = 3 + 1, which is False.
R(2,1) is the statement 2 = 1 + 1, which is True.
Unit II - Topic 2 - First order Predicate logic
Quantifiers
In predicate logic, predicates are used alongside quantifiers to
express the extent to which a predicate is true over a range of
elements. Using quantifiers to create such propositions is called
quantification.
There are two types of quantification-
1. Universal Quantification- Mathematical statements sometimes
assert that a property is true for all the values of a variable in a
particular domain, called the domain of discourse. Such a statement
is expressed using universal quantification. The universal
quantification of P(x) for a particular domain is the proposition that
asserts that P(x) is true for all values of x in this domain. The
Unit II - Topic 2 - First order Predicate logic
domain is very important here since it decides the possible values of
x.
The meaning of the universal quantification of P(x) changes when
the domain is changed. The domain must be specified when a
universal quantification is used, as without it, it has no meaning.
Formally,
The universal quantification of P(x) is the statement
"P(x) for all values of x in the domain"
The notation \forall P(x) denotes the universal quantification of P(x).
Here \forall is called the universal quantifier.
Unit II - Topic 2 - First order Predicate logic
\forall P(x) is read as "for all x P(x)".
Example 1:
Let P(x) be the statement “x + 2 >x “. What is the truth value of the
statement \forall xP(x) ?
Solution:
As x+2 is greater than x for any real number, so P(x) \equiv T for all x
or\forall xP(x) \equiv T .
Unit II - Topic 2 - First order Predicate logic
2. Existential Quantification-
Some mathematical statements assert that there is an element with a
certain property. Such statements are expressed by existential
quantification. Existential quantification can be used to form a
proposition that is true if and only if
P(x) is true for at least one value of x in the domain.
Formally,
The existential quantification of P(x) is the statement "There exists an
element x in the domain such that P(x)"
The notation \exists P(x) denotes the existential quantification of P(x).
Unit II - Topic 2 - First order Predicate logic
Here \exists is called the existential quantifier.
\exists P(x) is read as "There is at least one such x such that P(x)".
Example :
Let P(x) be the statement “x > 5″. What is the truth value of the
statement\exists xP(x) ?
Solution: P(x) is true for all real numbers greater than 5 and false for all
real numbers less than 5. So\exists xP(x) \equiv T .
Unit II - Topic 2 - First order Predicate logic
To summarise, \begin{tabular}{||c||c||c||}\hlineStatement & When True?
& When False? \\\hline\hline\forall P(x) & P(x) is\:true\:for\:all\:x &
There\:is\:an\:x\:for\:which\:P(x)\:is\:false \\\hline\exists P(x) &
There\:is\:an\:x\:for\:which\:P(x)\:is\:true & P(x) is\:false\:for\:all\:x \\\
hline\end{tabular}
Now if we try to convert the statement, given in the beginning of this
article, into a mathematical statement using predicate logic, we would
get something like-
\forall P(x) \leftrightarrow Q(x) \\
Here, P(x) is the statement "x is 18 years or older and,
Unit II - Topic 2 - First order Predicate logic
Q(x) is the statement "x is eligible to vote".
Notice that the given statement is not mentioned as a biconditional and
yet we used one. This is because Natural language is ambiguous
sometimes, and we made an assumption. This assumption was made
since it is true that a person can vote if and only if he/she is 18 years or
older. Refer
Introduction to Propositional Logic
for more explanation.
Unit II - Topic 2 - First order Predicate logic
Other Quantifiers –
Although the universal and existential quantifiers are the most important
in Mathematics and Computer Science, they are not the only ones. In
Fact, there is no limitation on the number of different quantifiers that
can be defined, such as “exactly two”, “there are no more than three”,
“there are at least 10”, and so on. Of all the other possible quantifiers,
the one that is seen most often is the
uniqueness quantifier
, denoted by
Unit II - Topic 2 - First order Predicate logic
\exists !
.
The notation \exists !xP(x) states "There exists a unique x such that P(x)
is true".
Quantifiers with restricted domains
Unit II - Topic 2 - First order Predicate logic
As we know that quantifiers are meaningless if the variables they bind
do not have a domain. The following abbreviated notation is used to
restrict the domain of the variables-
\forall x
> 0,
x^2
> 0. The above statement restricts the domain of
x
Unit II - Topic 2 - First order Predicate logic
, and is a shorthand for writing another proposition, that says
x>0
, in the statement. If we try to rewrite this statement using an
implication, we would get-
\forall x (x
>
0\: \rightarrow \: x^2
>
Unit II - Topic 2 - First order Predicate logic
0)
Similarly, a statement using Existential quantifier can be restated using
conjunction between the domain restricting proposition and the actual
predicate.
Restriction of universal quantification is the same as the universal
quantification of a conditional statement.
Restriction of an existential quantification is the same as the existential
quantification of conjunction.
Unit II - Topic 2 - First order Predicate logic
1. Binding variables- A variable whose occurrence is bound by a
quantifier is called a Bound variable. Variables not bound by any
quantifiers are called free variables.
2. Scope- The part of the logical expression to which a quantifier is
applied is called the scope of the quantifier.
