Using only the rules of inference and the logical equivalences, show that the following argument is valid. You may assume that all the premises given are true.


𝑢 ∧ 𝑡

𝑟 → 𝑞

s ∨ (𝑝 → 𝑟)

¬𝑠 ∧ 𝑡

¬𝑞 ∧ 𝑢

Show: ¬p

So I've attempted the solution but I'm stuck and not sure what steps I should take next. Any input or help would be appreciated.

My solution so far:

1) 𝑢 ∧ 𝑡

2) 𝑟 → 𝑞

3) s ∨ (𝑝 → 𝑟)

4) ¬𝑠 ∧ 𝑡

5) ¬𝑞 ∧ 𝑢

6) ¬𝑠 by simplification (4)

7) (𝑝 → 𝑟) by disjunctive syllogism (3, 6)

8) (𝑝 → q) by hypothetical syllogism (2, 7)

9) ¬𝑞 by simplification (5)

10) ¬p by modus tollens (8, 9)

I'm trying to get rid of 1) and 6) left but I'm out of formulas I can think of to use. I thought maybe I could use addition somehow, but I'm not quite sure how that formula works. Like would that allow me to add any variable from the alphabet that I want or can I only use the variables that have already been defined?

Any thoughts or ideas on what steps I could take next would be appreciated.

  • $\begingroup$ Not clear... It works: you have derived $\lnot p$. $\endgroup$ – Mauro ALLEGRANZA May 28 at 7:13
  • $\begingroup$ don't I have to get rid of the other premises? I thought I could only have 1 statement left. $\endgroup$ – GilmoreGirling May 28 at 7:15
  • 1
    $\begingroup$ Not necessarily; it means only that premise 1) is not needed for the argument. $\endgroup$ – Mauro ALLEGRANZA May 28 at 7:31
  • $\begingroup$ 1 is indeed redundant. It follows from 4 and 5. $\endgroup$ – PJK May 28 at 7:33
  • $\begingroup$ @PJK A redundant premise is merely one that is not required to entail the conclusion. $\endgroup$ – Graham Kemp May 30 at 2:20

$$\dfrac{\dfrac{\lower{1.5ex}{r\to q}~~\dfrac{\lower{1.5ex}{s\lor (p\to r)}~~\dfrac{\lnot s\land t}{\lnot s}{\tiny\text{simplification}}}{p\to r}{\tiny\text{disjunctive syl.}}}{p\to q}{\tiny\text{hypothetical syl.}}~~\dfrac{\lnot q\land u}{\lnot q}{\tiny\text{simplificaton}}}{\lnot p}{\tiny\text{modus tolens}}$$

You have correctly proven that $r \to q, s\lor (p\to r),\lnot s\land t,\lnot q\land u\vdash \lnot p$ and that was all you needed to do.

As the commenters have stated, the fact that you do not need premise $u\land t$ to derive $\lnot p$ is not a problem.   It is just a redundant premise.   You may have as many redundant premises as you wish.

$$m\lor n~,~u\land t~,~ r \to q~, s\lor (p\to r)~,\lnot s\land t~,\lnot q\land u\vdash \lnot p$$


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.