Discrete Mathematics Answers

1. Consider the K-Maps given below. For each K- Map 

i. Write the appropriate standard form (SOP/POS) of Boolean expression.

ii. Design the circuit using AND, NOT and OR gates.

iii. Design the circuit only by using 

• NAND gates if the standard form obtained in part (i) is SOP.

• NOR gates if the standard form obtained in pat (i) is POS.

1. Simplify the following Boolean expressions using algebraic methods. 

1.

A(A+B)+B(B+C)+C(C+A)

2.

(A+B ̅)(B+C)+(A+B)(C+A ̅)

3.

(A+B)(AC+AC ̅)+AB+B

4.

A ̅(A+B)+(B+A)(A+B ̅)

1. Assess whether the following undirected graphs have an Eulerian and/or a Hamiltonian cycle. 

Use Dijkstra’s algorithm to find the shortest path spanning tree for the following weighted 

directed graph with vertices A, B, C, D, and E given. Consider the starting vertex as E.

Discuss Karnaugh map with one, two, three and four

variables

I.

Write what is asked on the following item. Write your answer before the

item.

1. Set of points in a graph

2. Set of lines in a graph.

3. A node with no children.

4. Children with the same parent.

5. Tree with n vertices consists of _______ edges.

6. A graph which is connected and acrylic.

7. Disjoint collection of trees.

8. Graph with no edges.

9. A graph multiple edges between the same set of vertices.

10. Vertex with zero degree.  

Draw a binary search tree by inserting the values 50, 76, 21, 4, 32, 64, 15, 52, 14, 100, 83, 2, 3 and 70.

Let A = {0, 2, 4, 6, 8, 10}, B = {0, 1, 2, 3, 4, 5, 6}, and C = {4, 5, 6, 7, 8, 9, 10}. Find a) A ∩ B ∩ C. b) A ∪ B ∪ C. c) (A ∪ B) ∩ C. d) (A ∩ B) ∪ C.

Define a binary relation P from R to R as follows: for all real numbers x and y,

(𝑥, 𝑦) ∈ 𝑃 ⇔ 𝑥 = 𝑦

2

. Is P a function? Explain.

Let p, q and r be the propositions. p: You are a student of Govt. College of

science. q: You get first position in the college. r: You get first position in

University of the Punjab. i) You are a student of Govt. College of science, but

You do not get first position in the college. ii) You will get first position in

University of the Punjab if and only if You get first position in the college or You

are a student of Govt. College of science.