# 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 $\displaystyle \wedge$ for AND and $\displaystyle \vee$ for OR, we have the following properties:

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

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

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

$\displaystyle \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}$

$\displaystyle \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 $\displaystyle (A\vee B)\wedge C\Leftrightarrow (A\wedge C)\vee (B\wedge C)$ $\displaystyle \square$

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

$\displaystyle \emph{Proof: }$

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

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

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

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

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