Course Outline of Record

Item	Value
Curriculum Committee Approval Date	12/02/2020
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
Grading Policy	Standard Letter (S),  Pass/No Pass (B)
Associate Arts Local General Education (GE)	OC Comm/Analytical Thinking - AA (OA2)
Associate Science Local General Education (GE)	OCC Comm/AnalyticalThinking-AS (OAS2) OCC Mathematics (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, DeMorgans 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 DeMorgans 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 (Fleurys Algorithm) Hamiltonian paths and circuits Shortest path (Dijkstras Shortest Path Algorithm) Adjacency matrices Isomorphisms of graphs Planar graphs Trees   Terminology and characterizations of trees Spanning trees and minimal spanning trees (Kruskals Algorithm and Prims 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: Masters degree in mathematics or applied mathematics OR bachelors degree in either of the above AND masters degree in statistics, physics, or mathematics education OR the equivalent. Masters 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.