Ist it a tautology w/o truth table

Question

AB + CD = (A+C)(A+D)(B+C)(B+D) is a tautology (checked with wolfram alpha) I have to prove this whith boolean algebra but I don't get it right.

That'S what I have:

AB + CD = A(C+D)B(C+D) AB + CD = AB(C+D)

And here I'm stuck. I don't see any other simplification

Answer 1

You can prove that the statement is a tautology by showing that you can start with the left-hand side (or right-hand side), then use identities and rules of equivalence to modify/simplify the the statement, to show it ultimately is equivalent to the right-hand side (respectively, left-hand side).

I'll start with the left-hand side:

$$AB+CD = (A+CD)(B+CD) \tag{distributive law} $$ $$ = (A+C)(A+D)(B+C)(B+D)\tag{distributive law}$$

---

Hence, $AB + CD = (A+C)(A + D)(B+C)(B+D)\tag{$\dagger$}$

is necessarily true, regardless of the truth values of $A, B, C, D.$ Hence, we have have that $(\dagger)$ is a tautology.

Answer 2

You want the ‘other’ distributive law: $(X+Y)(X+Z)=X+YZ$.

$(A+C)(A+D)=A+CD$, and $(B+C)(B+D)=B+CD$, so the original righthand side reduces to $(A+CD)(B+CD)=AB+CD$.