Problem solving Logical Equivalence Question 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
 A: LHS :

$$(¬P ∧ ¬R) ∨ (P ∧ ¬Q ∧ ¬R) \equiv [¬P ∨ (P ∧ ¬Q)] ∧ ¬R \equiv$$ 

by Distributivity

$$\equiv [(¬P ∨ P) ∧ (¬P ∨ ¬Q)] ∧ ¬R \equiv$$

by Distributivity again; finally, due to : $T ∧ \alpha \equiv \alpha$, we have :


$$\equiv (¬P ∨ ¬Q) ∧ ¬R.$$



RHS :

$$[¬R ∧ (Q \to ¬(P ∧ ¬R))] \equiv [¬R ∧ (¬Q ∨ ¬P ∨ R)] \equiv$$

by Material Implication and De Morgan; then by Distributivity again and : $F ∨ \alpha \equiv \alpha$, we have :

$$\equiv (¬R ∧ ¬Q) ∨ (¬R ∧ ¬P) ∨ (¬R ∧ R) \equiv (¬R ∧ ¬Q) ∨ (¬R ∧ ¬P) \equiv$$

and finally, by Distributivity :

$$\equiv ¬R ∧ (¬Q ∨ ¬P).$$

A: 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}
A: 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}\;$.
