1
$\begingroup$

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!

  • 0
    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.2011-12-16

3 Answers 3

1

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

  • 0
    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.2011-12-11
1

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?

1

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