In-class Exercises (2)
Question 1
✘ Let P(x) denote the statement “x ≤ 4.” What are
these truth values?
a) P(0)
b) P(4)
c) P(6)
2
Question 1 (solution)
✘ Let P(x) denote the statement “x ≤ 4.” What are
these truth values?
a) P(0) True
b) P(4) True
c) P(6) False
3
Question 2
✘ Let P(x) be the statement “x spends more than
five hours every weekday in class,” where the
domain for x consists of all students. Express
each of these quantifications in English.
a) ∃xP(x)
b) ∀xP(x)
c) ∃x ￢P(x)
d) ∀x ￢P(x)
4
Question 2 (solution)
✘ Let P(x) be the statement “x spends more than five hours every
weekday in class,” where the domain for x consists of all students. Express
each of these quantifications in English.
a) ∃xP(x) :’’ There is a student who spends more than five hours
every weekday in class.’’
b) ∀xP(x) : “Every student spends more than five hours every
weekday in class.”
c) ∃x ￢P(x):” There is a student who does not spend more than
five hours every weekday in class.”
d) ∀x ￢P(x) :” No student spends more than five hours every
weekday in class. (Or, equivalently, every student spends less than
or equal to five hours every weekday in class.)”
5
Question 3
✘ 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))
6
Question 3(solution)
✘ 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))
This statement is that for every x, if x is a
comedian, then x is funny. In English, this is
most simply stated, "Every comedian is
funny."
7
Question 3(solution)
✘ 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.
b) ∀x(C(x) ∧ F(x))
This statement is that for every x in the
domain (universe of discourse), x is a
comedian and x is funny. In English, this is
most simply stated, "Every person is a funny
8 comedian."
Question 3(solution)
✘ 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.
c) ∃x(C(x) → F(x))
This statement is that there exists an x in the
domain such that if x is a comedian then x is
funny. In English, this might be rendered,
"There exists a person such that ifs/he is a
9 comedian, then s/he is funny."
Question 3(solution)
✘ 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.
d) ∃x(C(x) ∧ F(x))
This statement is that there exists an x in the
domain such that x is a comedian and x is funny. In
English, this might be rendered, ''There exists a
funny comedian" or "Some comedians are funny"
or "Some funny people are comedians."
10
Question 4
✘ Let P(x) be the statement “x can speak Russian” and let Q(x) be the
statement “x knows the computer language C++.” Express each of these
sentences in terms of P(x), Q(x), quantifiers, and logical connectives. The
domain for quantifiers consists of all students at your school.
a) There is a student at your school who can speak Russian and
who knows C++.
b) There is a student at your school who can speak Russian but
who doesn’t know C++.
c) Every student at your school either can speak Russian or knows
C++.
d) No student at your school can speak Russian or knows C++.
11
Question 4(solution)
✘ Let P(x) be the statement “x can speak Russian” and let Q(x) be the
statement “x knows the computer language C++.” Express each of these
sentences in terms of P(x), Q(x), quantifiers, and logical connectives. The
domain for quantifiers consists of all students at your school.
a) There is a student at your school who can speak Russian and who
knows C++. ∃x(P(x) ˄ Q(x)).
b) There is a student at your school who can speak Russian but who
doesn’t know C++. ∃x(P(x) ˄ ￢Q(x)).
c) Every student at your school either can speak Russian or knows C++.
∀ x(P(x) ˅Q(x))
d) No student at your school can speak Russian or knows C++.
12
￢ ∃x( P(x) ˅ Q(x) ) ≡ ∀ x(￢(P(x)) ˄ ￢(Q(x) )) .
Question 5
✘ Determine the truth value of each of these
statements if the domain consists of all integers.
a) ∀n(n + 1 > n)
b) ∃n(2n = 3n)
c) ∃n(n = −n)
d) ∀n(3n ≤ 4n)
13
Question 5(solution)
✘ Determine the truth value of each of these
statements if the domain consists of all integers.
a) ∀n(n + 1 > n) True
b) ∃n(2n = 3n) True since 2 · 0 = 3 · 0,
c) ∃n(n = −n) True since 0 = -0.
d) ∀n(3n ≤ 4n) False 3(-2) '≤ 4(-2).
14
Question 6
✘ 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) ∃xP(x)
b) ∀xP(x)
c) ∃x￢P(x)
d) ∀x￢P(x)
e) ￢∃xP(x)
f ) ￢∀xP(x)
15
Question 6(solution)
✘ 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) ∃xP(x)
P(O) V P(l) V P(2) V P(3) V P(4).
16
Question 6(solution)
✘ 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.
b) ∀xP(x)
P(O) ˄ P(l) ˄ P(2) ˄ P(3) ˄ P(4)
17
Question 6(solution)
✘ 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.
c) ∃x￢P(x)
￢ P(O) V ￢ P(l) V ￢ P(2) V ￢ P(3) V ￢ P(4)
18
Question 6(solution)
✘ 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.
d) ∀x￢P(x)
￢ P(O) ˄ ￢ P(l) ˄ ￢ P(2) ˄ ￢ P(3) ˄ ￢ P(4)
19
Question 6(solution)
✘ 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.
e) ￢∃xP(x)
￢ (P(O) V P(l) V P(2) V P(3) V P(4))
20
Question 6(solution)
✘ 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.
f ) ￢∀xP(x)
￢ (P(O) ˄ P(l) ˄ P(2) ˄ P(3) ˄ P(4))
21
Question 7
What are the negations of the statements ∀x(x2 > x) and
∃x(x2 = 2) ?
22
Question 7(solution)
What are the negations of the statements ∀x(x2 > x) and
∃x(x2 = 2) ?
1. The negation of ∀x(x2 > x) is the statement ￢∀x(x2 > x),
which is equivalent to ∃x￢(x2 > x). This can be rewritten
as ∃x(x2 ≤ x).
2. The negation of ∃x(x2 = 2) is the statement ￢∃x(x2 = 2),
which is equivalent to ∀x￢(x2 = 2). This can be rewritten
as ∀x(x2 ≠ 2).
23
Question 8
✘ Use predicates and quantifiers to express the
system specifications
✗ “Every mail message larger than one megabyte will be
compressed”
✗ “If a user is active, at least one network link will be
available.”
24
Question 8 (solution)
✘ Use predicates and quantifiers to express the
system specifications
✗ “Every mail message larger than one megabyte will be
compressed”
✘ Let S(m, y) be “Mail message m is larger than y megabytes,” where the
variable x has the domain of all mail messages and the variable y is a positive
real number, and let C(m) denote “Mail message m will be compressed.” Then
the specification “Every mail message larger than one megabyte will be
compressed” can be represented as ∀m(S(m, 1) → C(m)).
25
Question 8 (solution)
✘ Use predicates and quantifiers to express the
system specifications
✗ “If a user is active, at least one network link will be
available.”
✘ Let A(u) represent “User u is active,” where the variable u has the domain of
all users, let S(n, x) denote “Network link n is in state x,” where n has the
domain of all network links and x has the domain of all possible states for a
network link. Then the specification “If a user is active, at least one network
link will be available” can be represented by ∃uA(u) → ∃nS(n, available).
26
THANKS!
Any questions?
27