# natural deduction

Printable View

• Dec 12th 2011, 04:39 AM
Sea90
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!
• Dec 12th 2011, 06:22 AM
emakarov
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).
• Dec 12th 2011, 08:25 AM
Sea90
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)
• Dec 12th 2011, 08:31 AM
emakarov
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.