Discrete Mathematics Exam Notes

Section A: Very Short Answer Questions

Question 1: Distributive Lattice

Concept: In a distributive lattice $(L, \subseteq)$, if an element has a complement, that complement is unique.

Explanation:
A distributive lattice is one where the distributive laws hold:

1. $a \land (b \lor c) = (a \land b) \lor (a \land c)$
2. $a \lor (b \land c) = (a \lor b) \land (a \lor c)$

If an element $a$ in a lattice has a complement $a'$, then $a \land a' = 0$ and $a \lor a' = 1$, where 0 and 1 are the least and greatest elements of the lattice, respectively. To prove uniqueness, assume $a$ has two complements, $b$ and $c$. Then,

$a \land b = 0, a \lor b = 1$
$a \land c = 0, a \lor c = 1$

Using the distributive property, one can show that $b = c$, thus proving the complement is unique.

Question 2: Logic Gates

Concept: Logic gates are basic building blocks of digital circuits that perform logical operations on one or more inputs to produce a single output.

Types of Logic Gates:

1. AND Gate: The output is true (1) if and only if all inputs are true (1). Symbol: $\,\land$
2. OR Gate: The output is true (1) if at least one input is true (1). Symbol: $\,\lor$
3. NOT Gate: The output is the inverse of the input. If the input is true (1), the output is false (0), and vice versa. Symbol: $\,\neg$
4. NAND Gate: The output is the inverse of the AND gate. It is false (0) if and only if all inputs are true (1).
5. NOR Gate: The output is the inverse of the OR gate. It is true (1) if and only if all inputs are false (0).
6. XOR Gate: (Exclusive OR) The output is true (1) if the inputs are different.
7. XNOR Gate: (Exclusive NOR) The output is true (1) if the inputs are the same.

Question 2 OR: Simple Graph Edges

Theorem: The maximum number of edges in a simple graph with $n$ vertices is $\frac{n(n-1)}{2}$.

Proof:
In a simple graph, each vertex can be connected to every other vertex. Therefore, each of the $n$ vertices can be connected to a maximum of $n-1$ other vertices. This gives a total of $n(n-1)$ potential connections. However, since each edge connects two vertices, we have counted each edge twice. Therefore, the maximum number of edges is $\frac{n(n-1)}{2}$.

Question 2 OR: Types of Trees

Concept: A tree is a connected graph with no cycles.

Types of Trees:

1. Binary Tree: A tree in which each node has at most two children, referred to as the left child and the right child.
2. Full Binary Tree: A binary tree in which every node other than the leaves has two children, and all leaves are at the same level.
3. Complete Binary Tree: A binary tree in which every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.
4. Spanning Tree: A subgraph of a graph which is a tree and connects all the vertices of the original graph.
5. Rooted Tree: A tree in which one node has been designated as the root.
6. Decision Tree: A tree where each internal node represents a test on an attribute, each branch represents an outcome of the test, and each leaf node represents a class label (used in machine learning and decision-making).

Question 3: Recurrence Relations

Concept: A recurrence relation is an equation that defines a sequence recursively. Each term of the sequence is defined as a function of the preceding terms.

Example:
Fibonacci sequence: $F(n) = F(n-1) + F(n-2)$, with initial conditions $F(0) = 0$ and $F(1) = 1$. The sequence starts as 0, 1, 1, 2, 3, 5, 8, …

Another example: $a<em>n = 2a</em>{n-1} + 1$, with $a_0 = 1$. This generates the sequence 1, 3, 7, 15, …

Question 3 OR: Switching Circuit

Function: $f(x, y, z) = (x + y) \cdot (x' + yz')$

Switching Circuit:
This function can be represented by a switching circuit with switches $x$, $y$, and $z$. The term $(x + y)$ represents a parallel connection of switches $x$ and $y$. The term $(x' + yz')$ represents a parallel connection of the complement of switch $x$ and a series connection of switches $y$ and the complement of switch $z$.

Section B: Short Answer Questions

Question 1: Recurrence Relation

Recurrence Relation:
$a<em>n + 6a</em>{n-1} + 9a<em>{n-2} = 3$, with initial conditions $a</em>0 = 0$ and $a_1 = 1$.

Solution:

1. Homogeneous Solution:
   The characteristic equation for the homogeneous part $a<em>n + 6a</em>{n-1} + 9a<em>{n-2} = 0$ is $r^2 + 6r + 9 = 0$. This factors to $(r+3)^2 = 0$, so $r = -3$ is a repeated root. The homogeneous solution is $a</em>n^{(h)} = (A + Bn)(-3)^n$.

2. Particular Solution:
   Since the right-hand side is a constant, we guess a constant particular solution $a_n^{(p)} = C$. Substituting into the original equation, we get $C + 6C + 9C = 3$, which simplifies to $16C = 3$, so $C = \frac{3}{16}$.

3. General Solution:
   The general solution is $a_n = (A + Bn)(-3)^n + \frac{3}{16}$.

4. Apply Initial Conditions:

   • $a_0 = 0 = (A + B(0))(-3)^0 + \frac{3}{16} = A + \frac{3}{16}$, so $A = -\frac{3}{16}$.
   • $a_1 = 1 = (A + B)(-3)^1 + \frac{3}{16} = -3(A + B) + \frac{3}{16}$, so $\frac{13}{16} = -3(A + B)$. Substituting $A = -\frac{3}{16}$, we get $\frac{13}{16} = -3(-\frac{3}{16} + B)$, which gives $\frac{13}{16} = \frac{9}{16} - 3B$, so $3B = -\frac{4}{16} = -\frac{1}{4}$, and $B = -\frac{1}{12}$.

5. Final Solution:
   $a_n = (-\frac{3}{16} - \frac{1}{12}n)(-3)^n + \frac{3}{16}$

Question 1 OR: Incidence and Adjacency Matrix

Graph: A graph with vertices $V = {v<em>1, v</em>2, v<em>3, v</em>4}$ and edges $E = {e<em>1, e</em>2, e<em>3, e</em>4, e_5}$.

Incidence Matrix:
The incidence matrix $I$ is a $4 \times 5$ matrix where $I<em>{ij} = 1$ if vertex $v</em>i$ is incident to edge $e_j$, and 0 otherwise.

I = \begin{bmatrix}
1 & 1 & 0 & 0 & 0 \
1 & 0 & 1 & 1 & 0 \
0 & 1 & 1 & 0 & 1 \
0 & 0 & 0 & 1 & 1
\end{bmatrix}

Adjacency Matrix:
The adjacency matrix $A$ is a $4 \times 4$ matrix where $A<em>{ij} = 1$ if there is an edge between vertices $v</em>i$ and $v_j$, and 0 otherwise. Since the graph is undirected, the adjacency matrix is symmetric.

A = \begin{bmatrix}
0 & 1 & 1 & 0 \
1 & 0 & 1 & 1 \
1 & 1 & 0 & 1 \
0 & 1 & 1 & 0
\end{bmatrix}

Question 2: Equivalence Relation

Concept: A relation $R$ on a set $A$ is an equivalence relation if it is reflexive, symmetric, and transitive.

Relation: "is equal to" ($=$) on the set of all real numbers $\mathbb{R}$.

Proof:

1. Reflexive: For all $a \in \mathbb{R}$, $a = a$. Therefore, the relation is reflexive.
2. Symmetric: For all $a, b \in \mathbb{R}$, if $a = b$, then $b = a$. Therefore, the relation is symmetric.
3. Transitive: For all $a, b, c \in \mathbb{R}$, if $a = b$ and $b = c$, then $a = c$. Therefore, the relation is transitive.

Since the relation "is equal to" is reflexive, symmetric, and transitive, it is an equivalence relation.

Question 2 OR: Minimal Boolean Functions

Theorem: The number of minimal Boolean functions in $n$ variables is $2^{2^{n-1}}$.
Explanation:
A minimal Boolean function is a Boolean function that cannot be simplified further. A Boolean function in n variables can be represented by a truth table with $2^n$ rows. However, each minimal Boolean function is defined by minterms. There are $2^n$ minterms, and each minimal boolean function takes one of these minterms as input. This means the number of minimal boolean functions will be 2 to the power of the number of combinations of minterms, so the result is $2^{2^{n-1}}$.

Question 3: Poset and Lattice

Given: $A = {2, 3, 4, 6}$ and the divisibility relation $\,|\,$ on $A$.

Poset:
To show that $(A, \,|\,)$ is a poset, we need to show that the divisibility relation is reflexive, antisymmetric, and transitive.

1. Reflexive: For all $a \in A$, $a \,|\, a$. (2|2, 3|3, 4|4, 6|6). So, reflexive.
2. Antisymmetric: For all $a, b \in A$, if $a \,|\, b$ and $b \,|\, a$, then $a = b$. (If $a$ divides $b$ and $b$ divides $a$, then $a$ must equal $b$). So, antisymmetric.
3. Transitive: For all $a, b, c \in A$, if $a \,|\, b$ and $b \,|\, c$, then $a \,|\, c$. (If $a$ divides $b$ and $b$ divides $c$, then $a$ divides $c$). For example, 2|4 and 4|4 implies 2|4. SO, transitive.

Since the divisibility relation is reflexive, antisymmetric, and transitive, $(A, \,|\,)$ is a poset.

Not a Lattice:
To be a lattice, every pair of elements must have a least upper bound (LUB) and a greatest lower bound (GLB).

Consider the elements 3 and 4 in $A$. The divisors of 3 are {3} and the divisors of 4 are {2, 4}, while the multiples of 3 from the set $A$ are {3, 6} and the multiples of 4 from the set $A$ is {4}. The only divisors that it has in common is {}, meaning, the GLB (or meet) from 3 and 4 doesn't exist given the set $A$. Therefore, $(A, \,|\,)$ is not a lattice.

Question 3 OR: Graph with Two Odd Vertices

Theorem: If a graph $G$ has exactly two odd vertices, there must be a path joining these two vertices.
Explanation:

Let $G = (V, E)$ be a graph with exactly two odd vertices, say $u$ and $v$. Assume, for the sake of contradiction, that there is no path between $u$ and $v$. Then, $u$ and $v$ must belong to different connected components, say $G<em>1$ and $G</em>2$, respectively. Consider the connected component $G<em>1$ containing vertex $u$. Since $u$ is an odd vertex, the sum of the degrees of the vertices in $G</em>1$ is odd. However, the Handshaking Lemma states that the sum of the degrees of the vertices in any graph is equal to twice the number of edges, which must be even. This is a contradiction. Therefore, our assumption that there is no path between $u$ and $v$ must be false. Hence, there must be a path joining these two vertices.

Question 4: Hamiltonian and Eulerian Circuits

Hamiltonian Circuit: A cycle that visits each vertex exactly once.
Eulerian Circuit: A cycle that visits each edge exactly once.

1. Graph with Hamiltonian Circuit but not Eulerian Circuit:
   A complete graph with five vertices ($K_5$) has a Hamiltonian circuit (any cycle that visits all 5 vertices). However, each vertex has degree 4, so if we add one more vertex and connect it to 2 vertices, we will have an Eulerian circuit.

2. Graph with Eulerian Circuit but not Hamiltonian Circuit:
   Consider a graph with two cycles connected by a single vertex; both cycles use different edges but connect on a center vertex $v$. For example, two triangles that share a vertex. If we added another triangle and connected it to vertex $v$, we will still have an Eulerian circuit at vertex $v$, but not visit all vertices.

Question 4 OR: Tree with n Vertices

Theorem: A tree with $n$ vertices has $(n-1)$ edges.
Proof:

We can use induction on the number of vertices $n$.

Base Case: For $n = 1$, a tree with one vertex has 0 edges. Thus, the theorem holds.

Inductive Step: Assume the theorem holds for a tree with $k$ vertices, i.e., it has $(k-1)$ edges. Now, consider a tree with $(k+1)$ vertices. A tree is a connected graph with no cycles. If we remove a leaf (a vertex with degree 1) from the tree, we are left with a tree with $k$ vertices, which, by the inductive hypothesis, has $(k-1)$ edges. The removed leaf was connected to the rest of the tree by exactly one edge. Therefore, the original tree with $(k+1)$ vertices had $(k-1) + 1 = k$ edges.

Thus, the theorem holds for $(k+1)$ vertices. By the principle of mathematical induction, a tree with $n$ vertices has $(n-1)$ edges.

Section C: Long Answer Questions

Question 1: Generating Functions

Recurrence Relation: $y<em>{n+2} - 7y</em>{n+1} + 10y<em>n = 0$, with $y</em>0 = 0$ and $y_1 = 3$.

Solution:

1. Define Generating Function: Let $Y(x) = \sum<em>{n=0}^{\infty} y</em>n x^n$ be the generating function for the sequence ${y_n}$.

2. Apply Generating Function to Recurrence Relation:
   $\sum<em>{n=0}^{\infty} y</em>{n+2} x^n - 7 \sum<em>{n=0}^{\infty} y</em>{n+1} x^n + 10 \sum<em>{n=0}^{\infty} y</em>n x^n = 0$

3. Rewrite Summations:
   $\frac{Y(x) - y<em>0 - y</em>1 x}{x^2} - 7 \frac{Y(x) - y_0}{x} + 10Y(x) = 0$

4. Substitute Initial Conditions:
   $\frac{Y(x) - 0 - 3x}{x^2} - 7 \frac{Y(x) - 0}{x} + 10Y(x) = 0$

5. Solve for Y(x):
   $Y(x) - 3x - 7xY(x) + 10x^2 Y(x) = 0$
   $Y(x)(1 - 7x + 10x^2) = 3x$
   $Y(x) = \frac{3x}{1 - 7x + 10x^2} = \frac{3x}{(1-2x)(1-5x)}$

6. Partial Fraction Decomposition:
   $\frac{3x}{(1-2x)(1-5x)} = \frac{A}{1-2x} + \frac{B}{1-5x}$
   $3x = A(1-5x) + B(1-2x)$

   • Let $x = \frac{1}{2}$: $\frac{3}{2} = A(1 - \frac{5}{2}) = A(-\frac{3}{2})$, so $A = -1$
   • Let $x = \frac{1}{5}$: $\frac{3}{5} = B(1 - \frac{2}{5}) = B(\frac{3}{5})$, so $B = 1$

   Thus, $Y(x) = \frac{-1}{1-2x} + \frac{1}{1-5x}$

7. Expand as Power Series:
   $Y(x) = - \sum<em>{n=0}^{\infty} (2x)^n + \sum</em>{n=0}^{\infty} (5x)^n = \sum_{n=0}^{\infty} (5^n - 2^n) x^n$

8. Find $y<em>n$:
   $y</em>n = 5^n - 2^n$

Question 1 OR: Normal Forms

Function: $f(x, y, z) = (xy' + xz)' + x$

Conjunctive Normal Form (CNF):

1. Apply De Morgan's Law:
   $f(x, y, z) = (xy')'(xz)' + x = (x' + y)(x' + z') + x$

2. Distribute:
   $f(x, y, z) = x'x' + x'z' + yx' + yz' + x = x' + x'z' + yx' + yz' + x$

3. Apply X + X' = 1
   $f(x, y, z) = 1 + x'z' + yx' + yz'$

4. Simplify:
   $f(x, y, z) = 1$
   Since the solution is the function 1, the CNF (or DNF) is simply 1.

Disjunctive Normal Form (DNF):
Following the same steps as above, the simplified DNF is also be 1.

Question 2: Dijkstra's Algorithm

Graph: A weighted graph with vertices a, b, c, d, e, and z.

Dijkstra's Algorithm:

1. Initialization:

   • Distance to source (a) is 0: $d(a) = 0$. Distance to all other vertices is infinity: $d(b) = d(c) = d(d) = d(e) = d(z) = \infty$.
   • Unvisited set: $Q = {a, b, c, d, e, z}$

2. Iteration:

   • a:
     • Visit neighbors: b (3), c (14)
     • Update distances: $d(b) = 3, d(c) = 14$. $Q = {b, c, d, e, z}$
   • b:
     • Visit neighbors: a, c (5), d (8)
     • Update distances: $d(c) = \min(14, 3+5) = 8, d(d) = 3+8 = 11$. $Q = {c, d, e, z}$
   • c:
     • Visit neighbors: a, b, d (4), e (13)
     • Update distances: $d(d) = \min(11, 8+4) = 11, d(e) = 8+13 = 21$. $Q = {d, e, z}$
   • d:
     • Visit neighbors: b, c, e, z (10)
     • Update distances: $d(e) = \min(21, 11) = 11$ (Note: this update doesn't change the current value of d(e)), since d(d) + 8 = 19 > 11. $d(z) = 11 + 10 = 21$. $Q = { e, z}$
   • e
   • Visit neighbors: c, d, z (9)
     • Update distances: $d(z) = \min(21, 11+9) = 20.$ $Q = { z}$
   • z:
     • No unvisited neighbors. $Q = {}$

3. Shortest Path: a -> b -> d -> z. Total distance: 3 + 8 + 10 = 21.
   Answer:
   The shortest path from a to z is a -> b -> d -> z with a total distance of 21.

Question 2 OR: Kruskal's and Prim's Algorithms

Graph: A weighted graph with vertices v1, v2, v3, v4, v5, and v6.

Kruskal's Algorithm:

1. Sort Edges: Sort all edges in increasing order of weight.

2. Iterate: Add edges to the spanning tree in order, unless adding an edge creates a cycle.

   Edges (Weight): (v1, v2, 1), (v4, v6, 2), (v1, v5, 3), (v3, v4, 3), (v2, v4, 5), (v2, v3, 6), (v5, v6, 6), (v3, v5, 10)

3. Minimal Spanning Tree:

   • (v1, v2, 1)
   • (v4, v6, 2)
   • (v1, v5, 3)
   • (v3, v4, 3)
   • (v2, v4, 5)

   The minimal spanning tree consists of the edges (v1, v2), (v4, v6), (v1, v5), (v3, v4). The total weight is 1+2+3+3+5.

Prim's Algorithm:

1. Start Vertex: Choose any vertex as the starting vertex (e.g., v1).

2. Iterate: Grow the tree by adding the minimum weight edge that connects a vertex in the tree to a vertex not yet in the tree.

   • Start: v1
   • Edges from v1: (v1, v2, 1), (v1, v5, 3)
   • Add (v1, v2, 1): Tree = {v1, v2}
   • Edges from v1, v2: (v1, v5, 3), (v2, v3, 6), (v2, v4, 5)
   • Add (v1, v5, 3): Tree = {v1, v2, v5}
   • Edges from v1, v2, v5:
   • (v2, v3, 6), (v2, v4, 5), (v5, v6, 6), remove v5 to v1 since that is a cycle. *Add (v2,v4, 5): Tree={v1,v2,v5,v4}
     • Edges from (v1, v2, v5,v4): (v4, V3,3) (v4,V6,2) and remove others sine are cycles. add v4, v6 since vertex has 2 unit value, then add Vertex V4 unit 3 to complete.
       The minimal spanning tree consists of the edges (v1, v2), (v4, v6), (v1, v5), (v3, v4). Total weight is 1+3+2+3.