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?

EX-NOR | |

implication, negation | |

OR, negation | |

NAND |

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) ?

P(A\cap B) = \dfrac{1}{2}, P(A') = \dfrac{1}{3}, P(B') =\dfrac{1}{3}.

What is P(A\cup B) ?

\left(\dfrac{11}{12}\right) | |

\left(\dfrac{10}{12}\right) | |

\left(\dfrac{9}{12}\right) | |

\left(\dfrac{8}{12}\right) |

Question 2 Explanation:

Question 3 |

What is the chromatic number of the following graph?

2 | |

3 | |

4 | |

5 |

Question 3 Explanation:

Question 4 |

What is the size of the smallest MIS (Maximal Independent Set) of a chain of nine nodes

5 | |

4 | |

3 | |

2 |

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?

(0 + 1)^ * \ 11(0 + 1) ^* | |

0 ^* \ 110 ^* | |

0 ^* 10 ^* 10 ^* | |

(0 + 1) ^* 1(0 + 1) ^* 1 (0 + 1) ^* |

Question 5 Explanation:

There are 5 questions to complete.