Introductory Discrete Mathematics for Computer Science

From Wikiversity

Contents 1 Introduction 2 Course Outline 2.1 Logic 2.2 Set Theory 2.3 Functions 2.4 Counting 2.5 Graphs 3 Problems and Exams 4 Textbook 5 Instructors 6 Related Websites

[edit] Introduction

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.

[edit] Course Outline

[edit] Logic

• 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

[edit] Set Theory

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

[edit] Functions

• Lesson 3.1: Introduction to functions

[edit] Counting

• Lesson 4.1: Introduction to counting

[edit] Graphs

• Lesson 5.1: Introduction to graphs

[edit] Problems and Exams

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

• Review of Lesson 1

[edit] Textbook

It is recommended that you buy a copy of the following text, which is also used in the Columbia University course: Discrete Mathematics and its Applications, 6th ed. by Kenneth Rosen.

[edit] Instructors

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

[edit] Related Websites

• 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