Discrete math covers various topics, including logic, combinatorics, graph theory, and algorithms.
Traditionally, there were debates on whether a separate course in discrete math was necessary.
Eventually, it was agreed that all these topics are interconnected and crucial for computer science.
Key Themes in Discrete Math
The common theme among topics is counting.
Counting can be easy (e.g., counting class members) or complex (e.g., combinations and arrangements).
Important techniques in counting:
Recognizing when two things are the same.
Developing tools for counting complex situations.
Example Problem: Choosing Pairs
Example: How many ways to choose 2 people from a group of 36?
This is a combinatorial counting problem that will be explored further in the course.
Understanding Binary Trees
Binary trees serve as another counting example:
With 3 nodes, there are 5 unique binary trees.
The number of binary trees grows rapidly with more nodes, which relates to algorithms in computer science.
Matrix Multiplication Example
Example: Counting ways to multiply matrices.
The number of ways to multiply matrices corresponds to binary tree structures, illustrating connections between different areas of math.
Introduction to Proofs
Proofs are essential in discrete math; they convince others of a statement's truth.
Types of proofs include direct proofs and proofs by contradiction.
Proof by Contradiction Example: Square Root of 2
A classic proof that the square root of 2 is irrational.
Assumes it can be expressed as a fraction and leads to the conclusion that both numerator and denominator must be even, contradicting the assumption of being in lowest terms.
Number Theory
Number theory is elegant and abstract, but it has practical applications, especially in cryptography (public key encryption).
Infinite Primes Theorem (Euclid's Proof)
Euclid's proof that there are infinitely many prime numbers using contradiction:
If you assume a finite list of primes, constructing a new number (product of primes + 1) reveals a contradiction.
Counting Problem Example: Pancake Cuts
A puzzle where cuts through a pancake yield different pieces based on rules.
Explored by mathematical induction to prove the relationship between cuts and resulting pieces.
Logic Basics
Introduction to logical statements and their representations in Boolean algebra.
Variables can be true or false (1 or 0).
Logical connectives:
AND (x ∧ y)
OR (x ∨ y)
NOT (¬x)
IMPLICATION (x → y)
Truth Tables
Used to evaluate logical expressions:
Construct truth tables for implications and other logical operations.
Boolean Algebra
Boolean algebra allows for manipulating logical expressions algebraically.
Key rules include:
De Morgan's laws (¬(A ∧ B) ≡ ¬A ∨ ¬B and ¬(A ∨ B) ≡ ¬A ∧ ¬B)