-1

I'm trying to do a bunch of proofs to get better at them but it seems like I need some help with negation. Can anyone who has time prove the following arguments? I would really appreciate it!

¬(P ∧ ¬Q), ¬P → Q ∴ Q

P → ¬Q, ¬Q → P ∴ ¬(Q ↔︎ P)

Q → P, ¬P ∨ S ∴ ¬S → ¬Q

R ∨ (P ∨ Q), Q → ¬Q, R → P ∴ P

Thank you!

2
  • Which proof system are you talking about -- natural deduction? Which of these arguments are you having trouble with? What does your attempt look like and where specifically did you run into trouble? What is that issue you're having with negation, exactly? All I'm seeing is a bunch of assignments; where is your actual question? – lemontree Oct 18 '20 at 0:57
  • Hi, I'm talking about fitch style natural deduction. I have been attempting a lot of other negation arguments but I am having trouble when they get longer and more complex. These 4 different arguments are the ones I'm currently having a problem with. I was just asking if anyone who has time and who enjoys proofs could demonstrate correct proofs of these. – ddd Oct 18 '20 at 1:02
2

Just hints, since this is presumably some kind of homework assignment.

  1. From ¬(P ∧ ¬Q) prove ¬P ∨ Q and thence P → Q. Combine this with ¬P → Q to get Q.

  2. Assume (Q ↔︎ P) hence (Q → P) and (P → Q). Combine these with P → ¬Q and ¬Q → P to prove a contradiction, and hence ¬(Q ↔︎ P) by reductio.

  3. Assume ¬S. Prove ¬P and hence ¬Q then discharge the assumption to get ¬S → ¬Q.

  4. From Q → ¬Q prove ¬Q. Then prove R ∨ P and hence ¬R → P. Combine this with R → P to get P.

4
  • thank you! it is actually not, just some negation problems from a textbook to improve myself. I tend to understand better when I see sample proofs and I wanted to use these examples to find my way in other proofs. I do not like cheating either! :) i appreciate the hints – ddd Oct 18 '20 at 4:28
  • Hi again, @Bumble could you explain the hints more openly for 1. and 4.? I am still relatively new to logic and I'm trying my best at understanding and improving – ddd Oct 18 '20 at 22:55
  • With 1, one of De Morgan's rules says that ¬(A ∧ B) is equivalent to ¬A ∨ ¬B, so this plus double negation elimination gives the first step. De Morgan's rule itself can be proved by assuming the negation and deriving a contradiction. ¬P ∨ Q is equivalent to P → Q. P → Q together with ¬P → Q proves Q. Depending on your rules, you might need to prove the law of excluded middle. – Bumble Oct 19 '20 at 2:51
  • With 4, assume ¬R, then from R ∨ (P ∨ Q) by disjunctive syllogism you have P ∨ Q. ¬Q can be proved from Q → ¬Q, so then another application of disjunctive syllogism gives P. Discharge the assumption to get ¬R → P. Combine this with R → P to get P. – Bumble Oct 19 '20 at 2:51

Not the answer you're looking for? Browse other questions tagged or ask your own question.