MCCCD Program Description

Discrete Mathematical Structures

Course: MAT227

First Term: 2011 Fall

Lecture 3 Credit(s) 3 Period(s) 3 Load
Subject Type: Academic
Load Formula: S

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 Competencies must be coordinated with the content outline so that each major point in the outline serves one or more competencies. MCCCD faculty retains authority in determining the pedagogical approach, methodology, content sequencing, and assessment metrics for student work. Please see individual course syllabi for additional information, including specific course requirements.

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: 6/27/1995

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.