Why does F + F' = 1?

The point is, it really doesn't matter what the function \$f()\$ actually is. The key fact is that its output is a single binary value.

It is a fundamental fact in Boolean algebra that the complement of a binary value is true whenever the value itself is false. This is known as the law of excluded middle. So ORing a value with its complement is always true, and ANDing a value with its complement is always false.

It's nice that you were able to derive the specific function \$f'()\$, but that's actually irrelevant to the actual question!


All previous answers are correct, and very much in depth. But a simpler way to approach this might be to remember that in boolean algebra, all values must be either 0 or 1.

So... either F is 1, then F' is 0, or the other way around: F is 0 and F' is 1. If you then apply the boolean OR-function: F + F', you will always have one of both terms 1, so the result will always be 1.


My answer is similar to the one of Dave Tweed, meaning that I put it on a more formal level. I obviously answered later, but I decided to nevertheless post it since someone may find this approach interesting.


The relation you are trying to prove is independent from the structure of the function \$f\$ since it is, as a matter of fact, a tautology. To explain what I mean, I propose a demonstration for a general, correctly formed, Boolean expression \$P\$ in an arbitrary number of Boolean variables, say \$n\in\Bbb N\$, \$y_1,\ldots,y_n\$, where \$y_i\in\{0,1\}\$ for all \$i=1,\ldots,n\$.
We have that \$P(y_1,\ldots,y_n)\in\{0,1\}\$ and consider the following two sets of Boolean values for the \$n\$-dimensional Boolean vector \$(y_1,\ldots,y_n)\$ $$ \begin{align} Y&=\{(y_1,\ldots,y_n)\in\{0,1\}^n|P(y_1,\ldots,y_n)=1\}\\ \bar{Y}&= \{(y_1,\ldots,y_n)\in\{0,1\}^n|P(y_1,\ldots,y_n)=0\} \end{align} $$ These set are a partition of the full set of values the input Boolean vector can assume, i.e. \$Y\cup\bar{Y}=\{0,1\}^n\$ and \$Y\cap\bar{Y}=\emptyset\$ (the empty set), thus $$ \begin{align} P(y_1,\ldots,y_n)&= \begin{cases} 0&\text{if }(y_1,\ldots,y_n)\in \bar{Y}\\ 1&\text{if }(y_1,\ldots,y_n)\in Y\\ \end{cases}\\ &\Updownarrow\\ P'(y_1,\ldots,y_n)&= \begin{cases} 1&\text{if }(y_1,\ldots,y_n)\in \bar{Y}\\ 0&\text{if }(y_1,\ldots,y_n)\in Y\\ \end{cases} \end{align} $$ therefore we always have $$ P+P'=1\quad\forall(y_1,\ldots,y_n)\in\{0,1\}^n $$