COMP 1002: Introduction to Logic for Computer Scientists

This course is an introduction to discrete structures for all computer science majors.

It is required for entry into the  MAJ   CS Major and the  MIN   CS Minor.

Lab In addition to classes, this course has one structured laboratory session per week.

Prerequisites: None

Availability: This course is usually offered in Fall, Winter and Spring semesters.

Course Objectives

This course introduces the mathematical foundations of computer science, with a focus on proof techniques and their application to computational problems.

Students will learn propositional and predicate logic for formal reasoning, and develop skills in constructing proofs through induction, structural induction, and natural deduction. With this, students will study discrete structures such as sets, functions and relations, and directed graphs.

The pigeonhole principle, inclusion-exclusion, combinatorics, modular arithmetic, and number theory are introduced with their applications in computer science.

Throughout the course, students will practice proving properties of novel definitions and build up to proving the correctness of algorithms.

Representative Workload
  • Assignments 10%
  • Labs 30%
  • Midterm(s) 30%
  • Final Exam 30%
Representative Course Outline
  • Propositional and predicate logic (9 hours)
  • Proof techniques including natural deduction, induction, structural induction (10 hours)
  • Summation, product notations, sequences, and recurrences (2 hours)
  • Set theory, functions, relations including properties of binary relations, and directed graphs (4 hours)
  • Permutations, combinations, inclusion-exclusion principle, pigeonhole principle, modular arithmetic (5 hours)
Notes
  • Credit cannot be obtained for both Computer Science 1002 and either of Computer Science 2742 or Engineering 4424.
  • Students cannot received credit for Computer Science 1002, if completed with, or subsequent to, Mathematics 2320.
  • See the FAQ for why we require Computer Science 1002 for entry into the CS Major, and not Mathematics 2320.
  • COMP 1002 can be taken before or at the same time as COMP 1003, but COMP 1003 cannot be taken before COMP 1002.