Class Notes: Applied Discrete Structures

Spring Semester 1999 - MWF 5th Period CSE/E222, Section 4617X

Instructor: M.S. Schmalz -- TAs: James Jeffers, Yasmeen Fatimah, Jang-Uk In, Arun Srinivasan, Jing Zhao

Quiz #2 -- Solution

Question 1. (5 points) Prove or disprove the following statement without using truth tables:

"(not(p) and (p -> q) or r) -> not(q)" is a tautology.

Solution. Denote x = [not(p) and (p -> q)], yielding x or r -> not(q).
(1) By identity laws, T or r = T.

(2) By identity laws, [not(p) and (p -> q)] -> not(q).

(3) Thus, x = T.

(4) We now have T or r -> T, which yields T or r -> not(q).

(5) Therefore, the statement is a tautology.

Question 2. (5 points) Let f : A -> B and g : B -> C be functions. If f is onto and g is into, is f o g (a) a valid mapping, and (b) onto or into ?

Solution.
(a) Yes, since we are taking g(f(x)), where x is an element of A.

(b) f o g is onto because f and g are onto. So, the composition of f and g is onto, by the definition of composition and the fact that the composition maps A to C.

Copyright © 1999 by Mark S. Schmalz.