Use a numbered list of arguments to prove the argument: ((p∨q→r∨s)∧¬s)⊢(r∨¬p)

Question

This problem is from a Discrete Mathematics class, and I am having troubles proving 'r'.

I also am not sure if I proved ¬p correctly. Any advice will be appreciated as I am ripping my hair out trying to think what implications I can use.

Here is what I have so far: ((p∨q→r∨s)∧¬s)⊢(r∨¬p)

1. (p∨q→r∨s)              Premise
2.  ¬s                    Premise
3. (¬(r∨s)→¬(p∨q)         Transposition(1)
4. (¬r∧¬s)→(¬p∧¬q)        De Morgans Thereom(3)
5. (¬s→¬p)                Simplification(4)
6. ¬p                     Modus Ponens(5,2)

I know I am probably making this harder than it really is, but I am knew to all these logical concepts and I am not entirely sure what I can imply.

Answer 1

You can do this:

$1. (p \lor q) \rightarrow (r \lor s) \quad premise$

$2. \neg s \quad premise$

$3. \neg (p \lor q) \lor (r \lor s) \quad Implication \ 1$

$4. (\neg p \land \neg q) \lor (r \lor s) \quad DeMorgan \ 3$

$5. (\neg p \lor r \lor s) \land (\neg q \lor r \lor s) \quad Distribution \ 4$

$6. \neg p \lor r \lor s \quad Simplification \ 5$

$7. \neg p \lor r \quad Disjunctive \ Syllogism \ 2,6$

$8. r \lor \neg p \quad Commutation \ 7$

Answer 2

No, you cannot "simplify" by picking one of two conjuncts on one side of an implication sign, to say it implies the consequent.

Instead: For your third step, assume the negation of the conclusion: $$\lnot (r \lor \lnot p) \equiv \lnot r \land p$$

That can simplify, under this assumption, to

$\lnot r$
$p$

From $p$ we can derive $p \lor q$ (disjunction introduction).

Now, given premise (1), and $p \lor q$, by modus ponens, conclude:

$r\lor s$.

If $r$, that contradicts $\lnot r$ derived from the assumption.

If $s$, that contradicts $\lnot s$ as given in the second premise.

Hence $\lnot (r\lor s)$,

So the assumption was wrong, leading to the conclusion,

$\lnot(\lnot r \land p) \equiv r \lor \lnot p,$ as desired.

Answer 3

4. (¬r∧¬s)→(¬p∧¬q)        De Morgans Thereom(3)
5. (¬s→¬p)                Simplification(4)

Suppose step 4 was taken to mean "with sugar and flour you can make pies and waffles": $(S \land F) \to (P \land W)$.

It would be correct to conclude that "with sugar and flour you can make pies" : $(S \land F) \to P$.

It would be correct to conclude that "with sugar and flour you can make waffles": $(S \land F) \to W$.

It is not enough to conclude "with sugar you can make pancakes" : $S \to P$

The 4 general rules are:

$$\begin{array} {cc} \text{This is} & \text{equivalent to this} \\ \hline X \to (A \land B) & (X \to A) \land (X \to B) \\ \hline X \to (A \lor B) & (X \to A) \lor (X \to B) \\ \hline (A \land B) \to Y & (A \to Y) \lor (B \to Y) \\ \hline (A \lor B) \to Y & (A \to Y) \land (B \to Y) \\ \hline \end{array}$$