TAOCP 1.2.3 Exercise 21
By Eq.
Section 1.2.3: Sums and Products
Exercise 21. ▶ [M25] Derive rule (d) from (8) and (17).
Verified: yes
Solve time: 34s
Solution
By Eq. (17),
$$ \sum_{R(j)} a_j = \sum_j a_j [R(j)], \qquad \sum_{S(j)} a_j = \sum_j a_j [S(j)]. $$
Therefore
$$ \sum_{R(j)} a_j + \sum_{S(j)} a_j = \sum_j a_j [R(j)] + \sum_j a_j [S(j)]. $$
Applying Eq. (8),
$$ \sum_{R(j)} a_j + \sum_{S(j)} a_j = \sum_j a_j \bigl([R(j)] + [S(j)]\bigr). $$
For any statements $R(j)$ and $S(j)$,
$$ [R(j)] + [S(j)] = [R(j)\text{ or }S(j)] + [R(j)\text{ and }S(j)]. $$
This identity is verified by the four possible truth values of $R(j)$ and $S(j)$:
$$ \begin{array}{c|c|c|c} R(j) & S(j) & [R(j)] + [S(j)] & [R(j)\text{ or }S(j)] + [R(j)\text{ and }S(j)] \ \hline 0 & 0 & 0 & 0 \ 0 & 1 & 1 & 1 \ 1 & 0 & 1 & 1 \ 1 & 1 & 2 & 2 \end{array} $$
Hence
$$ \sum_{R(j)} a_j + \sum_{S(j)} a_j = \sum_j a_j [R(j)\text{ or }S(j)] + \sum_j a_j [R(j)\text{ and }S(j)]. $$
Applying Eq. (17) in reverse,
$$ \sum_{R(j)} a_j + \sum_{S(j)} a_j = \sum_{R(j)\text{ or }S(j)} a_j + \sum_{R(j)\text{ and }S(j)} a_j. $$
This is rule (d), Eq. (11). This completes the proof.
∎