There are no premises present. I need to prove ($\neg p \vee \neg q) \wedge (r \vee q) \wedge (r \implies s) \implies \neg(p \wedge \neg s)$.

The catch is I'm only allowed to use primitive inference rules (so only introduction and elimination rules). So far this is what I've done

  1. Assume $(\neg p \vee \neg q) \wedge (r \vee q) \wedge (r \implies s)$, derive $\neg(p \wedge \neg s)$

    1.1. $(\neg p \vee \neg q) \wedge (r \vee q) \wedge (r \implies s)$ by assumption

    1.2. $(\neg p \vee \neg q)$ by $\wedge$- elimination in 1.1

    1.3. $(r \vee q)$ by $\wedge$- elimination in 1.1

    1.4. $(r \implies s)$ by $\wedge$- elimination in 1.1

    1.5. Assume $p \wedge \neg s$, derive contradiction

    1.5.1. $p \wedge \neg s$ by assumption

    1.5.2. $p$ by $\wedge$- elimination in 1.5.1

    1.5.3. $\neg s$ by $\wedge$- elimination in 1.5.1

    1.5.4. Assume $r$, derive contradiction $r$ by assumption $s$ by $\implies$- elimination using, 1.4 contradiction due to, 1.5.3

    1.5.5 $\neg r$ by $\neg$-introduction in 1.5.4

and now I'm not sure how to proceed. But looking at steps 1.2, 1.3 and 1.5.5 I can sense that this will give me a $\neg p$ which will help in getting my contradiction which I require in 1.5 because I already have a $p$ in 1.5.2. The problem is I don't know how this should be represented formally. I know that I have to do some sort of $\vee$ elimination.


2 Answers 2


What you have so far is right. I'll present it in what I feel is a more readable format:

If $( \neg p \lor \neg q ) \land ( r \lor q ) \land ( r \to s )$:

  $\neg p \lor \neg q$.

  $r \lor q$.

  $r \to s$.

  If $p \land \neg s$:


    $\neg s$.

    If $r$:



    If $q$:


      $\neg p$.


    Contradiction.   [$\lor$-elim]

The method is to use $\lor$-elimination to make use of the two disjunctive sentences you have. I've shown you the final steps, and you just need to fill in the blank.


$(\neg p \lor \neg q) \land (r \vee q) \land (r \implies s) \implies \neg(p \land \neg s)\\\equiv\neg\{[(\neg p\lor \neg q)\land(r\lor q)\land\neg(r\land\neg s)]\land(p\land \neg s)\}\equiv\neg[(\neg p\lor\neg q)\land(r\lor q)\land\neg(r\land\neg s)\land p\land\neg s]\\\equiv\neg[(\neg p\lor\neg q)\land p\land (r\lor q)\land(\neg r\lor s)\land \neg s]\\\equiv\neg[(p\land\neg q)\land(r\lor q)\land(\neg r\land \neg s)]\\\equiv\neg[p\land\neg q\land\neg r\land\neg s\land(r\lor q)]\equiv\neg 0\equiv 1$

Hope it helps! (:


You must log in to answer this question.

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