Unit 1: Discrete Mathematics

1. Propositional Logic and Formal Reasoning

1.1 Propositions, Connectives, and Truth Tables

A proposition is a declarative statement that is either strictly True ( $T$ or $1$ ) or strictly False ( $F$ or $0$ ), but never both simultaneously.

Atomic Propositions: Fundamental statements containing no logical connectives (e.g., $p$ : "17 is a prime integer").
Compound Propositions: Formed by combining atomic statements via truth-functional logical connectives:
1. Negation ( $eg p$ or $\sim p$ ): True if and only if $p$ is false.
2. Conjunction ( $p \wedge q$ ): True if and only if both $p$ and $q$ are true.
3. Disjunction ( $p ee q$ ): Inclusive OR; true if at least one of $p$ or $q$ is true.
4. Conditional / Implication ( $p o q$ ): False if and only if hypothesis $p$ is true and conclusion $q$ is false. Vacuously true whenever $p$ is false.

eg p ee q $5. **Biconditional ($p \leftrightarrow q$)**: True if and only if $p$ and $q$ share identical truth values.$ ext{Identity: } p \leftrightarrow q \equiv (p o q) \wedge (q o p)$$

1.2 Variants of the Conditional Statement

Given the conditional proposition $p o q$ :

Converse: $q o p$ (Not logically equivalent to $p o q$ ).
Inverse: $eg p o eg q$ (Logically equivalent to converse).
Contrapositive: $eg q o eg p$ (Logically equivalent to $p o q$ ).

eg q o
eg p$$

1.3 Classification of Boolean Formulas and Normal Forms

Tautology: A compound proposition that evaluates to True under every possible truth assignment (e.g., $p ee eg p$ ).
Contradiction: Evaluates to False under all truth assignments (e.g., $p \wedge eg p$ ).
Contingency: A formula that is neither a tautology nor a contradiction.
Disjunctive Normal Form (DNF): An OR of ANDs (sum of minterms), useful for identifying satisfying assignments.
Conjunctive Normal Form (CNF): An AND of ORs (product of maxterms), fundamental for SAT solvers and automated theorem proving.

2. First-Order Logic (Predicate Calculus)

2.1 Predicates, Variables, and Domains

A predicate $P(x)$ is a statement involving variables that becomes a proposition once variables are bound to specific values from a non-empty Domain of Discourse ( $U$ ).

2.2 Quantifiers and Duality Laws

Universal Quantifier ( $orall x P(x)$ ): "For all $x$ in domain $U$ , $P(x)$ is true." True if and only if $P(x)$ holds for every element in $U$ .
Existential Quantifier ( $\exists x P(x)$ ): "There exists at least one $x$ in domain $U$ such that $P(x)$ is true."
De Morgan's Laws for Quantifiers:

eg orall x P(x) \equiv \exists x
eg P(x)$$

eg \exists x P(x) \equiv orall x eg P(x)$$ ### 2.3 Nested Quantifiers and Commutativity - Commutativity holds between identical quantifiers: $ orall x orall y P(x, y) \equiv orall y orall x P(x, y)$ and $\exists x \exists y P(x, y) \equiv \exists y \exists x P(x, y)$. - Alternating quantifiers **do not commute**: $$\exists y orall x P(x, y) \implies orall x \exists y P(x, y) \quad ( ext{Reverse implication fails!})$$ *(Example: "There exists a key $y$ that opens every door $x$" is strictly stronger than "For every door $x$, there exists some key $y$ that opens it".)* --- ## 3. Set Theory and Counting Principles ### 3.1 Fundamental Set Operations and Cardinality A **set** is an unordered collection of distinct objects. - **Power Set ($\mathcal{P}(A)$)**: The set of all subsets of $A$. If $|A| = n$, then $|\mathcal{P}(A)| = 2^n$. - **Cartesian Product ($A imes B$)**: The set of all ordered pairs $(a, b)$ with $a \in A, b \in B$. Cardinality: $|A imes B| = |A| \cdot |B|$. - **Symmetric Difference ($A \oplus B$)**: Elements belonging to $A$ or $B$, but not both: $$A \oplus B = (A \setminus B) \cup (B \setminus A) = (A \cup B) \setminus (A \cap B)$$ ### 3.2 The Inclusion-Exclusion Principle For finite sets $A_1, A_2, \dots, A_n$: $$|A_1 \cup A_2 \cup \dots \cup A_n| = \sum_{i=1}^n |A_i| - \sum_{1 \le i < j \le n} |A_i \cap A_j| + \sum_{1 \le i < j < k \le n} |A_i \cap A_j \cap A_k| - \dots + (-1)^{n-1} |A_1 \cap \dots \cap A_n|$$ ### 3.3 The Pigeonhole Principle (PHP) - **Basic Form**: If $k + 1$ or more pigeons are placed into $k$ pigeonholes, then at least one pigeonhole contains two or more pigeons. - **Generalized Form**: If $N$ objects are placed into $k$ boxes, then at least one box contains at least: $$\left\lceil rac{N}{k} ight ceil ext{ objects}$$ --- ## 4. Relations and Equivalence Structures ### 4.1 Binary Relations and Matrix Representation A binary relation $R$ from set $A$ to set $B$ is a subset of the Cartesian product: $R \subseteq A imes B$. If $A = B$, $R$ is a relation on $A$. - **Relation Matrix ($M_R$)**: For finite set $A = \{a_1, \dots, a_n\}$, $M_R[i][j] = 1$ if $(a_i, a_j) \in R$, and $0$ otherwise. ### 4.2 Properties of Binary Relations on a Set $A$ 1. **Reflexive**: $ orall x \in A, (x, x) \in R$ (All diagonal elements in $M_R$ are 1). Total reflexive relations on set of size $n$: $2^{n(n-1)}$. 2. **Irreflexive**: $ orall x \in A, (x, x) otin R$ (All diagonal elements in $M_R$ are 0). 3. **Symmetric**: $ orall x, y \in A, (x, y) \in R \implies (y, x) \in R$ ($M_R = M_R^T$). Total symmetric relations: $2^{n(n+1)/2}$. 4. **Antisymmetric**: $ orall x, y \in A, ((x, y) \in R \wedge (y, x) \in R) \implies x = y$. 5. **Transitive**: $ orall x, y, z \in A, ((x, y) \in R \wedge (y, z) \in R) \implies (x, z) \in R$ (Satisfied if $M_R^2 \le M_R$ under Boolean matrix product). ### 4.3 Equivalence Relations and Partitions A relation $R$ on set $A$ is an **Equivalence Relation** if and only if it is simultaneously: $$ ext{Reflexive} \wedge ext{Symmetric} \wedge ext{Transitive}$$ - **Equivalence Class ($[a]$)**: The set of all elements related to $a$: $[a] = \{x \in A \mid (a, x) \in R\}$. - **Fundamental Theorem of Equivalence Relations**: The distinct equivalence classes of an equivalence relation on $A$ form a **partition** of $A$ (mutually disjoint, non-empty, and their union equals $A$). - **Bell Numbers ($B_n$)**: The number of distinct equivalence relations on an $n$-element set equals the number of partitions of the set, given by the $n$-th Bell number. --- ## 5. Functions and Mappings ### 5.1 Injective, Surjective, and Bijective Functions Let $f: A o B$ be a function mapping domain $A$ to codomain $B$: - **Injective (One-to-One)**: $f(x) = f(y) \implies x = y$. Requires $|A| \le |B|$. Total injections: $P(|B|, |A|) = rac{|B|!}{(|B| - |A|)!}$. - **Surjective (Onto)**: $ orall b \in B, \exists a \in A ext{ s.t. } f(a) = b$ (Range equals Codomain). Requires $|A| \ge |B|$. $$ ext{Total surjections from } m ext{ to } n: n! \cdot S(m, n) = \sum_{k=0}^n (-1)^{n-k} inom{n}{k} k^m$$ *(where $S(m, n)$ is the Stirling number of the second kind).* - **Bijective (One-to-One Correspondence)**: Both injective and surjective. Requires $|A| = |B|$. A function is invertible if and only if it is a bijection. Total bijections: $n!$. --- ## 6. Partially Ordered Sets (Posets) and Lattices ### 6.1 Posets and Hasse Diagrams A relation $R$ on set $A$ is a **Partial Order** if it is: $$ ext{Reflexive} \wedge ext{Antisymmetric} \wedge ext{Transitive}$$ The pair $(A, \le)$ is called a **Partially Ordered Set (Poset)**. - **Hasse Diagram**: A simplified directed graph representation of a finite poset: - Transitive edges are omitted. - Reflexive self-loops are omitted. - If $a < b$, $b$ is placed vertically higher than $a$, eliminating directed arrows. - **Special Elements**: - **Maximal element**: An element $m$ such that no $x$ satisfies $m < x$. - **Minimal element**: An element $m$ such that no $x$ satisfies $x < m$. - **Greatest element (Maximum / Top $ op$)**: An element $g$ such that $ orall x, x \le g$ (unique if it exists). - **Least element (Minimum / Bottom $ot$)**: An element $l$ such that $ orall x, l \le x$ (unique if it exists). ### 6.2 Lattices and Boolean Algebras A poset $(L, \le)$ is a **Lattice** if every pair of elements $\{a, b\} \subseteq L$ has: - A unique **Least Upper Bound (LUB / Supremum / Join)**: $a ee b$. - A unique **Greatest Lower Bound (GLB / Infimum / Meet)**: $a \wedge b$. #### Key Lattice Varieties: 1. **Distributive Lattice**: Meet and join distribute over each other: $$a \wedge (b ee c) = (a \wedge b) ee (a \wedge c) \quad ext{and} \quad a ee (b \wedge c) = (a ee b) \wedge (a ee c)$$ 2. **Bounded Lattice**: Possesses a global least element $ot$ (0) and greatest element $ op$ (1). 3. **Complemented Lattice**: In a bounded lattice, every element $a$ has a complement $a'$ such that $a ee a' = op$ and $a \wedge a' = ot$. 4. **Boolean Algebra**: A lattice that is simultaneously **Distributive** and **Complemented**. - Every finite Boolean algebra is isomorphic to $(\mathcal{P}(S), \subseteq)$ for some finite set $S$, and therefore its cardinality must be a power of two: $|B| = 2^k$. --- ## 7. Abstract Algebraic Structures ### 7.1 Hierarchy of Algebraic Systems An algebraic system is a set $S$ equipped with one or more binary operations $*: S imes S o S$: | Structure | Closure | Associativity | Identity Element | Inverses | Commutativity | | :--- | :---: | :---: | :---: | :---: | :---: | | **Groupoid** | Yes | No | No | No | No | | **Semigroup** | Yes | Yes | No | No | No | | **Monoid** | Yes | Yes | Yes | No | No | | **Group** | Yes | Yes | Yes | Yes | No | | **Abelian Group** | Yes | Yes | Yes | Yes | Yes | ### 7.2 Group Theory and Subgroups A **Group** $(G, *)$ satisfies four fundamental axioms: 1. **Closure**: $ orall a, b \in G, a * b \in G$. 2. **Associativity**: $ orall a, b, c \in G, (a * b) * c = a * (b * c)$. 3. **Identity**: $\exists e \in G ext{ s.t. } orall a \in G, a * e = e * a = a$ (unique). 4. **Inverse**: $ orall a \in G, \exists a^{-1} \in G ext{ s.t. } a * a^{-1} = a^{-1} * a = e$ (unique). ### 7.3 Cyclic Groups and Lagrange's Theorem - **Cyclic Group**: A group $G$ generated by a single element $g \in G$, such that $G = \langle g angle = \{g^k \mid k \in \mathbb{Z}\}$. Every cyclic group is Abelian. - In a finite cyclic group $\mathbb{Z}_n$, the number of generators equals Euler's totient function $\phi(n)$. - **Lagrange's Theorem**: > *If $G$ is a finite group and $H$ is a subgroup of $G$, then the order of $H$ divides the order of $G$:* $$|G| = [G : H] \cdot |H|$$ *(where $[G : H]$ is the index of $H$ in $G$, representing the number of distinct cosets).* - **Corollary**: The order of any element $a \in G$ (i.e., smallest $k > 0$ with $a^k = e$) divides the order of the group $|G|$. Hence, for any $a \in G$, $a^{|G|} = e$.

Combinatorial Studies-I