Simple Problem (need help with notation)

Philosophical, mathematical and computational logic, linguistics, formal argument, game theory, fallacies, paradoxes, puzzles and other related issues.

Simple Problem (need help with notation)

Postby BadgerJelly on September 20th, 2017, 12:12 am 

VERY easy problem but struggling to write out Fitch notation correctly.

Premises

1) p=>q
2) m=> p|q

Prove m=>q

1- p=>q
2- m=>p|q
3- p 1 assumption
4- q 1,3 MP

I just cannot see what I am meant to write next? It is a glaringly obvious answer but need help writing this out correctly.

Thanks
User avatar
BadgerJelly
Resident Member
 
Posts: 4587
Joined: 14 Mar 2012


Re: Simple Problem (need help with notation)

Postby mitchellmckain on September 27th, 2017, 4:48 am 

I would have done this with a proof by contradiction.

But ok, its not the only way to do this. The problem is, (perhaps because of notation) I don't understand your meaning in what you have written in 3 and 4. So perhaps the way to proceed is for you to explain the gist of your proof in plain English and then I can address how to put this in the usual notation.
User avatar
mitchellmckain
Member
 
Posts: 734
Joined: 27 Oct 2016


Re: Simple Problem (need help with notation)

Postby mitchellmckain on September 27th, 2017, 1:06 pm 

You know, it looks like you are saying
p=>q therefore p which is incorrect.
now if it was
p and q
then you could say therefore p
perhaps a set of rules for constructing proofs in symbolic logic would help

http://sites.millersville.edu/bikenaga/ ... rence.html

http://www.inf.ed.ac.uk/teaching/course ... 4/Ch1c.pdf

https://leanprover.github.io/logic_and_ ... _proof.pdf
User avatar
mitchellmckain
Member
 
Posts: 734
Joined: 27 Oct 2016
BadgerJelly liked this post


Re: Simple Problem (need help with notation)

Postby BadgerJelly on September 28th, 2017, 12:43 am 

No, no, no! I was not saying that.

I was making an assumption of p in an attempt to prove m, but got stuck (maybe it is not the best way to go).

I can get either p or q from modus ponens and modus tollens. No matter what I have to start with an assumption of p or q because I don't have a premise for either p or q.

I need q to prove m => q

Just figured it out! DOH!

I need to use Logical Equivalence rule:

(~A -> B) <=> (A v B)

so

(p -> q) <=> (~p v q)

Then I just use v elimination to prove q

then

m -> (p v q) <=> (~m v (p v q))

Then use Associativity/ v elimination ... I don't think I need to bother with associativity though? Which just says ...

(~m v (p v q)) <=> ((~m v p) v q)

Then I just move to ~m v p and v (OR) elimination to get ~m and then negation to get m ... still not really there yet ... Mmmm

Going to take quite a lot of practice to get used to these puzzles!

Thanks for those great links :) MUCH appreciated. I am going to order The Logic Book in a few weeks, so hopefully I'll make a start on that when it arrives (maybe in a month or two.)
User avatar
BadgerJelly
Resident Member
 
Posts: 4587
Joined: 14 Mar 2012


Re: Simple Problem (need help with notation)

Postby mitchellmckain on September 28th, 2017, 3:28 am 

BadgerJelly » September 27th, 2017, 11:43 pm wrote:No, no, no! I was not saying that.

I was making an assumption of p in an attempt to prove m, but got stuck (maybe it is not the best way to go).

That sounds a little bit like a proof by cases. In this method the objective is to show that...
p -> (m->q) i.e. assume p to prove m->q
and
~p -> (m->q) i.e. assume ~p to prove m-> q
I think I got this to work, but it was not as sure and satisfying as the proof by contradiction.

BadgerJelly » September 27th, 2017, 11:43 pm wrote:Just figured it out! DOH!

I need to use Logical Equivalence rule:

(~A -> B) <=> (A v B)

so

(p -> q) <=> (~p v q)

yes that is a promising start and I used something similar in my proof by contradiction.

BadgerJelly » September 27th, 2017, 11:43 pm wrote:Then I just use v elimination to prove q

then

m -> (p v q) <=> (~m v (p v q))

Then use Associativity/ v elimination ... I don't think I need to bother with associativity though? Which just says ...

(~m v (p v q)) <=> ((~m v p) v q)

Then I just move to ~m v p and v (OR) elimination to get ~m and then negation to get m ... still not really there yet ... Mmmm

Yeah I got stuck going this route (what I would call an algebraic proof) as well.
User avatar
mitchellmckain
Member
 
Posts: 734
Joined: 27 Oct 2016


Re: Simple Problem (need help with notation)

Postby BadgerJelly on September 28th, 2017, 3:57 am 

I guess it would be more clever of me to have split the m -> (p v q)

so

m -> (p v q) <=> (m -> p) v (m ->q)

Then simply Disjunction Elimination OR Hypothetical Syllogism to get to (m -> q)

Easier than it looked! Hahaha!
User avatar
BadgerJelly
Resident Member
 
Posts: 4587
Joined: 14 Mar 2012


Re: Simple Problem (need help with notation)

Postby mitchellmckain on September 28th, 2017, 4:38 am 

congrats! An algebraic solution! I like it!


For readers the last step can be achieved with a implication chain

we have p->q so I think we can replace m->p with m->q.

then (m->p)|(m->q) becomes (m->q)|(m->q) which of course reduces to (m->q).



Still I recommend you work out the proof by contradiction. It is one of the more powerful methods of proof.
User avatar
mitchellmckain
Member
 
Posts: 734
Joined: 27 Oct 2016


Re: Simple Problem (need help with notation)

Postby BadgerJelly on September 28th, 2017, 10:47 am 

Will do :) I guess algebra is the natural way for my brain to work at the moment. After more practice I hope I'll be able to see more intuitively how to apply other methods.

Thanks for the help.
User avatar
BadgerJelly
Resident Member
 
Posts: 4587
Joined: 14 Mar 2012


Re: Simple Problem (need help with notation)

Postby BadgerJelly on September 29th, 2017, 2:18 am 

Okay, I get the reductio ad adsurdum (RAA) proof for proving p (simple enough.)

Now am I justified in taking the same route to prove (m -> q) ?

It seems obvious to common sense that if I bhave proven that if p then q and if not q then not p (which I have through contradiction (RAA)) then I have to extract through logical equivalence as I did in the other proof?

So I guess you worked it out like this ? :

1 - m -> (p v q)
2 - ~(p v q)
-------------------
----- 3- m (Supposition from premise 1)
------------------
----- 4- (p v q) (Modus Ponens from premise 1)
----- 5- ~(p v q) (Negation from 4)
-------------------
6- ~m (3,4,5 Reductio Ad Absurdum)

Therefore if (p v q) are false then m is ALWAYS false, proving the contradiction. I guess this is where the more algebraic habit of mine conflicts with my intuition :(

Is that basically it? (pls excuse the clumsy use of ---------- to split the supposition from the conclusion!)
User avatar
BadgerJelly
Resident Member
 
Posts: 4587
Joined: 14 Mar 2012


Re: Simple Problem (need help with notation)

Postby BadgerJelly on October 3rd, 2017, 3:42 am 

This is a problem on the Coursera site.

Still cannot use the table they have set up to get the correct answer.

I don't know if it's broken, but nothing I seem to do makes sense.

If someone could write out this in Fitch notation I would REALLY appreciate it.

It is REALLY annoying considering I have proven it above, but cannot get the bloody table on the site to do what I want :(

Here : http://intrologic.stanford.edu/coursera/exercise.php?exercise=exercise_04_04
User avatar
BadgerJelly
Resident Member
 
Posts: 4587
Joined: 14 Mar 2012


Re: Simple Problem (need help with notation)

Postby mitchellmckain on October 3rd, 2017, 4:19 am 

1) p=>q
2) m=> p|q

Prove m=>q


I did it like this...
~(m=>q) is equivalent to (m^~q)
If you want, you can derive this from your previous equivalence of m=>q with (~m or q) using
~(a or b) <=> (~a ^ ~b).

So we have
1) p=>q
2) m=> p|q
3) m^~q

3 gives m and by 2 we get p|q
4) p|q

But 3 also gives ~q
5) ~q

With 4 and 5 we have p
6) p

But then by 1 and 6 we have q
7) q

Now we have both 7)q and 5)~q which is a contradiction.

Thus we have by contradiction that m=>q


P.S. The link did not work for me.
User avatar
mitchellmckain
Member
 
Posts: 734
Joined: 27 Oct 2016



Return to Logic

Who is online

Users browsing this forum: No registered users and 7 guests