Predicate Logic

Man VM. Nguyen

Chapter 2 Contents

Predicate Logic Predicate Logic

Predicate Logic to
Logical Inference
Introduction to Mathematical Logic Exercise
on January 7, 2025

Man VM. Nguyen

Math Depart., MUSC
2.1

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 1 / 46
 Contents

Contents Predicate Logic

Man VM. Nguyen

Contents

Predicate Logic

Predicate Logic to
1 Predicate Logic Logical Inference

Exercise

2 Predicate Logic to Logical Inference

3 Exercise

2.2

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 2 / 46
 Contents

Course outcomes Predicate Logic

Man VM. Nguyen

Contents

Predicate Logic

Course learning outcomes Predicate Logic to

Logical Inference

Exercise
L.O.1 Understanding of logic and discrete structures
L.O.1.1 – Describe definition of predicate logic
L.O.1.2 – Define basic discrete structures: set, map, graph
L.O.2 Represent & model practical problems with discrete structures
L.O.2.1 – Logically describe KEY problems in Computing
L.O.2.2 – Use proving methods: contrapositive, induction
L.O.2.3 – Explain problem modeling using discrete structures

2.3

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 3 / 46
CHAPTER 2.
Predicate Logic
 Predicate Logic

Limits of Propositional Logic Predicate Logic

Man VM. Nguyen

Contents

Predicate Logic

Predicate Logic to
Logical Inference

• x>3 Exercise

• All square numbers are not prime numbers.

100 is a square number.
Therefore 100 is not a prime number.

2.5

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 5 / 46
 Predicate Logic

Predicates Predicate Logic

Man VM. Nguyen

Definition Contents

A predicate is a statement containing one or more variables. Predicate Logic

Predicate Logic to
If values are assigned to all the variables in a predicate, the Logical Inference
resulting statement is a proposition . Exercise

• x > 3 → P (x)
• 5 > 3 → P (5)
• A predicate with n variables P (x1 , x2 , ..., xn )
Example:
• x > 3 (predicate)
• 5 > 3 (proposition)
• 2 > 3 (proposition)

2.6

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 6 / 46
 Predicate Logic

Truth value Predicate Logic

Man VM. Nguyen

Contents

Predicate Logic

Predicate Logic to
• x > 3 is true or false? Logical Inference

• 5>3 Exercise

• For every number x, x > 3 holds

• There is a number x such that x > 3

2.7

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 7 / 46
 Predicate Logic

Quantifiers Predicate Logic

Man VM. Nguyen

Contents

Predicate Logic
• ∀: Universal – For all Predicate Logic to
• ∀xP (x) = P (x) is T for all x Logical Inference

Exercise

• ∃: Existential – There exits

• ∃xP (x) = There exists an element x such that P (x) is
T

• We need a domain of discourse for variable

2.8

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 8 / 46
 Predicate Logic

Predicate Logic

Example Man VM. Nguyen

Let P (x) be the statement “x < 2”.

Contents

Predicate Logic
What is the truth value of the quantification ∀xP (x), Predicate Logic to
where the domain consists of all real number? Logical Inference

Exercise

• P (3) = 3 < 2 is false

• ⇒ ∀xP (x) is false

• 3 is a counterexample of ∀xP (x)

Example
What is the truth value of the quantification ∃xP (x),
where the domain consists of all real number?

2.9

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 9 / 46
 Predicate Logic

Predicate Logic

Man VM. Nguyen

Example
Express the statement ”Some student in this class comes Contents

from Central Thailand.” Predicate Logic

Predicate Logic to
Logical Inference
Solution 1
Exercise
• M (x) = x comes from Central Thailand
• Domain for x is the students in the class
• ∃xM (x)

Solution 2
• Domain for x is all people
• ...

2.10

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 10 / 46
 Predicate Logic

Negation of Quantifiers Predicate Logic

Man VM. Nguyen

Statement Negation Equivalent form Contents

∀xP (x) ¬(∀xP (x)) ∃x¬P (x) Predicate Logic

Predicate Logic to
∃xP (x) ¬(∃xP (x)) ∀x¬P (x) Logical Inference

Exercise

Example
• All CSE students study Discrete Math 1
• Let C(x) denote ”x is a CSE student”
• Let S(x) denote ”x studies Discrete Math 1”
• ∀x : C(x) → S(x)
• ∃x : ¬(C(x) → S(x)) ≡ ∃x : C(x) ∧ ¬S(x)
• There is a CSE student who does not study Discrete
Math 1.
2.11

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 11 / 46
 Predicate Logic

Another Example Predicate Logic

Man VM. Nguyen

Example
Contents
Translate these: Predicate Logic
• All lions are fierce. Predicate Logic to
Logical Inference
• Some lions do not drink coffee. Exercise
• Some fierce creatures do not drink coffee.

Solution
Let P (x), Q(x) and R(x) be the statements “x is a lion”,
“x is fierce” and “x drinks coffee”, respectively.
• ∀x(P (x) → Q(x)).
• ∃x(P (x) ∧ ¬R(x)).
• ∃x(Q(x) ∧ ¬R(x)).
2.12

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 12 / 46
 Predicate Logic

The Order of Quantifiers Predicate Logic

Man VM. Nguyen

• The order of quantifiers is important, unless all the

Contents
quantifiers are universal quantifiers or all are existential
Predicate Logic
quantifiers
Predicate Logic to
• Read from left to right, apply from inner to outer Logical Inference

Exercise

Example
∀x ∀y (x + y = y + x)
T for all x, y ∈ R

Example
∀x ∃y (x + y = 0) is T,
while
∃y ∀x (x + y = 0) is F
2.13

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 13 / 46
 Predicate Logic

Translating Nested Quantifiers (I) Predicate Logic

Man VM. Nguyen

Contents
Example
Predicate Logic
∀x (C(x) ∨ ∃y (C(y) ∧ F (x, y)) ) Predicate Logic to
Logical Inference
Provided that:
Exercise
• C(x): x has a computer,
• F (x, y): x and y are friends,
• x, y ∈ all students in your school.

Answer
For every student x in your school, x has a computer or
there is a student y such that y has a computer and x and y
are friends.

2.14

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 14 / 46
 Predicate Logic

Translating Nested Quantifiers (II) Predicate Logic

Man VM. Nguyen

Contents

Example Predicate Logic

∃x∀y∀z (((F (x, y) ∧ F (x, z) ∧ (y ̸= z)) → ¬F (y, z))) Predicate Logic to

Logical Inference
Provided that: Exercise

• F (x, y): x, y are friends

• x, y, z ∈ all students in your school.

Answer
There is a student x, so that for every student y, every
student z not the same as y, if x and y are friends, and x
and z are friends, then y and z are not friends.

2.15

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 15 / 46
 Predicate Logic

Translating statements into Logical Expressions (I) Predicate Logic

Man VM. Nguyen

Example
Contents
1 “There is a student in the class has visited Hanoi”. Predicate Logic

2 “Every student in the class has visited Nha Trang or Predicate Logic to
Logical Inference
Vung Tau”. Exercise

Answer
Assume:
C(x) : x has visited Hanoi
D(x) : x has visited Nha Trang
E(x) : x has visited Vung Tau
We have:
1 ∃xC(x)
2 ∀x(D(x) ∨ E(x))
2.16

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 16 / 46
 Predicate Logic

Translating statements into Logical Expressions (II) Predicate Logic

Man VM. Nguyen

Example
Contents
If a person is a woman and a parent, then this person is Predicate Logic
mother of someone. Predicate Logic to
Logical Inference
Solution: We define: Exercise

• W (x) : x is woman
• P (x) : x is a parent
• M (x, y): x is mother of y
We have: ∀x((W (x) ∧ P (x)) → ∃yM (x, y))
Example
”Every people has only one best friend.”
Assume:
• B(x, y) : y is the best friend of x
2.17

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 17 / 46
 Predicate Logic

Translating statements into Logical Expressions (III) Predicate Logic

Man VM. Nguyen

Contents

Predicate Logic

Predicate Logic to
Example Logical Inference

”Every people has only one best friend.” Exercise

Assume:
• B(x, y) : y is the best friend of x

Solution
∀x ∃y ∀z [B(x, y) ∧ ((y ̸= z) → ¬B(x, z))]

2.18

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 18 / 46
 Predicate Logic to Logical Inference

Logical Inference Predicate Logic

Man VM. Nguyen

Contents
Example Predicate Logic
• If I have a girlfriend, I will take her to go shopping. Predicate Logic to
Logical Inference
• Whenever I and my girlfriend go shopping and that day Exercise
is a special day, I will surely buy her some expensive gift.
• If I buy my girlfriend expensive gifts, I will eat noodles
for a week.
• Today is March 8.
• March 8 is such a special day.
• Therefore, if I have a girlfriend,...
• I will eat noodles for a week.

2.19

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 19 / 46
 Predicate Logic to Logical Inference

Propositional Rules of Inferences (I) Predicate Logic

Man VM. Nguyen

Contents
Rule of Inference Name Predicate Logic
p Predicate Logic to
p→q Logical Inference

∴q Modus ponens Exercise

¬q
p→q
∴ ¬p Modus tollens
p→q
q→r
∴p→r Hypothetical syllogism

p∨q
¬p
∴q Disjunctive syllogism

2.20

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 20 / 46
 Predicate Logic to Logical Inference

Propositional Rules of Inferences (II) Predicate Logic

Man VM. Nguyen

Contents

Rule of Inference Name Predicate Logic

Predicate Logic to
p Logical Inference
∴p∨q Addition
Exercise

p∧q
∴p Simplification

p
q
∴p∧q Conjunction

p∨q
¬p ∨ r
∴q∨r Resolution

2.21

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 21 / 46
 Predicate Logic to Logical Inference

Predicate Logic

Example Man VM. Nguyen

If it rains today, then we will not have a barbecue today.

If we do not have a barbecue today, then we will have a Contents

Predicate Logic
barbecue tomorrow.
Predicate Logic to
Therefore, if it rains today, then we will have a barbecue Logical Inference
tomorrow. Exercise

Solution
• p: It is raining today
• q: We will not have a barbecue today
• r: We will have barbecue tomorrow
p→q
q→r
∴ p → r . This is Hypothetical syllogism

2.22

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 22 / 46
 Predicate Logic to Logical Inference

Predicate Logic

Man VM. Nguyen

Example
• It is not sunny this afternoon 1. ¬p ∧ q Hypothesis
Contents
(¬p) and it is colder than Predicate Logic
yesterday (q) 2. ¬p Simplification using (1)
Predicate Logic to
• We will go swimming (r) only 3. r → p Hypothesis
Logical Inference

if it is sunny Exercise

• If we do not go swimming, 4. ¬r Modus tollens

then we will take a canoe trip using (2) and (3)
(s)
• If we take a canoe trip, then 5. ¬r → s Hypothesis
we will be home by sunset (t)
6. s Modus ponens using (4) and (5)
• We will be home by sunset (t)
7. s → t Hypothesis

8. t Modus ponens using (6) and (7)

2.23

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 23 / 46
 Predicate Logic to Logical Inference

Fallacies Predicate Logic

Man VM. Nguyen

Contents
Definition
Predicate Logic
Fallacies resemble rules of inference but are based on
Predicate Logic to
contingencies rather than tautologies. Logical Inference

Exercise

Example
If you do correctly every questions in mid-term exam, you
will get 10 grade.
You got 10 grade.
Therefore, you did correctly every questions in mid-term
exam.

Q: Is [(p → q) ∧ q] → p a tautology? Say for any p, q?

2.24

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 24 / 46
 Predicate Logic to Logical Inference

Rules of Inference for Quantified Statements Predicate Logic

Man VM. Nguyen

Contents
Rule of Inference Name Predicate Logic

Predicate Logic to
∀xP (x) Logical Inference
Universal instantiation
∴ P (c) Exercise

P (c)for an arbitrary c
Universal generalization
∴ ∀xP (x)

∃xP (x)
Existential instantiation
∴ P (c)for some element c

P (c)for some element c

Existential generalization
∴ ∃xP (x)

2.25

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 25 / 46
 Predicate Logic to Logical Inference

Reasoning with Premises and Rules of Inference Predicate Logic

Man VM. Nguyen

Example Contents

• A student in this class has not gone to class ≡ α Predicate Logic

• Everyone in this class passed the first exam ≡ β Predicate Logic to

Logical Inference

• Someone who passed the first exam has not gone to Exercise

class ≡ γ?

Hint
We need 3 predicates
• C(x): x is in this class
• B(x): x has gone to class
• P (x): x passed the first exam
• Premises???

2.26

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 26 / 46
 Predicate Logic to Logical Inference

Solution of the last example Predicate Logic

Man VM. Nguyen

Contents
1. α = ∃x(C(x) ∧ ¬B(x)) Premise Predicate Logic
2. C(a) ∧ ¬B(a) Existential instantiation from (1)
Predicate Logic to
3. C(a) Simplification from (2) Logical Inference

4. β = ∀x(C(x) → P (x)) Premise Exercise

5. C(a) → P (a) Universal instantiation

from Premise (4)
6. P (a) Modus ponens
from (3) and (5)
7. ¬B(a) Simplification from (2)
8. P (a) ∧ ¬B(a) Conjunction from (6) and (7)

9. ∃x(P (x) ∧ ¬B(x)) ≡ γ? Existential generalization from (8)

2.27

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 27 / 46
 Exercise

Exercise A Predicate Logic

Man VM. Nguyen

Contents

Predicate Logic
Given the predicate p(x) :′′ x2 − 3x + 2 = 0′′ .
Predicate Logic to
Logical Inference

Exercise
What is the truth value of the following propositions:
a) p(0)
b) p(1)
c) p(2)
d) ∃x, p(x)
e) ∀x, p(x)

2.28

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 28 / 46
 Exercise

Exercise B Predicate Logic

Man VM. Nguyen

Let x, y ∈ Z+ , and
Contents
the predicate: p(x, y): ”x is a divisor of y” Predicate Logic

Predicate Logic to
Logical Inference
Determine the truth value of the following propositions:
Exercise
a) p(2, 3)
b) p(2, 6)
c) ∀y, p(1, y)
d) ∀x, p(x, x)
e) ∀x∃y, p(x, y)
f) ∃y∀x, p(x, y)
g) ∀x∀y, (p(x, y) ∧ p(y, x)) → (x = y)
h) ∀x∀y∀z(p(x, y) ∧ p(y, z)) → (p(x, z))
2.29

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 29 / 46
 Exercise

Exercise C- Provided that: Predicate Logic

Man VM. Nguyen

• F (x, y) : x is father of y, M (x, y) : x is mother of y,

Contents
• S(x, y) : x is sister of y, B(x, y) : x is brother of y,
Predicate Logic
• H(x, y) : x is spouse (wife/husband) of y, Predicate Logic to
Logical Inference
• O(x, y) : x is elder than y.
Exercise

Express each of these statements using predicates:

a) ‘He (a person) has an elder sister and younger brother’.
b) ‘All of her brothers are younger than her’.
c) ‘Jane has only one husband’ (Jane - a private name).
d) ‘One of his sisters is younger than him’.
e) ‘Everyone has grandfather, grandmother, maternal
grandfather, maternal grandmother’.
f) ‘A father of a person cannot be a mother of other ones’.
2.30

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 30 / 46
 Exercise

Solutions: Predicate Logic

Man VM. Nguyen

a) ‘He (a person) has an elder sister and younger brother’. Contents

∃x∃y(S(x, m) ∧ O(x, m) ∧ B(y, m) ∧ ¬O(y, m)). Predicate Logic

Predicate Logic to
b) ‘All of her brothers are younger than her’. Logical Inference
∀x(B(x, m) → ¬O(x, m)). Exercise

c) ‘Jane has only one husband’

∃x∀y H(x, Jane) ∧ H(y, Jane) → (x = y)
or ∃x∀y H(x, Jane) ∧ (x ̸= y) → ¬H(y, Jane).
d) ‘One
 of his sisters is younger than him’. ∃x ∀y 
S(x, m) ∧ ¬O(x, m) ∧ S(y, m) ∧ (x ̸= y) → O(y, m) .
e) DIY
f) ‘A father of a person cannot be a mother of other
ones’. ∃x∃y∀z(F (x, y) → ¬M (x, z)).

2.31

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 31 / 46
 Exercise

Exercise D Predicate Logic

Man VM. Nguyen

Contents
Translating the following nested quantifiers: Predicate Logic

a) B(c, m) ∧ (O(c, m) ∨ O(m, c)). Predicate Logic to

Logical Inference

b) B(c, m) ∧ F (a, m) → O(a, c) ∧ F (a, c). Exercise

c) ∀x∀y(S(x, m) ∧ B(c, y) → x = y).

d) ∃x ((S(x, m) ∨ H(c, x)) ∨ ∃x(H(x, m) ∧ O(x, m))).

e) ∀x∀y(S(x, m) ∧ S(y, m) → O(x, y) ∨ O(y, x))

2.32

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 32 / 46
 Exercise

Predicate Logic
Solutions of D:
Man VM. Nguyen
a) B(c, m) ∧ (O(c, m) ∨ O(m, c)).
c is a brother (elder/younger) of m.
Contents

Predicate Logic

b) B(c, m) ∧ F (a, m) → O(a, c) ∧ F (a, c). Predicate Logic to

Logical Inference
If c is a brother of m and a is a father of m, then a is Exercise
elder than c and a is the father of c.

c) ∀x∀y (S(x, m) ∧ B(c, y) → x = y).

Whoever is the sister of m, then c is also a brother of
that person?
d) ∃x ((S(x, m) ∨ H(c, x)) ∨ ∃x(H(x, m) ∧ O(x, m))).
DIY
e) ∀x∀y(S(x, m) ∧ S(y, m) → O(x, y) ∨ O(y, x))
All of the sisters of m are older or younger together.
2.33

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 33 / 46
 Exercise

Exercise E Predicate Logic

Man VM. Nguyen

Given a predicate N (x) ”x has been to Da Lat” with the
domain is the all students in Mathematics class. Contents
Translate the following predicates into English Predicate Logic

a) ∃xN (x) Predicate Logic to

Logical Inference
b) ∀xN (x) Exercise

c) ¬∃xN (x)
d) ∃x¬N (x)
e) ¬∀xN (x)
f) ∀x¬N (x)
a) There is a student in this class has been to Da Lat.
b) All students in Math class have been to Da Lat.
c) There is no exists a student in Math class has gone to Da Lat.
d) There is a student in this class has never gone to Da Lat.
e) Not all students in Math class have ever been to Da Lat.
f) All students in Math class have never been to Da Lat. 2.34

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 34 / 46
 Exercise

Exercise F Predicate Logic

Man VM. Nguyen

Contents
Given the predicate
Predicate Logic
N (x) = ”x studies more than 5 hours in class every
Predicate Logic to
weekday” Logical Inference

with the domain is the all students in Mathematics class. Exercise

Express the following predicates by natural English

sentences:
a) ∃xN (x)
b) ∀xN (x)
c) ∃x¬N (x)
d) ∀x¬N (x)

2.35

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 35 / 46
 Exercise

Exercise G Predicate Logic

Man VM. Nguyen

What is the propositional formula for Contents

the following pseudo code: Predicate Logic

Predicate Logic to
Logical Inference
for (i = 0; i¡numObjects; i++) {
Exercise
Object x = Objects(i);
if isMushroom(x)
if isPoisonous(x) && isPurple(x)
return false;
}
return true;

• There are no mushrooms that are poisonous and purple.

• ∀x, M ushroom(x) −→ ¬(P oisonous(x)∧P urple(x)).

2.36

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 36 / 46
 Exercise

Exercise H Predicate Logic

Man VM. Nguyen

Contents
What is the propositional formula for the following pseudo
Predicate Logic
code: Predicate Logic to
Logical Inference
for (i=0; i¡numObjects; i++) { Exercise
Object x = Objects(i);
if isMushroom(x) && isPoisonous(x) && isPurple(x)
return true;
}
return false;

• There is a mushroom that is purple and poisonous.

• ∃x, M ushroom(x) ∧ P oisonous(x) ∧ P urple(x)

2.37

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 37 / 46
 Exercise

Exercise J- Giving the following pseudo code: Predicate Logic

Man VM. Nguyen

//— Look for first match

for (x=0; x¡numKids; x++) Contents

Predicate Logic
if isParent(Peter, kids[x])
Predicate Logic to
match1Found = true; Logical Inference
//— Now look for a second match Exercise

for (y=0; (y¡numKids)&&(y!=x); y++)

if isParent(Peter, kids[y])
match2Found = true;
return match1Found && match2Found;
Knowing that: kids array has 3 elements: { Alice, Bob,
Charles } and Peter only have 1 child Alice.
What is the propositional formula for ”Peter has at least 2
children”.
∃x∃y
(P arentOf (P eter, x) ∧ P arentOf (P eter, y) ∧ ¬(x = y))
2.38

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 38 / 46
 Exercise

Exercise K Predicate Logic

Man VM. Nguyen

Let P(x) be ”x can speak Russian” and

Q(x) be ”x can use Java”. Formalize the following: Contents

Giving the space is ll students in your university. Predicate Logic

a) There is a student in your university that can speak Russian and Predicate Logic to
Logical Inference
can use Java.
Exercise
b) There is a student in your university that can speak Russian but
can’t use Java.
c) Every student in your university can speak Russian or can use
Java.
d) None of the student in your university can speak Russian or can
use Java.

a) ∃x(P (x) ∧ Q(x))

b) ∃x(P (x) ∧ ¬Q(x))
c) ∀x(P (x) ∨ Q(x))
d) ∀x¬(P (x) ∧ Q(x))
2.39

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 39 / 46
 Exercise

Exercise L (or Loving?!) Predicate Logic

Man VM. Nguyen

Let L(x,y) be ”x love y”, where the space of x and y is the

Contents
set of all people in the world. Use logical quantifier to
Predicate Logic
express the following: Predicate Logic to
a) Everybody loves Jerry. =⇒ ∀x, L(x, Jerry) Logical Inference

Exercise
b) Everybody loves someone.
c) There is a person who everybody loves.
d) Nobody loves everybody.
e) There is someone Lydica doesn’t love.
f) There is someone nobody loves.
g) There is exact one person everybody loves.
h) There are exact two person Lynn loves.
i) Everybody loves themselves.
j) There is a person who love nobody but himself.

DIY for the others.

2.40

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 40 / 46
 Exercise

Exercise M (or Doing MATHEMATICS? !) Predicate Logic

Man VM. Nguyen

Giving the following:

Contents
. -P(x): ”x is a math problem”.
Predicate Logic
. -Q(x): ”x is hard” (based on a well-defined standard). Predicate Logic to
. -R(x): ”x is easy” (based on a well-defined standard). Logical Inference

. -S(x): ”x is not solvable”. Exercise

Translate the following formulas to natural English

a) ∀x(P (x) → (Q(x) ⇐⇒ ¬R(x)))
b) ∃x(S(x) ∧ ¬P (x))
There are many ways to translate a formula to a natural
language and the following is one of them
a) If x is a math problem, to say x is hard is the same as
saying x is not easy.
b) There is unsolvable non-math problem.
2.41

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 41 / 46
 Exercise

Exercise N (Printing in Network) Predicate Logic

Man VM. Nguyen

Translate the following propositional formulas to natural Contents

English statements where: Predicate Logic

Predicate Logic to
Logical Inference
F (p) is “Printer p is broken”, Exercise
B(p) is “Printer p is currently printing another document”,
L(j) is “Printing job j is lost”,
and Q(j) is “Printing job j is in queue.”

a) ∃p(F (p) ∧ B(p)) → ∃jL(j)

b) ∀pB(p) → ∃jQ(j)
c) ∃j(Q(j) ∧ L(j)) → ∃pF (p)
d) (∀pB(p) ∧ ∀jQ(j)) → ∃jL(j)

2.42

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 42 / 46
 Exercise

Exercise P (Perfectness of Human-being?) Predicate Logic

Man VM. Nguyen

Formalize the following sentences:

Contents

Predicate Logic
a) Nobody is perfect.
Predicate Logic to
b) not everyone is perfect. Logical Inference

Exercise
c) All your friends are perfect.
d) At least one of your friend is perfect.
e) Everybody is your friend and they are perfect.
f) Not everybody is your friend or there is somebody not perfect.

Giving: C(x): x is perfect.

D(x): x is your friend.
E(x): x is someone else.
ANSWER:
f) ∀x∃y(D(y) ∧ (y ̸= x) ∨ ¬C(y)) =⇒ ¬∀xD(x) ∨ ∃yC(y)
2.43

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 43 / 46
 Exercise

Exercise Q (Quality control in Education?) Predicate Logic

Man VM. Nguyen

Giving the following Predicate:

- P(x): Training Program x satisfies ABET standard. Contents

- Q(x,y): x has the same educational goal as program y. Predicate Logic

- R(x): Educational outcome from program x is verifiable. Predicate Logic to

Logical Inference

Exercise

Which of the following formalize this sentence :

”Every program that has the same educational goal as a
ABET satisfied program and verifiable Educational outcome
also satisfies ABET standard”

A) ∀x(P (x) ∧ ¬Q(x)) → ∃x(R(x))

B) ∀x(∃y(Q(x, y) ∧ P (y) ∧ R(x)) → P (x))
C) ∀x(∃y(Q(x, y) ∧ P (y) ∧ R(x)) → P (x) ∨ R(x))
D) ∀x(∀y(Q(x, y) ∧ P (y) ∨ R(x)) → P (x))
2.44

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 44 / 46
 Exercise

Exercise R (Relationship in families?) Predicate Logic

Man VM. Nguyen

Let: Contents
- P (x, y): x is parent of y. Predicate Logic
- M (x): x is male . Predicate Logic to
Logical Inference

Exercise
Given: F (v, w) =
= M (v) ∧ ∃x∃y(P (x, y) ∧ P (x, v) ∧ (y ̸= v) ∧ P (y, w)),
then F (v, w) means:

A) v is brother of w
B) v is cousin of w
C) v is uncle of w
D) v is grand father of w

2.45

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 45 / 46
 Exercise

Exercise S (Summary of Chapter 1 and 2) Predicate Logic

Man VM. Nguyen

Formalize the following sentences using predicate logic:
a) When a hard drive has less than 30GB free space, a Contents

warning will be issued to all the users. Predicate Logic

Predicate Logic to
b) Do not back up the files if anyone is logging in the Logical Inference
system. Exercise

c) YouTube’s videos will be buffered if there are at least

8MB memory and 56kb/s line rate.
d) Few computer student is good at programming.
e) No computer student is not hard working.
f) Not all computer students are smart.
g) All the Pompeians are either loyal to or hate Caesar.
h) Everyone is loyal to someone.
i) People only want to assassinate the dictator whom they
are not loyal to. 2.46

Man VM. Nguyen (Math Depart., MUSC) Predicate Logic January 7, 2025 46 / 46