Use Algebraic Manipulation Part 2

[shamieh]

Use algebraic manipulation to show that for three input varibles x₁, x₂, and x₃

\(\displaystyle \sum\)m(1,2,3,4,5,6,7) = x₁ + x₂ + x₃

So far all I have is a truth table with 8 rows because I know 2^3 = 8 (starting at 0 of course, just assume the list I prepared on here is starting at 0 and not 1 - ending at 7.)

1. x₁x₂x₃
2. 0 0 0 = 0
3. 0 0 1 = 1 [x! x! x] +
4. 0 1 0 = 1 [x! x x!] +
5. 0 1 1 = 1 [x! x x] +
6. 1 0 0 = 1 [x x! x!] +
7. 1 0 1 = 1 [x x! x] +
8. 1 1 0 = 1 [x x x!] +
9. 1 1 1 = 1 [x x x] +

So how do we go from:
= \(\displaystyle (x1x2x3+x1x2x3+x1x2x3+x1x2x3)+ (x1x2x3+x1x2x3+x1x2x3+x1x2x3) +(x1x2x3+x1x2x3+x1x2x3+x1x2x3)\) <-- WHERE do these extra FOUR terms come out of nowhere??Here is the final solution. Just don't know how they got the four extra terms OR how they got there...
= x1+ x3+ x2

I am lost in the dark...(Emo)

 

[Ackbach]

It's not clear to me what $\sum m(1,2,3,4,5,6,7)$ means. Is that
$$\sum m(1,2,3,4,5,6,7)=\bar{x} \bar{y} \bar{z}+\bar{x} y \bar{z}+\dots?$$
Are you summing all the terms except one? As you can see, I've changed your notation of $x_{1}, x_{2}, x_{3}$ to $x,y,z$, as they're much faster to type.

 

[Evgeny.Makarov]

It's not clear to me what $\sum m(1,2,3,4,5,6,7)$ means. Is that
$$\sum m(1,2,3,4,5,6,7)=\bar{x} \bar{y} \bar{z}+\bar{x} y \bar{z}+\dots?$$

I think it is $\sum_{i=1}^7x^{b_2(i)}y^{b_1(i)}z^{b_0(i)}$ where $b_i(n)$ is the coefficient of $2^i$ in the binary expansion of $n$, i.e., the $i$th binary digit from the right, counting from $i=0$; $x^1=x$ and $x^0=\bar{x}$. Thus, \[\sum m(1,2,3,4,5,6,7)= \bar{x}\bar{y}z+\bar{x}y\bar{z}+\dots+xyz\]

 

[Ackbach]

I think it is $\sum_{i=1}^7x^{b_2(i)}y^{b_1(i)}z^{b_0(i)}$ where $b_i(n)$ is the coefficient of $2^i$ in the binary expansion of $n$, i.e., the $i$th binary digit from the right, counting from $i=0$; $x^1=x$ and $x^0=\bar{x}$. Thus, \[\sum m(1,2,3,4,5,6,7)= \bar{x}\bar{y}z+\bar{x}y\bar{z}+\dots+xyz\]

So it's every term except $\bar{x}\bar{y}\bar{z}$?

 

[shamieh]

The way I wrote it is exactly how I was given the question on my homework, as well as in the book. So I am just as lost as you Ach...Lol

 

[Evgeny.Makarov]

So it's every term except $\bar{x}\bar{y}\bar{z}$?

Yes. Thus, both this DNF and $x+y+z$ are false iff $x=y=z=0$. In fact, I don't know what $m(b_1,\dots,b_n)$ is, but it seems that instead of $\sum m(b_1,\dots,b_n)$ one should write $\sum_{i=1}^nm(i)$ or $m(b_1,\dots,b_n)$.

Converting a DNF into a CNF is simple in principle: apply repeatedly distributivity of conjunction over disjunction, merge disjunctions of the same literal and remove disjunction with complementary literals (e.g., $x$ and $\bar{x}$). Unfortunately, a DNF with 7 conjunctions and 3 literals in each conunctions generates $3^7=2187$ disjunctions, most of which are vacuously true. We need a meta-argument in English about a formal derivation, which is a series of equalities consisting of applications of Boolean laws. It seems that it is easiest to still go through truth tables. If necessary, I'll continue later.

The way I wrote it is exactly how I was given the question on my homework, as well as in the book.

To be honest, I resent such remarks. I don't doubt that both the textbook and the homework statement used m(...), but I am sure that the textbook, as well as your instructor during the lectures, defined it earlier, probably gave several examples of this concept and discussed it in other ways. All it takes is going back and studying the theory before attempting to solve exercises, which in general is impossible to do without knowing the theory. If m(...) is indeed undefined, then you can not only complain to your instructor, but write to the textbook author, who will probably will be very glad to find this omission and will include it into later editions.