Maricopa Community Colleges  MAT243   19946-19965 
Official Course Description: MCCCD Approval: 03/22/94
MAT243 19946-19965 LEC 3 Credit(s) 3 Period(s)
Discrete Mathematical Structures
Introduction to lattices, graphs, Boolean algebras, and groups. Emphasis on topics relevant to computer science. Prerequisites: Grade of "C" or better in CSC100 and (MAT220, or MAT223, or equivalent) or permission of instructor.
Go to Competencies    Go to Outline
 
MCCCD Official Course Competencies:
 
MAT243   19946-19965 Discrete Mathematical Structures
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)
Go to Description    Go to top of Competencies
 
MCCCD Official Course Outline:
 
MAT243   19946-19965 Discrete Mathematical Structures
    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
        Go to Description    Go to top of Competencies    Go to top of Outline