Math Is Fun Forum

Especi

Guest

Mathematical Logic.

I apologize for the double post I got a little bit confused with Latex. I am having some problems following this particular problem, even though I have the solution to this I cannot understand how he got certain lines and what would be the logic for getting them. Any bit of help/tips would be useful. Thank you very much for your help.

Below is the start of a proof that if p ,q   are propositional formulas, then

is a
theorem (of L ). Write this out again, but at each stage give the reasoning, and then complete the proof:

1.

2.

Denote this formula by r
3.

Bob

Administrator

Registered: 2010-06-20

Posts: 10,646

Re: Mathematical Logic.

hi Especi

Welcome to the forum.

2.

That should be

But what are you actually asking?

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

Especi

Guest

Re: Mathematical Logic.

That is true , I made a mistake when writing it down . Thank you for pointing that out.

Bob

Administrator

Registered: 2010-06-20

Posts: 10,646

Re: Mathematical Logic.

Are you saying that you have

already proven and are using it to prove something else (in which case I am unclear what)

or are you trying to prove

in which case what are you starting with?

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

Especi

Guest

Re: Mathematical Logic.

I did it again sorry, I have a bad habit of pressing enter. I am asking for the steps necessary to proving that it is a formula and detailing the logic behind picking that step. I hope I managed to explain myself well. Thank you again for your help.

Especi

Guest

Re: Mathematical Logic.

I need to prove 

and I am given the place to start this at 1.

Bob

Administrator

Registered: 2010-06-20

Posts: 10,646

Re: Mathematical Logic.

I AM finished with editing this post

Ok so we start with

Follows because not A => not B can be replaced by B => A.

I think you must have this as a theorem somewhere.  It is certainly true for all A and B

So I think that is step 2.

Don't know what 'r' is.  Don't need it.  You have a chain of logic.  A => B => C

I'm assuming you have a theorem for that too.

whoops too many brackets here.  I'll drop some of them to stop my eyes going screwy   .

therefore

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

Bob

Administrator

Registered: 2010-06-20

Posts: 10,646

Re: Mathematical Logic.

Maybe 'r' is the whole of step 2.

I'm not sure what theorems you already have; that's my trouble with this.  ** You'd have to post your entire course and that's a bit impractical.

Look for one that is equivalent to my A => B => C and that's the one to use to justify going from step 2 to step 3.

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

Especi

Member

Registered: 2012-06-29

Posts: 11

Re: Mathematical Logic.

That does make sense and it is easier to follow though it does not resemble the solution give by the lecturer.
This is the solution given by him :

Axiom 1

Axiom 3
Denote this formula by r

Axiom 1

2,3 Modus Ponens
Denote this by a

Axiom 2

4,5 Modus Ponens

I apologize if I missed any brackets , I tried to upload a picture of the solution but was unsuccessful.
This may sound as a silly question but how did he know when to apply Axioms ?

Last edited by Especi (2012-06-29 01:44:41)

Bob

Administrator

Registered: 2010-06-20

Posts: 10,646

Re: Mathematical Logic.

hi Especi,

It's not a silly question, but, if we knew the answer to that, maths would be a lot easier! 

In any rigorous mathematical discipline, you start with a set of axioms and then try to prove theorems from them.  Every proved theorem can then be added to the axioms as something you can use to extend the set of theorems.

Knowing what to apply and when is the tricky bit.  It's even harder to help someone over the net with this, because you don't necessarily know what the original axioms were nor what theorems have already been proved.  That's my excuse for being a bit vague about this; it's to cover up my incompetence! 

Plus I was having lots of trouble with brackets.  What I wanted to do was use curly or square brackets to help keep track, but of course Latex won't let you do that.

Thanks for posting the official answer; I'll print it off and use highlighter to sort out what he has done.  If I've got anything intelligent to say, I'll post again tomorrow.

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

Bob

Administrator

Registered: 2010-06-20

Posts: 10,646

Re: Mathematical Logic.

hi

I've had a more detailed look.

There is definitely a problem with the brackets in what you have posted.  Just count them.  There are several where there are more "(" openers than ")" closers.

But, not to worry, I can edit that.

What I'd like is the axioms.

Would you be able to post Axioms 1, 2 and 3 ?

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

Especi

Member

Registered: 2012-06-29

Posts: 11

Re: Mathematical Logic.

These are the axioms we were given :
1

2

3

for any formulas p,q,r
And the deduction rule Modus Ponens

Again if I missed any brackets I apologize.

Bob

Administrator

Registered: 2010-06-20

Posts: 10,646

Re: Mathematical Logic.

Just one bracket too many. But don't worry; I'm remembering stuff I did 40 + years ago.

Here's my take on the whole thing.  I've left out all the () around single letter statements and then used square and curly brakets to help with the readability. 

I cannot see why he has introduced proposition a, that just seems to complicate unnecessarily.  If it turns out to be important my apologies.

I have also made it clearer what r is and where it comes in the proof by changing the order of two steps.

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

Especi

Member

Registered: 2012-06-29

Posts: 11

Re: Mathematical Logic.

Thank you very much for your reply , I can follow the proof easily but I sadly still have my question of "when did you know you needed to apply A1/2/3?", or do you apply them while trying to make the result match what we needed to prove ?

I'm sorry I ask so many questions and that some of them do not even make sense

Bob

Administrator

Registered: 2010-06-20

Posts: 10,646

Re: Mathematical Logic.

hi Especi,

I wish I could give you a nice rule for when to apply axioms but I cannot.

All I can suggest is this:

(i) You know you must use some axioms because that's the only way to prove anything.

(ii) The question has q --> p in it so that suggests axiom 3.

(iii) but to use that axiom you need ~p ---> ~q, so you need to think how you can get that.

(iv) ~q --> ( ~p ---> ~q) could come from A1.  Once you spot that the rest follows.

Step (iv) is the non-obvious one for me, so I guess you just have to be on the lookout for when you can use it.

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

Especi

Member

Registered: 2012-06-29

Posts: 11

Re: Mathematical Logic.

One last question , I can follow it up until the point you say "So by A2" after that I cant really see how you got that relation. Could you possibly give a bit more information on that . Thank you.

Bob

Administrator

Registered: 2010-06-20

Posts: 10,646

Re: Mathematical Logic.

I've expanded the last few steps.  Hopefully, that will clear it up. 

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

Especi

Member

Registered: 2012-06-29

Posts: 11

Re: Mathematical Logic.

Thank you very much for your help , I cold follow all of the proof now