Credit Points 10

Legacy Code 200025

Coordinator Charles Zworestine Opens in new window

Description Discrete Mathematics introduces set theory, symbolic logic, graph theory and some counting techniques. The subject develops mathematical thinking and builds problem solving skills. It provides a solid foundation for further study in mathematics or computing.

School Computer, Data & Math Sciences

Discipline Mathematical Sciences, Not Elsewhere Classified.

Student Contribution Band HECS Band 1 10cp

Check your fees via the Fees page.

Level Undergraduate Level 1 subject

Equivalent Subjects LGYB 0448 - Discrete Mathematics (UWSC)

Incompatible Subjects MATH 2004 - Discrete Structures and Complexity

Assumed Knowledge

HSC Mathematics or equivalent.

Learning Outcomes

On successful completion of this subject, students should be able to:

1. Decide the truth of logical statements involving connectives, and simplify logical expressions using the laws of logic and truth tables
2. Give simple proofs by induction and contradiction;
3. Define and recognise primes, factorise small integers, use the Euclidean algorithm, and do calculations with modular arithmetic;
4. Perform simple operations on sets, find Cartesian products of sets, and use Venn diagrams to illustrate relationships between sets;
5. Solve basic problems in counting and probability;
6. Recognize a function, decide whether a given function is one-to-one or onto, and perform elementary manipulations with functions;
7. Describe simple and directed graphs, use concepts such as "path", and find minimal spanning trees

Subject Content

1. Sets: definitions, subsets, equality, operations, properties, empty set.

2. Counting and probability: Introduction, permutations and combinations, counting rules.

3. Functions: one-to-one, onto, inverse functions, composition.

4. Logic: logical connectives, equivalence, conditional statements, contrapositive, converse, valid arguments, predicates, quantifiers.

5.  Number theory and mathematical proof: division, direct proof, counter-examples, division into cases, proof by contradiction and contraposition.

6.  Induction and recursion: examples, sequences, sigma and product notation.

7.  Graphs and trees: paths, circuits, isomorphisms of graphs, definitions, spanning trees, Kruskal's algorithm.