I have the function: \$f(x,y,z,w) = wx + yz\$
I found its complement function to be: \$f '(x,y,z,w) = w'y' + w'z' + x'y' + x'z'\$
I have to show that: \$f + f '=1\$ but I can't see how to do it.
It seems as if there just isn't anything that cancels each other out.
Edit
As suggested, I have now used DeMorgan's theorem and found this:
\$f + f' = wx+yz+(w+y)'+(w+z)'+(x+y)'+(y+z)'\$
But it still seems to me that there is nothing that brings me closer to the realization of \$f+f' = 1\$
Since Carl asked nicely. Starting point: $$ f(x,y,z,w)=wx+yz $$ and $$ f′(x,y,z,w)=w′y′+w′z′+x′y′+x′z′ $$
Take the following steps with \$f'\$: $$ f′(x,y,z,w)=w′(y′+z′)+x′(y′+z′) $$ $$ f′(x,y,z,w)=(w′+x')(y′+z′) $$ DeMorgan: $$ f′(x,y,z,w)=(wx)′(yz)' $$ DeMorgan, again: $$ f′(x,y,z,w)=(wx + yz)' $$ So now the right-hand side of \$f'\$ is just the simple negation of the right-hand side of \$f\$. Which is a little anti-climactic, since now we just rely upon the fact that any expression \$x + x' = 1\$, which is what people have been saying all along about \$f+f'=1\$, but at least it provides a little Boolean-algebra explanation for why that is true.
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
$$
All good answers that provide the necessary justification in one way or the other. Since it is a tautology, it's hard to create a proof that doesn't just result in "it is what it is!". Perhaps this method help tackle it from yet another, broader angle:
Expand both statements to include their redundant cases, and the remove the repeated cases:
\$𝑓=𝑤𝑥+𝑦𝑧\\ \ \ =wx\cdot(y'z'+y'z+yz'+yz)\ +\ yz\cdot(x'w'+x'w+xw'+xw)\\ \ \ =wxy'z'+wxy'z+wxyz'+wxyz\ +\ yzx'w'+yzx'w+yzxw'+yzxw\\ \ \ =wxy'z'+wxy'z+wxyz'+wxyz\ +\ yzx'w'+yzx'w+yzxw' \$
and
\$𝑓′=𝑤′𝑦′+𝑤′𝑧′+𝑥′𝑦′+𝑥′𝑧′\\ \ \ \ = w'y'\cdot(x'z'+x'z+xz'+xz)\ +\ 𝑤′𝑧′\cdot(x'y'+x'y+xy'+xy)\ +\\ \ \ \ \ \ \ \ \ \ x′y′\cdot(w'z'+w'z+wz'+wz)\ +\ x′𝑧′\cdot(w'y'+w'y+wy'+wy)\\ \ \ \ = w'y'x'z'+w'y'x'z+w'y'xz'+w'y'xz\ +\ 𝑤′𝑧′x'y'+𝑤′𝑧′x'y+𝑤′𝑧′xy'+𝑤′𝑧′xy\ +\\ \ \ \ \ \ \ \ \ \ x′y′w'z'+x′y′w'z+x′y′wz'+x′y′wz\ +\ x′𝑧′w'y'+x′𝑧′w'y+x′𝑧′wy'+x′𝑧′wy\\ \ \ \ = w'y'x'z'+w'y'x'z+w'y'xz'+w'y'xz\ +\ 𝑤′𝑧′x'y+𝑤′𝑧′xy\ +\\ \ \ \ \ \ \ \ \ \ x′y′wz'+x′y′wz\ +\ x′𝑧′wy \$
I've kept the terms in consistent order to make the derivation more obvious, but they could be written alphabetically to be clearer. In any case, the point is that \$f\$ ORs seven 4-bit cases, and \$f'\$ ORs nine, distinct 4-bit cases. Together they OR all sixteen 4-bit cases, so reduce to \$1\$.
F + F' = 1 means that you have to show that no matter the state of the 4 inputs, OR'ing the result of those 2 always result in 1,
A few minutes in excel shows it is indeed the case. You can use "NOT()" to invert between 0 and 1 in excel.
F = W * X + Y * Z
F' = W' * Y' + W' * Z' + X' * Y' + X' * Z'
As to why this is the case, If you want F to be false, e.g. setting W and Y low, you just made F' true. If you make X and Z low, you also made F" true, same for swapping there pairs.
By simple definition of \$+\$ (OR) and \$′\$ (NOT)
A | B | A + B
---------------
0 | 0 | 0
1 | 0 | 1
0 | 1 | 1
1 | 1 | 1
A | A′| A + A′
----------------
0 | 1 | 1
1 | 0 | 1
\$∴ ∀f. f + f′ = 1\$
