1. (a) Explain Tautologies and Contradiction with help of example.
(b) Prove that the following propositions are Tautology
(i) p V ~p (ii) ~(p ^ q) V q (iii) p => (p V q)
2. (a) What is disjunctive normal form .Explain the procedure to obtain disjunctive normal form.
(b) Obtain the disjunctive normal forms of the followings
(ii) p ^ (p=>q) (ii) p =>((p=>q) ^ ~(~q V ~p))
3. Prove that with help of Boolean algebra
(i) (a+b)’ =a’.b’ (ii) (a.b)’ =a’ + b’
4. Explain all logic gates with symbol and truth table. Simplyfy the Boolean expression
A+B(A+B)+A(A’+B)
5. Explain 3 variable and 4 variable K’Map . Use Karnaugh map to simplify the followings
(a) X= ABC’ + ABC Ans: X=AB
(b) X= A’B’C’ + AB’C’ Ans: X= B’C’
(c) X= A’BC’D’ + ABC’D’ + A’BCD’ + ABCD’ Ans: X= B.D’
6.
7. Explain, Graph, multigraph, Null graph, with examples.
Prove that a simple graph with n vertices and k components cannot have more than
(n-k)(n-k+1)/2 edges.
8. A tree has two vertices of degree 2, one vertices of degree 3 and three vertices of degree 4. How many vertices of degree 1 does it have?
Case Detail
1.
2. Simplify the following Boolean function F(A,B,C,D)= Σ( 0,1,2,3,4,5,7,6,8,9,11)
Assignment C
1. Complement the expression by applying De-Morgan’s theorem (A+A’B)’?
Options
- AB
- A’B'
- A’B’ **
- AB’
2. Find the minimum sum of product using K-Map?
F= AB+AB’C+ABC
Options
- F=A’B+AC
- F=AB+AC’
- F=AB’+AC
- F=AB+AC**
3. what is the value of Boolean expression a+a’=?
Options
- 1**
- 2
- a
- a’
4. Consider the following--
p: Anil is rich q: Kanchan is poor
What is the symbolic form of the following statement?
Anil is poor and Kanchan is rich
Options
- ~p ^ q
- p ^ q**
- ~p ^ ~q
- None of above
5. Consider the following
P: This computer is good q: This computer is cheap
What is the symbolic form of the following statement?
This computer is neither good nor cheap
Options
- ~p ^ q
- p ^ ~q
- (~p) ^ (~q)**
- None of above
6. In which of the following gates the output is 1, if and only if at least one input is 1 ?
Options
- NOR
- AND
- OR**
- NAND
7. In which of the following gates the output is 0, if and only if at least one input is 1 ?
Options
- NOT
- AND
- NOR**
- NAND
8. What is the minimum number of two input NAND gates used to perform the function of two inputs OR gate?
Options
- Three**
- Two
- One
- Four
9. Which of the following gates are added to the inputs of the OR gate to convert it to the NAND gate?
Options
- NOT**
- AND
- AND
- XOR
10. What logic function is produced by adding an inverter to the output of an AND gate?
Options
- NAND**
- NOR
- XOR
- OR
11. Which of the following Boolean algebra expressions is incorrect?
Options
- A+ A’+= A+B
- A+AB =B **
- (A+B)(A+B) = A+BC
- (A+B’)(A+B)=A
12. The simplified form of the Boolean expression (X+Y+XY)(X+Z) is ?
Options
- X+Y+Z
- XY+YZ
- X+YZ**
- XZ+Y
13. The simplified form of the Boolean expression (X+Y’+Z)(Z+Y’+Z’) (X+Y+Z) is ?
Options
- X’Y+Z’
- X+Y’Z**
- X
- XY+Z’
14. A full binary tree with n leaves contains--
Options
- n nodes
- log2n nodes
- (2n-1) nodes **
- 2n nodes
15. A full binary tree with non- leaf nodes contains--
Options
- (2n+1) nodes **
- log2n nodes
- (n+1) nodes
- 2n nodes
16. A complete graph with five vertices is--
Options
- Non planar
- planar
- a non regular graph
- a tree **
17. Which of the following statement is true?
Options
- (A+ B)(A+C)=AC+BC
- (A+ B)(A+C)=AB+C
- (A+ B)(A+C)=A+BC **
- (A+ B)(A+C)=AC+B
18. A non empty connected graph G is Eulerian if and only if its vertices are all of--
Options
- Odd degree
- Even degree**
- Both (a) and (b)
- None
19. A ------ is a closed path of none zero length that does not contain repeated edge.
Options
- Path
- Simple path
- Circuit**
- None
20. A ------ is a path that does not contain a repeated vertex.
Options
- Path
- Simple path**
- Circuit
- None
21. The maximum number of edges in any simple graph with n vertices is--
Options
- n
- n+1
- n(n-1)/2**
- None
22. A simple graph is said to be ------------ if every vertex in graph is connected with every other vertex
Options
- null
- regular
- complete **
- None
23. A graph in which all vertices are equal degree is called a --------- graph--
Options
- null
- regular**
- complete
- None
24. What is the value of Boolean expression a + (a.b) =?
Options
- b
- a**
- ab
- a’
25. What is the value of Boolean expression a + 1 =?
Options
- 0
- a
- 1**
- none
26. Consider the following--
P: Today is Tuesday q: It is raining r: it is cold
Write in simple sentence for -q => (r ^ p)
This computer is neither good nor cheap
Options
- If today is Tuesday, then it is raining
- If today is not Tuesday, then it is raining or it is cold
- If it is not raining, then it is cold and today is Tuesday
- None of these
27. If there exists at least one path between every pair of vertices in a graph, the graph is known as--
Options
- Complete graph
- Disconnected graph
- Connected graph**
- Euler graph
28. The length of Hamiltonian path (if exists) in a connected graph of n vertices is--
Options
- n-1**
- n
- n+1
- n/1
29. If each node in a tree has value greater than every value in its left subtree and has value less than every value in its right subtree , the tree is known as--
Options
- Complete tree
- Full binary tree
- Binary search tree**
- Threaded tree
30. Which of the following statement is false ?
Options
- A tree contains a cycle**
- A tree with n nodes contains n-1 edges
- A tree is a connected graph
- None
31. Graph can be implemented using
Options
- arrays
- linked list**
- queue
- all of these
32. Traversing a binary tree first root and then left and right subtrees called------traversal
Options
- postorder
- preorder**
- inorder
- all of these
33. A circuit is a connected graph which includes every vertex of the graph is known as
Options
- Euler
- Unicursal
- Hamiltorium**
- Clique
34. The number of vertices of odd degree in a graph is
Options
- Always even**
- Always odd
- Either even or odd
- Always zero
35. If a binary tree traversal in inorder, then numbers of the node are printed in----- order
Options
- Ascending
- Descending**
- randomly
- none of these
36. Which gate is known as universal gate
Options
- NOT gate
- AND gate
- NAND gate**
- XOR gate
37. is the value of Boolean expression (a .b)’ =?a
Options
- a+b
- a’+b’**
- a.b
- None of above
38. Find the complement of Boolean expression xy’ +x’y
Options
- x+y
- (x’+y).(x+z’)**
- x+y’
- None
39. A Karnaugh map in four variables is a square divided into ---
Options
- 8
- 12
- 14
- 16**
40. A tree with n nodes has ----- edges
Options
- n/2
- n-1**
- n
- n+1