Logical Equivalences and Boolean Algebra

• February 4th 2013, 02:06 PM
aprilrocks92
Logical Equivalences and Boolean Algebra
Hi,

I have been trying to work around the following question, but can't seem to get it right.

(P ^ ¬Q) V (¬P ^ Q) <=> ¬(P ^ Q) ^ (P VQ)

Any help is highly appreciated.
• February 4th 2013, 02:44 PM
emakarov
Re: Logical Equivalences and Boolean Algebra
Use De Morgan's law on the right-hand side, then apply distributivity to the result, i.e., transform it into a disjunction of conjunctions. Simplify, and you'll get the left-hand side.
• February 4th 2013, 02:55 PM
Plato
Re: Logical Equivalences and Boolean Algebra
Quote:

Originally Posted by aprilrocks92
Hi,

I have been trying to work around the following question, but can't seem to get it right.

(P ^ ¬Q) V (¬P ^ Q) <=> ¬(P ^ Q) ^ (P VQ)

$\begin{gathered} (P \wedge \neg Q) \vee (\neg P \wedge Q) \Leftrightarrow \hfill \\ \left[ {(P \wedge \neg Q) \vee \neg P} \right] \wedge \left[ {(P \wedge \neg Q) \vee Q} \right] \Leftrightarrow \hfill \\ \left[ {\left( {P \vee \neg P} \right) \wedge \left( {\neg Q \vee \neg P} \right)} \right] \wedge \left[ {\left( {P \vee Q} \right) \wedge \left( {\neg Q \vee Q} \right)} \right] \Leftrightarrow \hfill \\ \neg \left( {P \wedge Q} \right) \wedge (P \vee Q) \hfill \\\end{gathered}$
• February 4th 2013, 03:52 PM
aprilrocks92
Re: Logical Equivalences and Boolean Algebra
I have tried doing this:

(P ^ ¬Q) V (¬P ^ Q) <=> ¬(P ^ Q) ^ (P VQ)

Swap sides
¬(P ^ Q) ^ (P VQ) <=> (P ^ ¬Q) V (¬P ^ Q)

Hence, since ¬(P ^Q) <=> ¬P V ¬Q (using De Morgan's Laws)
This gives us:(¬P V ¬Q) ^ (P V Q)

And in turn, (¬P V ¬Q) ^ (P V Q)<=> (P ^ ¬Q) V (¬P ^ Q)

However, I can't seem to figure out where to go from here.
• February 4th 2013, 03:56 PM
emakarov
Re: Logical Equivalences and Boolean Algebra
Quote:

Originally Posted by aprilrocks92
And in turn, (¬P V ¬Q) ^ (P V Q)<=> (P ^ ¬Q) V (¬P ^ Q)

However, I can't seem to figure out where to go from here.

As I said, use distributivity on the left-hand side.