GATE IT 2008


Question 1
A set of Boolean connectives is functionally complete if all Boolean functions can be synthesized using those. Which of the following sets of connectives is NOT functionally complete?
A
EX-NOR
B
implication, negation
C
OR, negation
D
NAND
Digital Logic   Boolean Algebra
Question 2
A sample space has two events A and B such that probabilities
P(A\cap B) = \dfrac{1}{2}, P(A') = \dfrac{1}{3}, P(B') =\dfrac{1}{3}.
What is P(A\cup B) ?
A
\left(\dfrac{11}{12}\right)
B
\left(\dfrac{10}{12}\right)
C
\left(\dfrac{9}{12}\right)
D
\left(\dfrac{8}{12}\right)
Discrete Mathematics   Probability Theory


Question 3
What is the chromatic number of the following graph?

A
2
B
3
C
4
D
5
Discrete Mathematics   Graph Theory
Question 4
What is the size of the smallest MIS (Maximal Independent Set) of a chain of nine nodes
A
5
B
4
C
3
D
2
Discrete Mathematics   Graph Theory
Question 5
Which of the following regular expressions describes the language over\{0, 1\} consisting of strings that contain exactly two 1's?
A
(0 + 1)^ * \ 11(0 + 1) ^*
B
0 ^* \ 110 ^*
C
0 ^* 10 ^* 10 ^*
D
(0 + 1) ^* 1(0 + 1) ^* 1 (0 + 1) ^*
Theory of Computation   Regular Expression




There are 5 questions to complete.

Leave a Comment