1. natural deduction

Hello,

I am new to logic and I could realy use some help.
is there anyone who can prove the following examples for me in Fitch style?

proof -(P v -(-Q v P)) without premisses.
proof -(P & Q) v (P V Q) without premisses.
proof -R v Q v -P v S from the premisses (-P v Q) & (-R v S).

Any help will be much apreciated!

2. Re: natural deduction

The first formula is false when P is true, so it can't be proved. Concerning the third formula, either premise ~P v Q or ~R v S is enough. You can get them by conjunction elimination. The conclusion follows just by disjunction elimination (considering whether ~P or Q holds) and then disjunction introduction. The second derivation is slightly more difficult. It requires either the law of excluded middle (easier) or double-negation elimination (harder).

3. Re: natural deduction

Thank you so much! You realy helped me out.
I have found the solutions, exepts for the second exercise. How can I apply the law of excluded middle on this one?

P.s. Excuse me for my Englisch, it is not my native language (there are no logic or mathematic forums in Holland)

4. Re: natural deduction

You reason by cases (vE, i.e., disjunction elimination) on P v ~P. If P, then -(P & Q) v (P v Q) by applying vI two times. If ~P, then you prove ~(P & Q) as follows. Assume P & Q, derive P by /\E and get a contradiction with ~P. Having proved ~(P & Q), derive -(P & Q) v (P v Q) again by vI.