2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Suppose that statement is false. What can you say from there? $\endgroup$
    – PacoK
    Mar 31, 2019 at 2:03

5 Answers 5

2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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*}

$\endgroup$
1
$\begingroup$

$((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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .