## MTH110 |
## Course Outline | |

The topics will not necessarily be covered in the exact order below.

Times given are rough guides only. Some topics will be covered as they come up in other sections.

Some topics will only be covered if time permits.

All Chapter references are from Discrete Mathematics by Epp.

## Weeks 1-4:

### The Logic of Compound Statements - Chapter 1 and Bitwise handout

- Statements and connectives.
- Relationship between english statements and statement forms.
- Truth tables, tautologies, contradictions, logically equivalent forms, De Morgan's laws.
- Logical implication, contrapositive, converse, inverse, if and only if.
- Arguments, valid conclusions.
- Digital Logic Circuits.
- Bitwise Arithmetic (Bitwise handout)

Section **Practice Exercises**1.1 3, 5, 6, 10ac, 11, 12, 16, 18, 19, 25, 27, 29, 31, 37, 39, 41, 42, 45, 47, 50. 1.2 1, 3, 5, 9, 12, 16, 19, 20df, 21a, 22df, 23df, 29, 32, 35, 40, 43, 45, 47, 49. 1.3 1, 3, 6, 8, 13a, 22, 24, 25, 26, 27, 36, 37, 38a, 39, 41, 43. 1.4 3, 7, 11, 18, 20, 22, 24, 28, 30. 1.5 1, 4, 7, 10, 27, 29, 38, 41, 44, 47a

## Week 4:

### Introduction to Set Theory - Chapter 5

- Naive set theory and Venn diagram
- Universe, null set, number sets
- Set inclusion, set operations
- Cartesian products, power sets
- Disjointedness and partitions
- Proving and Disproving set identities
- Boolean Algebras

We cover the following sections of Chapter 5 at this point:

5.1 All. 5.2 Statement of Theorems 5.2.1 & 5.2.2 only. (See below for more 5.2 material) 5.3 All. Section **Practice Exercises**5.1 1, 2, 4acd, 5, 7a, 8abfi, 9e, 10, 12, 18a, 19a, 20a, 21, 22ad, 23, 26, 27a, 28, 29a, 30. 5.2 1, 21. 5.3 1, 2, 3, 5, 6, 11, 13, 14, 15, 23, 24, 25, 26, 29, 32, 37ab, 39. 40, 44, 48, 51, 53.

## Weeks 5-7:

### The Logic of Quantified Statements - Chapter 2

- Quantifiers and manipulation of English statements and their equivalent symbolic form.
- Generalised De Morgan laws, multiple quantifiers.
- Counter-examples, necessary and sufficient conditions.
- Tilomino

Section **Practice Exercises**2.1 3, 4b, 5ac, 7ac, 9, 11, 13, 14, 16ace, 19, 26bd.2 2.2 1, 3, 11, 13, 20, 22, 27, 31, 33, 47. 2.3 2ab, 3ab, 11a, 12acd, 14, 15, 16, 19, 20a, 32, 33, 36, 38, 43a 2.4 1acd, 2, 3, 5, 7, 8, 9, 10, 16, 19ab, 21, 23, 25, 31, 33.

## Weeks 7-10:

### Proof Techniques - Chapter 3

- Axioms, theorems, lemmas and corollaries
- Proof structure
- Direct proofs: existential, by exhaustion, deduction, construction, counterexample
- Indirect proofs by contradiction, contraposition
- Common pitfalls and mistakes in proofs
- Algebraic axioms and divisibility in Z
- Prime and composite numbers
- Div, mod, quotient-remainder theorem
- Rational and irrational numbers
- Floor and Ceiling

Section **Practice Exercises**3.1 1, 2, 7, 9, 14, 17, 19, 22, 24, 25, 31, 34, 35, 36, 39, 40, 41, 43, 50. 3.2 4, 9, 12, 13, 14, 16, 18, 19, 20, 21, 31 3.3 1, 4, 6, 7, 8, 10, 12, 14, 15, 17, 19, 21, 22, 23, 24, 29, 33a 3.4 1, 3, 5, 20, 21, 23b, 24, 34, 35. 3.5 1, 3, 8, 12, 14, 17, 23, 26. 3.6 3, 5, 12, 16, 19, 23, 24, 25. 3.7 21.

## Weeks 10-12:

### Relations - Chapter 10

- Binary relations and directed graphs.
- Reflexivity, symmetry, transitivity, equivalence relations.
- Equivalence relations, equivalence classes, and partitions of a set.
- Antisymmetry, partial and total orders, Hasse diagrams.

Section **Practice Exercises**10.1 1, 5ab, 7a, 8, 12, 13, 19, 23, 25, 26, 28a, 29. 10.2 1, 3, 6, 9, 14, 15, 18, 21, 23, 26, 30, 31, 34, 43, 44, 45, 47, 50. 10.3 1, 2a, 3, 5, 7, 8, 10, 14a, 16a, 17a, 18, 23, 25, 27, 30, 31, 33, 36, 39ace, 40. 10.5 1ab, 2, 5, 8, 10, 11ab, 13, 15, 16a, 17a, 18, 21, 22, 24, 26, 31, 32, 33

## Weeks 12-13:

### Functions - Chapter 7

- Definitions and notation.
- One-to one and onto
- Inverse of a function
- Composition of functions
- Pigeonhole Principle
- Exponential and Logarithmic Functions

Section **Practice Exercises**7.1 1, 3ab, 6a, 7, 9, 13, 14, 23a, 27ac, 31. 7.2 1, 3, 5, 6, 7, 9, 12, 13, 14, 15, 16, 17, 21, 22, 24, 25, 26, 32, 36, 38, 39, 40. 7.3 1, 3, 5, 7, 9, 10, 12, 14, 17, 20, 22, 24, 25, 26, 29 7.4 1, 3, 7, 9, 13, 16, 18, 19, 21, 23, 26. 9.4 5, 9, 10, 13, 14, 15, 18, 20.

## If Time Permits

### Time did Permit!

### Set Theory - Chapter 5

- Set element methods, proving set identities

Section **Practice Exercises**5.2 2, 3, 6, 7, 8, 10, 11, 12, 15, 16, 18, 19, 22, 23, 27, 28, 32. ### Efficiency of Algorithms - Chapter 9

- Big O
- Comparing Efficiency of Algorithms

Section **Practice Exercises**9.2 11, 13, 14, 25, 35, 37, 39, 40, 43, 46, 49cde, 51, 52, 54, 55, 56, 59, 60

(In all questions use the limit definition from the Big O handout)9.3 1, 2, 3, 4, 5, 8, 9, 11, 17, 19

Maintained by Peter Danziger.

This page is best viewed with Mozilla Firefox.

Last modified
Monday, 30-Nov-2009 16:33:01 EST