Discrete Structures I

At the end of this course, students should be able to: 1. convert logical statements from informal language to propositional and predicate logic expressions; 2. describe the strengths and limitations of propositional and predicate logic; 3. outline the basic structure of each proof technique (direct proof, proof by contradiction, and induction) described in this unit; 4. apply each of the proof techniques (direct proof, proof by contradiction, and induction) correctly in the construction of a sound argument; 5. apply the pigeonhole principle in the context of a formal proof; 6. compute permutations and combinations of a set, and interpret the meaning in the context of the particular application; 7. map real-world applications to appropriate counting formalisms, such as determining the number of ways to arrange people around a table, subject to constraints on the seating arrangement, or the number of ways to determine certain hands in cards (e.g., a full house); and 8. solve a variety of basic recurrence relations.

Propositional Logic, Predicate Logic, Sets, Functions, Sequences and Summation, Proof Techniques, Mathematical induction, Inclusion-exclusion and Pigeonhole principles, Permutations and Combinations (with and without repetitions), The Binomial Theorem, Discrete Probability, Recurrence Relations. 300 Level