# Introductory Discrete Mathematics for Computer Science

Educational level: this is a tertiary (university) resource. |

Subject classification: this is an information technology resource. |

Subject classification: this is a mathematics resource. |

Completion status: this resource is ~25% complete. |

Resource type: this resource is a course. |

This is the first of two discrete math subjects for students of Computer Science at Wikiversity. The second course is called Discrete Mathematics for Computer Science. This page is tailored to provide you with introductory topics and problems in discrete mathematics. It is a prerequisite for Analysis of Algorithms, which is fundamental to any computing practices that require optimal performance in the face of limited resources.

Discrete mathematics is the part of mathematics devoted to the study of discrete (i.e. distinct) objects. In general, it is used whenever objects are counted, when relationships between finite (or countable) sets are studied, and when processes involving a finite number of steps are analyzed. It is important for computer science because in computing machines, information is stored and manipulated in a discrete fashion.

## Contents

## Course Outline[edit]

### Logic[edit]

- Video:
*Boolean Algebra and formal logic* - Video:
*More logic: quantifiers and predicates*

**Lesson 1.1:**Introduction to boolean logic**Lesson 1.2:**Using truth tables**Lesson 1.3:**Logical AND**Lesson 1.4:**Logical OR**Lesson 1.5:**Logical XOR**Lesson 1.6:**Conditional Operator**Lesson 1.7:**Biconditional Operator**Lesson 1.8:**Compound Propositions and Useful Rules

### Set Theory[edit]

**Lesson 2.1:**Introduction to set theory**Lesson 2.2:**Intersection**Lesson 2.3:**Union

### Functions and Relations[edit]

- Video:
*Equivalence Relations and Partial Orders* - Video:
*Equivalence Relations and Partial Orders*

**Lesson 3.1:**Introduction to functions

### Sums and Recurrence Relations[edit]

- Video:
*Basic arithmetic and geometric sums, closed forms* - Video:
*Solving recurrence equations* - Video:
*Solving recurrence equations (cont.)*

### Mathematical Reasoning[edit]

### Counting[edit]

- Video:
*Combinations and permutations* - Video:
*Counting problems 1* - Video:
*Counting problems 2* - Video:
*Counting problems using combinations, distributions* - Video:
*Counting problems using combinations, distributions* - Video:
*The pigeonhole principle and examples; inclusion/exclusion theorem and examples; a combinatorial card trick*

**Lesson 6.1:**Introduction to counting

### Graphs[edit]

**Lesson 7.1:**Introduction to graphs

### Number Theory[edit]

## Problems Sets[edit]

ADUni problem sets:

## Exams[edit]

ADUni exams:

Exam 1 |

Exam 2 |

Exam 3 |

Final Exam |

Exams are open notes, as they are in Columbia University's COMS 3203 course in Discrete Mathematics (as of Spring 2009).

## Textbooks[edit]

Free textbooks:

*A Short Course in Discrete Mathematics*, by Edward A. Bender and S. Gill Williamson

*Discrete Mathematics with Algorithms*, by M. O. Albertson and J. P. Hutchinson

You may also buy a copy of the following text, which is used in the Columbia University course: *Discrete Mathematics and its Applications*, 6th ed. by Kenneth Rosen (book homepage). *Schaum's Outline of Discrete Mathematics* by Lipschutz and Lipson is another possible resource.

## Instructors[edit]

- AFriedman 23:24, 11 January 2009 (UTC)

## Online Courses[edit]

Art of Problem Solving:

- Introduction to Counting and Probability
- Intermediate Counting and Probability
- Introduction to Number Theory
- Intermediate Number Theory

## Related Websites[edit]

- Extra lecture videos:
- Full set of lecture videos and notes from the University of Colorado
- MIT (ADUni) Discrete Mathematics course

- Art of Problem Solving:
- Columbia University's Spring 2009 course in discrete mathematics, offered by the Department of Computer Science
- Nic Ford's personal webpage, which contains a tutorial on logic, set theory and the foundations of mathematics
- A collection of logic resources intended for homeschoolers
- How to Write Proofs, from Professor Larry Cusick's page at California State University, Fresno
- Supplementary discrete mathematics Lecture notes by L. LovĂˇsz and K. Vesztergombi