# inference rules application (introduction / elimination): two examples

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?

-
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$.

-
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?

-

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

Proof:

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$.

-