Help on propositional calculus problem

Question

Prove that the statements “$(p \mathbin{\text{and}} \neg q) \mathbin{\text{implies}} q$” and “$(p \mathbin{\text{and}} \neg q) \mathbin{\text{implies}} \neg p$” are logically equivalent. What simpler statement is logically equivalent to both of them?

Answer 1

The following are equivalent:

1. $p\wedge q\Rightarrow \neg q$
2. $\neg \left(p\wedge q\right)\vee\neg q$
3. $\left(\neg p\vee\neg q\right)\vee\neg q$
4. $\neg p\vee\neg q$

Starting at 1) you arrive at 4). If you start with $p\wedge q\Rightarrow \neg p$ then you will end up with the same result.

Answer 2

Maybe this would help. Take the statement $(A\wedge B)\Rightarrow -B$. Then to obtain your first statement let $A=p$ and $B=-q$. Then use that $--q=q$. For your second statement let $A=-q$ and $B=p$. Here you need to use that $A\wedge B=B\wedge A$.

Answer 3

You might assume them equivalent, then only using equivalences try to find a common form. I use Reverse Polish Notation. Thus, instead of (p$\land$q) I write pqK. Instead of (p$\lor$q) I write pqA. Instead of $\lnot$p, I write pN. Instead (p$\rightarrow$q) I write pqC. I'll also write the logical equivalence of $\alpha$ and $\beta$ as

$\alpha$ $\beta$ E

So, let's suppose

1. pqNKqC and pqNKpNC logically equivalent or "pqNKqC pqNKpNC E". Since pqC pqNKN E we can thus obtain 2 from 1.

2. pqNKqNKN pqNKpNNKN E. Since ppN p E we can obtain 3.

3. pqNKqNKN pqNKpKN E. Since pqKN pNqNA E we can obtain 4.

4. pqNKNqNNA pqNKNpNA E. Since ppN p E we can obtain 5.

5. pqNKNqA pqNKNpNA E. Since pqKN pNqNA E we can obtain 6.

6. pNqNNAqA pNqNNApNA E. Since q qNN E we can obtain 7.

7. pNqAqA pNqApN E. Since pqArA pqrAA E we can obtain 8.

8. pNqqAA pNqpNAA E. Since pqA qpA E we can obtain 9.

9. pNqqAA pNpNqAA E. Since pqrAA pqArA E we can obtain 10.

10. pNqqAA pNpNAqA E. Since ppA p E we can obtain 11.

11. pNqA pNqA E.

Consequently, since we only used equivalences, and since equivalences all come as reversible when used, we could have started with 11. and derived 1 using the equivalence indicated on the right in the reverse order. 11. also contains a statement form logically equivalent to both of the original two statement forms.