edited by
940 views
3 votes
3 votes

Suppose $X_{1a}, X_{1b},X_{2a},X_{2b},\dots , X_{5a},X_{5b}$ are ten Boolean variables each of which can take the value TRUE or FLASE. Recall the Boolean XOR $X\oplus Y:=(X\wedge \neg Y)\vee (\neg X \wedge Y)$. Define the Boolean logic formulas

$$F:= (X_{1a}\vee X_{1b}) \wedge (X_{2a}\vee X_{2b})\wedge (X_{3a}\vee X_{3b})\wedge (X_{4a}\vee X_{4b})\wedge (X_{5a}\vee X_{5b}),$$

$$G_{i}:=(X_{i,a}\oplus X_{i+1,a})\vee (X_{i,b}\oplus X_{i+1,b}),\:\:\:1 \leq i \leq 4$$

$$G_{5}:=(X_{5a}\oplus X_{1a})\vee (X_{5b}\oplus X_{1b}),$$

$$H:=F\wedge G_1 \wedge G_2 \wedge G_3 \wedge G_4 \wedge G_5.$$

A truth assignment to the ten Boolean variables $X_{ia}, X_{ib},\:\:1\leq i \leq 5$ is said to be a satisfying assignment if $H$ takes the value TRUE for example,

$$(X_{1a},X_{1b},X_{2a},X_{2b},\dots, X_{5a}, X_{5b}) = (F,T,T,F,F,T,T,T,T,F)$$

 is a satisfying assignment,

$$(X_{1a},X_{1b},X_{2a},X_{2b},\dots, X_{5a}, X_{5b}) = (F,T,T,T,F,T,T,T,T,F)$$

 is  another satisfying assignment, while

$$(X_{1a},X_{1b},X_{2a},X_{2b},\dots, X_{5a}, X_{5b}) = (F,T,T,F,F,T,T,F,T,F)$$

 is  not a satisfying assignment.

How many satisfying assignments does $H$ have?

  1. $20$
  2. $30$
  3. $32$
  4. $160$
  5. $1024$
edited by

1 Answer

Best answer
5 votes
5 votes

Here, we have,

$G_1 = (X_{1a} \oplus X_{2a}) \vee (X_{1b} \oplus X_{2b}) $

$G_2 = (X_{2a} \oplus X_{3a}) \vee (X_{2b} \oplus X_{3b}) $

$G_3 = (X_{3a} \oplus X_{4a}) \vee (X_{3b} \oplus X_{4b}) $

$G_4 = (X_{4a} \oplus X_{5a}) \vee (X_{4b} \oplus X_{5b}) $

$G_5 = (X_{5a} \oplus X_{1a}) \vee (X_{5b} \oplus X_{1b}) $

$F=(X_{1a} \vee X_{1b} ) \wedge (X_{2a} \vee X_{2b} ) \wedge (X_{3a} \vee X_{3b} ) \wedge (X_{4a} \vee X_{4b} ) \wedge (X_{5a} \vee X_{5b} )$

$H= F \wedge G_1 \wedge G_2 \wedge G_3 \wedge G_4 \wedge G_5 $

Now, we have to assign boolean variables $X_{1a}$ to $X_{5a}$ and $X_{1b}$ to $X_{5b}$ as $1$ or $0$ in such a way that $H$ becomes $1$

To make $H$ as $1$, $F$ and all $G_1$ to $G_5$ should be $1.$  Now, either we start with $G_1$ or $G_2 $ or any $G_i, 1\leq i \leq 5 $, answer will remain same.

So, first to make both $G_1$ and $F$ as $1$ , possibilities are :

$(i)$ $X_{1a} = 1$ and $X_{1b} = 1$

$(ii)$ $X_{1a} = 1$ and $X_{1b} = 0$

$(iii)$ $X_{1a} = 0$ and $X_{1b} = 1$

So, case $(i)$ $X_{1a} = 1$ and $X_{1b} = 1$

Now, to make $F=1$ and $G_1 = 1$ $\Rightarrow$  $(1 \oplus X_{2a}) \vee (1 \oplus X_{2b}) =1  $ means both $(1 \oplus X_{2a})$ and $(1 \oplus X_{2b}) $ should not be $0$. As we know, that $x \oplus x = 0.$. So, $X_{2a} \neq 1$ and $X_{2b} \neq 1$.

So, when $X_{1a} = 1$ and $X_{1b} = 1$,

$X_{2a}=1, X_{2b}=0$

$X_{2a}=0, X_{2b}=1$.

So, $(1,1)$ maps to either $(1,0)$ or $(0,1)$ i.e.

$(1,1) \mapsto (1,0)$ (or) $(1,1) \mapsto (0,1)$

Similarly,

To make $F=1$ and $G_2 = 1$ $\Rightarrow$  $(1 \oplus X_{3a}) \vee (0 \oplus X_{3b}) =1  $  (or) $(0 \oplus X_{3a}) \vee (1 \oplus X_{3b}) =1  $ means both $(1 \oplus X_{3a})$ and $(0 \oplus X_{3b}) $ should not be $0$ and . As we know, that $x \oplus x = 0.$. So, $X_{3a} \neq 1$ and $X_{3b} \neq 0$ (or) $X_{3a} \neq 0$ and $X_{3b} \neq 1$.

So, when $X_{2a}=1, X_{2b}=0$ then $X_{3a}=0,$ $X_{3b}=1$ (or) $X_{3a}=1,$ $X_{3b}=1$ and

when $X_{2a}=0, X_{2b}=1$ then $X_{3a}=1,$ $X_{3b}=0$ (or) $X_{3a}=1,$ $X_{3b}=1$

So, $(1,0) \mapsto (0,1)$ (or) $(1,0) \mapsto (1,1)$ and 

      $(0,1) \mapsto (1,0)$ (or) $(0,1) \mapsto (1,1).$

Like this we can find the values of other boolean variables very easily if we know the following mappings :

                               

Using these mappings, we can get the possible values of other boolean variables.

So, here, $(X_{ia},Y_{ib})$  represents the value of boolean variables $X_{ia}$ and $X_{ib}$ at level $i$ where $1 \leq i \leq 5$

                      

Now, $G_5$ will be $0$ when $(X_{1a},X_{1b}) \oplus (X_{5a},X_{5b}) = 0$ which says those leaf nodes which have value same as $(1,1)$, $G_5$ will be zero. So, we have to exclude $(1,1)$ from leaf nodes. Out of $16$ leaf nodes, $6$ has values as $(1,1)$. So, remaining values will be $16-6 = 10.$

So, when $X_{1a} = 1$ and $X_{1b} = 1$,  $H=1$ for $10$ assignments.

Now for case $(ii) X_{1a} = 1$ and $X_{1b} = 0$ 

Tree structure will be like :

Here, total $6$ $(1,0)$(starting node) in leaf nodes. So, total $16-6 =10$ assignments for which $H=1$

Now, for case $(iii) X_{1a} = 0$ and $X_{1b} = 1$ 

Tree structure will be like :

 

Here, also $6$ $(0,1)$(starting node) in leaf nodes. So, total $16-6 =10$ assignments for which $H=1$

So, Total assignments in all 3 cases = $10+10+10 = 30.$

Now, since, structure is symmetric, so, you can start with either $(X_{2a},X_{2b})$ or $(X_{3a},X_{3b})$ or take any case, answer will remain the same. 

selected by
Answer:

Related questions

6 votes
6 votes
1 answer
2
3 votes
3 votes
2 answers
3
admin asked Feb 10, 2020
773 views
The sequence $s_{0},s_{1},\dots , s_{9}$ is defined as follows:$s_{0} = s_{1} + 1$$2s_{i} = s_{i-1} + s_{i+1} + 2 \text{ for } 1 \leq i \leq 8$$2s_{9} = s_{8} + 2$What is...