Predicate Logic
Prepared By N.Mogana
References:
1. Discrete Mathematics and its Applications by Kenneth H Rosen
2. Discrete Mathematical Structures with Applications in Computer Science by JP Tremblay
and Manohar
Predicate Logic
The logic based upon the analysis of predicates in any statement is called predicate logic.
Example:
John is a bachelor …………………………………..(1)
Smith is a bachelor…………………………………...(2)
Predicate: The part of the statement which describes the subject is called predicate. In
the above statements John and Smith are subjects. ‘is a bachelor’ is predicate
Notations used:
Predicate is indicated by capital letters
Subject is indicated by small letters
So, if John is represented as j and Smith by s, the predicate ‘ is a bachelor’ by B, then, the
statement (1) and (2) are written as B(j) and B(s) respectively.
Predicate
In general, any statement of the type “ p is Q” where Q is a predicate and
p is the subject can be denoted by Q(p).
Propositions can be combined with predicates to form complex
expressions.
Eg: This painting is red. ………………………………..(3)
If ‘painting’ is represented as p, ‘is red’ is represented as R then statement (3)
can be written as R(p).
Eg: John is a bachelor and this painting is red…….(4)
can be written as B(j) Λ R(p) .
Eg: Other representations
~ R(p) , B(j) -> R(p) etc
M-place Predicate
A predicate requiring m( where m>0) names or subjects is called an m-place predicate.
Examples:
(1) Amul is a student
The predicate S(Amal) : ‘Amal is a student’ is a 1-place predicate because it is related to one
subject Amal
(2) 2-place predicate :
Canada is to the north of the United states
The predicate N(c,s) : “c is to the north of s” where c: Canada and s: United States
Naveen is taller than Amal
The predicate P(a,b) : “a is taller than b“ where a:Naveen and b:Amal
(3) 3-place predicates :
Susan sits between Ralph and Bill
The predicate S(a,b,c): “ a sits between b and c” where a : Susan, b: Ralph and c: Bill
(4) 4-place predicates :
Green and Miller played badminton against John and Smith
The predicate B(a,b,c,d): ” played badminton against” where a: Green, b: Miller, c: John, d: Smith
Generalization of m-place predicate
If a1 , a2 ,........,a n are the names of subject, and S is a predicate
then S( a1 , a2 ,........,a n ) are n-place predicate.
If we write S(x) for “ x is a student”, then S(a) , S(b) , S(c) and others having the
same form can be obtained from S(x), by replacing x by an appropriate name.
Hence x is a place holder or variable
Compound statement functions can be formed by combining one or more
simple statement functions and logical connectives.
If x has a constraint that it can take only set of values or class of values then the
the possible values that x can take is called “Universe of Discourse”
Quantifier- definition
Quantifier is used to quantify the variables of a Predicate. It is the extent to which
predicate is true over range of elements.
It contains a formula, which is a type of statement whose truth value may depend on
values of some variables specified in the Predicate.
When we assign a fixed value to the variables in the Predicate, then it becomes a
Proposition.
Quantifier is mainly used to show the number of elements that makes a predicate true.
Quantifier - Example
Example : Let p: "x ≤ 5 ∧ x > 3“
(1) Is p true or false? { Can not be inferred as x value is not given}
(2) Is p true or false, if x=6 { false}
(3) Is p true or false, if x=4 { true }
(4) For every x, x ≤ 5 ∧ x > 3, is p true or false? {false}
(5)There exists an x such that "x ≤ 5 ∧ x > 3“ {true}
The variables in a formula/predicate cannot be simply true or false unless we bound
these variables by using the quantifier
Types of Quantifier
Universal Quantifier
Existential Quantifier
Universal Quantifier
Universal quantifier means – “ for all”
It means the predicate is true for every values of the variables in its domain.
(universe of discourse)
It uses the symbol ∀, which means "for all“
It is placed before the statement function to which this phrase is applied.
Example- ∀x P(x) or ∀x є D , P(x)
The universal quantifier is used to translate expressions such as “for all,” “ every “
and “for any “.
Universal Quantifiers
Lets take this example:
1. All men are mortal.
Subject is x-> man. Domain is all men, Predicate is M(x)- ‘ x is mortal’.
The symbolic form is - ∀x M(x)
2. Every apple is red.
Subject is x-> apple. Domain is all apples, Predicate is R(x)- ‘ x is red’.
The symbolic form is - ∀x R(x)
3. Any integer is either positive or negative
Subject is x->number . Domain is all integers, Predicate is I(x)- ‘ x is either positive or
negative”.
The symbolic form is - ∀x I(x)
G(x,y) : x is taller than y.
Represent: For any x and any y , if x is taller than y, than y is not taller than x”
or “ For any x and y , if x is taller than y, then it is not true that y is taller than
x.”
This statement can now be symbolized as (∀ x ) (∀ y ) ( G(x,y)->~ G(y,x))
2. Existential Quantifier
It symbolize expressions such as “ for some” , “there is at least one” or “
there exists some”
The existential quantifier symbol is denoted by the ∃, which means "there
exists“
The sentence ∃xP(x) will be true if and only if P(x) is true for at least one x in
Domain.
The statement ∃xP(x) will be false if and only if P(x) is false for all x in
Domain.
Example
M(x) : x is a man.
C(x) : x is clever
Where the domain is people
(∃ x ) ( M(x)) – There are some men among the crowd or there exists a
person who is a man
(∃ x ) (M(x) ΛC(x)) - There are few men who are clever
Examples-English to Formal lang Using Predicate Logic
For the examples given below consider the following cases and convert the English
statements to formal lang using predicate logic
(a)Domain as students in the class
(b)Domain as all people
1. Every student in this class has studied ‘Boolean Algebra’
The subject is student, lets say x
The predicate is ‘studied Boolean Algebra’,
lets say B(x) represent – x has studied Boolean Algebra
Case(a) :
The domain is all students in the class.
Formal language statement : ∀ x B(x)
Case (b):
The domain is all people.
Lets say S(x) represents ‘x is a student in this class’
Formal language statement : (∃ x )(S(x)-> B(x))
Examples-English to Formal lang Using Predicate Logic
2. Some students in the class have participated in quiz and every student in the class
has participated either in quiz or theatres
Solution: Here the subject is students, lets say x
Predicate is ‘participation in quiz’, ‘participation in theatres’
Lets say P(x) represent ‘x participates in quiz’ and
T(x) represent ‘ x participates in theatres’
Case (a): Domain is students in the class
The formal lang statement is : (∃ x P(x)) Λ (∀ x (P(x) V B(x)))
Case (b): Domain is all people
Let S(x) represent ‘x is a person who is a student in the domain of people’
The formal lang statement is : (∃ x (S(x) Λ P(x)) Λ (∀ x (S(x)-> (P(x) V T(x)))
Note: In the last expression (S(x) Λ P(x)) is used because if -> is used instead of Λ, it will become true even if S(x) if
False and P(x) is true.
Eg: Conversion of Arguments into Formal Lang
1. “All lions are fierce.”
2. “Some lions do not drink coffee.”
3. “Some fierce creatures do not drink coffee.
Note: First two statements are premises, third statement is the conclusion.
Let the subject is x, domain is all creatures
F(x) represent- x is fierce
L(x) represent- x is lion
C(x) represent – x drinks coffee
The argument can be given as
1. ∀ x(L(x) ->F(x))
2. ∃ x(L(x) Λ ~C(x))
3. ∃ x(F(x) Λ ~C(x))
Ex: Conversion of Argument into Formal Lang
“All hummingbirds are richly colored.”
“No large birds live on honey.”
“Birds that do not live on honey are dull in color.”
“Hummingbirds are small.
Nested Quantifiers
Example: ∀x∃y(x + y = 0)
Everything within the scope of a quantifier can be thought of as a
propositional function
∀x∃y(x + y = 0) ∀xQ(x), where Q(x) is ∃yP (x, y), where P (x, y) is x + y = 0
Reading Nested Quantifiers:
∀x∀y(x + y = y + x) - commutative law
∀x∃y(x + y = 0) - additive inverse of x is y
∀x∀y∀z(x + (y + z) = (x + y) + z) – associativity of x,y,z on additon
Domain of x,y is all real values.
Exercise
Translate the following from/to symbolic form
a) ∀x∀y((x > 0) ∧ (y < 0) → (xy < 0)) x,y belongs to real values
“The product of a positive real number and a negative real number is always a
negative real number.”
b) ∀x∀y((x > 0) ∧ (y > 0) → (x + y > 0)) x,y belongs to integers
For all positive integers, x and y, x + y is positive
c) “Every real number except zero has a multiplicative inverse.”
∀x((x≠ 0) → ∃y(xy = 1))
Order of Quantification
Is the following quantification logically equivalent?
∃y∀xP (x, y) and ∀x∃yP (x, y) where P(x,y) is x+y=0
No, they are not logically equivalent.
∃y∀xP (x, y) is false because there is no y why for which all x values are its
additive inverse.
∀x∃yP (x, y) is true because there is an(some) additive inverse y for every x.
Nested Quantification to English Statement
∀x(C(x) ∨ ∃y(C(y) ∧ F (x, y))) , where C(x) is “x has a computer,” F (x, y) is “x
and y are friends,” and the domain for both x and y consists of all students
in your school
Ans: every student in your school has a computer or has a friend who has a
computer
∃x∀y∀z((F (x, y) ∧ F (x, z) ∧ (y ≠ z)) → ~F(y,z) where F (a,b) means a and b are
friends and the domain for x, y, and z consists of all students in your school.
Ans: There is a student none of whose friends are also friends with each other.
