# How do you distribute AND and OR?

• Jun 28th 2008, 03:13 PM
Ultros88
How do you distribute AND and OR?
Hi all,
I'm working through a book on set theory and I haven't gotten very far yet. I'm sort of struck by the looseness of the proofs for the associative, distributive, and commutative laws provided by the book and I think this stems from the fact that I'm not sure how to relate / distribute the ANDs and ORs of written logic.

Example:
If x is an element of (A intersect B) union C, then x is an element of A AND x is an element of B, OR x is an element of C.

Why does the proof jump from this kind of formulation to: (A U C) intersect (B U C)?
Why is the OR back distributed over the AND?

Any help clarifying my confusion would be much appreciated.
Thanks,
Ultros
• Jun 28th 2008, 03:58 PM
Reckoner
Quote:

Originally Posted by Ultros88
Hi all,
I'm working through a book on set theory and I haven't gotten very far yet. I'm sort of struck by the looseness of the proofs for the associative, distributive, and commutative laws provided by the book and I think this stems from the fact that I'm not sure how to relate / distribute the ANDs and ORs of written logic.

Example:
If x is an element of (A intersect B) union C, then x is an element of A AND x is an element of B, OR x is an element of C.

Why does the proof jump from this kind of formulation to: (A U C) intersect (B U C)?
Why is the OR back distributed over the AND?

Any help clarifying my confusion would be much appreciated.
Thanks,
Ultros

Using $\wedge$ for AND and $\vee$ for OR, we have the following properties:

$(A\wedge B)\vee C\Leftrightarrow (A\vee C)\wedge(B\vee C)$

$(A\vee B)\wedge C\Leftrightarrow (A\wedge C)\vee (B\wedge C)$

$\emph{Proof: }$ We use a truth table (note that $\text{T}$ means "true" and $\text{F}$ "false"):

$\begin{tabular}{c|c|c|c|c}
A & B & C & A\wedge B & (A\wedge B)\vee C\\\hline
T & T & T & T & T\\
T & T & F & T & T\\
T & F & T & F & T\\
T & F & F & F & F\\
F & T & T & F & T\\
F & T & F & F & F\\
F & F & T & F & T\\
F & F & F & F & F
\end{tabular}$

$\begin{tabular}{c|c|c|c|c|c}
A & B & C & A\vee C & B\vee C & (A\vee C)\wedge (B\vee C)\\\hline
T & T & T & T & T & T\\
T & T & F & T & T & T\\
T & F & T & T & T & T\\
T & F & F & T & F & F\\
F & T & T & T & T & T\\
F & T & F & F & T & F\\
F & F & T & T & T & T\\
F & F & F & F & F & F
\end{tabular}$

Since the final columns of the two truth tables are the same, we can say that the two statements are equivalent.

Using a similar method, you can show that $(A\vee B)\wedge C\Leftrightarrow (A\wedge C)\vee (B\wedge C)$ $\square$

Thus, we can show that $x\in(A\cap B)\cup C\Leftrightarrow x\in(A\cup C)\cap(B\cup C)$

$\emph{Proof: }$

$x\in(A\cap B)\cup C\Leftrightarrow (x\in A\cap B)\vee(x\in C)$

$\Leftrightarrow (x\in A\wedge x\in B)\vee(x\in C)$

$\Leftrightarrow (x\in A\vee x\in C)\wedge(x\in B\vee x\in C)$ (from the result above)

$\Leftrightarrow (x\in A\cup C)\wedge(x\in B\cup C)$

$\Leftrightarrow x\in(A\cup C)\cap(B\cup C)\quad\square$