Determine the truth value of: $$((p \to \neg q)\space\land (\neg r \lor q) \land r) \to \neg p$$
I can determinate it easily with truth tables (it's a tautology), but i want to do it without the table.
Any hints?
Determine the truth value of: $$((p \to \neg q)\space\land (\neg r \lor q) \land r) \to \neg p$$
I can determinate it easily with truth tables (it's a tautology), but i want to do it without the table.
Any hints?
Suppose $((p\Rightarrow \lnot q) \land (\lnot r\lor q)\land r)\Rightarrow\lnot p$ is false. Then $(p\Rightarrow \lnot q) \land (\lnot r\lor q)\land r$ is true and $\lnot p$ is false. Then $p$ must be true. Furthermore, $p\Rightarrow \lnot q$ is true which implies that $\lnot q$ must be true. So $q$ is false. $\lnot r\lor q$ is also true, so $\lnot r$ must be true. But then $r$ is false. This is impossible (since $r$ must be true for $(p\Rightarrow \lnot q) \land (\lnot r\lor q)\land r$ to be true), so $((p\Rightarrow \lnot q) \land (\lnot r\lor q)\land r)\Rightarrow\lnot p$ must actually be true, a tautology.
Using some Boolean algebra with a better readable writing style you get
\begin{eqnarray*} ((p \to \neg q)\space\land ((\neg r \lor q) \land r) \to \neg p & \stackrel{a\to b = a'+b}{=} & ((p'+q')((r'+q)r))' + p' \\ & \stackrel{rr'=0}{=} & ((p'+q')rq)' + p' \\ & \stackrel{qq'=0}{=} & (p'rq)' + p' \\ & \stackrel{(abc)' = a'+b'+c'}{=} & p+r'+q'+ p' \\ & \stackrel{p+p' = 1, 1+a = 1}{=} & 1\\ \end{eqnarray*}
$((p\rightarrow \neg q)\land (\neg r\lor q) \land r)\rightarrow \neg p$
is equivalent to
$(r\land (r\rightarrow q) \land (q\rightarrow \neg p))\rightarrow \neg p$
which makes the tautology rather obvious.
The implication is false iff $p$ is true and the LHS is true. The first conjunct on the LHS can only fail if $q$ is true (since we know $p$ is true), hence $q$ must be false. Now whichever value $r$ takes the conjunction $(\lnot r \lor q ) \land r$ is unsatisfiable (since $q$ is false), thus the LHS is false, too.
I'm not familiar enough with different notations, but I assume '$\rightarrow$' means '$\implies$'. If so, let me rewrite your task so you could see if that is what you need: $((p \implies \neg q)\space\land (\neg r \lor q) \land r) \implies \neg p$ We know that: $\neg(P\implies Q)\iff(P \wedge \neg Q)$
Therefore: $$(p\implies \neg q)\iff \neg(p\wedge q)$$
You have:$$((\neg(p\wedge q)\wedge (q\wedge r))\implies \neg p)\iff\neg(\neg(p\wedge q)\wedge (q\wedge r)\wedge p)\iff\neg(\neg(p\wedge q)\wedge (p \wedge q)\wedge r)$$ $$\iff \neg(0\wedge r)=1$$