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: an = 2a{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:
an + 6a{n-1} + 9a{n-2} = 3, with initial conditions a0 = 0 and a_1 = 1.

Solution:

1. Homogeneous Solution:
   The characteristic equation for the homogeneous part an + 6a{n-1} + 9a{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 an^{(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 = {v1, v2, v3, v4} and edges E = {e1, e2, e3, e4, e_5}.

Incidence Matrix:
The incidence matrix I is a 4 \times 5 matrix where I{ij} = 1 if vertex vi 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{ij} = 1 if there is an edge between vertices vi 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 G1 and G2, respectively. Consider the connected component G1 containing vertex u. Since u is an odd vertex, the sum of the degrees of the vertices in G1 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{n+2} - 7y{n+1} + 10yn = 0, with y0 = 0 and y_1 = 3.

Solution:

1. Define Generating Function: Let Y(x) = \sum{n=0}^{\infty} yn x^n be the generating function for the sequence {y_n}.

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

3. Rewrite Summations:
   \frac{Y(x) - y0 - y1 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{n=0}^{\infty} (2x)^n + \sum{n=0}^{\infty} (5x)^n = \sum_{n=0}^{\infty} (5^n - 2^n) x^n

8. Find yn:
   yn = 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.