Discrete Math for Computer Science - Logic & Set Theory

Overview

This course introduces the foundational concepts of discrete mathematics that are essential for computer science, with a focus on logic, formal reasoning, and set theory. Discrete mathematics studies structures that are non-continuous and symbolic, making it the natural mathematical language of computation. You will begin by learning propositional and predicate logic, developing the ability to translate natural-language statements into precise formal expressions. The course covers logical operators, equivalence, quantifiers, and rules of inference, providing the tools needed to construct and evaluate rigorous arguments and proofs. The course then introduces set theory and functions, which form the backbone of data modeling and abstraction in computer science. Topics include set operations, relations, functions, and cardinality, along with their close connections to logical reasoning. Emphasizing understanding and problem-solving over memorization, this course builds the mathematical maturity required for algorithm design, program correctness, and advanced topics in the specialization.

Syllabus

Introduction to Discrete Mathematics

This module introduces the foundations of discrete math through logic and set theory. Students learn to reason rigorously with statements, solve classic puzzles like knights and knaves, and manipulate collections of objects using set operations and Venn diagrams. It builds essential reasoning skills for consistent rule design, data modeling, and correct algorithm foundations in computer science.

Propositional Logic

Propositional logic studies logical statements that are either true or false and how they can be combined using logical connectives. This topic introduces propositions, truth values, compound statements, truth tables, and logical equivalences, forming the basis for precise reasoning, digital circuits, and formal proofs.

Predicate Logic (First-order logic)

Predicate logic extends propositional logic by incorporating variables and quantifiers to express statements about collections of objects. It enables more expressive reasoning using predicates, universal and existential quantifiers, restricted domains, and nested quantifiers, allowing formal modeling of real-world and mathematical statements.

Inference

This topic focuses on formal reasoning through valid arguments and proofs. It introduces rules of inference for propositional and predicate logic and covers fundamental proof techniques such as direct proof, proof by contraposition, and proof by contradiction, which are essential for verifying mathematical and computational claims.

Sets-Functions

This topic introduces sets as collections of objects and functions as mappings between sets. It covers set notation, subsets, power sets, Cartesian products, cardinality, and basic properties of functions, providing essential tools for modeling data structures, relations, and mathematical abstractions in computer science.