Using Rules of Logic, Prove the Following

185 Views Asked by At

I am having trouble finding the correct laws to use to prove the following.

$\lnot (p \land q) \land (p \lor \lnot q) \equiv \lnot q$

I understand DeMorgans Law of:

$ \lnot (p \land q) \equiv \lnot p \lor \lnot q$

Am I on the right track? Is DeMorgans Law relevant in this case? I am only just getting into Logical Equivalence etc.

All help is appreciated.

1

There are 1 best solutions below

1
On BEST ANSWER

Yes, De Morgan law is relevant in this case, but alone it is not enough, you should use also other rules. More precisely:

\begin{align} \lnot (p \land q) \land (p ∨ \lnot q) &\equiv (\lnot p \lor \lnot q) \land (p ∨ \lnot q) & &\text{by De Morgan law}\\ &\equiv (\lnot p \land p) \lor \lnot q & &\text{by distributivity of $\lor$ over $\land$} \\ &\equiv \lnot q & & \text{by the identity law for $\lor$} \end{align}

We used the identity law for $\lor$ because $\lnot p \land p$ is a contradiction (i.e. a formula that is false for any truth assignment).

A list of the main logical equivalences in propositional calculus is here.