# Discrete Math: Logic and Directed Graphs

Please see the attached file for the fully formatted problems.

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).

5. (a) Find the first 4 terms of the sequence an = . (b) Show that: .

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

(c) H(101100111000,111111000000) (d)

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).

2i

i = 0

n

5i2 ( + i)

i = 1

5

5 i2

i = 1

5

i

i = 1

5

= +

( 3.3 + 1)( 5.9 )

#### Solution Preview

1.)

Every compound is either a tautology or a contradiction: F: because there is a possibility of neither also.

Integers are Rational: T: It can be written in the form of p/q, where, p and q are integers.

The empty set has no subset: T: because it has no element

Onto function map smaller set to bigger sets: F: onto means codomain = range.

Disjoint sets have non-empty intersection: F: disjoint sets means no intersection at all.

In logic, the implication process is in reality a Disjunctive process: F:

p=====1=1=0=0

q=====1=0=1=0

p->q==1=0=1=1

pvq===1=1=1=0

Therefore, from truth table: pvq != p->q.

A sequence is a function with the inputs selected in an order fashion: T

Bijective functions maps sets of the same cardinality to one another: T

The converse and inverse of a conditional statement are logically equivalent: ...

#### Solution Summary

A variety of discrete math problems are solved.