NOTE: This is a plaintext page. Some symbols expressed in ascii
may not look quite right in some browsers. When in doubt, download
the source file and look through an editor,
or check the sunya.class.csi210 newsgroup.
In particular: --> represents implication
<--> represents if and only if (biconditional)
~ represents negation
\/ represents disjunction
/\ represents conjunction
<==> represents logical equivalence
(i.e., a statement about 2 formulas)
and other operators are spelled out when necessary; e.g.,
EXISTS represents the existential quantifier
EXISTS! represents the uniqueness quantifier (exists unique)
FORALL represents the universal quantifier
NAND represents the Sheffer stroke, or NOT AND
NOR represents the uparrow, or NOT OR
XOR represents the exclusive OR operator
CSI 210 - Discrete Structures - Fall 2009
Sample Problems - Exam I
(Note: These are individual sample QUESTIONS; they do *not* form,
collectively, a sample EXAM. So this is a study aid for you, but
it is not an old exam, nor does it represent an exam, per se.)
1. State the converse of each of the following implications:
(a) If n > 3, then n^2 > 9.
(b) A positive integer is prime only if it has no divisors other
than 1 and itself.
2. State the contrapositive of each of the following implications:
(a) I go to the beach whenever it is a sunny summer day.
(b) If x^2 > 9, then x > 3.
3. (a) Verify that the propositional forms p XOR q and NOT (p IFF q)
have the same truth table.
(b) Construct a truth table for (i) p XOR p and (ii) (p XOR p) XOR p.
4. Restate the following as implications of the form "If ..., then...".
(a) A necessary condition that a given quadrilateral ABCD be a
rectangle is that it be a parallelogram.
(b) A sufficient condition that ABCD be a rectangle is that it be
a square.
(c) A necessary condition that a given integer n be divisible by
9 is that it be divisible by 3.
(d) A sufficient condition for n to be divisible by 9 is that the
sum of its digits be divisible by 9.
5. Use the logical equivalences discussed in class to prove the
following equivalences:
(a) (NOT(p AND q) --> (NOT p OR (NOT p OR q))) <--> (NOT p OR q)
(b) ((p OR q) AND (NOT p OR q) AND (p OR NOT q) AND (NOT p OR NOT q))
<--> 0.
Also state the equivalence obtained by applying the principle
of duality to this equivalence.
6. Simplify the following propositional forms:
(a) (p --> (q OR NOT r)) AND NOT p AND q
(b) p --> ((p OR q) AND (p OR NOT q))
7. (a) Express the propositional form p AND q using only the NOR
operator.
(b) Express the propositional form p XOR q using only the NAND operator.
(c) Express the propositional form (a AND b) OR (c AND d) using only
the NAND operator.
8. Let U = {1,2,3} denote the universe for the variables x and y in
the following predicates.
Express the following propositional forms using conjunctions,
disjunctions and negations.
(a) FORALL(x) FORALL(y) P(x,y) (b) FORALL(x) EXISTS(y) P(x,y)
(c) NOT EXISTS(x) P(x) (d) FORALL(x)NOT P (x)
(e) EXISTS(x)(P (x) OR Q(x)) (f) (EXISTS(x)P(x)) OR (EXISTS(x)Q(x))
9. Let P(x,y,z) denote the predicate "x - y = z" over the universe
of integers. Transcribe the following assertions into logical
notation.
(a) For every x and every y, there is some z such that x - y = z.
(b) There is an x such that for every y, y - x = y.
(c) When 0 is subtracted from any integer, the result is the
integer itself.
(d) 3 subtracted from 5 gives 2.
10. Let Q(x,y) denote the predicate (x-y >= -1) AND (x-y <= 1)
and U = {1,2,3} be the universe for both the variables x and y.
Find the truth values of the propositions
(a) EXISTS(x)EXISTS(y)Q(x,y)
(b) FORALL(x)EXISTS(y)Q(x,y)
(c) EXISTS(x)FORALL(y)Q(x,y).
(d) FORALL(x)FORALL(y)Q(x,y).
10.1. Let A = {q}.
What is the powerset of the powerset of A? [I.e., P(P(A))]
10.2. What is P(A) X P(A)?
10.3. What is P(P(A)) X P(P(A))?
11. Prove that for any two sets A and B, A SUBSET B iff A UNION B = B.
12. Prove or disprove the following statements. (Note that to
"disprove" a statement, you need to provide only one counter example).
(a) If (A UNION B) SUBSET (A INTERSECT B), then A = B.
(b) If A INTERSECT B = A INTERSECT C and A UNION B = A UNION C,
then B = C.
13. (a) Given that A SUBSET C and B SUBSET D,
prove that A x B SUBSET C x D.
(b) Prove or disprove: If A x B SUBSET C x D,
then A SUBSET C and B SUBSET D.
14. Let R denote the set of real numbers. Determine whether the
following functions from R to R are one-to-one and onto.
(a) f(x) = 2x + 1.
(b) f(x) = (x^2 + 1)/(x^2 + 2).
15. Let R denote the set of real numbers. Consider the function f on
R x R defined by f (x,y) = (x+y, x-y).
(a) Prove that f is a bijection.
(b) Find f inverse.
16. Let g : X --> Y and f : Y --> Z be functions. Prove or disprove:
If f o g (f composed with g) is onto, then g is onto.
-=*+#%|%#+*=-=*+#%|%#+*=-=*+#%|%#+*=-
-=*+#%|%#+*=-=*+#%|%#+*=-=*+#%|%#+*=-
-=*+#%| |%#+*=-
-=*+#%| ANSWERS BELOW |%#+*=-
-=*+#%| |%#+*=-
-=*+#%|%#+*=-=*+#%|%#+*=-=*+#%|%#+*=-
-=*+#%|%#+*=-=*+#%|%#+*=-=*+#%|%#+*=-
Solutions to Practice Problems - I
Question 1:
Part(a): If n^2 > 9, then n > 3.
Part(b): A positive integer is prime if it has no divisors other
than 1 and itself.
Question 2:
Part (a): If I don't go to the beach then it is not a sunny summer day.
Part (b): If x <= 3 then x^2 <= 9. (Note that "not >" is "<=").
Question 3:
Part (a): both tables have 4 rows: 0110 is the final column.
Part (b): both tables have 2 rows: 00 and 01 are the final columns.
Notice that (p XOR p) <==> 0 and that (p XOR p) XOR p <==> p.
Question 4:
(a) If a quadrilateral ABCD is a rectangle, then it is a parallelogram.
(b) If ABCD is a square, then it is rectangle.
(c) If n is divisible by 9, then it is divisible by 3.
(d) If the sum of its digits of n is divisible by 9,
then n is divisible by 9.
Question 5:
Part (a):
(NOT(p AND q) --> (NOT p OR (NOT p OR q)))
<==> (NOT(p AND q) --> ((NOT p OR NOT p) OR q)) (Associativity of OR)
<==> (NOT(p AND q) --> (NOT p OR q)) (Idempotence of OR)
<==> ((p AND q) OR (NOT p OR q)) (Implication rule)
<==> (((p AND q) OR NOT p) OR q) (Associativity of OR )
<==> (((p OR NOT p) AND (q OR NOT p)) OR q)
(Distributivity of OR over AND )
<==> ((q OR NOT p) OR q) (Since (p OR NOT p) <==> 1)
<==> (NOT p OR q)
(Commutativity, Associativity and Idempotence of OR )
Part (b):
((p OR q) AND (NOT p OR q) AND (p OR NOT q) AND (NOT p OR NOT q))
<==> ((p AND NOT p) OR q) AND ((p AND NOT p) OR NOT q)
(Associativity of AND, Distributivity of OR over AND )
<==> (0 OR q) AND (0 OR NOT q) (Since (p AND NOT p) <==> 0)
<==> (q AND NOT q)
<==> 0
The dual of the above equivalence is:
((p AND q) OR (NOT p AND q) OR (p AND NOT q) OR (NOT p AND NOT q)) <==> 1
Question 6:
Part (a):
(p --> (q OR NOT r)) AND NOT p AND q
<==> ((NOT p OR (q OR NOT r)) AND NOT p) AND q
(Implication rule<==> Associativity of AND )
<==> ((NOT p AND NOT p) OR (NOT p AND (q OR NOT r))) AND q
(Distributivity of AND over OR )
<==> (NOT p OR (NOT p AND (q OR NOT r))) AND q (Idempotence of AND)
<==> (NOT p AND q) (Absorption rule - see note below)
Note: In the last step above,
Absorption rule was used by setting s = NOT p and t = (q OR NOT r) and
noticing that the expression of the previous step is simply s OR (s AND t).
Part (b):
p --> ((p OR q) AND (p OR NOT q))
<==> NOT p OR ((p OR q) AND (p OR NOT q)) (Implication rule)
<==> NOT p OR (p OR (q AND NOT q)) (Distributivity of OR over AND)
<==> NOT p OR (p OR 0) (Since (q AND NOT q) <==> 0)
<==> NOT p OR p (Identity law)
Question 7:
Part (a): We will use the property that (s NOR s) <==> NOT s.
p AND q <==> NOT(NOT p OR NOT q) (DeMorgan's Law)
<==> (NOT p NOR NOT q) (Definition of NOR)
<==> (p NOR p) NOR (q NOR q) (Property above)
Part (b): You can verify (by constructing truth tables if necessary) that
(p XOR q) <==> ((p AND NOT q) OR (NOT p AND q))
and
(p NAND p) <==> NOT p.
Now, ((p AND NOT q) OR (NOT p AND q))
<==> NOT(NOT(p AND NOT q) AND NOT(NOT p AND q)) (DeMorgan's Law)
<==> NOT(p AND NOT q) NAND NOT(NOT p AND q) (Definition of NAND)
<==> (p NAND NOT q) NAND(NOT p NAND q) (Definition of NAND)
<==> (p NAND(q NAND q)) NAND((p NAND p) NAND q)
(Property of NAND mentioned above)
Part (c):
(a AND b) OR (c AND d) <==> NOT(NOT(a AND b) AND NOT(c AND d))
(DeMorgan's Law)
<==> NOT(a AND b) NAND NOT(c AND d)
(Definition of NAND)
<==> (a NAND b) NAND (c NAND d) (Definition of NAND)
2
Question 8: Here U = {1, 2, 3}.
Part (a):
FORALL(x)FORALL(y)P (x,y) <==> [P (1,1) AND P (1,2) AND P (1,3)] AND
[P (2,1) AND P (2,2) AND P (2,3)] AND
[P (3,1) AND P (3,2) AND P (3,3)]
Part (b):
FORALL(x)EXISTS(y)P (x,y) <==> [P (1,1) OR P (1,2) OR P (1,3)] AND
[P (2,1) OR P (2,2) OR P (2,3)] AND
[P (3,1) OR P (3,2) OR P (3,3)]
Part(c):
NOT EXISTS(x) P(x) <==> NOT(P(1) OR P(2) OR P(3))
<==> NOT P(1) AND NOT P(2) AND NOT P(3)
Part(d): FORALL(x)NOT P(x) <==> NOT P(1) AND NOT P(2) AND NOT P(3)
Part(e): EXISTS(x)(P(x) OR Q(x)) <==> (P(1) OR Q(1)) OR (P(2) OR Q(2))
OR (P(3) OR Q(3))
Part(f): (EXISTS(x) P(x)) OR (EXISTS(x)Q(x)) <==>
(P(1) OR P (2) OR P (3)) OR (Q(1) OR Q(2) OR Q(3))
Question 9:
Part(a): FORALL(x)FORALL(y)EXISTS(z) P(x,y,z)
Part(b): EXISTS(x)FORALL(y) P(y,x,y)
Part(c): FORALL(x) P(x,0,x)
Part(d): P(5,3,2)
Question 10:
Part(a): True, because Q(1,1) is true.
Part(b): True, because Q(x,2) is true for all x. (or choose y=x)
Part(c): True, because Q(2,y) is true for all y. (i.e., choose x=2)
Part(d): False, because Q(1,3) is false.
Question 10.1:
A = {q}, so P(A) = { {}, {q} } which could be written { {}, A },
and so P(P(A)) = { {}, {{}}, {{q}}, {{}, {q}} }
which could be written { {}, {{}}, {A}, P(A) }
Question 10.2:
P(A) X P(A) = { ({},{}), ({},A), (A,{}), (A,A) }
Question 10.3:
P(P(A)) X P(P(A)) = {
({},{}), ({},{{}}), ({},{A}), ({},P(A)),
({{}},{}), ({{}},{{}}), ({{}},{A}), ({{}},P(A)),
({A},{}), ({A},{{}}), ({A},{A}), ({A},P(A)),
(P(A),{}), (P(A),{{}}), (P(A),{A}), (P(A),P(A))
}
Question 11:
To prove: A SUBSET B iff A UNION B = B.
The proof is in two parts.
Part 1: Assume that A SUBSET B.
We will prove that (A UNION B) = B. (also in 2 parts)
Proof: Let x MEMBER (A UNION B). Then,
x MEMBER (A UNION B) ==> (x MEMBER A) OR (x MEMBER B) (Definition of UNION)
==> (x MEMBER B) OR (x MEMBER B) (Since A SUBSET B)
==> (x MEMBER B) (Since OR is idempotent)
Thus (A UNION B) SUBSET B. (part 1a)
Obviously, B SUBSET(A UNION B). (part 1b)
Therefore, B = A UNION B.
Part 2: Assume that A UNION B = B. We will prove that A SUBSET B.
Let x MEMBER A. Then x MEMBER (A UNION B) by the definition of union.
Since A UNION B = B, it follows that x MEMBER B.
Thus A SUBSET B.
This completes the proof.
Question 12:
Part (a): If (A UNION B) SUBSET (A INTERSET B), then A = B.
The statement is true.
Proof (by contradiction): Suppose (A UNION B) SUBSET (A INTERSECT B)
but A <> B. Then, without loss of generality,
there is an element (x MEMBER A) such that (x NOTMEMBER B).
Now, x MEMBER (A UNION B) (definition of union)
and x NOTMEMBER (A INTERSECT B) (definition of intersection)
and so (A UNION B) NOT SUBSET (A INTERSECT B),
contradicting the given condition. This completes the proof.
Part (b): If (A INTERSECT B) = (A INTERSECT C)
and (A UNION B) = (A UNION C), then B = C.
This statement is also true.
Proof (by contradiction): Suppose (A INTERSECT B) = (A INTERSECT C)
and (A UNION B) = (A UNION C), but (B <> C).
Then, without loss of generality,
there is an element x MEMBER B such that x NOTMEMBER C.
We now have two cases.
Case 1: x MEMBER A.
In this case, x MEMBER (A INTERSECT B) but x NOTMEMBER (A INTERSECT C).
This contradicts the assumption (A INTERSECT B) = (A INTERSECT C).
Case 2: x NOTMEMBER A.
In this case, x MEMBER (A UNION B) (since x MEMBER B)
but x NOTMEMBER (A INTERSECT C)
(since x is neither in A nor in C). Therefore,
(A UNION B) <> (A UNION C), again contradicting the given condition.
This completes the proof.
Question 13:
Part (a): Given: (A SUBSET C) and (B SUBSET D).
To prove: (A x B) SUBSET (C x D).
Proof: Let (x,y) be a member of A x B. Then,
(x,y) MEMBER A x B ==> (x MEMBER A) AND (y MEMBER B)
(Definition of product)
==> (x MEMBER C) AND (y MEMBER D)
(Since A SUBSET C and B SUBSET D)
==> (x,y) MEMBER C x D (Definition of product)
Thus A x B SUBSET C x D.
Part (b): The statement is false as the following counter example shows.
Let A = EMPTYSET, B = {1,2}; C = {1} and D = {1}. Then A x B = emptyset,
and so is trivially a subset of C x D. However, B is not a subset of D.
Question 14:
Part (a): f (x) = 2x + 1 is both one-to-one and onto.
To show that f is one-to-one, suppose f(x1) = f(x2). We must
show that x1 = x2. Since f(x1) = f(x2) we have, 2(x1) + 1 = 2(x2) + 1.
From this equation, we have x1 = x2. Thus f is one-to-one.
To show that f is onto, let y be an arbitrary element of R. We
will show that there is an element t in R such that y = f(t). By the
definition of f , we have y = 2t + 1. Thus t = (y - 1)/2. Since y is
a real number, so is t and thus f is onto.
Part (b): f(x) = (x^2 + 1)/(x^2 + 2) is neither one-to-one nor onto.
To see that f is not one-to-one, notice that for distinct real
numbers 1 and -1, f(1) = f(-1) = 2/3.
To see that f is not onto, observe that the value of f is always
less than 1. Thus the real number 1 is not in the range of f and so f
is not onto.
Question 15:
Given: The function f on R x R defined by f(x, y) = (x + y, x - y).
Part (a): To prove: f is a bijection.
The proof is in two parts.
Part 1: We will prove that f is one-to-one.
Proof: Consider two elements (x, y) and (x', y') in R x R. We will
show that if f(x, y) = f(x', y'), then (x, y) = (x', y') (i.e., x = x'
and y = y').
Using the definition of f , we have
f(x, y) = (x + y, x - y) and f(x', y') = (x' + y', x' - y')
Now, the condition f(x, y) = f(x', y') implies
x + y = x' + y' and x - y = x' - y'
Adding the last two equations, we see that x = x'. Subtracting
the second equation from the first, we see that y = y'. Therefore, f
is one-to-one.
Part 2: To prove: f is onto.
Proof: Consider an arbitrary element (p, q) in (R x R). We will show that
there are real numbers x and y such that f(x, y) = (p, q).
Using the definition of f , if f(x, y) = (p, q), we have,
x + y = p and x - y = q
Solving these simultaneous equations for x and y, we get,
x = (p + q)/2 and y = (p - q)/2
Since p and q are real numbers, the values of x and y given by
the above equations are also real numbers. This completes the proof
that f is onto.
Since f is both one-to-one and onto, f is a bijection.
-1
Part (b): To find f inverse = f .
-1
Let f (p, q) = (x, y). We have to show how to find x and y,
given p and q. We showed in the proof of Part 2 that x = (p + q)/2
and y = (p - q)/2.
-1
Thus f (p, q) = ((p + q)/2, (p - q)/2).
Question 16:
Given: g : X --> Y and f : Y --> Z are functions.
To Prove or disprove: If (f o g) is onto then g is onto.
The statement is false as shown by the following counter example.
Let X = {a, b, c}, Y = {p, q, r} and Z = {1, 2} and consider the
functions f and g defined below:
g(a) = p, g(b) = q, g(c) = q and f(p) = 1, f(q) = 2, f(r) = 2
Now, we can obtain the definition of (f o g):
(f o g)(a) = 1, (f o g)(b) = 2, (f o g)(c) = 2
Thus, range(f o g) = Z (i.e., (f o g) is onto) but g is not onto
(r is not in range(g)).