recategorized by
456 views
1 votes
1 votes
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 __________________
recategorized by

2 Answers

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

Related questions

0 votes
0 votes
0 answers
1