Discrete Math: Logic and Directed Graphs

Exam 1 - Spring 2003 - Discrete Structures
1. Circle T for True or F for False as they apply to the following statements:
T F Every compound is either a tautology or a contradiction.
T F Integers are Rational.
T F The empty set has no subsets.
T F Onto functions map smaller sets to bigger sets.
T F Disjoint sets have non-empty intersections.
T F In Logic, the Implication process is, in reality, a Disjunctive process.
T F A Sequence is a Function with the inputs selected in an ordered fashion.
T F Bijective functions maps sets of the same cardinality to one another.
T F The converse and inverse of a conditional statement are logically equivalent.
T F The negation of a universal conditional predicate is an existential conditional.


2. Find the truth table for the compound statement: q ¬[q (r ¬p)]


3. Find the related forms for the Universal Conditional Statement:
Every integer that is greater than 1 has a unique prime factorization.
CONVERSE: INVERSE: CONTRAPOSITIVE: NEGATION:


4. Find set X so that the function, f:Z X, given by f(n) = 2n + 3 is a bijection (one-to-one and onto).

n 5 5 5

2i . (b) Show that: ( 5i + i) = 5 i + i.
2 2
5. (a) Find the first 4 terms of the sequence an =
i=0 i=1 i=1 i=1


(
6. Calculate the following: (a) L 000000000000)(b) d(001100110101101)

(c) H(101100111000,111111000000) (d) ( 3.3 + 1 ) ( 5.9 )


7. (a) List the elements of a Bijective function from {2, -4, 8, -16, 32} to {1, 2, 3, 4, 5}

(b) Find the Inverse of the function you described in (a).

(c) Use Directed Graphs to verify that the composition of your function with its inverse is the Identity
function. Only test for the composition in one direction.


8. Find a formula for the following series: (a) 2 + 4 + 6 + ... + (2n) (b) 1 + 5 + 52 + 53 + ... + 5(2n+1)


9. Use the Laws of Logic to verify: p p (p q).