PhD Admissions Written Test (Basic)

Question

Let x1, x2, ...x8 be 8 propositional variables. Let · represent AND connective ⊕ represent the Exclusive-or connective.

The number of satisfying assignments of the formula x1 ⊕ x2 ⊕ ...x8 is _________________

The number of satisfying assignments of the formula (x1·x2) ⊕ (x3·x4)... ⊕ (x7·x8) is __________________

Answer 1

$n$ propositional variables connected by $\oplus$ will result in $1$, if out of those $n$ variables odd number of variables are $1$.

So, $blank_1 = {8 \choose 1} + {8 \choose 3} + {8 \choose 5} + {8 \choose 7}$

Here, out of $8$ variables $1$ variable can be $1$ or $3$ variables can be $1$ or $5$ variables can be $1$ or $7$ variables cane be $1$. These are the possible assignments.

Two propositional variables connected by $.$ will result in $1$, if both of the variables are $1$; and $0$, if atleast one variable is $0$.

Now keeping above facts in mind -

$blank_2 = {4 \choose 1} * (3) ^ 3 + {4 \choose 3} * (3) ^ 1$

Here, out of $4$ pairs of variables $(v_i,v_{i+1})$ $1$ pair can be $1$ and remaining $3$ pairs can be $0$, each in $3$ ways or $3$ pairs can be $1$ and remaining $1$ pair can be $0$ in $3$ ways. These are the possible assignments.

Comments

If we are selecting pair (v1,v2) to be 1 ,then pair (v3,v4) has 3 choices for becoming 0, pair (v5,v6) has 3 choices and pair(v7,v8) has 3 choices.

Therefore, at last, it will be 4*3*3*3.

---

$[(v_1,v_2),(v_3,v_4),(v_5,v_6),(v_7,v_8)] = [1,1,1,0]$

This particular case has $3$ assignments that’s why we multiplied by $3$,

(1). $[(v_1,v_2),(v_3,v_4),(v_5,v_6),(v_7,v_8)] = [(1,1),(1,1),(1,1),(0,0)]$

(2). $[(v_1,v_2),(v_3,v_4),(v_5,v_6),(v_7,v_8)] = [(1,1),(1,1),(1,1),(0,1)]$

(3). $[(v_1,v_2),(v_3,v_4),(v_5,v_6),(v_7,v_8)] = [(1,1),(1,1),(1,1),(1,0)]$

---

nice bro.

Answer 2

Propositional variables connected by XOR will result in 1, if there are odd number of ones in the variables.

In the first case, there are 8 variables, resulting in $2^8$ combinations of 0s’ and 1s’ [eg. for 3 variables, $2^3$ sequence of combinations running from 000 to 111]. Out of which half of the combinations will have odd number of 1s’ which will be equal to $2^8/2=128$.

Similarly, in the second case, due to the conjuction operation, two variables should be 1 at the same time. Therefore, the total number of variables determining the result will be 4 (8/2). Hence, the combinations having odd number of 1s’ will be half of the total possible combinations. ie. $2^4/2 = 8$

Comments

For second case, your answer is wrong.