powered by
Center for Curriculum and Transfer Articulation
Discrete Mathematical Structures
Course: MAT227

First Term: 2014 Summer
Lecture   3 Credit(s)   3 Period(s)   3 Load  
Subject Type: Academic
Load Formula: S - Standard Load

Description: Introduction to lattices, graphs, Boolean algebras, and groups. Emphasis on topics relevant to computer science.

MCCCD Official Course Competencies
1. Solve problems using sets, subsets, denumerable sets and find direct products of these sets. (I)
2. Determine paths, cycles, connectivity, and trees given a graph. (I)
3. Represent a graph with its incidence matrix. (I)
4. Create proofs using relations, order relations, and equivalence relations. (I)
5. Identify domain and range of a mapping and find its inverse. (I)
6. Calculate permutations and combinations of sets. (I)
7. Solve problems by using the definitions of groups, fields, lattices and transformations of these. (II)
8. Use the axioms of Boolean Algebra to evaluate propositional functions by assigning truth values and using truth tables. (III)
9. Analyze a switching circuit by denoting it using a Boolean function and simplifying that function into conjunctive and disjunctive normal forms. (III)
10. Apply Boolean Algebra to other computer science topics including decision tables, determination of minimal paths, and coding theory. (III)
MCCCD Official Course Outline
I. Foundations of Discrete Math
   A. Sets
      1. Direct Products
      2. Finite and Denumerable Sets
      3. Finite Sets and Their Subsets
   B. Graphs
      1. Paths
      2. Cycles
      3. Connectivity
      4. Trees
      5. Adjacency and the Incidence Matrix
   C. Relations
      1. Order Relations
      2. Equivalence Relations
         a. Equivalence Classes
         b. Partition of Sets
         c. Congruences
   D. Mappings
      1. Domains
      2. Ranges
      3. Inverse Mappings
      4. Preservation of Relations Under Mappings
   E. Combinatorial Concepts
      1. Permutations
      2. Combinations
II. Basic Algebraic Structures
   A. Algebraic Structures as Sets with Particular Functions and Relations Defined on Them
   B. Groups
      1. Subgroup
      2. Cyclic Groups
   C. The Concept of Hemomorphism and Isomorphism on a set with Operations
   D. Semigroups and Semigroups with Transformations
   E. Structures with Several Operations
      1. Fields
      2. Lattices
III. Boolean Algebra and Propositional Logic
   A. Theory: The Axioms of Set Algebra
      1. Axiomatic Definition of Boolean Algebras as Algebraic Structures with Two Operations
      2. Basic Facts About Boolean Functions
      3. Propositions and Propositional Functions
      4. Logical Connectives
      5. Truth Values and Truth Tables
      6. The Algebra of Propositional Functions
      7. The Boolean Algebra Truth Values
      8. Conjunctive and Disjunctive Normal Forms
   B. Applications: Boolean Algebra and Switching Circuits
      1. Basic Computer Components
      2. Decision Tables
      3. Graph Examples in Coding Theory
      4. Algorithms for Determined Cycles in Minimal Paths
      5. Basic Elements of List Structures
      6. Accessing Problems
      7. Graphs of a Game
      8. Matching Algorithms
MCCCD Governing Board Approval Date: March 25, 2014

All information published is subject to change without notice. Every effort has been made to ensure the accuracy of information presented, but based on the dynamic nature of the curricular process, course and program information is subject to change in order to reflect the most current information available.