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$ – Henning Makholm Jul 31 '16 at 13:04
  • $\begingroup$ @HenningMakholm I quoted the Implication Law, please check my question again $\endgroup$ – Samir Chahine Jul 31 '16 at 13:06
  • $\begingroup$ x @Samir: If that is the only law you have available, then you can't really prove anything interesting. $\endgroup$ – Henning Makholm Jul 31 '16 at 13:07
  • $\begingroup$ The question gave me these to use imgur.com/a/uQFX6 but I only used the first one @HenningMakholm $\endgroup$ – Samir Chahine Jul 31 '16 at 13:08

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$ – Samir Chahine Jul 31 '16 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$ – Daniel W. Farlow Jul 31 '16 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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.