How to prove P / Q or not Q without using any assumption?

Question

How to prove ( q or not q), which is tautology when an arbitrary premise is given? (Using natural deduction)

I tried to make steps that finally goes to HS but failed.

Sorry, it was not to use assumption. I edited my question. – Moibois Apr 15 '17 at 08:13 — Moibois, Apr 15 '17 at 08:13

axioman · Answer 1 · 2017-04-15T08:37:40.360

0

Case 1: q is true, therefore q or x is true for any x, especially for x= not q Case 2: q is false, therefore not q is true, therefore x or not q is true for any x, especially for x=q Because by law of exclused middle, q has to be false or true, those cases are exhaustive.

Edit: q or not q= not(not q and not not q)= not (not q and q)= not (False)=True using excluded middle in step 2

edited Apr 15 '17 at 08:37

answered Apr 15 '17 at 08:25

axioman

459

That's correct proof, but I don't think that can be expressed in form of natural deduction without using any assumption. – Moibois Apr 15 '17 at 08:30
I changed it not to use any assumptions, except basic logical rules – axioman Apr 15 '17 at 08:39

score 0 · Answer 2 · answered Apr 15 '17 at 22:13

0

Not every proof system will be able to prove this without any assumption. And when you say 'natural deduction' ... that could mean quite a few different proof systems! Maybe you could let us know what rules of inference you have?

answered Apr 15 '17 at 22:13

Bram28

100,612
6
70
118

How to prove P / Q or not Q without using any assumption?

2 Answers2