Discrete Mathematics: Set Theory

• Discrete mathematics is a field of mathematics that deals with discrete objects and structures, rather than continuous ones.

Set Theory

• A set is a well-defined collection of distinct objects, considered as an object in its own right.
• Sets are typically denoted by uppercase letters.
• Elements of a set are denoted by lowercase letters.
• If an element 'x' belongs to a set 'A', it is denoted as x ∈ A.
• If an element 'y' does not belong to a set 'A', it is denoted as y ∉ A.
• The empty set (or null set), denoted by ∅ or {}, is a set that contains no elements.
• A universal set, denoted by U, is a set that contains all possible elements relevant to a particular context.
• A subset: Set A is a subset of set B (denoted A ⊆ B) if every element of A is also an element of B.
• A proper subset: Set A is a proper subset of set B (denoted A ⊂ B) if A ⊆ B and A ≠ B.
• Set equality: Two sets A and B are equal (denoted A = B) if A ⊆ B and B ⊆ A.
• The power set of a set A, denoted P(A), is the set of all subsets of A, including the empty set and A itself.
• The cardinality of a set A, denoted |A|, is the number of elements in A.
• Union (A ∪ B): The set of all elements that are in A, or in B, or in both.
• Intersection (A ∩ B): The set of all elements that are in both A and B.
• Difference (A - B): The set of all elements that are in A but not in B.
• Complement (A'): The set of all elements in the universal set U that are not in A.
• Venn diagrams are used to visually represent sets and their relationships.
• Set identities include commutative laws, associative laws, distributive laws, identity laws, complement laws, and De Morgan's laws.
• De Morgan's Laws:
  • (A ∪ B)' = A' ∩ B'
  • (A ∩ B)' = A' ∪ B'

Graph Theory

• A graph is a mathematical structure used to model pairwise relations between objects.
• A graph consists of vertices (nodes) and edges that connect these vertices.
• Vertices are the fundamental units of which graphs are formed.
• Edges are connections between pairs of vertices.
• An edge can be directed (from one vertex to another) or undirected (no specific direction).
• In a simple graph, there's at most one edge between any two vertices, and no loops (edges from a vertex to itself).
• A multigraph allows multiple edges between the same pair of vertices.
• A pseudograph allows both multiple edges and loops.
• A directed graph (digraph) has directed edges.
• The degree of a vertex in an undirected graph is the number of edges incident to it, with loops counted twice.
• The in-degree of a vertex in a directed graph is the number of edges coming into it.
• The out-degree of a vertex in a directed graph is the number of edges going out of it.
• The Handshaking Theorem states that the sum of the degrees of all vertices in an undirected graph is twice the number of edges.
• A path is a sequence of vertices connected by edges.
• A cycle is a path that starts and ends at the same vertex.
• A graph is connected if there is a path between every pair of vertices.
• A connected component is a maximal connected subgraph of a graph.
• A complete graph (Kn) is a graph in which every pair of distinct vertices is connected by an edge.
• A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other set.
• Common graph representations include adjacency lists and adjacency matrices.
• Graph traversal algorithms include Breadth-First Search (BFS) and Depth-First Search (DFS).
• BFS explores the graph level by level.
• DFS explores as far as possible along each branch before backtracking.
• A tree is a connected graph with no cycles.
• A spanning tree of a connected graph is a subgraph that is a tree and connects all the vertices.

Logic and Proofs

• Logic is the study of reasoning.
• A proposition is a declarative statement that is either true or false, but not both.
• Propositional variables are used to represent propositions (e.g., p, q, r).
• Logical connectives are used to combine propositions.
• Common logical connectives include:
  • Negation (¬): "not"
  • Conjunction (∧): "and"
  • Disjunction (∨): "or"
  • Exclusive Or (⊕): "either... or..." but not both
  • Implication (→): "if... then..."
  • Biconditional (↔): "if and only if"
• A truth table shows the truth value of a compound proposition for all possible combinations of truth values of its constituent propositions.
• A tautology is a compound proposition that is always true.
• A contradiction is a compound proposition that is always false.
• A contingency is a compound proposition that is neither a tautology nor a contradiction.
• Logical equivalence: Two compound propositions are logically equivalent if they have the same truth table.
• Rules of inference are logical forms that are used to deduce conclusions from premises.
• Common rules of inference include Modus Ponens, Modus Tollens, Hypothetical Syllogism, and Disjunctive Syllogism.
• A proof is a sequence of statements that establishes the truth of a proposition.
• Common proof techniques include:
  • Direct proof: Start with the premises and use rules of inference to derive the conclusion.
  • Proof by contraposition: Prove the contrapositive of the statement.
  • Proof by contradiction: Assume the negation of the statement and derive a contradiction.
  • Proof by induction: Used to prove statements about natural numbers.
• A mathematical induction proof has two steps:
  • Base case: Show that the statement is true for the initial value (usually n=0 or n=1).
  • Inductive step: Assume that the statement is true for some arbitrary value k (the inductive hypothesis) and show that it is also true for k+1.

Number Theory

• Number theory is a branch of mathematics that studies the properties of integers.
• An integer is a whole number (not a fraction) that can be positive, negative, or zero.
• Divisibility: An integer 'a' divides an integer 'b' (denoted a|b) if there exists an integer 'k' such that b = ak.
• If a|b, then 'a' is a factor or divisor of 'b', and 'b' is a multiple of 'a'.
• Prime numbers are integers greater than 1 that have only two divisors: 1 and themselves.
• A composite number is an integer greater than 1 that is not prime (i.e., it has divisors other than 1 and itself).
• The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be uniquely expressed as a product of prime numbers (up to the order of the factors).
• The greatest common divisor (GCD) of two integers 'a' and 'b' is the largest integer that divides both 'a' and 'b'.
• The least common multiple (LCM) of two integers 'a' and 'b' is the smallest positive integer that is divisible by both 'a' and 'b'.
• The Euclidean Algorithm is an efficient method for computing the GCD of two integers.
• Modular arithmetic involves performing arithmetic operations on integers with a modulus.
• If a and b are integers and m is a positive integer, then a is congruent to b modulo m (denoted a ≡ b (mod m)) if m divides (a - b).
• Fermat's Little Theorem states that if 'p' is a prime number, then for any integer 'a' not divisible by 'p', a^(p-1) ≡ 1 (mod p).
• The Chinese Remainder Theorem provides a method for solving systems of congruences.

Combinatorics

• Combinatorics is a branch of mathematics that deals with counting, arrangement, and selection of objects.
• The multiplication principle states that if there are 'n1' ways to do one task and 'n2' ways to do another task, then there are 'n1 * n2' ways to do both tasks.
• The addition principle states that if there are 'n1' ways to do one task and 'n2' ways to do another task, and the tasks cannot be done at the same time, then there are 'n1 + n2' ways to do either task.
• A permutation is an arrangement of objects in a specific order.
• The number of permutations of 'n' distinct objects taken 'r' at a time is denoted by P(n, r) and is calculated as P(n, r) = n! / (n-r)!.
• A combination is a selection of objects without regard to order.
• The number of combinations of 'n' distinct objects taken 'r' at a time is denoted by C(n, r) or (n choose r) and is calculated as C(n, r) = n! / (r! * (n-r)!).
• The binomial theorem states that for any non-negative integer 'n', (x + y)^n = Σ(k=0 to n) (n choose k) * x^(n-k) * y^k.
• The principle of inclusion-exclusion (PIE) is a technique for counting the number of elements in the union of multiple sets.
• For two sets A and B, |A ∪ B| = |A| + |B| - |A ∩ B|.
• For three sets A, B, and C, |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|.
• Recurrence relations are equations that define a sequence recursively.
• A recurrence relation expresses the nth term of a sequence in terms of one or more of the previous terms.

Integration

• Integration is a fundamental concept of calculus that involves finding the area under a curve.
• It is the reverse operation of differentiation.
• The indefinite integral of a function f(x) is denoted as ∫f(x) dx, and it represents the family of functions whose derivative is f(x).
• The definite integral of a function f(x) from a to b is denoted as ∫[a to b] f(x) dx, and it represents the area under the curve of f(x) between the limits a and b.
• The Fundamental Theorem of Calculus relates differentiation and integration.
• Part 1 states that if F(x) = ∫[a to x] f(t) dt, then F'(x) = f(x).
• Part 2 states that ∫[a to b] f(x) dx = F(b) - F(a), where F(x) is an antiderivative of f(x).
• Basic integration rules include the power rule, constant multiple rule, sum/difference rule, and substitution rule.
• Integration techniques include u-substitution, integration by parts, trigonometric substitution, and partial fraction decomposition.
• U-substitution is used to simplify integrals by replacing a function and its derivative with a new variable.
• Integration by parts is used to integrate products of functions using the formula ∫u dv = uv - ∫v du.
• Trigonometric substitution is used to integrate functions involving square roots of quadratic expressions.
• Partial fraction decomposition is used to integrate rational functions by breaking them down into simpler fractions.
• Applications of integration include finding areas, volumes, arc lengths, and surface areas.

Differentiation

• Differentiation is a fundamental concept of calculus that involves finding the rate of change of a function.
• The derivative of a function f(x) is denoted as f'(x) or df/dx, and it represents the slope of the tangent line to the curve of f(x) at a given point.
• The derivative can be interpreted as the instantaneous rate of change of a function.
• Basic differentiation rules include the power rule, constant multiple rule, sum/difference rule, product rule, quotient rule, and chain rule.
• The power rule states that if f(x) = x^n, then f'(x) = nx^(n-1).
• The product rule states that if f(x) = u(x)v(x), then f'(x) = u'(x)v(x) + u(x)v'(x).
• The quotient rule states that if f(x) = u(x)/v(x), then f'(x) = (u'(x)v(x) - u(x)v'(x)) / (v(x))^2.
• The chain rule states that if f(x) = g(h(x)), then f'(x) = g'(h(x)) * h'(x).
• Implicit differentiation is used to find the derivative of a function that is not explicitly defined in terms of a single variable.
• Higher-order derivatives are derivatives of derivatives.
• The second derivative of a function f(x) is denoted as f''(x) or d^2f/dx^2.
• Applications of differentiation include finding critical points, local maxima and minima, inflection points, and optimization problems.
• Critical points are points where the derivative of a function is zero or undefined.
• Local maxima and minima are the highest and lowest points in a particular interval of a function.
• Inflection points are points where the concavity of a function changes.
• Optimization problems involve finding the maximum or minimum value of a function subject to certain constraints.