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: 5571
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: 1310
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: 1310
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: 5571
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: 1310
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: 5571
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: 1310
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: 5571
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: 5571
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: 5571
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: 1310
Joined: 27 Oct 2016