Ambo University Institute of Technology

School of Informatics and Electrical Engineering

Department of Computer Science

Logic In Computer Science

Chapter 4:Predicate Logic

Bayisa Gutema(MSc)

08/14/2025 Hachalu Hundessa Campus 1

 Predicate Logic
• Propositional logic dealt quite satisfactorily with sentence
components like not, and, or and if . . . then, but the logical
aspects of natural and artificial languages are much richer than
that.
• What can we do with modifiers like there exists. . . , all . . . ,
among . . . and only . . . ?
• Here, propositional logic shows clear limitations and the
desire to express more subtle declarative sentences led to the
design of predicate logic, which is also called first-order logic
• Let us consider the declarative sentence
 Every student is younger than some instructor

08/14/2025 Hachalu Hundessa Campus 2

 Cont..
• In propositional logic, we could identify this assertion with a
propositional atom p . However, that fails to reflect the finer
logical structure of this sentence.
• This statement is about being a student, being an instructor and
being younger than somebody else. These are all properties of
some sort, so we would like to have a mechanism for expressing
them together with their logical relationships and dependences.
• Predicates used for that purpose. For example, we could write
S(Tolera) to denote that Tolera is a student and I(Roba) to say
that Roba is an instructor.
• Likewise Y(Tolera, Roba) could mean that Tolera is younger
than Roba.

08/14/2025 Hachalu Hundessa Campus 3

 Cont..
• The symbols S, I and Y are called predicates. Variables are
written u, v, w, x, y, z, . . .or , , . . . and can be thought of as
place holders for concrete values(like a student, or a program
state)
• Using variables, we can now specify the meanings of S, I and
Y more formally.

08/14/2025 Hachalu Hundessa Campus 4

 Cont..

• We need to convey the meaning of ‘Every student x is younger than

some instructor y.
• This is where we need to introduce quantifiers ∀ (read: ‘for all’) and
∃ (read: ‘there exists’ or ‘for some’)
• ∀x (S(x) → (∃y (I(y) ∧ Y (x, y)))).
• Which is translated to For every x, if x is a student, then there is
some y which is an instructor such that x is younger than y.
• Different predicates can have a different number of arguments. The
predicates S and I have just one (they are called unary predicates),
but predicate Y requires two arguments (it is called a binary
predicate).Example

08/14/2025 Hachalu Hundessa Campus 5

 Cont..
meaning: ‘There is some x which is a bird and cannot fly.

08/14/2025 Hachalu Hundessa Campus 6

 Application of Predicate Logic
• It is the formal notation for writing perfectly clear, concise,
and unambiguous mathematical definitions, axioms, and
theorems for any branch of mathematics.
• Supported by some of the more sophisticated database query
engines.
• Basis for automatic theorem provers and many other Artificial
Intelligence systems.

08/14/2025 Hachalu Hundessa Campus 7

 Example #2

• “All child are younger than their mother”.

• Using predicates, we could express this sentence as
∀x ∀y (C(x) ∧ M(x, y) → Y (x, y)) where C(x) means that x is a child, M(x,
y) means that x is y’s mother and Y (x, y) means that x is younger than y .
Example #3
• Andy and Paul have the same maternal grandmother.
which, using ‘variables’ a and p for Andy and Paul and a binary predicate
M for mother as before, becomes
∀x ∀y ∀u ∀v (M(x, y) ∧ M(y, a) ∧ M(u, v) ∧ M(v, p) → x = u)
This formula says that, if y and v are Andy’s and Paul’s mothers,
respectively, and x and u are their mothers, then x and u are the same
person.
• For binary predicate equality x = y instead of = (x, y) to say that x and y are
equal .

08/14/2025 Hachalu Hundessa Campus 8

 Example #3

• Consider translating the sentence Every son of my father is my

brother. into predicate logic.
1. As a predicate. We choose a constant m for ‘me’ or ‘I,’ so m is
a term, and we choose further {S, F, B} as the set of predicates
with meanings.

08/14/2025 Hachalu Hundessa Campus 9

 Predicate logic as a formal language
• Because of the power of predicate logic, the language is much more
complex than that of propositional logic.
• There are two sorts of things involved in a predicate logic formula.
The first sort denotes the objects that we are talking about
individuals .Function symbols also allow us to refer to objects.
• Expressions in predicate logic which denote objects are called
terms.
• The other sort of things in predicate logic denotes truth values;
expressions of this kind are formulas: Y (x, m(x)) is a formula,
though x and m(x) are terms.
• A predicate vocabulary consists of three sets: a set of predicate
symbols P, a set of function symbols F and a set of constant
symbols C.

08/14/2025 Hachalu Hundessa Campus 10

 Term

It is important to note that

• The first building blocks of terms are constants (nullary
functions) and variables;
• More complex terms are built from function symbols using as
many previously built terms as required by such function
symbols; and
• The notion of terms is dependent on the set F. If you change it,
you change the set of terms.

08/14/2025 Hachalu Hundessa Campus 11

 Formulas
• The choice of sets P and F for predicate and function symbols,
respectively,
is driven by what we intend to describe.
• For example, if we work on a database representing relations between our
kin we might want to consider P = {M, F, S, D}, referring to being male,
being female, being a son of . . .and being a daughter of . . . . Naturally, F
and M are unary predicates (they take one argument) whereas D and S are
binary (taking two). Similarly, we may define F = {mother-of, father-of}.
• We define the set of formulas over (F, P) inductively, using the already
defined set of terms over F:
1. If P ∈ P is a predicate symbol of arity n ≥ 1, and if , , . . . , are terms
over.
F, then P (, , . . . , ) is a formula.
2. If 𝝓 is a formula, then so is (¬𝝓).

08/14/2025 Hachalu Hundessa Campus 12

 Convention
• For convenience, we retain the usual binding priorities that ∀y
and ∃y bind like ¬. Thus, the order is:
1. ¬, ∀y and ∃y bind most tightly;
2. then ∨ and ∧;
3. then →, which is right-associative.
We also often omit brackets around quantifiers, provided that
doing so introduces no ambiguities.
 Predicate logic formulas can be represented by parse trees.

08/14/2025 Hachalu Hundessa Campus 13

 parse tree for predicate Formula
• The parse tree represents formula ∀x ((P (x) → Q(x)) ∧ S(x,
y))

08/14/2025 Hachalu Hundessa Campus 14

 Cont..

• Consider translating the sentence Every son of my father is my

brother. into predicate logic.
• 1. As a predicate. We choose a constant m for ‘me’ or ‘I,’ so m
is a term, and we
choose further {S, F, B} as the set of predicates with meanings.

08/14/2025 Hachalu Hundessa Campus 15

 Cont..
• As a function. We keep m, S and B as above and write f for the
function which,
given an argument, returns the corresponding father.
• Note that this works only because fathers are unique and always
defined, so f really is a function as opposed to a mere relation. The
symbolic encoding of the sentence above is now
∀x (S(xf(m)) → B(x, m))
meaning: ‘For all x, if x is a son of y and the y is father of m, then x is a
brother of m;’ it is less complex because it involves only one quantifier.
 Formal specifications require domain-specific knowledge.
 Domain-experts often don’t make some of this knowledge explicit,
so a specifies may miss important constraints for a model or
implementation.

08/14/2025 Hachalu Hundessa Campus 16

 Free and Bound Variable
Bound: Every occurrence of variable x in : p(x) and in : p(x) is
bound.
Free: Every occurrence of a variable that is not bound is free
There are two important and different senses in which such
formulas can be ‘true’.
1. First, if we give concrete meanings to all predicate and
function symbols involved we have a model and can check
whether a formula is true for this particular model.
2. Second, one sometimes would like to ensure that certain
formulas are true for all models.

08/14/2025 Hachalu Hundessa Campus 17

 Cont..
 Consider P (c) ∧ ∀y(P (y) → Q(y)) → Q(c) for a constant c; clearly ,
this formula should be true no matter what model we are looking at .
 Now we need to understand that variables occur in different ways.
Consider the formula ∀x ((P (x) → Q(x)) ∧ S(x, y)).
 We draw its parse tree in the same way as for propositional
formulas, but with two additional sorts of nodes:
1. The quantifiers ∀x and ∃y form nodes and have, like negation, just
one subtree.
2. Predicate expressions, which are generally of the form P (, , . . . , ),
have the symbol P as a node, but now P has n many subtrees,
namely the parse trees of the terms , , . . . , .

08/14/2025 Hachalu Hundessa Campus 18

 Variable occurs at two different sorts of places.
1. First they appear next to quantifiers ∀ and ∃ in nodes like ∀x and
∃z; such nodes always have one subtree, subsuming their scope to
which the respective quantifier applies.
2. The other sort of occurrence of variables is leaf nodes containing
variables.
If variables are leaf nodes, then they stand for values that still have
to be made concrete. There are two principal such occurrences.
 From diagram on slide 14 we have three leaf nodes x.
A. If we walk up the tree beginning at any one of these x leaves, we run
into the quantifier ∀x. This means that those occurrences of x are
actually bound to ∀x so they represent, or stand for, any possible value
of x.

08/14/2025 Hachalu Hundessa Campus 19

 Cont..

B. In walking upwards, the only quantifier that the leaf node y

runs into is ∀x but that x has nothing to do with y; x and y are
different place holders.
So y is free in this formula. This means that its value has to be
specified by some additional information, for example, the
contents of a location in memory.
Definition: Let 𝝓 be a formula in predicate logic. An occurrence
of x in 𝝓 is free in 𝝓 if it is a leaf node in the parse tree of φ
such that there is no path upwards from that node x to a node ∀x
or ∃x. Otherwise, that occurrence of x is called bound.
For ∀x 𝝓, or ∃x 𝝓, we say that 𝝓 – minus any of 𝝓’s sub
formulas ∃x ψ, or ∀x ψ – is the scope of ∀x, respectively ∃x.
08/14/2025 Hachalu Hundessa Campus 20
 Figure show the parse tree of free and bound
tree

08/14/2025 Hachalu Hundessa Campus 21

 Example
 The scope of ∀x in ∀x (P (x) → ∃x Q(x)) is P (x). It is quite
possible, and common, that a variable is bound and free in a
formula. Consider the formula (∀x (P (x) ∧ Q(x))) → (¬P (x)
∨ Q(y) )
 The two x leaves in the subtree of ∀x are bound since they are
in the scope of ∀x, but the leaf x in the right subtree of → is
free since it is not in the scope of any quantifier ∀x or ∃x.
Note, however, that a single leaf either is under the scope of a
quantifier, or it isn’t.
 Hence individual occurrences of variables are either free or
bound, never both at the same time.

08/14/2025 Hachalu Hundessa Campus 22

 Proof theory of predicate logic
Natural deduction rules
The Proof Rule for Universal Quantifier
• The rule for eliminating ∀ is the following.

• It says: If ∀x 𝝓 is true, then you could replace the x in 𝝓 by any

term t (given, as usual, the side condition that t be free for x in φ)
and conclude that 𝝓 [t/x] is true as well.
• Recall that 𝝓 [t/x] is obtained by replacing all free occurrences of x
in 𝝓 by t.
• You may think of the term t as a more concrete instance of x.
Since 𝝓 is assumed to be true for all x, that should also be the case
for any term t .
08/14/2025 Hachalu Hundessa Campus 23
 Reasoning with Equality In predicate Logic
• Predicate logic allows the use of arbitary predicates P. Equality
(=) is such a predicate.
• It applies to two arguments; we can read t1=t2 as a predicate
=(t1,t2).The following three rules capture that equality is
an equivalence relation: it is reflexive, symmetric, and
transitive.

08/14/2025 Hachalu Hundessa Campus 24

 Universal Introduction
• The rule ∀x i is a bit more complicated.

• It says: If, starting with a ‘fresh’ variable x0, you are able to
prove some formula 𝝓[x0/x] with x0 in it, then (because x0 is
fresh) you can derive ∀x 𝝓.
• It takes a while to understand this rule, since it seems to be
going from the particular case of 𝝓 to the general case ∀x.
Proof of the sequent ∀x (P (x) → Q(x)), ∀x P (x) ⊢ ∀x Q(x)

08/14/2025 Hachalu Hundessa Campus 25

 Example #1
Proof of the sequent ∀x (P (x) → Q(x)), ∀x P (x) ⊢ ∀x Q(x)
1. ∀x (P (x) → Q(x)) premise
2. ∀x P (x) premise

6. ∀x Q(x) ∀x i 5

08/14/2025 Hachalu Hundessa Campus 26

 Example #2

2. Show the validity of the sequent P (t), ∀x (P (x) → ¬Q(x)) ⊢

¬Q(t) for any term t.
1. P (t) premise
2. ∀x (P (x) → ¬Q(x)) premise
3. P (t) → ¬Q(t) ∀x e 2
4. ¬Q(t) →e 1,3 or 1,3 MT
Note that we invoked ∀x e with the same instance t as in the
assumption
P (t). If we had invoked ∀x e with y, say, and obtained P (y) →
¬Q(y).

08/14/2025 Hachalu Hundessa Campus 27

 The proof rules for existential quantification
• The analogy between ∀ and ∧ extends also to ∃ and ∨;
• the rules for ∃ by starting from the rules for ∨ and applying
the same ideas as those that related ∧ to ∀ .
•
• Therefore, given the form of for all-elimination, we can infer
that exists introduction must be simply

08/14/2025 Hachalu Hundessa Campus 28

 Example #1
• Prove the validity of the sequent ∀x 𝝓 ⊢∃x 𝝓.
1. ∀x 𝝓 premise
2. 𝝓[x/x] ∀x e 1
3. ∃x 𝝓 ∃x i 2
demonstrates that, where we chose t to be x with respect to both
∀x e and to ∃x i (and note that x is free for x in 𝝓 and that 𝝓[x/x]
is simply 𝝓 again).

08/14/2025 Hachalu Hundessa Campus 29

 Example #2
2. Proving the validity of the sequent ∀x (P (x) → Q(x)), ∃x P (x)
⊢∃x Q(x) is more complicated:

08/14/2025 Hachalu Hundessa Campus 30

 Cont..
• The motivation for introducing the box in line 3 of this proof
is the existential quantifier in the premise ∃x P (x) which has
to be eliminated.
• Notice that the ∃ in the conclusion has to be introduced within
the box and observe the nesting of these two steps.
• The formula ∃x Q(x) in line 6 is the instantiation of χ in the
rule ∃e and does not contain an occurrence of x0, so it is
allowed to leave the box to line 7. The almost identical ‘proof

08/14/2025 Hachalu Hundessa Campus 31

 Cont…
• Line 6 allows the fresh parameter x0 to escape the scope of the
box which declares it.

08/14/2025 Hachalu Hundessa Campus 32

 Example #3
• A sequent with a slightly more complex proof is
∀x (Q(x) → R(x)), ∃x (P (x) ∧ Q(x)) ⊢ ∃x (P (x) ∧ R(x))
• and could model some argument such as
If all quakers are reformists and if there is a protestant who is
also a quaker, then there must be a protestant who is also a
reformist.
• One possible proof strategy is to assume P (x) ∧ Q(x0), get the
instance
Q(x0) → R(x0) from ∀x (Q(x) → R(x)) and use ∧ e2 to get our
hands on Q(x0), which gives us R(x0) via →e .

08/14/2025 Hachalu Hundessa Campus 33

 Cont..

08/14/2025 Hachalu Hundessa Campus 34

 Quantifier equivalences

• Let 𝝓 and ψ be formulas of predicate logic. Then we have the

following equivalences:

08/14/2025 Hachalu Hundessa Campus 35