Discrete Mathematics Exam Notes

Discrete Mathematics Notes

Section A: Objective Questions

1. Two lattices $L<em>1$ and $L</em>2$ are isomorphic if there is a bijection from $L<em>1$ to $L</em>2$. So the answer is (b).

2. POSET is denoted by $(S, \leq)$. So the correct answer is (b) (S, < ).

3. In Boolean algebra, $a \cdot b = (a+b)(a'+b)$. So the answer is (b) $(a + b) (a'+ b)$.

4. A complete undirected graph with $n$ nodes can have a maximum of $\frac{n(n-1)}{2}$ spanning trees. So the answer is (c) $n (n + 1) / 2$.

5. In a 7-node directed cyclic graph, the number of Hamiltonian cycles is to be determined. This is more complex and requires graph theory knowledge. Without further context on graph structure, a precise number is hard, but (d) 260 seems the closest reasonable answer given the options.

6. For the recurrence relation $a<em>n = 2a</em>{n-1} + 3$ with $a<em>0 = 6$, we need to find $a</em>4$. Let's iterate:

   • $a<em>1 = 2a</em>0 + 3 = 2(6) + 3 = 15$
   • $a<em>2 = 2a</em>1 + 3 = 2(15) + 3 = 33$
   • $a<em>3 = 2a</em>2 + 3 = 2(33) + 3 = 69$
   • $a<em>4 = 2a</em>3 + 3 = 2(69) + 3 = 141$
     So the answer is (c) 141.

Section B: Short Answer Questions

1. (a) Hasse Diagram for subsets of $S = {a, b, c}$ with inclusion relation $\subseteq$:
   The subsets are: $\emptyset, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}$. A Hasse diagram would show these sets with upward edges indicating inclusion (subset) relation. Omitted here due to markdown.

   (b) Prove that a finite non-empty POSET $(P, R)$ has at least one minimal and one maximal element:
   In a finite POSET, since the set is finite, any chain must also be finite. If we start at any element $x \in P$, if it's not minimal, there exists $y \in P$ such that $yRx$ and $y \neq x$. We can repeat this, but since $P$ is finite, we must eventually reach a minimal element. A similar argument applies to maximal elements.

   (c) Let $A = {2, 3, 4, 6}$ and $|$ be the divisibility relation on $A$. Show that $(A, |)$ is a POSET but not a lattice:

   • POSET: Divisibility is reflexive (a | a), antisymmetric (if a | b and b | a, then a = b), and transitive (if a | b and b | c, then a | c). Hence, it's a POSET.
   • Not a Lattice: Consider the elements 2 and 3. Their least upper bound (LUB) would be the smallest number divisible by both, which is 6 (present in A). However, their greatest lower bound (GLB) would be the largest number that divides both, which is 1 (not in A). Also, consider 4 and 6, GLB(4,6) = 2(present in A). LUB(4,6) = 12 ( not in A). Since not every pair has both a LUB and GLB within A, it's not a lattice.

2. (a) Logic circuit for $F(x, y, z) = x \cdot z + [y \cdot (y' + z)(x' + xz')]$:
   First, simplify the expression:
   $F(x, y, z) = xz + [y(y' + z)(x' + xz')] = xz + [y(y' + z)x'] = xz + [yy'x' + yzx'] = xz + yzx'$
   $F(x, y, z) = xz + x'yz$
   The logic circuit can be created directly from the simplified boolean expression using AND, OR and NOT gates.

   (b) Convert $F(x, y, z) = xy' + xz + xyz$ to Conjunctive Normal Form (CNF):
   $F(x, y, z) = xy' + xz + xyz = x(y' + z) + xyz = x(y' + z + yz) = x(y' + z(1+y)) = x(y' + z)$
   $F(x, y, z) = x(y' + z) = (x + 0)(y' + z) = (x + y y')(y' + z) = (x + y)(x + y')(y' + z)$
   The CNF is $(x+y)(x+y')(y'+z)$.

   (c) Define logic gates with truth tables:

   • AND: Output is 1 only if all inputs are 1.
   • OR: Output is 1 if at least one input is 1.
   • NOT: Output is the inverse of the input.
   • XOR: Output is 1 if inputs are different.
   • NAND: Output is the inverse of AND.
   • NOR: Output is the inverse of OR.

3. (a) Show that a complete graph with five vertices ($K<em>5$) is not a planar graph: A graph is planar if it can be drawn on a plane without any edges crossing. $K</em>5$ has 5 vertices and $\frac{5(5-1)}{2} = 10$ edges. According to Kuratowski's theorem, a graph is non-planar if and only if it contains a subgraph that is a subdivision of $K<em>5$ or $K</em>{3,3}$. Since $K<em>5$ itself exists as as subgraph of $K</em>5$, it is non-planar.

   (b) Show that a simple graph with n vertices has a maximum of $\frac{n(n-1)}{2}$ edges:
   In a simple graph, each vertex can be connected to every other vertex, but not itself, and there's at most one edge between any two vertices. So each of the $n$ vertices can connect to $n-1$ other vertices. This gives $n(n-1)$ potential connections, but since each edge connects two vertices, we divide by 2 to avoid double counting. Thus, the maximum number of edges is $\frac{n(n-1)}{2}$.

   (c) Explain Euler graph and Hamiltonian path with examples:

   • Euler Graph: A graph that has an Euler circuit, which is a path that visits every edge exactly once and returns to the starting vertex. A connected graph has an Euler circuit if and only if every vertex has even degree. Example: A square graph (4 vertices, 4 edges forming a square).
   • Hamiltonian Path: A path that visits every vertex exactly once. It doesn't necessarily have to return to the starting vertex (Hamiltonian Cycle). Example: In a complete graph, there's always a Hamiltonian path.

4. (a) Adjacency and Incidence Matrix for the directed graph:
   Adjacency Matrix: A matrix where entry (i, j) is 1 if there is an edge from vertex i to vertex j, and 0 otherwise.
   Incidence Matrix: A matrix where entry (i, j) is 1 if vertex i is incident to edge j, -1 for the target vertex of the directed edge, and 0 otherwise.

   (b) Define Planar graph and show that G is a planner graph:
   A planar graph is a graph that can be drawn on a plane without any edges crossing. To show that G is a planar graph, you'd either need to redraw it without crossings or demonstrate that it satisfies Euler's formula for planar graphs: $v - e + f = 2$ where $v$ is the number of vertices, $e$ is the number of edges, and $f$ is the number of faces.

   (c) Define Rank and Nullity of a graph:

   • Rank: The number of vertices minus the number of connected components in the graph. If $G$ has $n$ vertices and $k$ connected components, then rank(G) = $n - k$.
   • Nullity: The number of edges minus the rank of the graph. If $G$ has $e$ edges, then nullity(G) = $e - (n - k) = e - n + k$.

5. (a) Find the generating function for the numeric sequence 2, 6, 18, 54, 162, …:
   This is a geometric sequence with first term $a = 2$ and common ratio $r = 3$. The generating function is:
   $G(x) = \sum<em>{n=0}^{\infty} a</em>n x^n = \sum<em>{n=0}^{\infty} 2 \cdot 3^n x^n = 2 \sum</em>{n=0}^{\infty} (3x)^n$
   Since $\sum_{n=0}^{\infty} r^n = \frac{1}{1-r}$ for |r| < 1,
   $G(x) = \frac{2}{1 - 3x}$.

   (b) Define Recurrence Relation and its partial conditions with an example:
   Recurrence Relation: An equation that defines a sequence recursively. Each term is defined as a function of preceding terms.
   Partial Condition: Also known as initial conditions, these are necessary to fully define the sequence. They provide starting values for the recurrence relation.
   Example: Fibonacci sequence: $F<em>n = F</em>{n-1} + F<em>{n-2}$, with initial conditions $F</em>0 = 0$ and $F_1 = 1$.

   (c) Solve the recurrence relation $a<em>n = a</em>{n-1} + 2a<em>{n-2}$ for $n \geq 2$ with initial conditions $a</em>0 = 0$ and $a<em>1 = 1$: The characteristic equation is $r^2 - r - 2 = 0$, which factors as $(r - 2)(r + 1) = 0$. So the roots are $r</em>1 = 2$ and $r<em>2 = -1$. The general solution is $a</em>n = A(2)^n + B(-1)^n$.
   Using the initial conditions:

   • $a_0 = 0 = A(2)^0 + B(-1)^0 = A + B$
   • $a<em>1 = 1 = A(2)^1 + B(-1)^1 = 2A - B$ Solving the system of equations: $A + B = 0 \implies B = -A$$2A - B = 1 \implies 2A - (-A) = 3A = 1 \implies A = \frac{1}{3}$$B = -\frac{1}{3}$ Therefore, $a</em>n = \frac{1}{3}(2)^n - \frac{1}{3}(-1)^n = \frac{2^n - (-1)^n}{3}$.

Section C: Long Answer Questions

1. Define Generating Function and solve for $a<em>{n+2} - 3a</em>{n+1} + 2a<em>n = 0$, with $a</em>0 = 2$, $a_1 = 3$:

   • Generating Function: A power series representation of a sequence.
   • To solve the recurrence, let $G(x) = \sum<em>{n=0}^{\infty} a</em>n x^n$. Multiply the recurrence by $x^n$ and sum from $n=0$ to $\infty$.
     $\sum<em>{n=0}^{\infty} a</em>{n+2}x^n - 3 \sum<em>{n=0}^{\infty} a</em>{n+1}x^n + 2 \sum<em>{n=0}^{\infty} a</em>n x^n = 0$
     After substitution and simplification using initial conditions, the generating function comes out to be $G(x) = \frac{2-x}{1-3x+2x^2}$. Solving partial fractions, and comparing the coefficeint, you will find the general form of $a_n$.

2. Determine PCNF (Product of Conjunctive Normal Forms) and PDNF (Sum of Minterms/Disjunctive Normal Form) for the given Boolean function:
   To find PCNF and PDNF. you need the truth table for the boolean expression M. Then, PCNF can be derived by taking the product of maxterms (rows where M=0), and PDNF is the sum of minterms (rows where M=1).

3. Dijkstra's Algorithm to find the shortest path from A to I:
   Dijkstra's algorithm is used to find the shortest path in a weighted graph. The algorithm maintains a set of visited nodes and a distance estimate for each node. Starting from A, it iteratively visits the unvisited node with the smallest distance estimate, updates the distances of its neighbors, and repeats until I is reached. Note: The actual working of the algorithm and shortest path requires applying Dijkstra's algorithm on the graph. So you perform Dijkstra's algorithm, noting visited nodes and update the edge with the smallest distance to I. (Implementation is omitted)

4. Kruskal's and Prim's Algorithms for Minimal Spanning Tree:

   • Kruskal's Algorithm: Sort all edges by weight and iteratively add the smallest edge that doesn't create a cycle.
   • Prim's Algorithm: Start with a single vertex and iteratively add the smallest edge that connects the current tree to a new vertex. (Implementation is omitted)

5. Define Equivalence Relation and show that R is an equivalence relation. Draw the graph of R:
   Let $X = {1, 2, …, 7}$ and $R = {(x, y) | x - y \text{ is divisible by } 3}$.

   • Equivalence Relation: A relation that is reflexive, symmetric, and transitive.

     • Reflexive: For all $x \in X$, $(x, x) \in R$ (since $x - x = 0$ is divisible by 3).
     • Symmetric: If $(x, y) \in R$, then $(y, x) \in R$ (if $x - y$ is divisible by 3, then $y - x$ is also divisible by 3).
     • Transitive: If $(x, y) \in R$ and $(y, z) \in R$, then $(x, z) \in R$ (if $x - y$ and $y - z$ are divisible by 3, then $(x - y) + (y - z) = x - z$ is also divisible by 3).
       Therefore, R is an equivalence relation.

   • Graph of R: The graph would have vertices 1 to 7. There's an edge between $x$ and $y$ if $(x, y) \in R$. That is the following edges are present
     $(1,1), (2,2),(3,3),(4,4),(5,5),(6,6),(7,7),(1,4),(4,1),(1,7),(7,1),(4,7),(7,4),(2,5),(5,2),(2,8),(8,2),(5,8),(8,5),(3,6),(6,3)$