# 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 1 Explanation:
 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 2 Explanation:

 Question 3
What is the chromatic number of the following graph? A 2 B 3 C 4 D 5
Discrete Mathematics   Graph Theory
Question 3 Explanation:
 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 4 Explanation:
 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
Question 5 Explanation:

There are 5 questions to complete.