Logics (cont.

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen

Chapter 2 An Khuong, Le Hong

Trang

Logics (cont.)
Discrete Structures for Computing on September 3, 2021
Contents

Predicate Logic

Exercise

Huynh Tuong Nguyen, Tran Tuan Anh, Nguyen An Khuong, Le

Hong Trang
Faculty of Computer Science and Engineering
University of Technology - VNUHCM
trtanh@[Link] - htnguyen@[Link]
2.1
 Logics (cont.)
Contents
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

1 Predicate Logic Contents

Predicate Logic

Exercise

2 Exercise

2.2
 Logics (cont.)
Course outcomes
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang
Course learning outcomes

L.O.1 Understanding of logic and discrete structures

L.O.1.1 – Describe definition of propositional and predicate logic
L.O.1.2 – Define basic discrete structures: set, mapping, graphs

Contents
L.O.2 Represent and model practical problems with discrete structures
L.O.2.1 – Logically describe some problems arising in Computing Predicate Logic

L.O.2.2 – Use proving methods: direct, contrapositive, induction Exercise

L.O.2.3 – Explain problem modeling using discrete structures

L.O.3 Understanding of basic probability and random variables

L.O.3.1 – Define basic probability theory
L.O.3.2 – Explain discrete random variables

L.O.4 Compute quantities of discrete structures and probabilities

L.O.4.1 – Operate (compute/ optimize) on discrete structures
L.O.4.2 – Compute probabilities of various events, conditional
ones, Bayes theorem

2.3
 Logics (cont.)
Limits of Propositional Logic
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Contents
• x>3
Predicate Logic
• All square numbers are not prime numbers. 100 is a square Exercise

number. Therefore 100 is not a prime number.

2.4
 Logics (cont.)
Predicates
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Definition
A predicate (vị từ) is a statement containing one or more
variables. If values are assigned to all the variables in a predicate,
the resulting statement is a proposition (mệnh đề ). Contents

Predicate Logic
• x > 3 → P (x) Exercise

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

2.5
 Logics (cont.)
Truth value
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

• x > 3 is true or false? Contents

• 5>3 Predicate Logic

Exercise
• For every number x, x > 3 holds
• There is a number x such that x > 3

2.6
 Logics (cont.)
Quantifiers
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

• ∀: Universal – Với mọi

Contents
• ∀xP (x) = P (x) is T for all x Predicate Logic

• ∃: Existential – Tồn tại Exercise

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

• We need a domain of discourse for variable

2.7
 Logics (cont.)

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang
Example
Let P (x) be the statement “x < 2”. What is the truth value of the
quantification ∀xP (x), where the domain consists of all real
number?

• P (3) = 3 < 2 is false Contents

Predicate Logic
• ⇒ ∀xP (x) is false Exercise

• 3 is a counterexample (phản ví dụ) of ∀xP (x)

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

2.8
 Logics (cont.)

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang
Example
Express the statement "Some student in this class comes from
Central Vietnam."

Solution 1
Contents
• M (x) = x comes from Central Vietnam Predicate Logic

• Domain for x is the students in the class Exercise

• ∃xM (x)

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

2.9
 Logics (cont.)
Negation of Quantifiers
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Statement Negation Equivalent form

∀xP (x) ¬(∀xP (x)) ∃x¬P (x)
∃xP (x) ¬(∃xP (x)) ∀x¬P (x)
Contents

Predicate Logic
Example Exercise

• 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.10
 Logics (cont.)
Another Example
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

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

Exercise

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.11
 Logics (cont.)
The Order of Quantifiers
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

• The order of quantifiers is important, unless all the quantifiers

are universal quantifiers or all are existential quantifiers
• Read from left to right, apply from inner to outer
Contents
Example
Predicate Logic
∀x ∀y (x + y = y + x) Exercise
T for all x, y ∈ R

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

2.12
 Logics (cont.)
Translating Nested Quantifiers
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Example
∀x (C(x) ∨ ∃y (C(y) ∧ F (x, y)) )
Provided that:
Contents
• C(x): x has a computer, Predicate Logic

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

• 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.13
 Logics (cont.)
Translating Nested Quantifiers
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Example
∃x∀y∀z (((F (x, y) ∧ F (x, z) ∧ (y 6= z)) → ¬F (y, z)))
Provided that: Contents
• F (x, y): x, y are friends Predicate Logic

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

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.14
 Logics (cont.)
Translating into Logical Expressions
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Example

1 “There is a student in the class has visited Hanoi”.

2 “Every student in the class has visited Nha Trang or Vung
Tau”. Contents

Predicate Logic

Answer Exercise

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.15
 Logics (cont.)
Translating into Logical Expressions
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang
Example
If a person is a woman and a parent, then this person is mother of
someone.

Solution
Contents
We define:
Predicate Logic
• W (x) : x is woman Exercise

• 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.16
 Logics (cont.)
Translating into Logical Expressions
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Example
"Every people has only one best friend." Contents

Assume: Predicate Logic

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

Solution
∀x∃y∀z(B(x, y) ∧ ((y 6= z) → ¬B(x, z)))

2.17
 Logics (cont.)
Inference
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Example

• If I have a girlfriend, I will take her to go shopping.

• Whenever I and my girlfriend go shopping and that day is a Contents

special day, I will surely buy her some expensive gift. Predicate Logic

• If I buy my girlfriend expensive gifts, I will eat noodles for a Exercise

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.18
 Logics (cont.)
Propositional Rules of Inferences
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Rule of Inference Name

p
p→q
∴q Modus ponens
Contents

¬q Predicate Logic

p→q Exercise

∴ ¬p Modus tollens
p→q
q→r
Hypothetical syllogism
∴p→r
(Tam đoạn luận giả định)
p∨q
¬p
Disjunctive syllogism
∴q
(Tam đoạn luận tuyển)

2.19
 Logics (cont.)
Propositional Rules of Inferences
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Rule of Inference Name

p
Addition
∴p∨q
(Quy tắc cộng )
Contents

p∧q Predicate Logic

Simplification
∴p Exercise
(Rút gọn)
p
q
Conjunction
∴p∧q
(Kết hợp)
p∨q
¬p ∨ r
Resolution
∴q∨r
(Phân giải)

2.20
 Logics (cont.)

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Example Trang

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 barbecue
tomorrow. Therefore, if it rains today, then we will have a
barbecue tomorrow.
Contents

Solution Predicate Logic

Exercise
• 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
Hypothetical syllogism

2.21
 Logics (cont.)

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

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

it is sunny Predicate Logic

4. ¬r Modus tollens using (2) andExercise
(3)
• If we do not go swimming, then
we will take a canoe trip (s) 5. ¬r → s Hypothesis
• If we take a canoe trip, then 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.22
 Logics (cont.)
Fallacies
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Definition
Fallacies (ngụy biện) resemble rules of inference but are based on
contingencies rather than tautologies. Contents

Predicate Logic

Example Exercise

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.
Is [(p → q) ∧ q] → p a tautology?

2.23
 Logics (cont.)
Rules of Inference for Quantified Statements
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Rule of Inference Name

∀xP (x)
Universal instantiation
∴ P (c)
(Cụ thể hóa phổ quát) Contents

Predicate Logic
P (c)for an arbitrary c Exercise
Universal generalization
∴ ∀xP (x)
(Tổng quát hóa phổ quát)
∃xP (x)
Existential instantiation
∴ P (c)for some element c
(Cụ thể hóa tồn tại)
P (c)for some element c
Existential generalization
∴ ∃xP (x)
(Tổng quát hóa tồn tại)

2.24
 Logics (cont.)

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Example

• A student in this class has not gone to class

• Everyone in this class passed the first exam
• Someone who passed the first exam has not gone to class Contents

Predicate Logic

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

2.25
 Logics (cont.)

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

1. ∃x(C(x) ∧ ¬B(x)) Premise

2. C(a) ∧ ¬B(a) Existential instantiation from (1)
3. C(a) Simplification from (2)
4. ∀x(C(x) → P (x)) Premise Contents

Predicate Logic
5. C(a) → P (a) Universal instantiation from (4)
Exercise
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.26
 Logics (cont.)

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Given the predicate p(x) :00 x2 − 3x + 2 = 000 . What is the truth

value (chân trị) of the following propositions:
a) p(0) Contents

b) p(1) Predicate Logic

Exercise
c) p(2)
d) ∃x, p(x)
e) ∀x, p(x)

2.27
 Logics (cont.)

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Let x, y ∈ Z+ , and the predicate: p(x, y): "x is a divisor of y"

Determine the truth value of the following propositions:
a) p(2, 3)
b) p(2, 6)
Contents
c) ∀y, p(1, y) Predicate Logic

d) ∀x, p(x, x) Exercise

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.28
 Logics (cont.)

Provided that: Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
• F (x, y) : x is father of y, An Khuong, Le Hong
Trang
• M (x, y) : x is mother of y,
• S(x, y) : x is sister of y,
• B(x, y) : x is brother of y,
• H(x, y) : x is spouse (wife/husband) of y,
• O(x, y) : x is elder than y. Contents

Predicate Logic

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) ‘Thuyen has only one husband’ (Thuyen is 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.29
 Logics (cont.)

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
Solutions: An Khuong, Le Hong
Trang

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

∃x∃y(S(x, m) ∧ O(x, m) ∧ B(y, m) ∧ ¬O(y, m)).
b) ‘All of her brothers are younger than her’.
∀x(B(x, m) → ¬O(x, m)).
c) ‘Thuyen has only one husband’ (Thuyen is a private name). Contents

∃x∀y H(x, Thuyen) ∧ H(y, Thuyen) → (x = y) Predicate Logic

or ∃x∀y H(x, Thuyen) ∧ (x 6= y) → ¬H(y, Thuyen). Exercise

d) ‘One of his sisters is younger than him’.

∃x∀y(S(x, m) ∧ ¬O(x, m) ∧ S(y, m) ∧ (x 6= y) → O(y, m)).
e) ‘Everyone has grandfather, grandmother, maternal
grandfather, maternal grandmother’. ∀x∃y∃z∃y1 ∃y2 ∃z1 ∃z2
(F (y, x)∧M (z, x)∧F (y1 , y)∧M (y2 , y)∧F (z1 , z)∧M (z2 , z)).
f) ‘A father of a person cannot be a mother of other ones’.
∃x∃y∀z(F (x, y) → ¬M (x, z)).

2.30
 Logics (cont.)

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Translating the following nested quantifiers:

a) B(c, m) ∧ (O(c, m) ∨ O(m, c)).

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

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

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.31
 Logics (cont.)

Huynh Tuong Nguyen,

Given a predicate N (x) "x has been to Da Lat" with the domain Tran Tuan Anh, Nguyen
An Khuong, Le Hong
is the all students in Mathematics class. Translate the following Trang

predicates into English

a) ∃xN (x)
b) ∀xN (x)
c) ¬∃xN (x) Contents

d) ∃x¬N (x) Predicate Logic

e) ¬∀xN (x) Exercise

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.32
 Logics (cont.)

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Given the predicate N (x) "x studies more than 5 hours in class
every weekday" with the domain is the all students in
Mathematics class. Express the following predicates: Contents

a) ∃xN (x) Predicate Logic

b) ∀xN (x) Exercise

c) ∃x¬N (x)
d) ∀x¬N (x)

2.33
 Logics (cont.)

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

What is the propositional formula for the following pseudo code:

for (i = 0; i<numObjects; i++) {

Object x = Objects(i);
if isMushroom(x) Contents

Predicate Logic
if isPoisonous(x) && isPurple(x)
Exercise
return false;
}
return true;

• There are no mushrooms that are poisonous and purple.

• ∀xM ushroom(x) → ¬(P oisonous(x) ∧ P urple(x))

2.34
 Logics (cont.)

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

What is the propositional formula for the following pseudo code:

for (i=0; i<numObjects; i++) {

Object x = Objects(i); Contents
if isMushroom(x) && isPoisonous(x) && isPurple(x) Predicate Logic
return true; Exercise
}
return false;

• There is a mushroom that is purple and poisonous.

• ∃xM ushroom(x) ∧ P oisonous(x) ∧ P urple(x)

2.35
 Logics (cont.)

Giving the following pseudo code: Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

//— Look for first match

for (x=0; x<numKids; x++)
if isParent(Peter, kids[x])
match1Found = true;
Contents
//— Now look for a second match Predicate Logic
for (y=0; (y<numKids)&&(y!=x); y++) Exercise

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.36
 Logics (cont.)

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang
Let P(x) be "x can speak Russian" and Q(x) be "x can use Java".
Formalize the following:
Giving the space is ll students in your university.
a) There is a student in your university that can speak Russian and can use
Java.
b) There is a student in your university that can speak Russian but can’t Contents

use Java. Predicate Logic

c) Every student in your university can speak Russian or can use Java. Exercise

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.37
 Logics (cont.)

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Let L(x,y) be "x love y", where the space of x and y is the set of
all people in the world. Use logical quantifier to express the
following:
a) Everybody loves Jerry.
b) Everybody loves someone.
Contents
c) There is a person who everybody loves.
Predicate Logic
d) Nobody loves everybody. Exercise

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.

2.38
 Logics (cont.)

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Giving the following: Trang

. -P(x): "x is a math problem".

. -Q(x): "x is hard" (based on a well-defined standard).
. -R(x): "x is easy" (based on a well-defined standard - same
as above).
. -S(x): "x is not solvable". Contents
Translate the following propositional formulas to natural English Predicate Logic

a) ∀x(P (x) → (Q(x) ⇐⇒ ¬R(x))) Exercise

b) ∃x(S(x) ∧ ¬P (x))
There are many ways to translate a formula to 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.39
 Logics (cont.)

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Translate the following propositional formulas to natural English

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

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.40
 Logics (cont.)

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Formalize the following sentences:

a) Nobody is perfect.
b) not everyone is perfect.
c) All your friends are perfect. Contents

d) At least one of your friend is perfect. Predicate Logic

e) Everybody is your friend and they are perfect. Exercise

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.

2.41
 Logics (cont.)

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Giving the following Predicate:

- P(x): Program x satisfies ABET standard.
- Q(x,y): Program x has the same educational goal as program y.
- R(x): Educational outcome from program x is verifiable.
Which of the following formalize this sentence : "Every program Contents

that has the same educational goal as a ABET satisfied program Predicate Logic

and verifiable Educational outcome also satisfies ABET standard" Exercise

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.42
 Logics (cont.)

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Trang

Let:
- P (x, y): x is parent of y.
- M (x): x is male .
Given:
Contents
F (v, w) = M (v) ∧ ∃x∃y(P (x, y) ∧ P (x, v) ∧ (y 6= v) ∧ P (y, w)),
Predicate Logic
then F (v, w) means: Exercise

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.43
 Logics (cont.)

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
An Khuong, Le Hong
Formalize the following sentences using predicate logic: Trang

a) When a hard drive has less than 30GB free space, a warning
will be issued to all the users.
b) Do not back up the files if anyone is logging in the system.
c) YouTube’s videos will be buffered if there are at least 8MB
Contents
memory and 56kb/s line rate.
Predicate Logic
d) Few computer student is good at programming. Exercise

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.44