This is my first post(:
I'm trying to understand how to prove the distributive property using the indicator function. I have made the truth tables and understand how this is proved using set notation as in this question: Set Distributive Property Proof
But I cant seem to understand how to write this using indicator function notation.
$\mathbb{A}$ is a proposition about elements $x \in X$ and we put the corresponding set $A = \{x \ \in X: \mathbb{A}(x)\}$.
For each $x \in X$ and $A \subset X$ define the indicator function of the set A by
\[1_A (x) := \begin{cases}
1 & if \; x \in A \\
0 & if \; x \notin A
\end{cases}
\]
Further, the "and" and "or" of this are given by:
$ (1_A \wedge 1_B)(x) = 1_A(x) \cdot 1_B(x) = 1_A \cdot 1_B $
$ (1_A \vee 1_B)(x) = 1_A(x) + 1_B(x) – 1_A(x) \cdot 1_B(x) = 1_A + 1_B – 1_A \cdot 1_B$
Prove:
$ (\mathbb{A} \vee (\mathbb{B} \wedge \mathbb{C})) \iff ((\mathbb{A} \vee \mathbb{B}) \wedge (\mathbb{A} \vee \mathbb{C})) $
Writing the left side in indicator function notation I think it should be:
$ 1_A \vee (1_B \wedge 1_C)(x) = 1_A \vee ( 1_B \cdot 1_C ) = 1_A + (1_B \cdot 1_C) – 1_A \cdot (1_B \cdot 1_C) $
However, the textbook says it should be: $ 1_A \cdot (1_B + 1_C – 1_B \cdot 1_C) $
Which looks like the reverse order of what I think, so I'm stuck here.
Thank you!
Best Answer
It’s generally easiest to start with the more complicated expression, which in this case is the indicator function corresponding to the righthand side,
$$(1_A+1_B-1_A\cdot 1_B)\cdot(1_A+1_C-1_A\cdot 1_C)\;.$$
If you multiply this out, you get
$$\begin{align*} 1_A\cdot(1_A&+1_C-1_A\cdot 1_C)+1_B\cdot(1_A+1_C-1_A\cdot 1_C)-1_A\cdot 1_B\cdot(1_A+1_C-1_A\cdot 1_C)\\ &=(1_A+\color{brown}{1_A\cdot 1_C}-\color{brown}{1_A\cdot 1_C})+(\color{blue}{1_A\cdot 1_B}+1_B\cdot 1_C-1_A\cdot 1_B\cdot 1_C)\\ &\qquad-(\color{blue}{1_A\cdot 1_B}+\color{green}{1_A\cdot 1_B\cdot 1_C}-\color{green}{1_A\cdot 1_B\cdot 1_C})\\ &=1_A+1_B\cdot 1_C-1_A\cdot 1_B\cdot 1_C\;, \end{align*}$$
as desired.