Netaji Subhash University of Technology, Dwarka.

Delhi

Tutorial Sheet 2 (UNIT-1)

Academic Year: 2022-2023 Semester: 2

CO Mapping

Tutorial Sheet Topics CO1 CO2 CO3 CO4

Objective: The main objective of this Tutorial sheet is to gain the knowledge about Predicates
and quantifier and its applications.

Ques 1: Translate these statements into English, where C(x) is “x is a comedian” and F (x) is “x is
funny” and the domain consists of all people.
a) ∀ x(C(x) → F (x))
b) ∀ x(C(x) ∧ F (x))
c) ∃ x(C(x) → F (x))
d) ∃ x(C(x) ∧ F (x)).
Ques 2: 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.” Then 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.
a) A student in your class has a cat, a dog, and a ferret.
b) All students in your class have a cat, a dog, or a ferret.
c) Some student in your class has a cat and a ferret, but not a dog.
d) No student in your class has a cat, a dog, and a ferret.
e) For each of the three animals, cats, dogs, and ferrets, there is a student in your class
who has this animal as a pet.
Ques 3: Determine the truth value of each of these statements if the domain for all variables
consists of all integers.
a) ∀ n(n2 ≥ 0)
b) ∃ n(n2 = 2)
c) ∀ n(n2 ≥ n)

1
 d) ∃ n(n2 < 0).
Ques 4: Suppose that the domain of the propositional function P (x) consists of 5, 3, 1, 1, 3, and 5.
Express these statements without using quantifiers, instead using only negations,
disjunctions, and conjunctions.
a) ∃ xP (x)
b) ∀ xP (x)
c) ∀ x ((x ̸= 1) → P (x))
d) ∃ x ((x ≥ 0) ∧ P (x))
e) ∃ x (∼ P (x)) ∧ ∀x((x < 0) → P (x)).
Ques 5: Translate in two ways each of these statements into logical expressions using predicates,
quantifiers, and logical connectives. First, let the domain consist of the students in your
class and second, let it consist of all people.
a) Someone in your class can speak Hindi.
b) Everyone in your class is friendly.
c) There is a person in your class who was not born in California.
d) A student in your class has been in a movie.
e) No student in your class has taken a course in logic programming.
Ques 6: Suppose that the domain of Q(x, y, z) consists of triples x, y, z, where x = 0, 1, or 2, y = 0
or 1, and z = 0 or 1. Write out these propositions using disjunctions and conjunctions.
a) ∀ y Q(0, y, 0)
b) ∃ x Q(x, 1, 1)
c) ∃ z ∼ Q(0, 0, z)
d) ∃ x ∼ Q(x, 0, 1).
Ques 7: Suppose that the domain of the propositional function P(x) consists of the integers 0, 1, 2,
3, and 4. Write out each of these propositions using disjunctions, conjunctions, and
negations.
a) ∃ x P (x)
b) ∀ x P (x)
c) ∃ x ∼ P (x)
d) ∀ x ∼ P (x).
e) ∼ ∃ x P (x)
f) ∼ ∀ x P (x).
 Ques 8: For each of these statements find a domain for which the statement is true and a domain
for which the statement is false.
a) Everyone is studying discrete mathematics.
b) Everyone is older than 21 years.
c) Every two people have the same mother.
d) No two different people have the same grandmother.
Ques 9: Find a counterexample, if possible, to these universally quantified statements, where the
domain for all variables consists of all integers.
a) ∀ x (x2 ≥ x)
b) ∀ x (X = 1)
Ques 10: Let P (x), Q(x), andR(x) be the statements “x is a professor,” “x is ignorant,” and “x is
vain,” respectively. Express each of these statements using quantifiers; logical connectives;
and P (x), Q(x), andR(x), where the domain consists of all people.
a) No professors are ignorant.
b) All ignorant people are vain.
c) No professors are vain.
d) Does (c) follow from (a) and (b)?
Ques 11: Let Q(x, y) be the statement “x has sent an e-mail message to y,” where the domain for
both x and y consists of all students in your class. Express each of these quantifications in
English.
a) ∃ x ∃ yQ(x, y)
b) ∃ x ∀ yQ(x, y)
c) ∀ x ∃ yQ(x, y)
d) ∃ y ∀ xQ(x, y)
e) ∀ y ∃ xQ(x, y)
f) ∀ x ∀ yQ(x, y) .
Ques 12: Let S(x) be the predicate “x is a student,” F (x) the predicate “x is a faculty member,” and
A(x, y) the predicate “x has asked y a question,” where the domain consists of all people
associated with your school. Use quantifiers to express each of these statements.
a) Lois has asked Professor Michaels a question.
b) Every student has asked Professor Gross a question.
c) Every faculty member has either asked Professor Miller a question or been asked a
question by Professor Miller.
d) Some student has not asked any faculty member a question.
e) There is a faculty member who has never been asked a question by a student.
f) Some student has asked every faculty member a question.
g) There is a faculty member who has asked every other faculty member a question.
h) Some student has never been asked a question by a faculty member.
Ques 13: Use quantifiers and predicates with more than one variable to express these statements.
a) Every computer science student needs a course in discrete mathematics.
b) There is a student in this class who owns a personal computer.
c) Every student in this class has taken at least one computer science course.
d) There is a student in this class who has taken at least one course in computer science.
e) Every student in this class has been in every building on campus.
f) There is a student in this class who has been in every room of at least one building on
campus.
g) Every student in this class has been in at least one room of every building on campus.
Ques 14: Determine the truth value of each of these statements if the domain for all variables
consists of all integers.
a) ∀ n ∃ m (n2 < m)
b) ∃ n ∀ m (n < m2 )
c) ∀ n ∃ m (n + m = 0)
d) ∃ n ∀ m (nm = m)
Ques 15: Suppose the domain of the propositional function P (x, y) consists of pairs x and y, where x
is 1, 2, or 3 and y is 1, 2, or 3. Write out these propositions using disjunctions and
conjunctions.
a) ∀ x ∀ y P (x, y)
b) ∃ x ∃ y P (x, y)
c) ∃ x ∀ y P (x, y)
d) ∀ x ∃ x P (x, y)