Course Outline of Record

Item	Value
Curriculum Committee Approval Date	12/04/2024
Top Code	170100 - Mathematics, General
Units	5 Total Units
Hours	90 Total Hours (Lecture Hours 90)
Total Outside of Class Hours	0
Course Credit Status	Credit: Degree Applicable (D)
Material Fee	No
Basic Skills	Not Basic Skills (N)
Repeatable	No
Open Entry/Open Exit	No
Grading Policy	Standard Letter (S),  Pass/No Pass (B)
Associate Arts Local General Education (GE)	Area 1B Communication and Analytical Thinking (OA2)
Associate Science Local General Education (GE)	Area 1B Communication and Analytical Thinking (OAS2) Area 2 Mathematical Concepts and Quantitative Reasoning (OMTH)
California General Education Transfer Curriculum (Cal-GETC)	Cal-GETC 2A Math Concepts (2A)
Intersegmental General Education Transfer Curriculum (IGETC)	IGETC 2A Math Concepts (2A)
California State University General Education Breadth (CSU GE-Breadth)	CSU B4 Math/Quant.Reasoning (B4)

Course Description

Introduction to logic, sets, relations, algorithms, number theory, combinatorics, graphs, trees, and Boolean algebra. PREREQUISITE: MATH A185, MATH A185H or MATH A182H. Transfer Credit: CSU; UC.

Course Level Student Learning Outcome(s)

1. Recognize and use basic logic notation.
2. Find GCD's and LCM's.
3. Find the shortest path of a graph.
4. Prove logical equivalency of two propositions.
5. Identify Prime and Composite numbers.

Course Objectives

• 1. Use basic logic notation.
• 2. Prove that two propositions are logically equivalent.
• 3. Denote statements in basic set notation.
• 4. Identify functions and relations.
• 5. Use the concepts of injectivity, surjectivity and bijectivity.
• 6. Analyze equivalence relations (including congruence classes mod n).
• 7. Use the Euclidean algorithm to find GCDs and LCMs.
• 8. Use the Fundamental Theorem of Arithmetic.
• 9. Identify prime and composite numbers.
• 10. Create proofs using mathematical induction.
• 11. Use combinatorial counting techniques such as permutations, combinations, multinomial coefficients and the Pigeonhole Principle.
• 12. Solve advanced counting problems by constructing and solving recurrence relations.
• 13. Find Euler and Hamiltonian paths and circuits for graphs.
• 14. Find the shortest path of a graph.
• 15. Prove that two graphs are isomorphic.
• 16. Identify planar graphs.
• 17. Identify trees, spanning trees, minimal spanning trees and binary trees.
• 18. Prove that two trees are isomorphic.
• 19. Use Boolean algebra notation.
• 20. Create combinatorial circuits and their logic tables.
• 21. Minimize combinatorial circuits.

---

Lecture Content

It is understood that instructors will present some proofs of major laws, theorems and algorithms. The instructor will choose which proof to present and discuss. Recommended time for each topic is shown in the outline below, based on a 16 week format, and allowing 1.5 weeks for exams. Logic Notation Propositions (AND, OR, NOT, IF/THEN, DeMorgan s Laws, Biconditionals, Converse and Contrapositive) Logical Equivalence Quantifiers Analyze prepositional statements with logic tables Mathematical induction Sets Basic definitions and notation Laws of sets such as associative, identity, absorption and DeMorgan s Venn Diagrams Subsets Cartesian products Cardinality Partially ordered sets and lattices Relations Functions (domain and range) Relations Recurrence relations Digraphs Injectivity, surjectivity and bijectivity of functions Reflexivity, Symmetry and Transitivity Equivalence Relations including equivalence classes of a set and congruence classes mod n (proofs) Intro to Number Theory (The Euclidean Algorithm) Euclidean Algorithm GCD and LCM Prime and composite numbers Relatively prime Fundamental Theorem of Arithmetic Use of mathematical induction in proofs Combinatorics Product Rule Permutations Combinations Counting problems involving multinomial coefficients Advanced counting situations involving construction and solution of recurrence relations Pigeonhole Principle Applications of finite probabilities (lott ery, buckets of balls, etc.) Graphs Basic terminology, paths and circuits, subgraphs Euler paths and circuits (Fleury s Algorithm) Hamiltonian paths and circuits Shortest path (Dijkstra s Shortest Path Algorithm) Adjacency matrices Isomorphisms of graphs Planar graphs Trees Terminology and characterizations of trees Spanning trees and minimal spanning trees (Kruskal s Algorithm and Prim s Algorithm) Binary trees Isomorphisms of trees Boolean Algebra Combinatorial circuits (AND, OR, NOT, NOR and NAND gates) Logic tables for combinatorial circuits Boolean algebras Minimizing combinatorial circuits (including Karnaugh Maps)

Method(s) of Instruction

• Lecture (02)

Instructional Techniques

Lecture, written homework, discussion.

Reading Assignments

Students will spend approximately 1 hour per week reading from assigned text.

Writing Assignments

Students will spend approximately 1 hour per week on writing assignments.

Out-of-class Assignments

Students will spend approximately 8 hours per week on out-of-class assignments, including reading, writing, and assigned exercises for practice.

Demonstration of Critical Thinking

Several unit written exams and comprehensive final.

Required Writing, Problem Solving, Skills Demonstration

Several unit written exams and comprehensive final.

Eligible Disciplines

Mathematics: Master's degree in mathematics or applied mathematics OR bachelor's degree in either of the above AND master's degree in statistics, physics, or mathematics education OR the equivalent. Master's degree required.

Textbooks Resources

1. Required Rosen, Kenneth H. . Discrete Mathematics and its Applications , 7TH ed. New York: McGraw Hill, 2011 Rationale: -

Other Resources

1. Other appropriate textbook as chosen by faculty.