The German University in Cairo (GUC) Summer 2025 (RS25)

Faculty of Media Engineering and Technology (MET) Discrete Mathematics

Dr. Ahmed Abdelfattah MATH 501 (MET) / MATH 305 (BI)
; PA03 : Predicate Logic (FoL) <

Practice Assignment PA03

Predicate Logic (FoL)
Exercise 3–1 (Basics)
Let Q(x) be the statement “x + 1 > 2x”. If the domain consists of all integers, what are the following truth values?

(1) Q(0) (3) Q(1) (5) ∀x Q(x) (7) ∀x ¬Q(x)

(2) Q(−1) (4) ∃x Q(x) (6) ∃x ¬Q(x)

Exercise 3–2 (Basics)

Suppose P (x, y) is a predicate and the universe for the variables is U = {1, 2, 3}. Suppose P (1, 3), P (2, 1),
P (2, 2), P (2, 3), P (3, 1), but P (3, 2) are true, yet P (x, y) is false otherwise. Determine whether the following
statements are true.

(1) ∀x ∃y P (x, y) (4) ∀y ∃x (P (x, y) → P (y, x))

(2) ∃x∀y P (x, y) (5) ∀x ∀y (x ̸= y → (P (x, y) ∨ P (y, x))
(3) ¬∃x ∃y (P (x, y) ∧ ¬P (y, x)) (6) ∀y ∃x (x ≤ y ∧ P (x, y))

Exercise 3–3 (Basics)

Find a counterexample, if possible, to these universally quantified statements, where the domain U = Z for all
variables consists of all integers.

(1) ∀x ∀y(x2 = y 2 → x = y)
(2) ∀x ∃y (y 2 = x)
(3) ∀x ∀y (xy ≥ x)

Note that this type of basic questions is totally different from the types of the VIP exercise in page 3, in which you
are asked to not only find a counterexample in a given domain, but also to construct a complete domain (with its
elements, constants, and predicates, etc.) that shows the truth or falsity of a given predicate formula.

Exercise 3–4 (Basics)

A discrete mathematics class contains 1 mathematics major who is a freshman, 12 mathematics majors who are
sophomores, 15 computer science majors who are sophomores, 2 mathematics majors who are juniors, 2 computer
science majors who are juniors, and 1 computer science major who is a senior.
Express each of the following statements in terms of quantifiers and then determine its truth value.

(1) There is a student in the class who is a junior.

(2) Every student in the class is a computer science major.
(3) In the class, there is a student who is neither a mathematics major nor a junior.
(4) Every student in the class is either a sophomore or a computer science major.
(5) There is a major such that there is a student in the class in every year of study with that major.

This exercise is only here to train the student understand the symbolic representations. However, in exams, there is
nothing left unspecified or works in a metaphorical way. In particular, an interpretation must define the domain U
over which the quantifiers range. Predicates work as the tool to indicate the sets to which the elements belong (e.g.,
StdClass(s) means: “s is a student in the class”).
Digression: The initial (basic) exercises are short and simple but offer a great opportunity to review the fundamentals:

Practice Assignment PA03 (Last Updated: 2025-06-30) Page 1 (of 7)

 The German University in Cairo (GUC) Summer 2025 (RS25)
Faculty of Media Engineering and Technology (MET) Discrete Mathematics
Dr. Ahmed Abdelfattah MATH 501 (MET) / MATH 305 (BI)
; PA03 : Predicate Logic (FoL) <

• The basic connectives and symbols in propositional logic are used in predicate logic with the same meanings.
For example, ⊥ represents False, ⊤ represents True, ∧ is conjunction, ∨ is disjunction, and → is material
implication, among others.

• Predicates are statements that can be true or false depending on the argument AS WELL AS the quantifier. In
predicate logic, a predicate serves the role of a proposition in propositional logic.

• Predicates must have one or more arguments. An argument can be a constant or a variable. If the argument is
a variable, a quantifier must be present in the expression. The only two quantifiers in first-order predicate logic
are the existential and universal quantifiers.

• A predicate with a variable argument has no truth value. For example, a STATEMENT like “x + 1 > 2x”
is NOT A PROPOSITION because it cannot be assigned a truth value. As mentioned in the lecture slides, we
assume a STATEMENT containing a free variable (such as Q(x)) is neither true nor false. However, ∀x Q(x)
or ∃x Q(x) do have truth values because they include quantifiers. Q(−1) has a truth value too since it is a
predicate with a constant argument. This is why we agreed in the first PL lecture that a SENTENCE containing
a variable is NOT a proposition, even if it appears true (e.g., ‘‘2n is even’’).

In a future practice assignment on “proof techniques”, we will see that ‘‘∀n ∈ N : 2n is even’’ can be assigned
a specific truth value. In fact, the statement ‘‘If n is an integer, then 2n is even" can be expressed
in predicate logic as: ∀n Int(n) → Even(2n), where Int(x) is a unary predicate meaning ‘‘x is an
integer" and Even(x) is a unary predicate meaning ‘‘x is even". These are NOT propositions; they are
predicates! The difference between ‘‘2n is even’’ (the non-quantified predicate, which is NOT a proposition)
and ‘‘∀n : 2n is even’’ is subtle!

Exercise 3–5 (Key Focus)

Translate these statements into English, where R(x) is: “x is a rabbit” and H(x) is “x hops”, and the domain U
consists of all animals.

(1) ∀x (R(x) → (2) ∀x (R(x) ∧ H(x)) (3) ∃x (R(x) → (4) ∃x (R(x) ∧ H(x)
H(x)) H(x))

Exercise 3–6 (Key Focus)

Let C(x) be the statement “x has a cat,” let D(x) be the statement “x has a dog,” and let F (x) be the statement “x
has a ferret.” Express each of these statements in terms of C(x), D(x), F (x), quantifiers, and logical connectives.
Let the domain consist of all students in your class.

(1) A student in your class has a cat, a dog, and a ferret.

(2) All students in your class have a cat, a dog, or a ferret.
(3) Some student in your class has a cat and a ferret, but not a dog.
(4) No student in your class has a cat, a dog, and a ferret.
(5) For each of the three animals, cats, dogs, and ferrets, there is a student in your class who has this animal as a
pet.

Exercise 3–7 (Key Focus)

In two different ways, translate each of the following statements into logical expressions using predicates, quantifiers,
and logical connectives. First, in the first way, let the domain consist of the students in your class. Secondly, let it
consist of all people.

(1) Everyone in your class has a cellular phone.

Practice Assignment PA03 (Last Updated: 2025-06-30) Page 2 (of 7)

 The German University in Cairo (GUC) Summer 2025 (RS25)
Faculty of Media Engineering and Technology (MET) Discrete Mathematics
Dr. Ahmed Abdelfattah MATH 501 (MET) / MATH 305 (BI)
; PA03 : Predicate Logic (FoL) <

(2) Somebody in your class has seen a foreign movie.

(3) There is a person in your class who cannot swim.
(4) All students in your class can solve quadratic equations.
(5) Some student in your class does not want to be rich.

Exercise 3–8 (Key Focus)

Express each of these system specifications using predicates, quantifiers, and logical connectives, if necessary.

(1) Every user has access to exactly one mailbox.

(2) There is a process that continues to run during all error conditions only if the kernel is working correctly.
(3) All users on the campus network can access all websites whose URLs have .edu extension.
(4) There are exactly two systems that monitor every remote server.

Exercise 3–9 (Important)

Translate each of these statements into logical expressions using predicates, quantifiers, and logical connectives.

(1) Something is not in the correct place.

(2) All tools are in the correct place and are in excellent condition.
(3) Everything is in the correct place and in excellent condition.
(4) Nothing is in the correct place and is in excellent condition.
(5) One of your tools is not in the correct place, but it is in excellent condition.

Exercise 3–10 (Important)

For each of these statements find a domain for which the statement is true and a domain for which the statement is
false.

(1) Everyone speaks Hindi.

(2) There is someone older than 21 years.
(3) Every two people have the same first name.
(4) Someone knows more than two other people.

Exercise 3–11 (VIP)

(A disguised disproof of (In-)Validity)
For each of these statements find a domain UT for which the statement is true and a domain UF for which the
statement is false.

(1) ∀x P (x) ∨ ∀x ¬P (x).

(2) ∃x P (x) → ∃y Q(y).
(3) P (c), where c is a constant in the domain.
(4) ∀x P (x) ∨ ¬P (x).

Exercise 3–12 (Important)

Express each of these system specifications using predicates, quantifiers, and logical connectives.

Practice Assignment PA03 (Last Updated: 2025-06-30) Page 3 (of 7)

 The German University in Cairo (GUC) Summer 2025 (RS25)
Faculty of Media Engineering and Technology (MET) Discrete Mathematics
Dr. Ahmed Abdelfattah MATH 501 (MET) / MATH 305 (BI)
; PA03 : Predicate Logic (FoL) <

(1) When there is less than 30 megabytes free on the hard disk, a warning message is sent to all users.
(2) No directories in the file system can be opened and no files can be closed when system errors have been detected.
(3) The file system cannot be backed up if there is a user currently logged on.
(4) Video on demand can be delivered when there are at least 8 megabytes of memory available and the connection
speed is at least 56 kilobits per second.

Exercise 3–13 (Negation Basics)

A student is asked to give the negation of “all bananas are ripe.”

(1) The student responds “all bananas are not ripe.” Explain why the English in the student’s response is ambiguous.
(2) Another student says that the negation of the statement is “no bananas are ripe.” Explain why this is not correct.
(3) Another student says that the negation of the statement is “some bananas are ripe.” Explain why this is not
correct.
(4) Give the correct negation.

Exercise 3–14 (Negation Basics)

Express the negation of each of these statements in terms of quantifiers without using the negation symbol.

(1) ∀x (x > 1) (3) ∃x (x ≥ 4) (5) ∀x ((x < −1) ∨ (x > 2))

(2) ∀x (x ≤ 2) (4) ∃x (x < 0) (6) ∃x (x < 4) ∨ (x > 7)

Exercise 3–15 (Negation Key Focus)

Express the negation of these propositions using quantifiers, and then express the negation in English.

(1) Some drivers do not obey the speed limit.

(2) All Swedish movies are serious.
(3) No one can keep a secret.
(4) There is someone in this class who does not have a good attitude.

Exercise 3–16 (Negation Key Focus)

Express each of the following statements using quantifiers. Then, form the negation of the statement so that no
negation is to the left of a quantifier. Next, express the negation in simple English. (Do not simply use the phrase “It
is not the case that . . . ”)

(1) All dogs have fleas.

(2) There is a horse that can add.
(3) Every koala can climb.
(4) No monkey can speak French.
(5) There exists a pig that can swim and catch fish.

Exercise 3–17 (Negation Key Focus)

Express the negations of each of these statements so that all negation symbols immediately precede predicates.

(1) ∃z ∀y ∀x T (x, y, z)

Practice Assignment PA03 (Last Updated: 2025-06-30) Page 4 (of 7)

 The German University in Cairo (GUC) Summer 2025 (RS25)
Faculty of Media Engineering and Technology (MET) Discrete Mathematics
Dr. Ahmed Abdelfattah MATH 501 (MET) / MATH 305 (BI)
; PA03 : Predicate Logic (FoL) <

(2) ∃x ∃y P (x, y) ∧ ∀x ∀y Q(x, y)

(3) ∃x ∃y (Q(x, y) ↔ Q(y, x))
(4) ∀y ∃x ∃z (T (x, y, z) ∨ Q(x, y))

Exercise 3–18 (VIP)

Let L(x, y) be the statement “x loves y,” where the domain for both x and y consists of all people in the world. Use
quantifiers to express each of these statements.

(1) Everybody loves Jerry.

(2) Everybody loves somebody.
(3) There is somebody whom everybody loves.
(4) Nobody loves everybody.
(5) There is somebody whom Lydia does not love.
(6) There is somebody whom no one loves.
(7) There is exactly one person whom everybody loves.
(8) There are exactly two people whom Lynn loves.
(9) Everyone loves himself (or herself).
(10) There is someone who loves no one besides himself (or herself).

Exercise 3–19 (VIP)

Express the negations of these propositions using quantifiers, and in English.

(1) Every student in this class likes mathematics.

(2) There is a student in this class who has never seen a computer.
(3) There is a student in this class who has taken every mathematics course offered at this school.
(4) There is a student in this class who has been in at least one room of every building on campus.

Exercise 3–20 (VIP)

Suppose that the domain U consisting only of students and courses. Let:
U (y): y is an upper-level course M (y): y is a math course F (x): x is a freshman student
A(x): x is a part-time student B(x): x is a full-time student T (x, y): student x is taking course y.
Write the statements from 1 to 9 using the given predicates and any needed quantifiers, and write the other statements
in good English without using variables in your answers.

(1) (student) Hamoksha is taking (course) MATH5.

(2) All students are freshmen.
(3) No student is a freshman.
(4) Every freshman is a full-time student.
(5) No math course is upper-level (course).
(6) Every student is taking at least one course.
(7) There is a part-time student who is not taking any math course.
(8) Every part-time freshman is taking some upper-level course.
(9) There is a full-time freshman who is taking MATH5 and exactly one upper-level course.

Practice Assignment PA03 (Last Updated: 2025-06-30) Page 5 (of 7)

 The German University in Cairo (GUC) Summer 2025 (RS25)
Faculty of Media Engineering and Technology (MET) Discrete Mathematics
Dr. Ahmed Abdelfattah MATH 501 (MET) / MATH 305 (BI)
; PA03 : Predicate Logic (FoL) <

(10) F (Samer)
(11) ¬∃y T (Anass, y)
(12) ∃x (A(x) ∧ ¬F (x))
(13) ∀x ∀y (A(x) ∧ ¬F (x)) → [¬T (x, y) ∧ U (y)]

Exercise 3–21 [VIP] (When the domain of discourse is partitioned)

The universe of discourse in this exercise is divided into two distinct parts, based on the symbol used. The variable
symbol determines the type of elements being discussed: when the symbol x is used, it refers to students; when the
symbol y is used, it refers to courses. Therefore, a quantifier over x always refers to students, while a quantifier over
y always refers to courses.
Now, let’s consider the following predicates:
ST (x): x is a full-time student. P T (x): x is a part-time student. F R(x): x is a freshman.
DF (y): y is a difficult course. M T H(y): y is a math course. T K(x, y): student x is taking course y.

(1) FIRST PART: You are given English statements and predicate logic statements in the following. Write the En-
glish statements using the given predicates (and any needed quantifiers), and write the predicate logic statements
in good English without using variables in your answers.

(a) Noura is taking Discrete Math.

(b) Every freshman is a full-time student.
(c) All students are freshmen.
(d) No math course is difficult.
(e) Every student is taking at least one course.
(f) There is a part-time student who is not taking any math course.
(g) Every part-time freshman is taking some difficult course.
(h) F R(Mazen)
(i) ¬∃y T K(Rawan, y)
(j) ∃x (P T (x) ∧ ¬F R(x))
(k) ∀x∃y T K(x, y)
(l) ∃x∀y T K(x, y)
(m) ∀x∃y [(ST (x) ∧ F R(x)) → (M T (y) ∧ T K(x, y))]

(2) SECOND PART: Match the English statement with all its equivalent symbolic statements in this list:
1. ∃x∀y T K(x, y) 2. ∃y∀x T K(x, y) 3. ∀x∃y T K(x, y)
4. ¬∃x∃y T K(x, y) 5. ∃x∀y ¬T K(x, y) 6. ∀y∃x T K(x, y)
7. ∃y∀x ¬T K(x, y) 8. ¬∀x∃y T K(x, y) 9. ¬∃y∀x T K(x, y)
10. ¬∀x∃y ¬T K(x, y) 11. ¬∀x¬∀y ¬T K(x, y) 12. ∀x∃y ¬T K(x, y)
(a) Every course is being taken by at least one student.
(b) Some student is taking every course.
(c) No student is taking all courses.
(d) There is a course that all students are taking.
(e) Every student is taking at least one course.
(f) There is a course that no students are taking.
(g) Some students are taking no courses.
(h) No course is being taken by all students.
(i) Some courses are being taken by no students.

Practice Assignment PA03 (Last Updated: 2025-06-30) Page 6 (of 7)

 The German University in Cairo (GUC) Summer 2025 (RS25)
Faculty of Media Engineering and Technology (MET) Discrete Mathematics
Dr. Ahmed Abdelfattah MATH 501 (MET) / MATH 305 (BI)
; PA03 : Predicate Logic (FoL) <

(j) No student is taking any course.

Exercise 3–22 (A disguised abstraction of Validity in FoL)

Let U be a finite universe of elements. Let P (x) and Q(x) be unary predicates, and R(x, y) be a binary predicate,
on the elements of U . Determine the scope of the variables in each of the following predicate formulas, then determine
which of them must have the truth value ⊥ (false) under the given interpretation. Justify your answers in detail.

(1) ∀x P (x) ∨ Q(x).

(2) ∀x P (x) ∨ ∀x Q(x).
(3) ∃x P (x) ∨ ∃x ¬P (x).
(4) ∃x P (x) ∧ ∃x ¬P (x).
(5) ∀x P (x) ∧ ∀x ¬P (x).
(6) ∀x P (x) ∧ ¬P (x).
(7) ∀x ∃y P (x) ∧ Q(y) → R(x, y).
(8) ∀x ∃y P (x) → R(x, y) ∧ ∃x R(x, x).

N.B. It is highly recommended to identify and compare the differences and similarities between each of the provided
formulas, particularly since the question is phrased for a very abstract domain.

This isn’t for everyone, that’s clear!

Practice Assignment PA03 (Last Updated: 2025-06-30) Page 7 (of 7)