6
$\begingroup$

Prove that $[(p \to\neg q) \wedge q] \to \neg p$ is a tautology Laws of logic

I tried prove it by using truth table but it didn't produce a tautology.

This is my work so far: $$ [(p \to \neg q) \wedge q] \to \neg p\\ [(\lnot p \vee \lnot q) \wedge q] → \lnot p\\ \lnot [(\lnot p \vee \lnot q) \wedge q] \vee \lnot p\\ [\lnot (\lnot p \vee \lnot q) \vee \lnot q] \vee \lnot p\\ [(p ∧ q) \vee \lnot q ] \vee \lnot p\\ $$

Can anyone help me?

  • 1
    Try using the contrapositive of $p\to\neg q$.2012-10-23
  • 3
    Hold on... Did you just say "truth tables imply it's not a tautology"? And now you want to prove it is a tautology?2012-10-23
  • 0
    It all depends on exactly which axiomatization of predicate logic you're working within. The best answer also depends on what auxiliary rules of inference you already have available. Probably the easiest is to assume both p and [(p → ¬q) ∧ q], and derive a contradiction.2012-10-23
  • 2
    I undid an edit by Flower Ahmed that changed the $\lnot p$ to $\lnot q$. On one hand the answers were already written for the original question, and on the other hand the new formula is no longer a tautology, so it would be impossible to prove it is a tautology.2012-10-23
  • 0
    Exapand your fourth line using the distributive laws.2012-10-23
  • 1
    I think using truth tables would be easier!2012-10-23
  • 0
    @CarlMummert No, the OP question is indeed a tautology!2014-09-27
  • 0
    @FlowerAhmed There is a mistake in the last step.2014-09-27

8 Answers 8