## 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)

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 Resident Member

Posts: 5606
Joined: 14 Mar 2012    ### Re: Simple Problem (need help with notation)

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. mitchellmckain
Active Member

Posts: 1302
Joined: 27 Oct 2016    ### Re: Simple Problem (need help with notation)

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 mitchellmckain
Active Member

Posts: 1302
Joined: 27 Oct 2016    ### Re: Simple Problem (need help with notation)

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.) Resident Member

Posts: 5606
Joined: 14 Mar 2012    ### Re: Simple Problem (need help with notation)

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. mitchellmckain
Active Member

Posts: 1302
Joined: 27 Oct 2016    ### Re: Simple Problem (need help with notation)

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! Resident Member

Posts: 5606
Joined: 14 Mar 2012    ### Re: Simple Problem (need help with notation)

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. mitchellmckain
Active Member

Posts: 1302
Joined: 27 Oct 2016    ### Re: Simple Problem (need help with notation)

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. Resident Member

Posts: 5606
Joined: 14 Mar 2012    ### Re: Simple Problem (need help with notation)

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!) Resident Member

Posts: 5606
Joined: 14 Mar 2012    ### Re: Simple Problem (need help with notation)

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 Resident Member

Posts: 5606
Joined: 14 Mar 2012    ### Re: Simple Problem (need help with notation)

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. mitchellmckain
Active Member

Posts: 1302
Joined: 27 Oct 2016  