Discrete Math & Logic Essentials

Cheatsheet Content

Mathematical Logic Propositional Logic Propositions: Statements that are true or false. Connectives: Negation: $\neg p$ (not $p$) Conjunction: $p \land q$ ($p$ and $q$) Disjunction: $p \lor q$ ($p$ or $q$) Implication: $p \to q$ (if $p$ then $q$) Biconditional: $p \leftrightarrow q$ ($p$ if and only if $q$) Truth Tables: Evaluate truth values of compound propositions. Tautology: Always true. Contradiction: Always false. Propositional Equivalences De Morgan's Laws: $\neg(p \land q) \equiv \neg p \lor \neg q$ $\neg(p \lor q) \equiv \neg p \land \neg q$ Distributive Laws: $p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$ $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$ Implication Equivalence: $p \to q \equiv \neg p \lor q$ Normal Forms Conjunctive Normal Form (CNF): Conjunction of disjunctions (clauses). Example: $(p \lor \neg q) \land (r \lor s)$ Disjunctive Normal Form (DNF): Disjunction of conjunctions (minterms). Example: $(p \land q) \lor (\neg r \land s)$ Predicates and Quantifiers Predicate: A property that the subject of the statement can have. $P(x)$ Universal Quantifier: $\forall x P(x)$ (for all $x$, $P(x)$ is true) Existential Quantifier: $\exists x P(x)$ (there exists an $x$ such that $P(x)$ is true) Negations of Quantifiers: $\neg \forall x P(x) \equiv \exists x \neg P(x)$ $\neg \exists x P(x) \equiv \forall x \neg P(x)$ Nested Quantifiers $\forall x \exists y P(x, y)$: For every $x$, there exists a $y$ such that $P(x, y)$. $\exists x \forall y P(x, y)$: There exists an $x$ such that for every $y$, $P(x, y)$. Rules of Inference Rule Premises Conclusion Modus Ponens $p \to q$, $p$ $q$ Modus Tollens $p \to q$, $\neg q$ $\neg p$ Hypothetical Syllogism $p \to q$, $q \to r$ $p \to r$ Disjunctive Syllogism $p \lor q$, $\neg p$ $q$ Conjunction $p$, $q$ $p \land q$ Simplification $p \land q$ $p$ Addition $p$ $p \lor q$ Resolution $p \lor q$, $\neg p \lor r$ $q \lor r$ Sets and Relations Set Operations Union: $A \cup B = \{x \mid x \in A \text{ or } x \in B\}$ Intersection: $A \cap B = \{x \mid x \in A \text{ and } x \in B\}$ Difference: $A - B = \{x \mid x \in A \text{ and } x \notin B\}$ Complement: $\bar{A} = U - A$ (where $U$ is the universal set) Cartesian Product: $A \times B = \{(a, b) \mid a \in A \text{ and } b \in B\}$ Power Set: $P(A)$ (set of all subsets of $A$) Representation and Properties of Relations Relation: A subset of $A \times B$. Properties of a relation $R$ on set $A$: Reflexive: $(a, a) \in R$ for all $a \in A$. Symmetric: If $(a, b) \in R$, then $(b, a) \in R$. Antisymmetric: If $(a, b) \in R$ and $(b, a) \in R$, then $a = b$. Transitive: If $(a, b) \in R$ and $(b, c) \in R$, then $(a, c) \in R$. Equivalence Relations A relation $R$ is an equivalence relation if it is reflexive, symmetric, and transitive. Equivalence Classes: For an equivalence relation $R$ on $A$, the equivalence class of $a \in A$ is $[a]_R = \{x \in A \mid (a, x) \in R\}$. Equivalence classes partition the set $A$. Partially Ordering (Posets) A relation $R$ is a partial order if it is reflexive, antisymmetric, and transitive. A set $A$ with a partial order $R$ is called a partially ordered set (poset) $(A, R)$. Hasse Diagram: A graphical representation of a finite poset. Counting, Mathematical Induction and Discrete Probability Basics of Counting Sum Rule: If tasks $T_1$ and $T_2$ can be done in $n_1$ and $n_2$ ways, and cannot be done simultaneously, then there are $n_1 + n_2$ ways to do one of them. Product Rule: If a procedure has $k$ steps, and step $i$ can be done in $n_i$ ways, then there are $n_1 n_2 \dots n_k$ ways to do the procedure. Pigeonhole Principle If $k+1$ or more items are placed into $k$ bins, then at least one bin contains two or more items. Generalized: If $N$ items are placed into $k$ bins, then at least one bin contains $\lceil N/k \rceil$ or more items. Permutations and Combinations Permutation: Order matters. $P(n, k) = \frac{n!}{(n-k)!}$ (number of ways to arrange $k$ distinct items from $n$) Permutations with repetition: $n^k$ Combination: Order does not matter. $C(n, k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}$ (number of ways to choose $k$ items from $n$) Combinations with repetition: $\binom{n+k-1}{k}$ Inclusion-Exclusion Principle $|A \cup B| = |A| + |B| - |A \cap B|$ $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$ Mathematical Induction Principle: To prove $P(n)$ for all integers $n \ge n_0$: Basis Step: Show $P(n_0)$ is true. Inductive Step: Assume $P(k)$ is true for an arbitrary integer $k \ge n_0$ (inductive hypothesis), and show $P(k+1)$ is true. Strong Induction: Inductive hypothesis assumes $P(j)$ is true for all $j$ with $n_0 \le j \le k$. Probability Sample Space ($S$): Set of all possible outcomes. Event ($E$): A subset of the sample space ($E \subseteq S$). Probability of an Event: $P(E) = \frac{|E|}{|S|}$ (for equally likely outcomes). Conditional Probability: $P(E|F) = \frac{P(E \cap F)}{P(F)}$ (probability of $E$ given $F$). Independence: Events $E$ and $F$ are independent if $P(E \cap F) = P(E)P(F)$, or $P(E|F) = P(E)$. Bayes' Theorem $P(H|E) = \frac{P(E|H)P(H)}{P(E)}$ $P(E) = P(E|H)P(H) + P(E|\neg H)P(\neg H)$ Group Theory Group $(G, \cdot)$: A set $G$ with a binary operation $\cdot$ satisfying: Closure: $a \cdot b \in G$ for all $a, b \in G$. Associativity: $(a \cdot b) \cdot c = a \cdot (b \cdot c)$. Identity Element: $\exists e \in G$ such that $a \cdot e = e \cdot a = a$. Inverse Element: For each $a \in G$, $\exists a^{-1} \in G$ such that $a \cdot a^{-1} = a^{-1} \cdot a = e$. Abelian Group: A group where the operation is commutative ($a \cdot b = b \cdot a$). Subgroup: A subset $H \subseteq G$ that is itself a group under the same operation. Semi-group: A set with an associative binary operation. Cosets: For a subgroup $H$ of $G$ and $g \in G$, the left coset is $gH = \{gh \mid h \in H\}$. Lagrange's Theorem: If $H$ is a subgroup of a finite group $G$, then $|H|$ divides $|G|$. Isomorphism: A bijective homomorphism $\phi: G \to G'$ such that $\phi(a \cdot b) = \phi(a) \cdot' \phi(b)$. Homomorphism: A map $\phi: G \to G'$ such that $\phi(a \cdot b) = \phi(a) \cdot' \phi(b)$. Automorphism: An isomorphism from a group to itself. Rings, Integral Domains, Fields Ring $(R, +, \cdot)$: A set $R$ with two binary operations (addition and multiplication) such that $(R, +)$ is an abelian group, $(R, \cdot)$ is a semi-group, and multiplication distributes over addition. Commutative Ring: A ring where multiplication is commutative. Ring with Unity: A ring that has a multiplicative identity element. Integral Domain: A commutative ring with unity and no zero divisors (if $ab=0$, then $a=0$ or $b=0$). Field: A commutative ring with unity where every non-zero element has a multiplicative inverse. Graph Theory Graph $G=(V, E)$: A set of vertices $V$ and a set of edges $E$. Simple Graph: No loops (edges from a vertex to itself) and no multiple edges between the same two vertices. Multigraph: Allows multiple edges between vertices. Weighted Graph: Edges have associated numerical values (weights). Degree of a Vertex: Number of edges incident to it. $\sum_{v \in V} \deg(v) = 2|E|$. Path: A sequence of distinct vertices where consecutive vertices are connected by an edge. Circuit (Cycle): A path that starts and ends at the same vertex. Connected Graph: There is a path between every pair of distinct vertices. Eulerian Path/Circuit: A path/circuit that traverses every edge exactly once. Eulerian Circuit exists if all vertices have even degree. Eulerian Path exists if exactly two vertices have odd degree. Hamiltonian Path/Circuit: A path/circuit that visits every vertex exactly once. (No simple necessary/sufficient conditions). Planar Graph: Can be drawn in a plane without any edges crossing. Euler's Formula: For a connected planar graph, $v - e + f = 2$. If $G$ is planar, then $e \le 3v - 6$ (for $v \ge 3$). Graph Coloring: Assigning colors to vertices such that no two adjacent vertices have the same color. Chromatic Number ($\chi(G)$): Minimum number of colors needed. Bipartite Graph: Vertices can be divided into two disjoint sets $U$ and $W$ such that every edge connects a vertex in $U$ to one in $W$. (Contains no odd-length cycles). Trees Tree: A connected undirected graph with no simple circuits. A tree with $n$ vertices has $n-1$ edges. Rooted Tree: A tree where one vertex is designated as the root. Parent, Child, Siblings, Ancestors, Descendants, Leaves, Internal Vertices. Binary Tree: A rooted tree where each internal vertex has at most two children. Prefix Codes: Variable-length codes where no codeword is a prefix of another (e.g., Huffman codes). Tree Traversals (for binary trees): Preorder: Root, Left, Right Inorder: Left, Root, Right Postorder: Left, Right, Root Spanning Tree: A subgraph of a connected graph $G$ that is a tree and includes all vertices of $G$. Minimum Spanning Tree (MST): A spanning tree with the smallest possible sum of edge weights (e.g., Kruskal's, Prim's algorithms). Cut-Set: A set of edges whose removal increases the number of connected components of a graph. Boolean Algebra Boolean Variables: Can take values 0 (false) or 1 (true). Boolean Operations: AND ($\cdot$): $x \cdot y$ or $xy$ OR ($+$): $x+y$ NOT (complement): $\bar{x}$ or $x'$ Boolean Functions: Map Boolean variables to Boolean values. Representation: Truth tables, Boolean expressions, logic gates. Simplification: Laws of Boolean Algebra: Commutative, Associative, Distributive, Identity, Complement, Idempotent, De Morgan's, Absorption. Karnaugh Maps (K-maps): Graphical method for simplifying Boolean expressions. Quine-McCluskey Algorithm: Tabular method for simplifying Boolean expressions, especially for more variables. Sum-of-Products (SOP): Disjunction of minterms (e.g., $(\bar{A}B\bar{C}) + (AB\bar{C})$). Product-of-Sums (POS): Conjunction of maxterms (e.g., $(A+B+C)(A+\bar{B}+\bar{C})$). Optimization Linear Programming (LP) Mathematical Model: Objective Function: Maximize or minimize $Z = c_1x_1 + c_2x_2 + \dots + c_nx_n$. Constraints: $a_{i1}x_1 + a_{i2}x_2 + \dots + a_{in}x_n \le b_i$ (or $\ge$ or $=$). Non-negativity: $x_j \ge 0$. Graphical Solution: For 2 variables, plot constraints, identify feasible region (polygon), evaluate objective function at corner points. Simplex Method: Algebraic iterative method to find optimal solution for problems with many variables. Converts inequalities to equalities using slack/surplus variables. Uses a tableau to move from one basic feasible solution to another, improving the objective function. Dual Simplex Method: Used when the primal problem is infeasible but the dual is feasible. Works with dual variables. Sensitivity Analysis: How changes in objective function coefficients or constraint values affect the optimal solution. Integer Programming (IP) Linear programming where some or all variables must be integers. Methods: Branch and Bound, Cutting Plane. Transportation and Assignment Models Transportation Problem: Minimize cost of shipping goods from sources to destinations. Methods: Northwest Corner, Least Cost, Vogel's Approximation, Stepping Stone, MODI. Assignment Problem: Assigning tasks to agents to minimize total cost/time. Special case of transportation problem. Methods: Hungarian Algorithm. PERT-CPM (Project Evaluation and Review Technique - Critical Path Method) Purpose: Project scheduling and management. Diagram Representation: Activity-on-Node (AON): Nodes are activities, arrows show precedence. Activity-on-Arrow (AOA): Arrows are activities, nodes are events. Critical Path Calculations: Earliest Start (ES): Earliest time an activity can begin. Earliest Finish (EF): ES + duration. Latest Start (LS): Latest time an activity can begin without delaying project. Latest Finish (LF): LS + duration. Slack/Float ($S = LS - ES = LF - EF$): Amount of time an activity can be delayed. Critical Path: The longest path through the network; activities on this path have zero slack. Resource Levelling: Adjusting activity start/finish times to smooth out resource demand, typically without delaying the project completion. Cost Consideration in Project Scheduling: Crashing: Shortening project duration by adding resources at an increased cost. Identifying the optimal trade-off between time and cost.