MCQ:

A)

In the following expressions, - represents the negation of a variable. For example, -x stands for "NOT x"), + represents logical OR, and juxtaposition represents logical AND (e.g., (x+y)(y+z) represents (x OR y) AND (y OR z).

Identify the expression that is satisfiable, from the list below.

a) (-x+-z)(x)(-z+-y)(y+-x)

b) (x+z)(-x)(x+-z)(z+y)

c) (-x+z)(x)(-z+y)(-y+-x)

d) (x+z)(-z+y)(-x)(-y+x)

-

B)

Find all the minimum-weight Hamilton circuits in the graph below:

Then, identify in the list below the edge that is NOT on any minimum-weight Hamilton circuit.

a) (A, D) b) (B, D) c) (A, B) d) (E, F)

2 /(D 1 B 2T 1/ 2 1 A E C/2