ICT 2021: Computational Mathematics
Predicate Logic: Predicates
Lecture 4
Phyela Mbewe
LIS Department
University of Zambia
February 2023
Overview
▪ predicates
➢ meaning
➢ domain
▪ Quantifiers
➢ Universal quantifier
➢ Existential quantifier
➢ Quantifier negation
➢ Logical equivalence for quantifiers
ICT 2021 2
Predicate
▪ A predicate
➢ a function, takes a variable as an argument(input) and returns true or
false as output (based on the input)
For example:
Suppose P(x): x + 1 = 5 is a predicate
P(1): 1 + 1 = 5 is a proposition (true or false)
▪ Difference
➢ a proposition is not a function, it is a statement which either true or
false. It cannot include a variable
ICT 2021 3
Predicate & Proposition Difference
➢ a proposition is not a function, it is a statement which either true or
false. It cannot include a variable
➢ a predicate is a function, because it has a variable it isn’t definitively
true or false. It returns a true or false for each possible argument
• i.e. when the variable is a known value, a predicate will return a
proposition
Example 2:
Suppose P(x) is the predicate x - 2 = 7
then P(4) is the proposition “4 – 2 = 7” is a proposition (false)
P(9) is another proposition “9 – 2 = 7” (true)
ICT 2021 4
Predicate Domain
▪ A predicate’s domain:
➢ predicate variables are associated with a universe (or domain)
➢ the domain indicates the argument(input) values which are allowed
for that predicate
For example:
Suppose P(x) is a predicate, whereby the universe(domain) is {1,2,3}. In this case
P(1), P(2) & P(3) are the possible propositions
ICT 2021 5
Predicate Example (2 variables)
▪ 𝑷 𝒙, 𝒚 ∶ "𝒙 − 𝟓 = 𝒚" is a predicate
▪ Domain: given with the predicate
➢ 𝒙 is in {4,5,6,7}
➢ and 𝒚 is in {2,3,4}
▪ Then, certain propositions are possible:
➢ 𝑃 4, 3 ∶ 𝟒 − 5 = 𝟑 (false proposition)
➢ 𝑃 7, 2 ∶ 7 − 5 = 2 (true)
➢ 𝑃 4,9 : unknown, since 9 is not in the domain for variable 𝑦
ICT 2021 6
Predicate Exercise (2 variables)
▪ Given the predicate 𝑷 𝒙, 𝒚 ∶ "𝒙 + 𝒚 < 𝟏𝟓“ where the
domain is all positive integers. State whether the following
propositions are true or false
1. 𝑃 9, 3
True
2. 𝑃 11, 4 False
3. 𝑃 22, −10 Unknown
4. 𝑃 11, 10 False
note: number 3 is not a proposition (it is unknown since -10 is not in the domain
of all positive integers), pay attention to the domain when solving predicate problems
ICT 2021 7
Universal quantifier
▪ The symbol ∀ is called the universal quantifier
➢ it is read as “for all”
➢ means 𝑃(𝑥) is true for all possible 𝑥 values in the given domain (universe)
For example:
𝑃 𝑥 ∶ "𝑥 + 2 > 3"
for domain: {2,3,4}
∀ 𝒙 𝑷(𝒙) means “for all 𝑥 in {2,3,4}, 𝑥+2>3
➢ ∀ 𝒙 𝑷(𝒙) is true if 𝑃(𝑥) is true for every possible 𝑥
➢ ∀ 𝒙 𝑷(𝒙) is false if there is an 𝑥 for which 𝑃(𝑥) is false
ICT 2021 8
Universal quantifier (example)
▪ statements with ∀ (the universal quantifier) convert a predicate
into a proposition (true or false)
For example:
𝑷 𝒙 ∶ "𝒙 > 𝟏“
𝑩 𝒙 ∶ 𝒙 − 𝟐>𝟎
and Q 𝒙 ∶ "𝒙 𝒊𝒔 𝒑𝒐𝒔𝒊𝒕𝒊𝒗𝒆“
for domain {2,3,4}
∀𝒙 𝑷 𝒙 →𝑸 𝒙 is read as for all 𝒙, if 𝑥 > 1 then 𝑥 is positive (true)
∀𝒙 𝑩 𝒙 ∧𝑸 𝒙 is read as for all 𝒙, 𝑥 − 2 > 0
and 𝑥 is positive (false, not true when 𝑥 is 2, see the domain)
ICT 2021 9
Existential quantifier
▪ The symbol ∃ is called the existential quantifier
➢ it is read as “there exists”
➢ means 𝑃(𝑥) is true for some 𝑥 in the given domain (universe)
For example:
𝑃 𝑥 ∶ "𝑥 + 1 > 3" for domain: {2,3,4}
∃ 𝒙 𝑷(𝒙) means “there exists an 𝑥 in {2,3,4} whereby 𝑥 + 1 > 3
➢ ∃𝒙 𝑷(𝒙) is true if 𝑃(𝑥) is true for at least one possible 𝑥
➢ ∃𝒙 𝑷(𝒙) is false if 𝑃(𝑥) is false for every 𝑥 value in the domain
ICT 2021 10
Existential quantifier (example)
▪ statements with ∃ convert a predicate into a proposition (true or
false)
Exercise:
Given that:
𝑷 𝒙 ∶ "𝒙 > 𝟏“
𝑩 𝒙 ∶ 𝒙 − 𝟐>𝟎
and Q 𝒙 ∶ "𝒙 𝒊𝒔 𝒑𝒐𝒔𝒊𝒕𝒊𝒗𝒆“
for domain {3,4,5}
state whether the following are true or false:
1. ∀ 𝒙 𝑷 𝒙 → 𝑸 𝒙 (read as “for all 𝑥, if 𝑥 > 1 then 𝑥 is positive”)
2. ∃𝒙 𝑩 𝒙 ∧𝑸 𝒙
ICT 2021 11
Quantifier negation
▪ The symbol ¬ (negation operator)
➢ indicates the inverse of a given predicate
➢ or, indicates the inverse of a quantifier (∀ 𝑜𝑟 ∃)
𝑃 𝑥 ∶ "𝑥 𝑖𝑠 𝑎𝑛 𝐼𝐶𝑇 𝑠𝑡𝑢𝑑𝑒𝑛𝑡“
for domain: all students
Meaning:
∀ 𝒙 𝑷(𝒙) means “all students are ICT students”
∃ 𝒙 𝑷(𝒙) means “there exists a student that is an ICT student”
¬∀ 𝒙 𝑷(𝒙) means “not all students are ICT students”
∀ 𝒙 ¬𝑷(𝒙) means “all students are not ICT students”
ICT 2021 12
Quantifier negation – Example (cont.)
𝑃 𝑥 ∶ "𝑥 𝑖𝑠 𝑎𝑛 𝐼𝐶𝑇 𝑠𝑡𝑢𝑑𝑒𝑛𝑡“
𝑄 𝑥 : "𝑥 ℎ𝑎𝑠 𝑎 𝑔𝑜𝑜𝑑 𝐶𝐴“
for domain: all students
Meaning:
∃𝒙(𝑷 𝒙 ∧𝑸 𝒙 )
means “there exists a student that is an ICT student and has a good CA”
¬∃ 𝒙 ( 𝑷 𝒙 ∧ 𝑸 𝒙 )
means “there is no student that is an ICT student and has a good CA”
∀𝒙(𝑷 𝒙 → 𝑸 𝒙 )
means “all students that are ICT students have a good CA”
(for all students, if the student is an ICT student, then the student has a good CA)
ICT 2021 13
Logical equivalence for quantifiers
𝑃 𝑥 ∶ "𝑥 𝑖𝑠 𝑎𝑛 𝐼𝐶𝑇 𝑠𝑡𝑢𝑑𝑒𝑛𝑡“
for domain: all students
Consider the following propositions
¬∀𝒙 𝑷 𝒙
means “not all students are ICT students”
∃ 𝒙 ¬𝑷 𝒙
means “there is(exists) a student who is not an ICT student”
Note: these 2 propositions have the same meaning
ICT 2021 14
Logical equivalence for quantifiers [2]
▪ De Morgan’s Law for quantifiers states that:
¬∀𝒙 𝑷 𝒙 ≡ ∃ 𝒙 ¬𝑷 𝒙
¬∃𝒙 𝑷 𝒙 ≡ ∀ 𝒙 ¬𝑷 𝒙
Guideline (from LHS to RHS)
i. move the negation to the predicate
ii. switch the ∀ to an ∃, (or switch ∃ to an ∀)
ICT 2021 15
De Morgan’s Law for quantifiers (example 2)
𝑃 𝑥 ∶ "𝑥 ℎ𝑎𝑠 𝑎 𝐶𝐴 𝑏𝑒𝑙𝑜𝑤 10“
for domain: all students
¬∃𝒙 𝑷 𝒙 ≡ ∀ 𝒙 ¬𝑷 𝒙
Consider the following propositions
¬∃𝒙 𝑷 𝒙
means “there is no student that has a CA below 10”
∀𝒙 ¬𝑷 𝒙
means “all the students have a CA not below 10”
or “all the students have a CA which is not below 10”
Note:
ICT 2021these 2 propositions have the same logical meaning 16
Exercise
P 𝑥 : “𝑥 is a comedian”
Q 𝑥 : “𝑥 is funny”
for domain: all people
Using the given predicates, translate the following statements into
English/regular language
a) ∀𝑥 𝑃 𝑥 ∨ 𝑄 𝑥
b) ∀𝑥 𝑃 𝑥 → 𝑄 𝑥
c) ¬∃𝑥 ( 𝑃 𝑥 ∧ ¬𝑄 𝑥 )
ICT 2021 17
