Prove that $(\neg p \wedge \neg q) \vee (p \wedge q) \equiv (\neg p \vee q) \wedge (\neg q \vee p)$

Question

Prove that $(\neg p \wedge \neg q) \vee (p \wedge q) \equiv (\neg p \vee q) \wedge (\neg q \vee p)$.

I need to prove it by using equivalent sentences.

Answer 1

Using a table of truth you can prove that:

(1) w $\vee$ (p $\wedge$ q) ≡ (w $\vee$ p) $\wedge$ (w $\vee$ q)

Hint: use w = (~p ∧ ~q).

Here follows the steps

(2) (~p ∧ ~q) ∨ (p ∧ q) ≡ ((~p ∧ ~q) $\vee$ p) $\wedge$ ((~p ∧ ~q) $\vee$ q)

Using (1) we can say that

(~p ∧ ~q) $\vee$ p ≡ (~p $\vee$ p) $\wedge$ (~q $\vee$ p)

as (~p $\vee$ p) its a tautology,

(3)(~p ∧ ~q) $\vee$ p ≡ (~q $\vee$ p)

using (3) and (2):

(4) (~p ∧ ~q) ∨ (p ∧ q) ≡ (~q $\vee$ p) $\wedge$ ((~p ∧ ~q) $\vee$ q)

Using (1) we can say that

(~p ∧ ~q) $\vee$ q ≡ (~p $\vee$ q) $\wedge$ (~q $\vee$ q)

as (~q $\vee$ q) its a tautology,

(5)(~p ∧ ~q) $\vee$ q ≡ (~p $\vee$ q)

Using (4) and (5)

(6)(~p ∧ ~q) ∨ (p ∧ q) ≡ (~q $\vee$ p) $\wedge$ (~p $\vee$ q)

And there you go

Answer 2

Assuming you have this in your arsenal, try using a "first-inside outside-last" distribution for the propositions. Then simplify.

That is, think of it like addition and multiplication:

$(a+b) \cdot (c+d) = (a \cdot c) + (a \cdot d) + (b \cdot c) + (b \cdot d)$.

If that isn't allowed, try using truth tables as a simple way of approaching it.

Answer 3

Propositional Calculus
Use de Morgan's rules. Start like this: $$(\neg p \wedge \neg q) \vee (p \wedge q) \equiv (\neg p \vee (p \wedge q)) \wedge (\neg q \vee (p \wedge q))$$ Now apply them again inside the parentheses and remove tautologies. Then you're done.

---

Truth table
You can make a truth table with two variables and two outcomes. It will have four rows, so it's not too much work.
The start will look like this:

$$\begin{array}{cc|c|c} p & q & (\neg p \wedge \neg q) \vee (p \wedge q) & (\neg p \vee q) \wedge (\neg q \vee p) \\ \hline T & T & &\\ T & F & &\\ F & T & &\\ F & F & & \end{array}$$ The statement then says that the missing two columns are identical.

Answer 4

$(\neg p\wedge\neg q)\vee(p\wedge q)=\neg((p\vee q)\wedge\neg(p\wedge q))=\neg((\neg p\wedge q)\vee(p\wedge\neg q))=(p\vee\neg q)\wedge(\neg p\vee q)$