Prove the following $f_{(A \cup B)}(x)=f_A(x)+f_B(x)-f_A(x)\cdot f_B(x)$

Question

There is option to prove the following with truth table? $$f_{(A \cup B)}(x)=f_A(x)+f_B(x)-f_A(x)\cdot f_B(x)$$ I would like to get some hints how to do it in formal way(not truth table)
thanks!

Answer 1

Assuming that $$f_C(x)=\begin{cases}1 & \text{if }x\in C\\0 & \text{if }x\notin C,\end{cases}$$ we can make the following observations (which will help prove the claim):

1. For any sets $A,B$ and any $x,$ we have: $$f_{A\cup B}(x)=\max\bigl\{f_A(x),f_B(x)\bigr\},\\f_{A\cap B}(x)=\min\bigl\{f_A(x),f_B(x)\bigr\}.$$
2. For any sets $A,B$ and any $x,$ we have: $$f_{A\cap B}(x)=f_A(x)\cdot f_B(x).$$

By the first observation, we can readily see that $$f_{A\cup B}(x)+f_{A\cap B}(x)=f_A(x)+f_B(x),$$ whence the second lets us draw the desired conclusion.

Answer 2

To do it formally you have to prove that for every $x$ both sides of the equation have the same value.

Recall that either $x\in A\cup B$ or $x\notin A\cup B$. In the first case the left hand side is clearly $1$, and there are three three possible case for the right hand side (either $x$ in $A$ but not in $B$, or vice versa, or it is in both). Show that all the cases give $1$.

If $x\notin A\cup B$ then $x\notin A$ and $x\notin B$, therefore it's not hard to see that all the values on the right hand side are indeed $0$.

Answer 3

$ \newcommand{\ifelse}[3]{(#1\text{ if }#2\text{ else }#3)} $To prove basic facts about characteristic functions, it seems unavoidable (and perhaps clearest) to introduce a case split.

Here is one way to do this, using an $\;\ifelse{\dots}{\dots}{\dots}\;$ notation, and the definition $$ (0) \;\;\; f_V(x) = \ifelse{1}{x \in V}{0} $$

For the left hand side,

\begin{align} & f_{A \cup B}(x) \\ = & \qquad \text{"definition $(0)$"} \\ & \ifelse{1}{x \in A \cup B}{0} \\ = & \qquad \text{"definition of $\;\cup\;$"} \\ & \ifelse{1}{x \in A \lor x \in B}{0} \\ = & \qquad \text{"case split on $\;x \in A\;$ -- we could also have chosen $\;x \in B\;$"} \\ & \ifelse{\ifelse{1}{\text{true} \lor x \in B}{0}}{x \in A}{\ifelse{1}{\text{false} \lor x \in B}{0}} \\ = & \qquad \text{"simplify; definition $(0)$"} \\ & \ifelse{1}{x \in A}{f_B(x)} \\ \end{align}

And for the right hand side,

\begin{align} & f_A(x) + f_B(x) - f_A(x) \cdot f_B(x) \\ = & \qquad \text{"case split on $\;x \in A\;$, using $(0)$"} \\ & \ifelse{1 + f_B(x) - 1 \cdot f_B(x)}{x \in A}{0 + f_B(x) - 0 \cdot f_B(x)} \\ = & \qquad \text{"simplify"} \\ & \ifelse{1}{x \in A}{f_B(x)} \\ \end{align}

This makes both sides equal, proving the original statement.