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.


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! (:


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.