Discrete Mathematics Answers

We have 5 distinct jobs to be finished in the first 22 days of June but no two of the jobs will be finished on consecutive days. In how many ways can we plan the finishing days for these 5 distinct jobs? Write your answer: the number of ways this can be done is  

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.