MATH 2345 SYLLABUS (3 SEMESTER HOUR COURSE)

Pre-requisite: Math 2253, Calculus I

Text:Discrete Mathematics with Applications, Second Edition, Susanna S. Epp

A basic calculator is needed for this course. The calculator policy is set by the instructor.

The following sections are suggested. Unless otherwise indicated the sections are from Epp. The level of the course is indicated by the homework problems chosen. Due to time restrictions and the book's organization, material in some sections should be covered differently than the text. This is indicated where appropriate.

Section 1.1 Logical Form and Logical Equivalence

Homework: pg. 15; 6-10,12-15,17-33 odd,37,39,43,45,48

Section 1.2 Conditional Statements

Homework: pg. 27; 1-19 odd,20,22,24,25,28,29,33-39 odd

Section 2.1 Predicates and Quantified Statements I

Homework: pg. 87; 1,4-13,17,19,24-26,28,29,31

Section 2.2 Predicates and Quantified Statements II

Homework: pg. 97; 1-9 odd,11-13,16,17,31-37 odd,42

There is a great deal of material in Chapter 3 that is not needed for the homework problems chosen. As far as "definitions and unproven assumptions" are concerned, it is possible to work with all three proof techniques (Direct, Contrapositive, and Contradiction) in the suggested homework problems using only:

The definitions of even and odd on page 114.

Assuming "Every integer is either even or odd, but not both".

Assuming "Products, sums, and positive integer powers of

integers are integers".

The definitions of prime and composite on page 115.

The definition of divisibility on page 132.

It is suggested that these definitions and assumptions be stated clearly when beginning Chapter 3 as the only ones to be used.

Section 3.1 Direct Proof and Counterexample I: Introduction

Homework: pg. 124; 1-4,6-8,12-16,22,23,25,29,30,32,

34,35,41

Section 3.3 Direct Proof and Counterexample III: Divisibility

Homework: pg. 138; 1-9 odd,14,16,18,19,21,22,24-26

Section 3.6 Indirect Argument: Contradiction and Contraposition

Homework: pg. 161; 1,5,7,8,10,12,13,15,17,21

Section 4.1 Sequences

Homework: pg. 192; 1,3,10-15,18,21,22,24,29,31,32,48-54

Section 4.2 Mathematical Induction I

Homework: pg. 204; 1,5,7-9,11,13,14,19-28

Section 4.3 Mathematical Induction II

Homework: pg. 210; 2,3,5,8-10,12,16,17,20-22,24

Chapter 5 includes element chasing proofs of set theoretic statements. In the interest of time these have been omitted in the selection of homework problems. The goal is to make students familiar with notation, definitions (particularly those that may be less familiar such as cross product, partitions, formal languages, and power sets), and the use of Venn diagrams.

Section 5.1 Basic Definitions of Set Theory

Homework: pg. 242; 1-8,13-15,17,19,20

Section 5.3 The Empty Set, Partitions, Power Sets, and Boolean Algebras

Homework: pg. 266; 1,35-41,42ab,44-46

In chapter 6 the text uses probability occasionally. This is to be omitted from assigned problems where it occurs. That is, any homework problems involving probability are treated as two separate counting problems, one for the numerator and one for the denominator. This avoids a consideration of whether the objects being counted are equally likely.

Section 6.2 Possibility Trees and the Multiplication Rule

Homework: pg. 292; 1,3,4,8-11,14-20,28,30-38

Section 6.3 Counting Elements of Disjoint Sets: The Addition Rule

Homework: pg. 303; 1,3,4,6,9,11,14,17,18,20-25,27

Section 6.4 Counting Subsets of a Set: Combinations

Homework: pg. 320; 1,2a,4-6,8-10,13,14,16,17,19,20,22,23

Section 6.5 R-Combinations with Repetition Allowed

Homework: pg. 328; 1-4,10-14,16-19

Section 7.2 Applications: Finite-State Automata

Homework: pg. 367; 1-3,5,8-16,18-21,23,27,28

Section 10.1 Relations on Sets

Homework: pg. 544; 1-3,6,8,10,14-16,19,23-27,29

Section 10.2 Reflexivity, Symmetry, and Transitivity

Homework: pg. 554; 1-5,9-15,19,20,23-26,33,34,37,43,44

Section 11.1 Graphs: An Introduction

Homework: pg. 616; 1,3,5,6,8,15-23,25,27-29,33-37,39,40,44,45

Section 11.2 Paths and Circuits

Hamiltonian circuits are ommitted.

Homework: pg. 636; 1,2,4,5,7-22,47a,48a

Section 11.4 Isomorphisms of Graphs

Isomorphism is only done for simple graphs. This allows the treatment of an isomorphism as a single function involving the vertex sets (avoiding an additional mapping for the edge sets).

Homework: pg. 662; 6-15,17-19

Section 11.5 Trees

Homework: pg. 681; 1,3,5,7,8-23,30,32,33

Section 11.6 Spanning Trees

Homework: pg. 692; 1-8,11,23,24

Note: Elements of this syllabus are subject to revision.