Logical Equivalence of two propositions

Question

Are the following two propositions logically equivalent?

$p \rightarrow (\neg q \land r)$

and

$\neg p \lor \neg(r \rightarrow q) $

For this one, I'm pretty sure that they are not equivalent because of DeMorgan laws, but I'm not sure how to prove it.

Also, is the following proposition a tautology?

$((p \rightarrow \neg q) \land q)\rightarrow \neg p)$

I think this is true, based on lecture notes I have and an example in the textbook, but I don't know how the logic works.

Thanks in advance.

You should definitely show more effort in basically all your questions... — Stefan Mesken, Mar 04 '16 at 00:09

score 1 · Answer 1 · answered Mar 04 '16 at 00:27

Implication Equivalence: $\quad a\to b$ is equivalent to $\neg a \vee b$

deMorgan's Laws : $\qquad \neg(a\wedge b)$ is equivalent to $(\neg a\vee \neg b)$

$\qquad\qquad\qquad\qquad\quad \neg(a\vee b)$ is equivalent to $(\neg a\wedge \neg b)$

Use them.

OGC · Accepted Answer · 2016-03-04T01:20:11.023

1

Start from $\neg p \lor \neg(r \rightarrow q)$. Then by applying the metioned logical rules you'll have $$\neg p \lor \neg(r \rightarrow q)$$ $$\equiv \neg p \lor \neg (\neg(r \rightarrow q))$$ $$\equiv \neg p \lor (\neg(\neg r)) \land \neg q$$ $$\equiv \neg p \lor (\neg r \land q)$$ $$\equiv p \rightarrow (\neg q \land r)$$

So yes, the statements are equivalent.

I'm sure you can get the second question for yourself by following these logical rules.

edited Mar 04 '16 at 01:20

answered Mar 04 '16 at 01:13

OGC

2,305

1

Thank you for your response. For the second one, I did $((p \rightarrow \neg q) \land q) \rightarrow \neg p$. Then, I did $\neg p \lor \neg q \land q \rightarrow \neg p$. Next, I took $\neg p \lor \neg q \land q \rightarrow \neg p$, and got $\neg p \rightarrow \neg p$, saying it is, in fact, a tautology. Did I do that right? – CSstudent Mar 04 '16 at 01:44

score 0 · Answer 3 · answered Mar 04 '16 at 01:03

You may always decide equivalence by the simple expedient of looking at the truth tables for the expressions. This does not tell you how to prove equivalence by DeMorgan's laws but if the truth tables show that the expressions are not equivalent you have saved yourself the trouble of trying to show otherwise. And if they are not equivalent the truth tables show which truth values of the variables provide counterexamples.

Logical Equivalence of two propositions

3 Answers3