MATH-2010: Introduction to Discrete Mathematics

MATH-2010: Introduction to Discrete Mathematics 1

MATH-2010: INTRODUCTION TO DISCRETE MATHEMATICS

Cuyahoga Community College

Viewing: MATH-2010 : Introduction to Discrete Mathematics

Board of Trustees:

March 2024

Academic Term:

Fall 2024

Subject Code

MATH - Mathematics

Course Number:

2010

Title:

Introduction to Discrete Mathematics

Catalog Description:

Foundation course in discrete mathematics with applications. Topics include logic, methods of proof, mathematical induction,

elementary number theory, sequences, set theory, functions, counting and probability, and graph theory.

Credit Hour(s):

Lecture Hour(s):

Requisites

Prerequisite and Corequisite

MATH-1530 College Algebra or MATH-153H College Algebra or MATH-1580 Precalculus; or qualiﬁed Math placement; or departmental

approval: equivalent coursework.

Outcomes

Course Outcome(s):

Apply logical analysis to compound statements.

Objective(s):

1. Translate between English sentences and logical form.

2. Construct and interpret truth tables for compound statements involving negation, conjunction, disjunction, conditional, and

biconditional connectives.

3. Apply DeMorgan's Laws to ﬁnd the negations of and and or statements.

4. Deﬁne and apply tautology and contradiction.

5. Apply basic laws of equivalence to determine if statements are logically equivalent.

6. Deﬁne and apply conditional statements, negation, contrapositive,converse, inverse, biconditional statements, and necessary and

sufﬁcient conditions.

7. Deﬁne and apply arguments and argument forms.

8. Determine if an argument form is valid or invalid.

9. Recognize and apply rules of inference (e.g., modus ponens, modus tollens, generalization, specialization, conjunction, elimination,

and transitivity) and fallacies (e.g., converse error and inverse error).

Course Outcome(s):

Apply logical analysis to quantiﬁed statements.

2 MATH-2010: Introduction to Discrete Mathematics

Objective(s):

1. Translate between English sentences and logical form for statements involving universal and existential quantiﬁers, including

statements with multiple quantiﬁers.

2. Determine if a quantiﬁed statement involving one or two quantiﬁers is true or false.

3. Determine the negation of a quantiﬁed statement involving one or two quantiﬁers.

4. Use diagrams to determine if an argument form with quantiﬁed statements is valid or invalid.

5. Recognize and apply rules of inference and fallacies for arguments with quantiﬁed statements.

Course Outcome(s):

Apply basic methods of proof to elementary number theory.

Essential Learning Outcome Mapping:

Critical/Creative Thinking: Analyze, evaluate, and synthesize information in order to consider problems/ideas and transform them in

innovative or imaginative ways.

Objective(s):

1. Determine if statements involving concepts from elementary number theory are true or false.

2. Prove or disprove existential and universal statements using constructive proof of existence, the method of exhaustion,

generalizing from the generic particular, and counterexample.

3. Identify logical errors in a proposed incorrect proof.

4. Prove theorems and statements using the methods of direct proof, division into cases, and proof by contradiction.

Course Outcome(s):

Apply fundamental principles of sequences and mathematical induction.

Essential Learning Outcome Mapping:

Critical/Creative Thinking: Analyze, evaluate, and synthesize information in order to consider problems/ideas and transform them in

innovative or imaginative ways.

Objective(s):

1. Deﬁne and apply the basic properties of sequences.

2. Compute and apply the properties of summations and products.

3. Prove conjectures by mathematical induction.

4. Deﬁne and apply recursively deﬁned sequences.

Course Outcome(s):

Apply fundamental principles of set theory and related methods of proof.

Essential Learning Outcome Mapping:

Critical/Creative Thinking: Analyze, evaluate, and synthesize information in order to consider problems/ideas and transform them in

innovative or imaginative ways.

Objective(s):

1. Deﬁne and apply the basic properties of and operations on sets, including empty set, set equality, subset, proper subset, union,

intersection, set difference, symmetric difference, complement, set partition, power set, and cross product.

2. Use Venn diagrams to solve problems, illustrate set identities, and apply the inclusion-exclusion principle.

3. Prove or disprove subset relations and set identities.

4. Prove a set is equal to the empty set by contradiction.

Course Outcome(s):

Apply fundamental principles of functions and related methods of proof.

MATH-2010: Introduction to Discrete Mathematics 3

Essential Learning Outcome Mapping:

Critical/Creative Thinking: Analyze, evaluate, and synthesize information in order to consider problems/ideas and transform them in

innovative or imaginative ways.

Objective(s):

1. Identify the domain, codomain, and range of discrete functions.

2. Deﬁne and identify functions that are one-to-one (injective), onto (surjective), and one-to-one correspondences (bijective).

3. Prove or disprove that a function is one-to-one, onto, or a one-to-one correspondence.

Course Outcome(s):

Apply fundamental principles of counting and probability.

Essential Learning Outcome Mapping:

Quantitative Reasoning: Analyze problems, including real-world scenarios, through the application of mathematical and numerical

concepts and skills, including the interpretation of data, tables, charts, or graphs.

Objective(s):

1. Deﬁne and apply the basic rules of probability.

2. Solve counting problems using the multiplication rule, permutations, distinguishable permutations, and combinations (with and

without repetition).

3. Apply the addition rule and the inclusion-exclusion rule.

4. Deﬁne and apply the pigeonhole principle.

Course Outcome(s):

Apply fundamental principles of graph theory.

Essential Learning Outcome Mapping:

Quantitative Reasoning: Analyze problems, including real-world scenarios, through the application of mathematical and numerical

concepts and skills, including the interpretation of data, tables, charts, or graphs.

Objective(s):

1. Deﬁne and apply basic features and properties of graphs, including edges, vertices, the degree of a vertex, paths, circuits, bridges,

subgraphs, and connected or disconnected graphs.

2. Determine if a graph has an Euler path, Euler circuit, Hamilton path, and/or Hamilton circuit, and identify them if so.

3. Deﬁne and apply basic properties of trees.

Course Outcome(s):

Apply methods and ideas learnedthroughout this course in different contexts.

Objective(s):

1. Investigate and solve applications related to computer science.

2. Solve other applications related to the topics learned throughout this course.

Methods of Evaluation:

1. A minimum of 3 periodic exams

2. Quizzes

3. Homework

4. In-class collaborative work

5. Computer application problems

6. Comprehensive ﬁnal exam

4 MATH-2010: Introduction to Discrete Mathematics

Course Content Outline:

1. Logic

a. Logical form

b. Truth tables

c. Compound statements

i. negation

ii. conjunction

iii. disjunction

d. DeMorgan's Laws

i. negation of an and statement

ii. negation of an or statement

e. Tautology and contradiction

f. Logical equivalence

g. Conditional statements

i. negation

ii. contrapositive

iii. converse

iv. inverse

v. biconditional statements

vi. necessary and sufﬁcient conditions

h. Validity of an argument

i. modus ponens

ii. modus tollens

iii. generalization

iv. specialization

v. conjunction

vi. elimination

vii. transitivity

viii. converse error

ix. inverse error

2. Quantiﬁed statements

a. Logical form

b. Universal statements

i. truth or falsity

ii. negation

c. Existential statements

i. truth or falsity

ii. negation

d. Statements with multiple quantiﬁers

i. truth or falsity

ii. negation

e. Arguments with quantiﬁed statements

3. Number theory and proofs

a. Number theory basic concepts

b. Methods of proof

i. constructive proof of existence

ii. method of exhaustion

iii. generalizing from the generic particular

iv. counterexample

v. direct proof

vi. proof by division into cases

vii. proof by contradiction

4. Sequences and proofs

a. Properties of sequences

b. Summations and products

c. Proof by mathematical induction

d. Recursively deﬁned sequences



5. Set theory andproofs

MATH-2010: Introduction to Discrete Mathematics 5

a. Properties of and operations on sets

i. empty set

ii. set equality

iii. subset

iv. proper subset

v. union

vi. intersection

vii. set difference

viii. symmetric difference

ix. complement

x. partition

xi. power set

xii. cross product

b. Venn diagrams

c. Proofs

i. subset relations

ii. set identities

iii. empty set

6. Functions and proofs

a. Discrete functions

i. domain

ii. codomain

iii. range

b. Properties of functions

i. one-to-one (injective)

ii. onto (surjective)

iii. one-to-one correspondence (bijective)

c. Proofs

i. one-to-one

ii. onto

iii. one-to-one correspondence

7. Counting and probability

a. Counting methods

i. multiplication rule

ii. permutation

iii. distinguishable permutation

iv. combination

v. combination with repetition

b. Addition rule

c. Inclusion-exclusion rule

d. Pigeonhole principle

8. Graph theory

a. Basic features and properties of graphs

i. edges

ii. vertices

iii. degree of a vertex

iv. paths

v. circuits

vi. bridges

vii. subgraphs

viii. connected or disconnected graphs

b. Special features of graphs

i. Euler paths

ii. Euler circuits

iii. Hamilton paths

iv. Hamilton circuits

c. Basic properties of trees

6 MATH-2010: Introduction to Discrete Mathematics

Resources

Epp, Susanna S.Discrete Mathematics with Applications.5th ed.Boston, MA: Cengage,2020.

Rosen, Kenneth H.Discrete Mathematics and Its Applications.8th ed.New York, NY: McGraw-Hill,2019.

Lipschutz, Seymour, and Marc Lars Lipson.Schaum's Outline of Discrete Mathematics.4th ed.New York, NY: McGraw-Hill,2022.

Lipschutz, Seymour, and Marc Lars Lipson.Schaum's 2000 Solved Problems in Discrete Mathematics.New York, NY: McGraw-Hill,1991.

Johnsonbaugh, Richard.Discrete Mathematics.8th ed.New York, NY: Pearson,2023.

Resources Other

Cengage WebAssign

Instructional Services

OAN Number:

Ohio Transfer 36 TMMSL

Top of page

Key: 2869