How do I prove this statement is a tautology without using truth tables (transformation proof)?

472 Views Asked by At

I think I'm just being dumb. I've manged to work it out via a truth table as I thought that would help with working it out using a transformation proof, but I'm really struggling. Any guidance is appreciated.

Here is my statement: **

(p ∧ ¬ q) ⇒ ¬ (¬ p ∧ q)

** Thank you in advance.

2

There are 2 best solutions below

1
On

Suppose that [(p ∧ ¬ q) ⇒ ¬ (¬ p ∧ q)] is false. Then (p ∧ ¬ q) is true. ¬ (¬ p ∧ q) is false.
Thus, (¬ p ∧ q) is true. So, ¬ p is true. p also holds true. We have a contradiction.

Therefore, [(p ∧ ¬ q) ⇒ ¬ (¬ p ∧ q)] is true.

1
On

Consider the following: \begin{align} (p\land\neg q)\to\neg(\neg p\land q)&\equiv\neg(p\land\neg q)\lor\neg(\neg q\land q)\tag{material implication}\\[1em] &\equiv (\neg p\lor q)\lor(p\lor\neg q)\tag{De Morgan}\\[1em] &\equiv (\neg p\lor p)\lor (q\lor\neg q)\tag{associativity}\\[1em] &\equiv \mathbf{T}\lor\mathbf{T}\tag{negation}\\[1em] &\equiv \mathbf{T}.\tag{domination} \end{align}