Problem while solving a logic expression

Question

How can I simplify this expression:

$\lnot[(p \rightarrow r) \land (q \rightarrow r)] \land (\lnot p\lor r)$

I tried to solve it and I got the result 0 or F, but the correct answer is:

$\lnot p\land q \land \lnot r$

I would appreciate if someone could help me. I'm on the 10th grade and can't solve this.

Answer 1

$$\lnot[(p \rightarrow r) \land (q \rightarrow r)] \land (\lnot p\lor r)$$

$$\begin{align} &= [\lnot (p\rightarrow r) \lor \lnot (q\rightarrow r)] \land (\lnot p \lor r)\tag{DeMorgan's}\\ \\ & = [ \lnot (\lnot p \lor r) \lor \lnot(\lnot q \lor r] \land (\lnot p \lor r)\tag{$a\rightarrow b \equiv \lnot a \lor b$}\\ \\ &\equiv [(p\land \lnot r) \lor (q \land \lnot r)] \land (\lnot p \lor r)\tag{DeMorgan's applied twice}\\ \\ &\equiv [(p \lor q)\land \lnot r] \land (\lnot p \lor r)\tag{distributive property}\\ \\ &\equiv (*)\quad(p\lor q) \land (\lnot r) \land (\lnot p \lor r)\tag{associative property}\\ \\ &\equiv (p \vee q) \wedge \neg r \wedge \neg p\tag{Reduction principle}\\ \\ &\equiv q\land \lnot r \land \lnot p\tag{Reduction principle}\\ \\ &\equiv \lnot p \land q \land \lnot r\tag{commutativity of $\land$} \end{align}$$

Now, refer back to $(*)$ in case you're unfamiliar with the Reduction principle. We can instead, reason our way to the conclusion. Now, notice that because we have three propositions with $\land$'s connecting them, in order for the statement to be true, all three propositions must be must evaluate to true.

That determines $\lnot r$. And if $\lnot r$, we determine $\lnot p$ from $\lnot p \lor r$. And since we have $\lnot p$, we must have $q$.

That gives us the conclusion: $\lnot p \land q \land \lnot r$.

Answer 2

$$\lnot[(p \rightarrow r) \land (q \rightarrow r)] \land (\lnot p\lor r) \equiv [\lnot(p \rightarrow r) \lor \neg(q \rightarrow r)] \land (\lnot p\lor r) \equiv [(p \land \neg r) \lor (q \land \neg r)] \land (\lnot p\lor r)$$

One of the disjuncts of the first conjunct must be true, so it must be $\neg r$, and because of that the first disjunct of the second conjunct must be true, so you have $\neg r\land \neg p$, and because of that you deduce the first disjuct of of the first conjunt of your conjunction is false and hence the second one is true, so $q\land \neg p\land \neg r$

Answer 3

So using that handy Reduction rule, here is another derivation:

$\neg [(p \rightarrow r) \wedge (q \rightarrow r)] \wedge (\neg p \vee r) \equiv$ Implication ($p \rightarrow q \equiv \neg p \vee q$)

$\neg [(\neg p \vee r) \wedge (\neg q \vee r)] \wedge (\neg p \vee r) \equiv$ Reduction

$\neg (\neg q \vee r) \wedge (\neg p \vee r) \equiv$ DeMorgan

$q \wedge \neg r \wedge (\neg p \vee r) \equiv$ Reduction

$q \wedge \neg r \wedge \neg p \equiv$ Association

$\neg p \wedge q \wedge \neg r$

Answer 4

Here is a truth table that may be of help.
$\begin{array}{lcl} a&\equiv&p\to r\\ b&\equiv&q\to r\\ c&\equiv&a\land b\\ d&\equiv&\lnot c\\ e&\equiv&\lnot p\\ f&\equiv&e\lor r\\ x&\equiv&d\land f \end{array}$

$\mathtt{pqr·abcdef·x}$
$\mathtt{000·111011·0}$
$\mathtt{001·111011·0}$
$\mathtt{010·100111·1}$
$\mathtt{011·111011·0}$
$\mathtt{100·010100·0}$
$\mathtt{101·111001·0}$
$\mathtt{110·000100·0}$
$\mathtt{111·111001·0}$