Basic Information

Syllabus

Describing Sets : Logic & Proofs - 18L + 4T Introduction to Logic. Propositional Logic, Truth tables, Deduction, Resolution, Predicates and Quantifiers, Mathematical Proofs. Infinite sets, well-ordering. Cardinality of finite sets, Cartesian Product, countable and Uncountable sets, Cantor's diagonalization. Mathematical Induction - weak and strong induction.

Sizes of Sets : Counting & Combinatorics - 12L + 3T Counting, Sum and product rule, Principle of Inclusion Exclusion. Pigeon Hole Principle, Counting by Bijections. Double Counting. Linear Recurrence relations - methods of solutions. Generating Functions. Permutations and counting.

Structured Sets : Algebraic & Relational Structures - 6L + 2T Relations, Equivalence Relations. Functions, Bijections. Binary relations and Graphs. Trees (Basics). Posets and Lattices, Hasse Diagrams. Boolean Algebra. Structured sets with respect to binary operations.

Learning Outcomes

After completing the course, the student will be able to:

• Use logic to define and obtain mathematical formalization of statements related to computational problems and programs.
• Obtain mathematical proofs of statements regarding data types (Sets etc).
• Comprehend and Evaluate rigor in the definitions and conclusions about mathematical models and identify fallacious reasoning and statements.
• Identify and Apply properties of combinatorial structures and properties - know the basic techniques in combinatorics and counting.
• Analyze sets with operations, and identify their structure. Reason and Conclude properties about the structure based on the observations.
• Gain the conceptual background needed to be able to identify structures of algebraic nature, and discover, prove and use properties about them.