Discrete Mathematics - Questions & Answers for Competitive Exams | GkSeries

13. Traveling salesman problem is example for_______graph.

• [A] eulerian
• [B] hamiltonian
• [C] tournament
• [D] planar

Answer: Option [B]

14. If a normal form contains all minterms, then it is ________.

• [A] a tautology
• [B] a contradiction
• [C] a contingency
• [D] both A and B

Answer: Option [A]

15. PCNF is also called _______.

• [A] sum of product canonical form.
• [B] product of sum canonical form
• [C] sum canonical form
• [D] product canonical form

Answer: Option [B]

16. Max-terms of two statements are formed by introducing the connective _________.

• [A] disjunction
• [B] conjunction
• [C] negation
• [D] conditional

Answer: Option [A]

17. The number of relations from A = {a,b,c] to B = {1,2] are __________.

• [A] 6
• [B] 8
• [C] 32
• [D] 64

Answer: Option [D]

18. A graph is planar if and only if it does not contain ________.

• [A] subgraphs homeomorphic to k3 & k3,3
• [B] subgraphs isomorphic to k5 or k3,3
• [C] subgraphs isomorphic to k3 & k3,3
• [D] sub graphs homeomorphic to k5 or k3,3

Answer: Option [D]

19. sub graphs homeomorphic to k5 or k3,3

• [A] one arrow between each pair of distinct vertices
• [B] two arrows between each pair of distinct vertices
• [C] n-1 arrows between each pair of distinct vertices
• [D] path between every two distinct vertices

Answer: Option [A]

20. If a compound statement is made up of three simple statements then the number of rows in the truth table is _______.

• [A] 2
• [B] 4
• [C] 6
• [D] 8

Answer: Option [D]

21. If R= {(x, 2x)] and S= {(x, 4x)] then R composition S=____.

• [A] {(x, 4x)]
• [B] {(x, 2x)]
• [C] {(x, 8x)]
• [D] {(x, 10x)]

Answer: Option [C]

22. A regular grammar contains rules of the form _______.

• [A] A tends to AB
• [B] AB tends to a
• [C] A tends to aB
• [D] AB tends to CD

Answer: Option [C]

23. The NAND statement is a combination of ________.

• [A] NOT and AND
• [B] NOT and OR
• [C] AND and OR
• [D] NOT or OR

Answer: Option [A]

24. The NOR statement is a combination of ________.

• [A] NOT and AND
• [B] NOT and OR
• [C] AND and OR
• [D] NOT or OR

Answer: Option [B]