Question

Prove that $(p\wedge \mathrm{\neg }q)\vee q\vee (\mathrm{\neg }p\wedge q)=p\vee q$ by simplification.

Answer 1

Hint: We are asked to solve this question by simplification. So we can start from the left hand side and apply the laws of logic and reach the right hand side.

Formula used: Laws of logic:
(i) Idempotence: $$p\vee p\iff p,p\wedge p\iff p$$
(ii) Commutative: $$p\vee q\iff q\vee p,p\wedge q\iff q\wedge p$$
(iii) Associative: $(p\vee q)\vee r\iff p\vee (q\vee r),(p\wedge q)\wedge r\iff p\wedge (q\wedge r)$
(iv) Distributive: $p\vee (q\wedge r)\iff (p\vee q)\wedge (p\vee r),p\wedge (q\vee r)\iff (p\wedge q)\vee (p\wedge r)$
(vi) Absorption: $p\wedge 1\iff p,p\wedge 0\iff 0$
(vii) Dominance: $p\vee 1\iff 1,p\vee 0\iff p$
Here,$1$ denotes a statement which is always true (tautology) and $0$ denotes a statement which is always false (contradiction).

Complete step by step solution:
To prove left hand side equals right hand side we can start from left side.
$(p\wedge \mathrm{\neg }q)\vee q\vee (\mathrm{\neg }p\wedge q)$
By the associative property of logics we have,
(iii) Associative: $(p\vee q)\vee r\iff p\vee (q\vee r)$
Using this we can combine the first two terms.
$(p\wedge \mathrm{\neg }q)\vee q\vee (\mathrm{\neg }p\wedge q)\equiv [(p\wedge \mathrm{\neg }q)\vee q]\vee (\mathrm{\neg }p\wedge q)$
By the distributive property of logic we have,
(iv) Distributive: $p\vee (q\wedge r)\iff (p\vee q)\wedge (p\vee r)$
Using this result in the square bracket we have,
$(p\wedge \mathrm{\neg }q)\vee q\vee (\mathrm{\neg }p\wedge q)\equiv [(p\vee q)\wedge (\mathrm{\neg }q\vee q)]\vee (\mathrm{\neg }p\wedge q)$
We know either a statement or its negation is always true.
$\Rightarrow \mathrm{\neg }q\vee q\equiv 1$
Using this we have,
$(p\wedge \mathrm{\neg }q)\vee q\vee (\mathrm{\neg }p\wedge q)\equiv [(p\vee q)\wedge 1]\vee (\mathrm{\neg }p\wedge q)$
Then by absorption laws of logic we have,
(vi) Absorption: $p\wedge 1\iff p$
Using this result,
$(p\wedge \mathrm{\neg }q)\vee q\vee (\mathrm{\neg }p\wedge q)\equiv (p\vee q)\vee (\mathrm{\neg }p\wedge q)$
Now again applying distributive laws we have,
(iv) Distributive: $p\vee (q\wedge r)\iff (p\vee q)\wedge (p\vee r),p\wedge (q\vee r)\iff (p\wedge q)\vee (p\wedge r)$
$(p\wedge \mathrm{\neg }q)\vee q\vee (\mathrm{\neg }p\wedge q)\equiv [(p\vee q)\vee \mathrm{\neg }p]\wedge [(p\vee q)\vee q]$
By commutative property of logic we have,
(ii) Commutative: $$p\vee q\iff q\vee p$$
Using this we get,
$(p\wedge \mathrm{\neg }q)\vee q\vee (\mathrm{\neg }p\wedge q)\equiv [(q\vee p)\vee \mathrm{\neg }p]\wedge [(p\vee q)\vee q]$
Again using associative property,
(iii) Associative: $$(p\vee q)\vee r\iff p\vee (q\vee r)$$
$(p\wedge \mathrm{\neg }q)\vee q\vee (\mathrm{\neg }p\wedge q)\equiv [q\vee (p\vee \mathrm{\neg }p)]\wedge [(p\vee q)\vee q]$
We know either a statement or its negation is always true.
$\Rightarrow p\vee \mathrm{\neg }p\equiv 1$
Using this we have,
$(p\wedge \mathrm{\neg }q)\vee q\vee (\mathrm{\neg }p\wedge q)\equiv (q\vee 1)\wedge [(p\vee q)\vee q]$
And applying associativity in the square bracket we have,
$(p\wedge \mathrm{\neg }q)\vee q\vee (\mathrm{\neg }p\wedge q)\equiv (q\vee 1)\wedge [p\vee (q\vee q)]$
For any statements we have
$q\vee q\equiv q\Rightarrow p\vee (q\vee q)=p\vee q$
Using this we have,
$(p\wedge \mathrm{\neg }q)\vee q\vee (\mathrm{\neg }p\wedge q)\equiv (q\vee 1)\wedge (p\vee q)$
By the laws of dominance we have,
(vii) Dominance: $$p\vee 1\iff 1$$
Using this we get,
$(p\wedge \mathrm{\neg }q)\vee q\vee (\mathrm{\neg }p\wedge q)\equiv 1\wedge (p\vee q)$
Now again by laws of absorption,
(vi) Absorption: $p\wedge 1\iff p$
$(p\wedge \mathrm{\neg }q)\vee q\vee (\mathrm{\neg }p\wedge q)\equiv p\vee q$
So we had reached the right hand side.
$\therefore$ The result is proved.

Note: We can also prove this result with the help of truth tables.

$$p$$	$$q$$	$$\stackrel{~}{}p$$	$$p\to q$$	$$\stackrel{~}{}pVq$$
$$T$$	$$T$$	$$F$$	$$T$$	$$T$$
$$T$$	$$F$$	$$F$$	$$F$$	$$F$$
$$F$$	$$T$$	$$T$$	$$T$$	$$T$$
$$F$$	$$F$$	$$T$$	$$T$$	$$T$$

But in the question it is said to use simplification. So we have to use this one. If not mentioned the method precisely we are free to use any one.