Could someone please tell me if I am correct and if I am not, tell me where I went wrong?

Using the laws of logic prove that $ [\neg q \land (p \rightarrow q)] \rightarrow \neg p$ is a tautology.

First I used the Implication law $(p \rightarrow q) \equiv (\neg p \vee q)$ to show that $$[\neg q \land (p \rightarrow q)] \equiv [\neg q \land (\neg p \vee q)]$$

Then I "factored" (?) the $\neg$ out and had $$ \neg [q \vee (p \land \neg q)] $$

And since $(p \land \neg q)$ denotes to "$p$ but not $q4" then I assumed I could leave $q$ out, leaving me with $$ ¬[q∨(p)] $$

Which is

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

Which says "not $q$ and not $p$".

Since it is "not $p$", does that mean that

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

and prove that $ [\neg q \land (p \rightarrow q)] \rightarrow \neg p$ is a tautology?

  • 1
    $\begingroup$ You need to explain in detail what "the laws of logic" are. Obviously it must mean some kind of proof system for propositional logic, but there are many ways to construct such a system, and their names are not well standardized. Any textbook author who presents such as system is free to call his choice "the laws of logic" (though it is somewhat confusing to give any single system such a generic name), so in order to let the reader know which particular laws you need to work with here, you need to quote the actual laws. $\endgroup$ Jul 31, 2016 at 13:04
  • $\begingroup$ @HenningMakholm I quoted the Implication Law, please check my question again $\endgroup$ Jul 31, 2016 at 13:06
  • $\begingroup$ x @Samir: If that is the only law you have available, then you can't really prove anything interesting. $\endgroup$ Jul 31, 2016 at 13:07
  • $\begingroup$ The question gave me these to use imgur.com/a/uQFX6 but I only used the first one @HenningMakholm $\endgroup$ Jul 31, 2016 at 13:08

3 Answers 3


As Henning notes, you really do need to specify what laws are at your disposal. With that in mind, here is one approach (assuming you are able to use what I use): \begin{align} [\neg q\land(p\to q)]\to\neg p&\equiv\neg[\neg q\land(\neg p\lor q)]\lor\neg p\tag{material implication}\\[1em]&\equiv [q\lor(p\land\neg q)]\lor\neg p\tag{De Morgan}\\[1em] &= (q\lor\neg p)\lor(p\land\neg q)\tag{associativity}\\[1em] &\equiv \neg(p\land\neg q)\lor(p\land\neg q)\tag{De Morgan}\\[1em] &\equiv \neg M\lor M\tag{let $M\equiv p\land\neg q$}\\[1em] &\equiv \mathbf{T}\tag{negation}. \end{align}

  • $\begingroup$ This is really great, I never knew how to layout a proof but this is extremely helpful, thank you! $\endgroup$ Jul 31, 2016 at 13:59
  • 2
    $\begingroup$ Sure thing! In the future, I recommend laying out your prop calc proofs in this manner, where the margin notes on the side show what you are doing at each step. They force you to understand what you are doing at each step, and they also help the reader along in case anything is fuzzy. :-) $\endgroup$ Jul 31, 2016 at 14:01

$(-q \wedge (p \rightarrow q) ) \rightarrow -p$

$= -(-q\wedge(p\rightarrow q)) \vee -p$

$= (--q\vee-(-p\vee q))\vee -p$

$= (--q \vee (--p \wedge -q)) \vee -p$

$=(q \vee (p \wedge -q)) \vee -p$

$=((q \vee p) \wedge (q \vee -q)) \vee -p$

$=((q\vee p)\wedge 1) \vee (-p)$

$=(q \vee p) \vee (-p) = q \vee (p \vee -p) = q \vee 1 = 1$

Hence it is a tautology. I used the rules $--a = a$ and $a \wedge 1= a$, $a \vee 1 = 1$


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

$\equiv [\neg q \land (\neg p \vee q)] \rightarrow \neg p$

$\equiv [q \vee \neg(\neg p \vee q)] \vee \neg p$

$\equiv q \vee (p \land \neg q) \vee \neg p$

$\equiv [(q \vee p) \land (q \vee \neg q)] \vee \neg p$

$\equiv q \vee 1$

$\equiv 1$


You must log in to answer this question.

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