Comprehensive Discrete Mathematics Study Notes

Set Theory

• Definition of a Set: Sets are the fundamental discrete structures on which all others are built. Formally, a set is an unordered, well-defined collection of distinct objects, known as elements or members of the set, all of the same type. The "type" is defined by the person establishing the set.
  • Examples of Sets:
    • $A = \{0, 2, 4, 6, \dots\}$
    • $B = \{1, 3, 5, \dots\}$
    • $C = \{x \mid x \in \text{Natural number} \}$
• Notation and Membership:
  • Sets are generally denoted by capital letters ($A, B, C$).
  • Objects within a set are called elements or members.
  • Lower case letters ($x, y, z$) are used to denote elements.
  • $x \in A$ means that element $x$ is a member of set $A$.
  • $x \notin A$ means that element $x$ is not a member of set $A$.
• Cardinality of a Set: This refers to the number of elements present in a set, denoted as $|A|$. For example, if $A = \{0, 2, 4, 6\}$, then $|A| = 4$.
• Representation of Sets:
  • Tabular/Roster Form: The set is defined by actually listing all its members inside curly braces. Examples include $A = \{a, e, i, o, u\}$, $B = \{1, 2, 3, 4\}$, and $C = \{\dots, -4, -2, 0, 2, 4, \dots\}$.
  • Set Builder Form: The set is defined by specifying the property that all elements must satisfy. Examples include:
    • $A = \{x \mid x \text{ is an odd positive number less than } 10\}$
    • $B = \{x \mid x \in \text{English alphabet and } x \text{ is a vowel}\}$
    • $C = \{x \mid x \in Z \text{ and } x \pmod 2 = 0 \}$
• Types of Sets:
  • Finite Set: A set $S$ is finite if it contains exactly $n$ elements, where $n$ is a non-negative integer. Example: $A = \{1, 2, 3, 4\}$.
  • Infinite Set: A set is infinite if the count of its elements never comes to an end. Example: The set of all natural numbers.
  • Null / Empty Set: A unique set containing no elements, denoted by $\phi$ or $\emptyset$ or $\emptyset$, with a cardinality of zero ($|\phi| = 0$).
  • Singleton Set: A set containing exactly one element.
  • Universal Set: A fixed set containing all objects under investigation, of which all other sets are subsets. In Venn diagrams, it is represented by a rectangle and denoted by $U$.
• Subsets:
  • If every element of set $A$ is also an element of set $B$, then $A$ is a subset of $B$, written as $A \subseteq B$. Formally: $\forall x(x \in A \rightarrow x \in B)$.
  • If $A \subseteq B$, then $B$ is called the superset of $A$.
  • To show $A$ is not a subset of $B$, one must find at least one element $x \in A$ such that $x \notin B$.
  • Important Properties:
    • $\phi \subseteq A$: The empty set is a subset of every set.
    • $A \subseteq U$: Every set is a subset of the Universal set.
    • $A \subseteq A$: Every set is a subset of itself.
• Proper Subset: If $A \subseteq B$ and $A \neq B$, then $A$ is a proper subset of $B$, denoted as $A \subset B$. This implies there is at least one element in $B$ not present in $A$.
• Equality of Sets: Sets $A$ and $B$ are equal ($A = B$) if they contain exactly the same elements. This is true if $A \subseteq B$ and $B \subseteq A$, or $\forall x(x \in A \leftrightarrow x \in B)$.
• Power Set: The set of all subsets of a set $A$ is called the power set, denoted $P(A)$ or $2^A$. If $|A| = n$, then the cardinality of the power set is $|P(A)| = 2^n$. For example, if $A = \{1, 2, 3\}$, then $P(A) = \{\phi, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{2, 3\}, \{1, 3\}, \{1, 2, 3\}\}$.

Operations on Sets

• Complement of a Set: The set of all elements in the universal set $U$ that are not in set $A$, denoted $A^c$. Formally: $A^c = \{x \mid x \notin A \text{ and } x \in U\}$.
• Union of Sets: The set containing all elements that belong to either set $A$, set $B$, or both. Denoted $A \cup B = \{x \mid x \in A \text{ or } x \in B\}$.
• Intersection of Sets: The set containing all elements that belong to both set $A$ and set $B$. Denoted $A \cap B = \{x \mid x \in A \text{ and } x \in B\}$.
• Disjoint Sets: Two sets are disjoint if they have no common elements, meaning $A \cap B = \phi$.
• Set Difference: The set of all elements that belong to set $A$ but do not belong to set $B$. Denoted $A - B = \{x \mid x \in A \text{ and } x \notin B\}$.
• Symmetric Difference: The set of elements that are in $A$ or in $B$ but not in both. Denoted $A \oplus B$. Equivalents include:
  • $A \oplus B = (A \cup B) - (A \cap B)$
  • $A \oplus B = \{x \mid (x \in A \text{ and } x \notin B) \text{ or } (x \in B \text{ and } x \notin A)\}$
  • $A \oplus B = (A - B) \cup (B - A)$

Mathematical Laws of Sets

• Idempotent Laws:
  • $A \cup A = A$
  • $A \cap A = A$
• Associative Laws:
  • $(A \cup B) \cup C = A \cup (B \cup C)$
  • $(A \cap B) \cap C = A \cap (B \cap C)$
• Commutative Laws:
  • $A \cup B = B \cup A$
  • $A \cap B = B \cap A$
• Distributive Laws:
  • $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
  • $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
• De Morgan's Laws:
  • $(A \cup B)^c = A^c \cap B^c$
  • $(A \cap B)^c = A^c \cup B^c$
• Identity Laws:
  • $A \cup \phi = A$
  • $A \cap \phi = \phi$
  • $A \cup U = U$
  • $A \cap U = A$
• Complement Laws:
  • $A \cup A^c = U$
  • $A \cap A^c = \phi$
  • $U^c = \phi$
  • $\phi^c = U$
• Involution Law:
  • $(A^c)^c = A$

Relations

• Cartesian Product: The set of all ordered pairs $(a, b)$ where $a \in A$ and $b \in B$. Denoted $A \times B = \{(a, b) \mid a \in A \text{ and } b \in B\}$.
  • It is the maximum possible relation between two sets.
  • It is generally not commutative: $A \times B \neq B \times A$.
  • If $|A| = m$ and $|B| = n$, then $|A \times B| = m \times n$.
• Definition of a Relation: A relation from set $A$ to set $B$ is any subset of the Cartesian product $A \times B$.
  • Since a relation is a subset of $A \times B$, the total number of possible relations is $2^{m \times n}$.
• Representation: Relations can be represented using a matrix where rows correspond to elements of $A$ and columns to elements of $B$. A value of $1$ indicates a pair is in the relation, and $0$ indicates it is not.
• Complement of a Relation ($R'$): Let $R$ be a relation from $A$ to $B$. The complement consists of all pairs in $A \times B$ not present in $R$.
  • $R' = \{(a, b) \mid (a, b) \in A \times B, (a, b) \notin R\}$
  • $R \cup R' = A \times B$
  • $R \cap R' = \phi$
• Inverse of a Relation ($R^{-1}$): A relation from $B$ to $A$ formed by reversing the pairs in $R$.
  • $R^{-1} = \{(b, a) \mid (a, b) \in R \}$. The size remains the same: $|R| = |R^{-1}|$.
• Diagonal Relation ($\Delta_A$): A relation containing all pairs $(x, x)$ for every $x \in A$. Denoted $\Delta_A = \{(x, x) \mid \forall x \in A \}$.

Types of Relations on a Set

• Reflexive Relation: A relation $R$ on set $A$ is reflexive if $\forall x \in A, (x, x) \in R$.
• Irreflexive Relation: A relation $R$ on set $A$ is irreflexive if $\forall x \in A, (x, x) \notin R$.
• Symmetric Relation: If $\forall a, b \in A, (a, b) \in R \rightarrow (b, a) \in R$.
• Anti-Symmetric Relation: If $\forall a, b \in A, (a, b) \in R \text{ and } (b, a) \in R \rightarrow a = b$. Symmetry is not allowed except for diagonal pairs ($a=b$).
• Asymmetric Relation: If $\forall a, b \in A, (a, b) \in R \rightarrow (b, a) \notin R$. No symmetry is allowed, including diagonal pairs.
• Transitive Relation: If $\forall a, b, c \in A, (a, b) \in R \text{ and } (b, c) \in R \rightarrow (a, c) \in R$.
• Equivalence Relation: A relation that is simultaneously reflexive, symmetric, and transitive.
  • If $R_1$ and $R_2$ are equivalence relations, their intersection $R_1 \cap R_2$ is an equivalence relation, but their union $R_1 \cup R_2$ is not necessarily one.
• Partial Order Relation: A relation that is reflexive, anti-symmetric, and transitive.
• Poset (Partially Ordered Set): A set $A$ paired with a partial order relation $R$, denoted $[A, R]$. Examples include $[A, \text{divides}]$, $[A, \le]$, and $[P(S), \subseteq]$.

Hasse Diagrams and Lattices

• Hasse Diagram: A graphical representation of a partial order relation in its transitive reduction form.
  • Steps to create:
    1. Draw a vertex for each element.
    2. Draw an edge from $a$ to $b$ if $(a, b) \in R$.
    3. Remove all reflexive edges (loops) and transitive edges.
    4. Remove direction and arrange by increasing height.
• Lattice: A Poset or Hasse diagram where every pair of elements has a unique supremum (least upper bound or Join) and infimum (greatest lower bound or Meet).
  • A Lattice is both a Join Semi-Lattice and a Meet Semi-Lattice.
  • Lattice Laws: Idempotent, Associative, Commutative, Distributive, De Morgan's, Identity, Complement, and Involution laws all apply to lattice operations $\vee$ (Join) and $\wedge$ (Meet).
• Properties of Lattices:
  • Unbounded Lattice: Contains an infinite number of elements.
  • Bounded Lattice: Contains a finite number of elements, with a defined upper bound ($U$) and lower bound ($\phi$).
  • Complement of an Element: Element $a^c$ is a complement of $a$ if $a \vee a^c = \text{Upper bound}$ and $a \wedge a^c = \text{Lower bound}$.
  • Distributive Lattice: For every element, there exists at most one complement (zero or one).
  • Complemented Lattice: For every element, there exists at least one complement (one or more).
  • Boolean Algebra: A lattice that is both complemented and distributive, where every element has exactly one complement.

Functions

• Definition: A function is a relation between sets $A$ and $B$ that associates every element of set $A$ to exactly one element of set $B$. Written as $f: A \rightarrow B$.
• Range of a Function: The set of all images of elements of $A$, such that $\text{Range} = \{ y \mid y \in B \text{ and } (x, y) \in f \}$. Note that $\text{Range} \subseteq B$.
• Total Number of Functions: If $|A| = m$ and $|B| = n$, there are $n^m$ possible functions.
• Function Composition: Operation taking $f: X \rightarrow Y$ and $g: Y \rightarrow Z$ to produce $h(x) = g(f(x))$. Denoted $g \circ f$. Composition is associative: $f \circ (g \circ h) = (f \circ g) \circ h$.
• Types of Functions:
  • One-to-One (Injective): Function where distinct elements of the domain map to distinct elements of the codomain. Possible if $|A| \le |B|$. Number of injective functions is $P(n, m)$. If $|A| = |B| = n$, there are $n!$ functions.
  • Onto (Surjective): Function where every element in codomain $B$ is the image of at least one element in domain $A$ ($\text{Range} = B$). Possible if $|B| \le |A|$.
    • Formula for Number of Onto Functions: $n^m - \binom{n}{1}(n-1)^m + \binom{n}{2}(n-2)^m - \binom{n}{3}(n-3)^m + \dots + (-1)^{n-1}\binom{n}{n-1}1^m$
  • Bijective: A function that is both injective and surjective. Possible only if $|A| = |B| = n$. Total bijective functions: $n!$.
• Inverse of a Function ($f^{-1}$): A function that reverses the original mapping. If $f(x) = y$, then $f^{-1}(y) = x$. Only bijective functions have inverses.

Theory of Logics

• Proposition: A declarative sentence that is either true ($T$) or false ($F$), but not both.
  • Determining Propositions:
    • "Delhi is the capital of USA": Proposition ($F$).
    • "How are you doing?": Not a proposition.
    • $5 \le 11$: Proposition ($T$).
    • $X + y = z$: Not a proposition unless variables are defined.
• Arguments: A set of premises ($P_1, P_2, \dots, P_n$) yielding a conclusion ($Q$). An argument is valid if whenever all premises are true, the conclusion must be true.
• Logical Operators:
  • Negation ($\neg p$): "It is not the case that $p$". Inverts truth value.
  • Conjunction ($p \wedge q$): True only if both $p$ and $q$ are true.
  • Disjunction ($p \vee q$): False only if both $p$ and $q$ are false.
  • Implication ($p \rightarrow q$): True except when $p$ is true and $q$ is false. $p \rightarrow q \equiv \neg p \vee q$.
  • Biconditional ($p \leftrightarrow q$): True only if $p$ and $q$ have the same truth value. $p \leftrightarrow q \equiv (p \rightarrow q) \wedge (q \rightarrow p)$.
• Derived Conditional Statements:
  • Implication: $p \rightarrow q$
  • Converse: $q \rightarrow p$
  • Inverse: $\neg p \rightarrow \neg q$
  • Contrapositive: $\neg q \rightarrow \neg p$ (Logically equivalent to Implication).
• Logical States:
  • Tautology: Always true regardless of variable truth values.
  • Contradiction: Always false regardless of variable truth values.
  • Contingency: Neither a tautology nor a contradiction.
  • Satisfiable: Has at least one true value in its truth table.
• Functionally Complete Set: A set of connectives that can express any propositional function. Examples: $\{\wedge, \neg\}$ and $\{\vee, \neg\}$.
• Canonical Normal Forms:
  • Canonical SOP (PDNF): Sum of Product where each AND term contains all literals.
  • Canonical POS (PCNF): Product of Sum where each OR term contains all literals.

First Order Predicate Logic (FOPL)

• Subject and Predicate: Logic used to extract more information than propositional logic. In "$1$ is a natural number", "$1$" is the subject and "natural number" is the predicate ($NatNo(1)$).
• Quantifiers:
  • Universal ($\forall x P(x)$): Assert that $P(x)$ is true for all values of $x$ in the universe of discourse.
  • Existential ($\exists x P(x)$): Assert that $P(x)$ is true for at least one value of $x$ in the universe of discourse.
• Quantification Logic Examples:
  • "Every Indian likes cricket": $\forall x [\text{Indian}(x) \rightarrow \text{Cricket}(x)]$
  • "Some Indians like samosa": $\exists x [\text{Indian}(x) \wedge \text{Samosa}(x)]$
• Negation of Quantifiers:
  • $\neg [\forall x P(x)] \equiv \exists x [\neg P(x)]$
  • $\neg [\exists x P(x)] \equiv \forall x [\neg P(x)]$
• Rules of Inference:
  • Universal Specification: $\forall x P(x) \therefore P(c)$
  • Universal Generalization: $P(c) \text{ for all } c \therefore \forall x P(x)$
  • Existential Specification: $\exists x P(x) \therefore P(c)$
  • Existential Generalization: $P(c) \therefore \exists x P(x)$
  • Universal Modus Ponens: $\forall x (P(x) \rightarrow Q(x)), P(c) \therefore Q(c)$

Algebraic Structures

• Binary Operation Properties:
  • Closure: For set $A$ and operation $*$, $\forall a, b \in A, a*b \in A$.
  • Associativity: $\forall a, b, c \in A, (a*b)*c = a*(b*c)$.
  • Identity: There exists $e \in A$ such that $\forall a \in A, a*e = e*a = a$.
  • Inverse: For each $a \in A$, there exists $a^{-1} \in A$ such that $a*a^{-1} = a^{-1}*a = e$.
  • Commutativity: $\forall a, b \in A, a*b = b*a$.
• Hierarchical Structures:
  • Algebraic Structure: Satisfies Closure.
  • Semi-Group: Satisfies Closure and Associativity.
  • Monoid: Satisfies Closure, Associativity, and Identity.
  • Group: Satisfies Closure, Associativity, Identity, and Inverse.
  • Abelian Group: A Group that also satisfies Commutativity.
• Properties of Groups:
  • If the group order is even, there is at least one element that is its own inverse.
  • $(a*b)^{-1} = b^{-1} * a^{-1}$.
  • Cancellation law: $a*b = a*c \rightarrow b=c$.
• Finite Groups and Modulo Operators:
  • Addition Modulo ($+_m$): $a +_m b = (a+b) \pmod m$.
  • Multiplication Modulo ($*_m$): $a *_m b = (a \times b) \pmod m$.
  • Examples: $\langle \{0, 1, 2, \dots, p-1\}, +_p \rangle$ is always a group. $\langle \{1, 2, \dots, p-1\}, *_p \rangle$ is a group if $p$ is prime.
• Subgroup: A subset of a group that is itself a group under the same operation.
  • Lagrange's Theorem: The order of a subgroup must exactly divide the order of the group ($O(G) \pmod{O(H)} = 0$).
• Cyclic Group: A group containing at least one generator '$a$' such that every element can be expressed as an integral power of '$a$'.
  • Number of generators for a cyclic group of order $n$ is given by $\phi(n) = n \times \frac{(p_1-1)(p_2-1)\dots(p_k-1)}{p_1 p_2 \dots p_k}$, where $p_k$ are distinct prime factors of $n$.
• Cosets:
  • Left Coset: $aH = \{ah \mid h \in H\}$.
  • Right Coset: $Ha = \{ha \mid h \in H\}$.
• Advanced Structures:
  • Ring: An algebraic system $\langle R, +, \cdot \rangle$ where $\langle R, + \rangle$ is an abelian group, $\langle R, \cdot \rangle$ is a semigroup, and $\cdot$ distributes over $+$.
  • Integral Domain: A commutative ring with unity and no zero divisors ($a \cdot b = 0 \rightarrow a=0 \text{ or } b=0$).
  • Field: A commutative ring where every non-zero element has a multiplicative inverse ($\langle R \setminus \{0\}, \cdot \rangle$ is an abelian group).

Graph Theory

• Basic Definitions:
  • Graph G(V, E): Consists of vertices ($V$) and edges ($E$).
  • Self-Loop: Edge $(v_i, v_i)$ connecting a vertex to itself.
  • Parallel Edges: Multiple edges between the same two vertices.
  • Adjacent Vertices: Vertices connected by the same edge.
  • Complete Graph ($K_n$): A simple graph with an edge between every pair of vertices. Total edges: $\frac{n(n-1)}{2}$.
• Degree and Theorems:
  • Degree: Number of edges incident to a vertex.
  • Hand-shaking Theorem: $\sum \text{deg}(v_i) = 2|E|$.
  • The number of vertices with odd degree in a graph must be even.
• Memory Representations:
  • Adjacency Matrix: Symmetric $V \times V$ matrix for undirected graphs.
  • Incidence Matrix: $V \times E$ matrix where rows are vertices and columns are edges.
  • Adjacency List: An array of lists representing adjacent vertices for each node.
• Popular Graphs:
  • Bipartite Graph: Vertices can be partitioned into two disjoint sets $V_1, V_2$ such that all edges connect a vertex in $V_1$ to one in $V_2$.
  • Complete Bipartite Graph ($K_{m,n}$): Every vertex in $V_1$ is connected to every vertex in $V_2$.
  • Planar Graph: A graph that can be drawn on a plane without edges crossing.
    • Euler's Formula: $r = e - v + 2$ (for connected planar graphs, where $r$ is regions, $e$ edges, $v$ vertices).
    • Disconnected Euler Formula: $v - e + r - k = 1$ (where $k$ is number of components).
  • Kuratowski's Non-Planar Graphs: $K_5$ and $K_{3,3}$ are the simplest non-planar graphs.
• Graph Coloring: Vertex coloring assigns colors such that no adjacent vertices share a color. The minimum colors required is the Chromatic Number ($\chi(G)$).
• Traversals:
  • Path: Open walk with no repeated vertices.
  • Connectivity: Minimum edges required for connectivity is $n-1$. Guaranteed for all graphs if edges exceed $\frac{(n-1)(n-2)}{2}$.
  • Euler Graph: Connected graph with a closed walk containing all edges. Exists iff all vertices have even degree.
  • Hamiltonian Graph: Contains a circuit visiting every vertex exactly once.

Combinatorics

• Permutation ($P(n, r)$): Arrangement of items where order matters. $P(n, r) = \frac{n!}{(n-r)!}$.
• Combination ($C(n, r)$): Selection of items where order does not matter. $C(n, r) = \frac{n!}{r!(n-r)!}$.
• Pigeonhole Principle: If $n$ items are put into $m$ containers and $n > m$, then at least one container must contain more than one item ($\lceil \frac{n}{m} \rceil$ elements).
• Principle of Inclusion-Exclusion (PIE): Used to find the size of the union of sets.
  • $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |A \cap C| + |A \cap B \cap C|$

Questions & Discussion

• Proposition Validity Example:
  • "If the labor market is perfect then wages are equal. Wages are not equal. Therefore the labor market is not perfect." - This is a valid argument (Modus Tollens).
• Logic Problem:
  1. "If it does not rain or if it is not foggy, then the sailing race will be held."
  2. "If the sailing race is held, then the trophy will be awarded."
  3. "The trophy was not awarded."
  • Conclusion: It must have rained. (Reasoning via contrapositive through the chain).
• Pigeonhole Application: In a class of $30$ students, at least $\lceil 30/12 \rceil = 3$ students must share the same birthday month.
• PIE Problem: Finding integers between $1$ and $500$ divisible by $3$ or $5$ or $7$:
  • $|A| = \lfloor 500/3 \rfloor = 166$
  • $|B| = \lfloor 500/5 \rfloor = 100$
  • $|C| = \lfloor 500/7 \rfloor = 71$
  • $|A \cap B| = \lfloor 500/15 \rfloor = 33$
  • $|B \cap C| = \lfloor 500/35 \rfloor = 14$
  • $|A \cap C| = \lfloor 500/21 \rfloor = 23$
  • $|A \cap B \cap C| = \lfloor 500/105 \rfloor = 4$
  • Result: $166 + 100 + 71 - 33 - 14 - 23 + 4 = 271$.