I am working with Logical Equivalence problems as practice and im getting stuck on this question. Can somebody help?
Im trying to show that The LHS is equivalent to the RHS
(¬P ∧ ¬R) ∨ (P ∧ ¬Q ∧ ¬R) is equivalent to ¬R ∧ (Q ⇒ ¬(P ∧ ¬R))
I have tried this so far:
(¬(P ∨ R) ∨ (¬Q ∧ P ∧ ¬R))
¬(¬(P ∨ R) ∨ (¬Q ∧ P ∧ ¬R))
(P ∨ R) ∨ (Q ∧ ¬(P ∨ ¬R))
But im unsure how to carry on from here
On
You want to show that $(\neg P\land\neg R)\lor (P\land\neg Q\land\neg R)$ is equivalent to $\neg R\land(Q\to\neg(P\land\neg R))$. That is, you want to show that $$ \underbrace{\neg R\land(Q\to\neg(P\land\neg R))}_{\text{LHS}} \equiv \underbrace{(\neg P\land\neg R)\lor (P\land\neg Q\land\neg R)}_{\text{RHS}}. $$ To this end, consider the following chain of equivalences: \begin{align} \text{LHS} &\equiv \neg R\land(Q\to\neg(P\land\neg R))\tag{definition}\\[0.5em] &\equiv \neg R\land[\neg Q\lor\neg(P\land\neg R)]\tag{$p\to q\equiv\neg p\lor q$}\\[0.5em] &\equiv \neg R\land[\neg Q\lor(\neg P\lor R)]\tag{DeMorgan}\\[0.5em] &\equiv \neg R\land[\neg Q\lor\neg P\lor R]\tag{associativity}\\[0.5em] &\equiv (\neg R\land\neg Q)\lor(\neg R\land\neg P)\lor(\neg R\land R)\tag{distributivity}\\[0.5em] &\equiv (\neg R\land\neg Q)\lor(\neg R\land\neg P)\tag{$\neg R\land R\equiv F$}\\[0.5em] &\equiv \neg R\land(\neg Q\lor\neg P)\tag{distributivity}\\[0.5em] &\equiv \neg R\land(\neg Q\lor\neg P)\land(\neg P\lor P)\tag{$\neg P\lor P\equiv T$}\\[0.5em] &\equiv \neg R\land[(\neg Q\lor\neg P)\land(\neg P\lor P)]\tag{associativity}\\[0.5em] &\equiv \neg R\land[\neg P\lor(\neg Q\land P)]\tag{distributivity}\\[0.5em] &\equiv (\neg R\land\neg P)\lor[\neg R\land(\neg Q\land P)]\tag{distributivity}\\[0.5em] &\equiv (\neg R\land\neg P)\lor[\neg R\land\neg Q\land P]\tag{associativity}\\[0.5em] &\equiv (\neg P\land\neg R)\lor(P\land\neg Q\land\neg R)\tag{desired expression}\\[0.5em] &\equiv \text{RHS}\tag{definition} \end{align}
On
To my mind, the simplest proof is to simplify both sides, showing that these lead to the same result.
$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}} \newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} } \newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\ref}[1]{\text{(#1)}} \newcommand{\then}{\Rightarrow} \newcommand{\followsfrom}{\Leftarrow} \newcommand{\true}{\text{true}} \newcommand{\false}{\text{false}} $For the left hand side,
$$\calc \tag{L} (\lnot P \land \lnot R) \;\lor\; (P \land \lnot Q \land \lnot R) \op\equiv\hint{extract common conjunct $\;\lnot R\;$, i.e., $\;\land\;$ distributes over $\;\lor\;$} (\lnot P \lor (P \land \lnot Q)) \;\land\; \lnot R \op\equiv\hint{use negation of $\;\lnot P\;$ on right hand side of $\;\lor\;$} (\lnot P \lor (\true \land \lnot Q)) \;\land\; \lnot R \op\equiv\hint{simplify} \tag{*} (\lnot P \lor \lnot Q) \;\land\; \lnot R \endcalc$$
And for the right hand side:
$$\calc \tag{R} \lnot R \;\land\; (Q \then \lnot(P \land \lnot R)) \op\equiv\hint{write $\;X \then Y\;$ as $\;\lnot X \lor Y\;$} \lnot R \;\land\; (\lnot Q \lor \lnot(P \land \lnot R)) \op\equiv\hint{use $\;\lnot R\;$ on right hand side of leftmost $\;\land\;$} \lnot R \;\land\; (\lnot Q \lor \lnot(P \land \true)) \op\equiv\hint{simplify} \tag{**} \lnot R \;\land\; (\lnot Q \lor \lnot P) \endcalc$$
Now $\ref{*}$ and $\ref{**}$ are equivalent, and therefore $\;\ref{L} \equiv \ref{R}\;$.
LHS :
by Distributivity
by Distributivity again; finally, due to : $T ∧ \alpha \equiv \alpha$, we have :
RHS :
by Material Implication and De Morgan; then by Distributivity again and : $F ∨ \alpha \equiv \alpha$, we have :
and finally, by Distributivity :