MATH 211 Exam 1, Spring 2015
American University of Beirut · Discrete Structures · 6 pages
More MATH 211 files
Show the text of this exam
MATH 211 SPRING 2015
TEST I
NAME:
SECTION:
(1) True/False Questions (2 points each): Here A, B etc. denote sets while x, y, · · · denote elements,
and P(A) denotes the power set of a set A
T
F
The logical expression ∃xP(x) → Q(x) is not a proposition.
T
F
{φ} ⊆ {{φ}, {{φ}}, {{φ}}}
T
F
(A ∩ ¯B) ∩ (B ∩ ¯A) ⊆ A ∩ B.
T
F
A and B are two sets such that card(A) = 3 and = card(B) = 4, then card(P (A × B)) =
23 × 24
T
F
existential instantiation states that if ∃xP(x) is true, then you can prove that P(c) is
true for an arbitrarily selected member in the domain.
T
F
If A ⊆ B then ¯A − ¯B ⊆ B.
T
F
The power set of the set A = {φ, {φ}} is the set A itself.
T
F
The following is a valid argument: “if p → q is true, and p → r is true, then p → (q ∨ r)
is true.”
T
F
π is only one member of the set {R, C, R+}, even though it appears three times.
T
F
The proposition (p ∧ q → (¬p → q) → (q → p) is not a contingency
T
F
(A ∩ ¯B) ∪ ( ¯A ∩ B) ∪ (A ∩ B) = A ∪ B
T
F
The set
∞
�
n=0
{n, n + 1, n + 2, · · · } is empty.
1
(2) In the following let the universe of discourse for x be all people in your neighborhood. Using the
premises: D(x): “x has a dog”; F(x, y) is “person x is friends with person y”. Translate the
following statements from logical expressions to English or vice versa, as appropriate.:
(a) (5 pt.) There is a person who does not have a dog and who is friends with everyone in the
neighborhood.
(b) (5 pt.) Only one person does not have a dog.
(c) (5 pt.) Everyone who has a dog is friends with another person who also has a dog.
(d) (5 pt.) ∀x(D(x) → ∀y(D(y) ↔ F(x, y)))
(e) (5 pt.) ∀x∀y(((D(x) ∧ D(y)) ↔ ¬F(x, y))
2
(3) (8 pt.) Use a truth table to find a simpler representation of the compound proposition p → p ⊕ q
(4) (8 pt.) Show that the function f : Z → Z defined as f(n) = n2 + 3n + 4 is not one-to-one.
3
(5) (8 pt.) Let A and B be two sets. Show that A − B ⊆ B − A if and only if A ⊆ B. Which method
of proof did you use?
4
(6) (8 pt.) Prove that an integer n is odd if 3n2 + 7 is even.
(7) (8 pt.) An integer is a perfect square if it can be written as k2 for some integer k. Show that either
3 × 10450 + 7 or 3 × 10450 + 8 is not a perfect square.
5
(8) (11 pt.) Consider the following premises: “All Lebanese people are good looking”, “No stupid
person eats tabbouli”, “people who do not eat tabbouli are ugly”. Prove that “All Lebanese people
are smart”.
(Let the universe of discourse be all people and use the predicates: L(x): “x is Lebanese”, G(x):
“x is good looking”, T(x): “x eats tabbouli”, S(x): “x is smart”.)
6