# Logical Reasoning $(\neg p \vee \neg q) \wedge (r \vee q) \wedge (r \implies s) \implies \neg(p \wedge \neg s)$

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

1.5.4.1 $r$ by assumption

1.5.4.2 $s$ by $\implies$- elimination using 1.5.4.1, 1.4

1.5.4.3 contradiction due to 1.5.4.2, 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$:

$p$.

$\neg s$.

If $r$:

$s$.

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