UNIT-2

• Predicate calculus
• Inference theory of predicate calculus
• Predicate calculus
– Predicates
– Statement function
– Variables
– Quantifiers
– Predicate formulas
– Free and Bound variables
– Universe of Discourse
• The propositional logic is not powerful enough to
represent all types of statements that are used in computer
science and mathematics, or to express certain types of
relationship between propositions such as equivalence.
• For example, the statement "x is greater than 1", where
x is a variable, is not a proposition because you can not
tell whether it is true or false unless you know the value
of x.

• Thus the propositional logic can not deal with such

sentences.

• However, such statements appear quite often in

mathematics and we want to do inferencing on those
statements.
⮚ “Not all birds fly" is equivalent to "Some birds don't fly".
⮚ "Not all integers are even" is equivalent to "Some integers are not
even".
⮚ "Not all cars are expensive" is equivalent to "Some cars are not
expensive“.
…
⮚ Each of those propositions is treated independently of the others in
propositional logic. For example, if P represents "Not all birds fly"
and Q represents "Some integers are not even", then there is no
mechanism in propositional logic to find out that P is equivalent to Q.

⮚ Thus we need more powerful logic to deal with these and other
problems. The predicate logic is one of such logic and it addresses
these issues among others.
 Predicates

• A predicate is a verb phrase template that describes

a property of objects, or a relationship among
objects represented by the variables.

• The logic based upon the analysis of predicates in

any statement is called predicate logic.
• John is a bachelor.
• Smith is a bachelor.
🡪 the part “is a bachelor” is called a predicate.

⮚ All human beings are mortal.

⮚ John is a human being.
⮚ Therefore, John is a mortal.
• Symbolize a predicate by a capital letter and names of
individuals or objects in general by small letters.
• Every predicate describes about one or more objects.
• Therefore a statement could be written symbolically in
terms of the predicate letter followed by the name or
names of the objects to which the predicate is applied.
(1) John is a bachelor.
(2) Smith is a bachelor.

⮚ Here, “is a bachelor “ symbolically denoted by the

predicate letter B, ”John” by j, and “Smith” by s.
⮚ Statements (1) and (2) can be written as B(j) and B(s)
respectively.
⮚ 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).
⮚ A statement which is expressed by using a predicate letter
must have at least one name of an object associated with
the predicate.
⮚ A predicate requiring m(m>0) names is called an m-place
predicate.
⮚ Example:
B in (1) and (2) is a 1-place predicate.
⮚ When m=0 , then we shall call a statement a 0-place
predicate because no names are associated with a
statement.
3. This painting is red. R(p)
⮚ B(j) ∧ R(p).

⮚ B(j) → R(p).
⮚ ~R(p).

Statements involving the names of two objects

4. Jack is taller than Jill.
5. Canada is to the north of the United states.

Note: the order in which the names appear in the statement as well as
in the predicate is important.
Examples of 3-place and 4-place predicates .
• Susan sits between Ralph and Bill.
• Green and Miller played bridge against Johnston and Smith.

⮚ In general , an n-place predicate requires n names of objects to be

inserted in fixed positions in order to obtain a statement. The
position of these names is important.
⮚ If S is an n-place predicate letter and a1,a2,……………,an are the
names of objects, then S(a1,a2,……………,an ) is a statement.
 Statement function, Variables, and
Quantifiers
⮚ A statement function of one variable is defined to be an
expression consisting of a predicate symbol and an
individual variable.
⮚ Such a statement function becomes a statement when the
variable is replaced by the name of any object.
⮚ The statement resulting from a replacement is called a
substitution instance of the statement function and is a
formula of statement calculus.
The statement function of two variables
G(x , y): x is taller than y
⮚ If both x and y are replaced by the names of objects, we get a
statement.
⮚ If m represents Mr. Miller and f Mr. Fox, then we have
⮚ G(m , f): Mr. Miller is taller than Mr. Fox
⮚ and G(f , m): Mr. Fox is taller than Mr. Miller
⮚ It is possible to form statement function of two variables by
using statement functions of one variable
Example
⮚ M(x): x is a man
⮚ H(y): y is a mortal
⮚ M(x) ∧ H(y): x is a man and y is a mortal

⮚ It is not possible to write every statement function of two

variables using statement function of one variable
 Quantifiers
• Quantifiers allow us to quantify (count) how many
objects in the universe of discourse satisfy a given
predicate
• Universe of discourse - the particular domain of the
variable in a propositional function
• Two types of quantifiers
– Universal
– Existential
Predicative Logic
Universal & Existential Quantifiers.
The quantifier all is called as the Universal quantifier, denoted as
∀x .
Represents each of the following phrases:
For all x, All x are such that
For every x Every x is such that
For each x Each x is such that
The quantifier some is the Existential quantifier denoted as ∃x.
Represents each of the following phrases:
There exists an x such that ...
There is an x such that ...
For some x ...
There is at least one x such that ...
Some x is such that ...
The symbol ∃!x. is read there is a unique x such that ... or There is one and
only one x such that ...
Ex: There is one and only one even prime.
∃!x, [x is an even prime]
∃!x, P(x) where P(x)≡x is an even prime integer.
Statement Negation
All true ∀x, F(x) ∃x, [~F(x)] Atleast one false
All false ∀x, [~F(x)] ∃x, F(x) Atleast one true

To form the negation of a statement involving one quantifier, change the quantifier
form universal to existential, or from existential to universal, and negate the
statement, which it quantifies.
Quantified statements and their abbreviated and meaning:
Sentence Abbreviated Meaning
∀x, F(x) All true
∃x, F(x) Atleast one true
~[∃x, F(x)] None true
∀x, [~F(x)] All false
∃x, [~F(x)] Atleast one false
~{∃x, [~F(x)} None false
~{∀x, [F(x)]} Not all true / Atleast one false
~{∀x, [~F(x)]} Not all false / Atleast one true
Equivalent Formulas:
All true {∀x, F(x)} ≡ {~[∃x, ~F(x)]} None false
All false {∀x,[~(x)]} ≡ {~[∃x, F(x)]} None true
Not all true {~[∀x, F(x)]} ≡ {∃x,[~F(x)]} Atleast one
false
Not all false {~[∀x,{~F(x)}]} ≡ {∃x, F(x)} Atleast one true
 Free and Bound Variables
A formula containing a part of the form (x)P(x) or ( ∃x )P(x),such a part is
called an x-bound part of the formula.
Any occurrence of x in an x-bound part of a formula is called a bound
occurrence of x, while any occurrence of x or of any variable that is not a
bound occurrence is called a free occurrence
The formula P(x) either in (x)P(x) or in (∃x )P(x) is described as the
scope of the quantifier.
Quantified Propositions:
Fundamental rule 5: (Universal Specification)
If a statement of a form ∀x, P(x) is assumed to be true, then the
universal quantifier can be dropped to obtain P(c) is true for an
arbitrary object c in the universe. This may be represented as

∀x, P(x)
∴ P(c) for all c
Ex: Suppose the universe is the set of humans.
M(x) denotes the statement “x is mortal.”
If ∀x, M(x) i.e. “All men are mortal” is true,
then “Socrates is mortal” is true.
Fundamental Rule 6: (Universal Generalisation)
If a statement P(c) is true of each element c of the
universe, then the universal quantifier may be prefixed to
obtain ∀x, P(x). It is represented as
P(c) for all c
∴ ∀x, P(x)
Fundamental Rule 7: (Existential Specification)
If ∃x, P(x) is assumed to be true, then there is an
element c in the universe such that P(c) is true. This may
be represented as
∃x, P(x)
∴ P(c) for some c
Fundamental Rule 8: (Existential Generalization)

If P(c) is true for some element c in the universe then ∃x, P(x) is true.
This may be represented as
P(c) for some c
∴ ∃x, P(x)

In order to draw conclusions from quantified premises, (we need to)

remove the quantifiers properly, argue with the resulting propositions,
and then properly prefix the correct quantifiers.
Examples:

1. Consider the argument.

All men are fallible.
All kings are men.
∴ All kings are fallible.
Let M(x) denote the assertion “x is a man”
K(x) denote the assertion “x is a king”
F(x) denote the assertion “x is fallible”
The above argument is symbolised as
∀x, [M(x)→F(x)]
∀x, [K(x)→M(x)]
∴ ∀x, [K(x)→F(x)]
Proof:
1) ∀x, [M(x)→F(x)] Premise 1
2) M(c)→F(c) Step 1) and Rule 5
3) ∀x, [K(x)→M(x)] Premise 2
4) K(c)→M(c) by 3) and Rule 5
5) K(c)→F(c) by 2) & 4) and Rule 2
6) ∀x, [K(x)→F(x)] by 5) and Rule 6
2. Symbolize the following argument and check for its validity:
Lions are dangerous animals.
There are lions.
∴There are dangerous animals.
Let L(x) denotes ‘x is a lion’
D(x) denotes ‘x is dangerous’
Symbolically
∀x,[L(x)→D(x)]
∃x, L(x)
∴ ∃x, D(x)

Proof:
1. ∀X, [L(x)→D(x)] Premise 1
2. L(c)→D(c) by 1) and Rule 5
3. ∃X, L(x). Premise 2
4. L(c) by 3) and Rule 7
5. D(c) by 2) & 4) and Rule 1
6. ∃X, D(x) by 5) and Rule 8