Discrete Mathematics I
- Set Theory
- Algorithms, Integers and Matrices
- Mathematical Reasoning and Recursive Definitions
- Graphs and Trees
- Languages and Finite State Machines
Lectures, problem sessions, tutorial sessions and assignments
Evaluation will be carried out in accordance with Douglas College policy. The instructor will present a written course outline with specific evaluation criteria at the beginning of the semester. Evaluation will be based on some of the following:
At the end of the course, the successful student should be able to:
- write English statements in symbolic form using prepositional variables or functions, logical connectives and any necessary quantifiers;
- determine the truth value of a statement under an interpretation;
- determine the negation, converse, inverse, and contrapositive of a statement;
- verify logical equivalencies;
- demonstrate an understanding of tautologies, contradictions and duals;
- prove the properties of logic;
- determine the cardinality of sets, subsets, power sets and Cartesian products;
- combine sets using the set operators;
- prove set identities using a series of known set identities or by showing that each expression is a subset of the other;
- use membership tables or Venn diagrams to prove set identities;
- classify functions as injective, surjective or bijective;
- demonstrate an understanding of domains, codomains, ranges, mappings and images;
- create new functions by composition;
- find the inverse of an injective function;
- demonstrate an understanding of the floor and ceiling functions;
- compute finite sums;
- give a big-O estimate for a function;
- write a simple algorithm in pseudocode;
- determine the time complexity of simple algorithms;
- demonstrate an understanding of divisibility, the greatest common divisor and modular arithmetic;
- use the Euclidean algorithm to find the gcd of two numbers;
- convert between binary, octal and hexadecimal;
- demonstrate an understanding of the rules of inference;
- analyze an argument as to its validity using the concepts of mathematical logic;
- use a direct proof, indirect proof, or contradiction to prove a mathematical theorem;
- prove mathematical theorems using formal inductive techniques;
- give a recursive definition of a function or a set;
- use the sum and product rules and tree diagrams to solve basic counting problems;
- apply the inclusion-exclusion principle to solve counting problems for two tasks;
- solve counting problems using the Pigeon-Hole Principle;
- count unordered selections of distinct objects;
- count ordered arrangements of a set of disctinct objects;
- count ordered and unordered selections of r objects chosen with or without repetition from a set of n elements;
- count the number of arrangements of a set of objects some of which are indistinguishable;
- find the expansion of a binomial;
- determine the probability of a combination of events for an equi-probable sample space;
- determine whether or not a relation is reflexive, irreflexive, symmetric, antisymmetric and or transitive;
- represent a relation as a matrix and a digraph;
- determine whether a string belongs to the language generated by a given grammar;
- classify a grammar;
- find the language created by a grammar;
- draw the state diagram for a finite-state machine;
- construct a finite-state machine to perform a function;
- determine the output of a finite state machine;
- demonstrate an understanding of the vocabulary of graph theory;
- determine whether a graph is bi-partite or not;
- represent a graph as an adjacency matrix and an incidence matrix;
- determine whether a pair of graphs are isomorphic;
- find circuits and paths in a graph;
Consult the Douglas College Bookstore for the latest required textbooks and materials.
Example textbooks and materials may include:
Rosen, H.R., Discrete Mathematics and Its Applications, current edition, McGraw Hill.
Grimaldi, R.P, Discrete and Combinatorial Mathematics: An Applied Introduction, current edition, Pearson.
Precalculus 12 with a C or better; or Foundations of Math 12 with a C or better.
No corequisite courses.
No equivalent courses.
Course Guidelines for previous years are viewable by selecting the version desired. If you took this course and do not see a listing for the starting semester / year of the course, consider the previous version as the applicable version.
These are for current course guidelines only. For a full list of archived courses please see https://www.bctransferguide.ca
|Institution||Transfer Details for MATH 1130|
|Camosun College (CAMO)||CAMO MATH 126 (3)|
|Coquitlam College (COQU)||COQU MACM 101 (3)|
|Langara College (LANG)||LANG CPSC 1XXX (3)|
|Langara College (LANG)||DOUG MATH 1130 (3) & DOUG MATH 2230 (3) = LANG CPSC 1XXX (3) & LANG CPSC 2190 (3)|
|Simon Fraser University (SFU)||SFU MACM 101 (3)|
|Thompson Rivers University (TRU)||TRU MATH 2220 (3)|
|Trinity Western University (TWU)||TWU MATH 150 (3)|
|University of British Columbia - Okanagan (UBCO)||UBCO MATH 1st (3)|
|University of British Columbia - Vancouver (UBCV)||UBCV MATH 1st (3)|
|University of Northern BC (UNBC)||UNBC CPSC 141 (3)|
|University of the Fraser Valley (UFV)||UFV MATH 125 (4)|
|University of Victoria (UVIC)||UVIC MATH 122 (1.5)|
MATH 1130 001 - Students must ALSO register in one of MATH 1130 T01, T02 or T03.
MATH 1130 002 - Students must ALSO register in one of MATH 1130 T01, T02 or T03.
MATH 1130 T01 - Students must FIRST register in MATH 1130 001 or 002.
MATH 1130 T02 - Students must FIRST register in MATH 1130 001 or 002.
MATH 1130 T03 - Students must FIRST register in MATH 1130 001 or 002.