Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Got stuck while trying out how to apply inference rules (introduction and elimination) for the following examples:

  1. From $\lnot(P\land Q)$ and $P$ infer $\lnot Q$

  2. From $P\lor Q$ and $Q$ infer $\lnot P$

Could you please demonstrate how this can be done?

Thanks a lot in advance!

share|cite|improve this question
This is a common homework problem, if this is indeed originated from a homework assignment, it is common to use the [homework] to signal the community on that. Don't worry, it's will still get answered even if it is homework. – Asaf Karagila Dec 12 '11 at 20:28
I think I can guess your rules for introduction and elimination of "^", "V", "->" and "<->". But, what are you introduction and elimination rules for negation, "¬", exactly? There do exist different negation rules in different natural deduction systems. – Doug Spoonwood Dec 14 '11 at 13:18
the OP keeps asking these kinds of (very basic) questions, as has been observed in another comment elsewhere. The problem is that he refuses to provide further information on his deduction method or book reference. – magma Dec 16 '11 at 13:36

For the first question, recall DeMorgan's laws. Thus, the statement becomes $¬P\vee¬Q$. Then, taking $P$ as true, you have $¬P$ false. So, then $¬Q$ must be true for the statement to be true.

For the second I don't believe you can infer $¬P$. $P\vee Q$ reads as 'At least one of P or Q is true'. If Q is true by assumption, $P\vee Q$ is always true regardless of the truth value of $P$.

share|cite|improve this answer
I don't think $\wedge$ and $\vee$ are meant to be interpreted as the standard "and" and "or". I think they are suppose to be arbitrary binary logical connective that happen to satisfy rule 1 and 2. – William Dec 11 '11 at 22:09

The second isn't valid, and almost surely not proveable in your system.

For the first, you want the negation of Q. So, you might want to assume Q and see if you can then infer a contradiciton. Does that help enough?

share|cite|improve this answer

For 1. Claim: Let $\Gamma =\{\neg(P \wedge Q), P\}$. Then, $\Gamma \vdash \neg Q$.


By DeMorgann's Law, $\neg(P \wedge Q) \equiv \neg P \vee \neg Q$. Then, by disjunctive syllogism, since we know $P$, we may conclude $\neg Q$.

For 2. Claim: Let $\Gamma = \{P \vee Q, Q\}$. Then, $\Gamma \vdash \neg P$.

Disproof: Let $Q$ be true and $P$ be true, then $P \vee Q$ holds, $Q$ holds, and $P$ holds. Therefore, $\Gamma \nvdash \neg P$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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