169 views
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 __________________

$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.

@shishir__roy I can’t understand blank 2...after selecting 1 pair, that it will be 1..other pairs will surely be 0, then why you have multiplied by 3?

A pair $(v_i . v_{i+1})$ can be $0$ in $3$ ways viz. $(1,0), (0,1), (0,0)$
But why we are considering 0 bcz if we are selecting that the pair (v1,v2) will be 1 then other pairs will be 0.

So possible combinations are:

(v1,v2)     (v3,v4)        (v5,v6)       (v7,v8)

1                    0              0              0

0                     1             0              0

0                      0             1            0

0                      0           0             1
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.
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$
by