Introduction to Discrete Structure &Linear Algebra (AL-401) - Unit 5 Short Notes

Unit 5: Comprehensive Topics from Exams

I. Set Theory

Core Concepts:

• Set: A well-defined collection of distinct objects.

• Operations:

  • Union: $$\displaystyle A \cup B = \{x \mid x \in A \text{ or } x \in B\} $$

  • Intersection: $$\displaystyle A \cap B = \{x \mid x \in A \text{ and } x \in B\} $$

  • Difference: $$\displaystyle A - B = \{x \mid x \in A \text{ and } x \notin B\} $$

  • Complement (w.r.t. universal set $U$): $$\displaystyle A' = U - A $$

  • Cartesian Product: $$\displaystyle A \times B = \{(a,b) \mid a \in A, b \in B\} $$

De Morgan's Laws (Proof via Venn Diagrams):

1. $$\displaystyle (A \cup B)' = A' \cap B' $$

2. $$\displaystyle (A \cap B)' = A' \cup B' $$

[!TIP] Exam Focus: You may be asked to prove De Morgan's laws using Venn diagrams. Draw two overlapping circles for $A$ and $B$, shade the left side, then show the right side yields the same shaded region.

II. Relations

Properties of a Relation $R$ on set $A$:

Equivalence Relation: A relation that is reflexive, symmetric, and transitive. Partitions the set into equivalence classes.

Transitive Closure $$\displaystyle R^+ $$: The smallest transitive relation containing $R$. For common relations on $\mathbb{Z}$:

• $$\displaystyle a+1=b $$ → Transitive closure is $a \le b$ (or $a \le b$ on integers).

• $$\displaystyle a-b=2 $$ → Transitive closure is $a-b$ is even (i.e., $a \equiv b \pmod{2}$).

• $$\displaystyle a^2 - b^2 $$ divisible by 4 → Transitive closure is $a \equiv b \pmod{2}$ (both even or both odd).

• $|a-b| \le 1$ → Transitive closure is $$\displaystyle a=b $$ (since $|a-b|\le1$ and $|b-c|\le1$ does NOT imply $|a-c|\le1$ generally; closure forces equality).

Relation Matrix & Digraph:

• Matrix $$\displaystyle M_R $$: $$\displaystyle [m_{ij}] $$ where $$\displaystyle m_{ij}=1 $$ if $$\displaystyle (a_i, b_j) \in R $$, else 0.

• Digraph: Directed graph with vertices as set elements, edge $a \to b$ iff $(a,b) \in R$.

Domain & Range:

• Domain: $\{a \mid \exists b, (a,b) \in R\}$

• Range: $\{b \mid \exists a, (a,b) \in R\}$

[!TIP] Common Pitfall: For $aRb$ defined by $a$ is multiple of $b$ on $$\displaystyle A=\{1,2,3,4,5,6\} $$, note $a$ is multiple of $b$ means $$\displaystyle a = kb $$. So $(4,2) \in R$ but $(2,4) \notin R$. Domain is all $a$ that are multiples of some $b$—here all of $A$. Range is all $b$ that divide some $a$—here $\{1,2,3,4,5,6\}$ but check: $5$ only divides $5$ in $A$, so yes.

III. Partially Ordered Sets (Posets)

Definition: A set $A$ with relation $\le$ that is reflexive, antisymmetric, and transitive.

Key Terms (for Poset $(A, \le)$):

• Maximal element: $a$ such that no $b \in A$ with $$\displaystyle a < b $$.

• Minimal element: $a$ such that no $b \in A$ with $$\displaystyle b < a $$.

• Greatest element (maximum): $a$ such that $\forall b \in A, b \le a$.

• Least element (minimum): $a$ such that $\forall b \in A, a \le b$.

• Lattice: A poset where every pair of elements has a least upper bound (join) and greatest lower bound (meet).

Hasse Diagram:

• Draw vertices as elements.

• Omit reflexive loops and transitive edges.

• Place higher elements above lower ones.

• Connect with edges only for covering relation ($a$ covers $b$ if $$\displaystyle a > b $$ and no $c$ with $$\displaystyle a > c > b $$).

Common Divisor Sets:

• $$\displaystyle D_{15} = \{1,3,5,15\} $$: 1 at bottom, 15 at top, 3 and 5 in middle, edges: $1\to3$, $1\to5$, $3\to15$, $5\to15$.

• $$\displaystyle D_{24} = \{1,2,3,4,6,8,12,24\} $$: Build stepwise: 1 covers 2,3; 2 covers 4,6; 3 covers 6; 4 covers 8,12; 6 covers 12; 8 covers 24; 12 covers 24.

• $$\displaystyle A=\{1,2,3,4,6,8,9,12,18,24\} $$: Similar to $$\displaystyle D_{24} $$ but missing 16? Actually includes 9,18. Check divisibility: 1 covers 2,3; 2 covers 4,6; 3 covers 6,9; 4 covers 8,12; 6 covers 12,18; 8 covers 24; 9 covers 18; 12 covers 24; 18 covers 24.

[!TIP] Exam Tip: For Hasse diagram, always list elements in order of divisibility. Draw from bottom (1) to top (largest). Ensure no crossing edges if possible.

IV. Propositional Logic

Basic Connectives & Truth Tables:

Tautology: Always true (e.g., $p \lor \neg p$).
Contradiction: Always false (e.g., $p \land \neg p$).

Logical Equivalence: $p \equiv q$ iff $$\displaystyle p \leftrightarrow q $$ is a tautology. Prove via truth tables or laws.

Normal Forms:

• DNF (Disjunctive Normal Form): OR of ANDs (minterms). Example: $(p \land \neg q) \lor (\neg p \land q)$.

• CNF (Conjunctive Normal Form): AND of ORs (maxterms). Example: $(p \lor q) \land (\neg p \lor q)$.

Conversion to CNF:

1. Eliminate $$\displaystyle \leftrightarrow $$, $\to$.

2. Move $\neg$ inward (De Morgan, double negation).

3. Distribute $\lor$ over $\land$.

[!EXAMPLE]

$p \land (p \to q)$

Step 1: $p \land (\neg p \lor q)$

Step 2: $(p \land \neg p) \lor (p \land q)$

Step 3: $F \lor (p \land q) \equiv p \land q$ (already CNF? Actually $p \land q$ is a conjunction of literals, so it's CNF).

V. Graph Theory

Basic Definitions:

• Graph $$\displaystyle G = (V,E) $$: $V$ vertices, $E$ edges.

• Simple graph: No loops, no multiple edges.

• Weighted graph: Edges have weights/costs.

• Directed graph (digraph): Edges are ordered pairs.

Representations:

1. Adjacency Matrix $A$: $$\displaystyle a_{ij} = \text{number of edges from } v_i \text{ to } v_j $$.

2. Adjacency List: For each vertex, list adjacent vertices.

3. Incidence Matrix: Rows = vertices, columns = edges; entry = 1 if vertex incident to edge.

Eulerian Graph:

• Euler's Theorem: A connected graph has an Eulerian circuit iff every vertex has even degree.

• **Eulerian path