Note that using Karnaugh maps is a bit of an art, it is particularly
useful when you have only and/or/not. Generally you need to be able to
spot patterns and map these back to the algebraic expression.
Note that while Karnaugh maps are a useful tool for learning, understanding and
writing expressions for a few variables, in digital design one relies on
logic compilers to deal with the actual map of functionality into gates
(and timing, which is important, though functionally irrelevant in this context. However, the gray code aspect in the Karnaugh map arises because of the timing issue).
You can also use a modified Karnaugh map as I will show below.
Here is a Karnaugh map for $S$:
$$\begin{array}{c|c|c||c|c}
C_\text{in} \setminus AB & 00 & 01 & 11 & 10 \\ \hline
0 & 0 & 1 & 0 & 1 \\ \hline
1 & 1 & 0 & 1 & 0 \\ \hline
\end{array}$$
In terms of and/or/not gates this doesn't help since there are none of the usual patterns, so this would require four minterms to represent the 'on'
condition.
If I fix $A=0$ I recognise the xor pattern, and note that I get the
same with $A=1$ (but reversed, because of the Gray coding that people
using in Karnaugh maps).
This suggests $S = \bar{A} (B \oplus C_\text{in}) + A (\overline{B \oplus C_\text{in}})$ which we recognise as $S= A \oplus (B \oplus C_\text{in})$ (order
does't matter here since $\oplus$ is commutative). The circuit for $S$ should
be fairly straightforward to create from this expression.
Another way to recognise this is to draw a Karnaugh map but a 'functional' one: That is, fix $AB$ and place the function of $C_\text{in}$ in the
corresponding box:
$$\begin{array}{c|c|c|}
A \setminus B & 0 & 1 \\ \hline
0 & C_\text{in} & \overline{C_\text{in}} \\ \hline
1 & \overline{C_\text{in}} & C_\text{in} \\ \hline
\end{array}$$
Here the xor pattern is more obvious, and gives, or course, the same result.
For $C_\text{out}$, the same idea follows (only this time it is a more straightforward use of the Karnaugh map). We have the map for $C_\text{out}$:
$$\begin{array}{c|c|c||c|c}
C_\text{in} \setminus AB & 00 & 01 & 11 & 10 \\ \hline
0 & 0 & 0 & 1 & 0 \\ \hline
1 & 0 & 1 & 1 & 1 \\ \hline
\end{array}$$
You can see the bottom row can be represented by $C_\text{in} (A + B)$ and
the column before the last can be represented by $A B$, so we can write
$C_\text{out} = AB + C_\text{in} (A + B)$, which can be implemented in
a straightforward way.
However, since we already have $A \oplus B$ to compute $S$, we might note
that since the $C_\text{in} AB$ entry is covered by $AB$ the remaining two
terms can be written as $C_\text{in} (A \oplus B)$, which gives
$C_\text{out} = AB + C_\text{in} (A \oplus B)$, thus sharing a gate with
$S$.
So, you see that there isn't (in many cases) a single answer, and that
the Karnaugh map may be useful for spotting patterns, but you need to
eyeball the results and look for further sharing/simplifications.
Note that from a digital design perspective there is typically a tradeoff
between sharing (number of gates) and timing (propagation delay, power)
which the Karnaugh map can't help you with.
I think you are justifiably confused. This is a poorly worded question and an obscure answer.
Let's start with the question. The main problem is the vagueness of this phrase:
every row and every column of the resulting table has an even number of ones and zeros in it.
What does "even number of ones and zeros" mean? It can mean any of these things:
- The number of
1s is even, and also the number of 0s is even
- The (number of
1s + the number of 0s) is even
- The number of ones is the same as the number of zeros (they are even)
After I thought about it, I realised that none of these options make much sense with the question posed. They all make the opening statement/claim false (even though the question asks us to prove why it is true). It turns out that the question does not mean any of these options but instead means:
every row and every column of the resulting table has an even number of ones in it.
Or in other words, if we add all the digits of a row or a column (of the extended table) we will get an even number. This is made clearer in the answer, where the parity of rows and columns is mentioned. Parity, in general, means whether an integer is even or odd. If we are talking about the parity of a string of bits (as in our case) then parity refers to the parity of the sum of the bits, or in other words whether the number of 1s in the string is even or odd. In computer science, we have the parity bit which is a bit added to a string of bits in order to always make the parity of the (extended) string be even. So in essense this question asks about adding an extra row and an extra column of parity bits.
Also note that the ending question which mentions
has an odd number of binary digits
is clearly wrong. They mean to say:
has an odd number of binary ones
The crux of the question
Let's look into the heart of the question. What is the problem here? If I give you a string of bits, it's easy to compute the (even) parity bit. You count the 1s and if they are even the parity bit is $0$, otherwise we set it to $1$. Here are the parity bits (in blue) for every row and column of your example table:
$$
\begin{array}{llllll|l}
1& 0& 0& 0& 1& 1& \color{blue}1\\
1& 0& 0& 0& 1& 1& \color{blue}1\\
1& 0& 0& 0& 1& 1& \color{blue}1\\
0& 1& 1& 1& 0& 0& \color{blue}1\\
0& 1& 1& 1& 0& 0& \color{blue}1\\
0& 1& 1& 1& 0& 0& \color{blue}1\\
\hline
\color{blue}{1}&\color{blue}{1}&\color{blue}{1}&\color{blue}{1}&\color{blue}{1}&\color{blue}{1}& \color{red}?
\end{array}
$$
They all happen to be $1$ with the table example you gave. The real problem is: What is the bit denoted as a red questionmark? This bit should set the even parity for both the extra row and the extra column. In other words, it is the parity bit of the column of parity bits, as well as the parity bit of the row of parity bits. Since just a single string of bits (either a row or a column) can fully specify a parity bit, our red questionmark bit is overspecified. In our example above we can set it to $\color{red}0$ and satisfy both the extra row and column (i.e., we can set it with no conflict).
Let's see another table. Just take our previous example table and make it non-square by removing the last row. So now we have:
$$
\begin{array}{llllll|l}
1& 0& 0& 0& 1& 1& \color{blue}1\\
1& 0& 0& 0& 1& 1& \color{blue}1\\
1& 0& 0& 0& 1& 1& \color{blue}1\\
0& 1& 1& 1& 0& 0& \color{blue}1\\
0& 1& 1& 1& 0& 0& \color{blue}1\\
\hline
\color{blue}{1}&\color{blue}{0}&\color{blue}{0}&\color{blue}{0}&\color{blue}{1}&\color{blue}{1}& \color{red}1
\end{array}
$$
Again we find that the overspecified bit satisfies the even parity of both the extra row and the extra column. Is this always the case? The question claims that it is, and we need to explain why.
The answer
The first observation I made was that if we change a single bit in the $6\times 6$ table of our example (or the truncated $5\times 6$ table), a single bit in the parity column will change, and a single bit in the parity row will also change. This means that the overspecified bit will change too, and both parity row and parity column will be in agreement. So any number of bit changes we make for these table sizes will be ok (no conflict for the overspecified bit). But is there some other table size that produces a conflicted overspecified bit? We could perhaps make an inductive proof for every size table starting with a $1\times 1$ table, but there is a simpler method:
I made this general observation about even parity:
The parity of a concatenation of two strings is equal to the parity of concatenating their parity bits.
This might sound a bit confusing, so let me write it with symbols in order to make it more digestable. I will use the following notation: If $S$ is a string of bits, then $P_e(S)$ is the even parity bit of this string. Also if $S_1, S_2$ are bitstrings, then $S_1\oplus S_2$ is the concatenation of these two strings (in other words "glue" them together to make a bigger string). Finally a parity bit can be considererd a bitstring of length one and can be concatenated with other strings. This is what I claim:
$$P_e(S_1\oplus S_2) = P_e(P_e(S_1)\oplus P_e(S_2))$$
To prove this claim simply consider all four combinations of parity for two strings: (odd, odd), (even, odd), (odd, even), (even, even). Note that when we concatenate two odd strings we get one even string, when we concatenate one odd and one even we get odd, and finally two even strings concatenate in one even. Let $O$ denote odd strings and $E$ denote even strings in the formulas below.
$$
\begin{array}{rlrlrl}
P_e(O\oplus O)&= P_e(P_e(O)\oplus P_e(O)) &\iff P_e(E) &= P_e(1\oplus 1)) &\iff 0&=0 \\
P_e(O\oplus E)&= P_e(P_e(O)\oplus P_e(E)) &\iff P_e(O) &= P_e(1\oplus 0)) &\iff 1&=1 \\
P_e(E\oplus O)&= P_e(P_e(E)\oplus P_e(O)) &\iff P_e(O) &= P_e(0\oplus 1)) &\iff 1&=1 \\
P_e(E\oplus E)&= P_e(P_e(E)\oplus P_e(E)) &\iff P_e(E) &= P_e(0\oplus 0)) &\iff 0&=0
\end{array}
$$
And more generally:
$$P_e(S_1\oplus S_2\oplus \dots \oplus S_n) = P_e(P_e(S_1)\oplus P_e(S_2)\oplus \dots \oplus P_e(S_n)) \qquad (\text{lemma}\; 1)$$
The generalisation is actually crucial for what we want to prove. I will not give a full proof here, but instead provide a sketch and leave the fleshed out proof as an exercise. To prove lemma 1 we need to consider having $i$ odd strings and $k$ even strings. Then examine all four cases were $i,k$ are
(odd, odd), (even, odd), (odd, even), (even, even).
After we have established lemma 1, notice again that the overspecified bit is the even parity of the bits in the parity column. In turn, the bits in the parity column are the even parities of the rows of the table. So, using lemma 1, we can say that the overspecified bit is the even parity bit of all the bits in the table. If this is unclear just set strings $S_1,\dots S_n$ in lemma 1 to be the rows of bits of our table. Moreover, we can have the same argument about the overspecified bit being the parity of the bits in the parity row, and again we end up with the overspecified bit being equal to the parity of all bits in the table (this time we set strings $S_1,\dots S_n$ in lemma 1 to be the columns of bits of our table). In other words, it does not matter if we consider all the bits row-first, or column-first, the overspecified bit is essentially calculated as the even parity bit of all bits in the table. In a picture:
$\hspace{2cm}$
Saying the same thing with formulas: Let $R_1, R_2,\dots R_n$ be the rows of the original (non-extended) table of bits. And let $C_1, C_2,\dots C_n$ be the columns. We have:
$$ P_e(P_e(R_1)\oplus P_e(R_2)\oplus \dots \oplus P_e(R_n)) \stackrel{\text{lemma 1}}= P_e(R_1\oplus R_2\oplus \dots \oplus R_n) = P_e(\text{all the bits in the table}) = P_e(C_1\oplus C_2\oplus \dots \oplus C_n) \stackrel{\text{lemma 1}}= P_e(P_e(C_1)\oplus P_e(C_2)\oplus \dots \oplus P_e(C_n)) $$
Their answer
I believe that the answer given on the webpage is playing with properties closer to my first observation. The problem is that it describes the "solution" with very few words ("addition of tables (using cell-by-cell xor) preserves even parity") and ends up being obscure. When I first read it, I had no idea what it meant. Now that I've done my analysis I think I understands what it means.
I believe that the general idea is to break the table into "basic" tables where only one cell has a 1 and then you add the parity row and column for each of them to get an extended "basic" table. The parity row and column of an extended "basic" table have only one 1 bit each, and the overspecified bit is always 1. Then you combine these extended basic tables by doing bitwise XOR operations and it is implied that you get your initial extended table. It is further implied that there will always be a valid oversimplified bit. Even though all this is correct, it needs considerably more work to be proven and explained properly. It seems to me that this solution gets messy when you try to explain it properly. I prefer my approach, as I think it's cleaner, but that's a matter of taste.
An odd parity matrix
The question finally asks us what happens if we choose odd parity. Can we always have a valid overspecified bit? It seems that it is nudging us towards a "no". It's easy to find a counterexample. Just look at the truncated table we used before. Let's consider the odd parities this time:
$$
\begin{array}{llllll|c}
1& 0& 0& 0& 1& 1& \color{blue}0\\
1& 0& 0& 0& 1& 1& \color{blue}0\\
1& 0& 0& 0& 1& 1& \color{blue}0\\
0& 1& 1& 1& 0& 0& \color{blue}0\\
0& 1& 1& 1& 0& 0& \color{blue}0\\
\hline
\color{blue}{0}&\color{blue}{1}&\color{blue}{1}&\color{blue}{1}&\color{blue}{0}&\color{blue}{0}& \color{red}{0/1}
\end{array}
$$
We see that now the overspecified bit is conflicted. We could stop there as far as the question is concerned (we found a counterexample) but thanks to our earlier analysis we know why this is the case: Odd parity does not have the property that even parity has. More specifically:
$$P_o(S_1\oplus S_2\oplus \dots \oplus S_n) \neq P_o(P_o(S_1)\oplus P_o(S_2)\oplus \dots \oplus P_o(S_n))$$
For example, consider three odd-parity strings:
$$P_o(O\oplus O \oplus O) \neq P_o(P_o(O)\oplus P_o(O) \oplus P_o(O)) \iff P_o(O) \neq P_o(0\oplus 0 \oplus 0)) \iff 0 \neq 1$$
I hope you now have a much fuller understanding of the question and the answer. It was certainly rewarding for me to investigate it.
Best Answer
(EDIT: I misunderstood the problem description initially; this has been corrected to fix that misperception.)
I'm not sure what you mean by 'won't my output bit always be 0?'. Your output bit will be precisely 'were an even number of my input bits on or not?' - in other words, 'was this a valid example or not?'; for instance, the truth table for checking parity on two data bits would look like:
$$\begin{array}{ccc|l} a&b&parity&out\\ \hline \\ 0&0&0&1 \\ 1&0&0&0 \\ 0&1&0&0 \\ 1&1&0&1 \\ 0&0&1&0 \\ 1&0&1&1 \\ 0&1&1&1 \\ 1&1&1&0 \end{array} $$
This shows the definition of the output bit as the negation of the XOR of the other bits - and that representation, incidentally, makes the algebraic expression much easier to find (hint: how can you express $a$ XOR $b$ algebraically? Having that 'subroutine' will make the overall job much simpler).