Help with Predicate Calculus

techguy

Hi,
I've jsut started on Predicate Calculus in college and I don't know what to make of it. Some people picked it up straight off the bat but i'm having awful problems trying to understand it.

I've attatched some of the laws for an example of what I am doing.

What I am looking for is an introduction to this kind of stuff. I have tried looking it up but I am getting lots of strange stuff thrown in and am not sure what's relevant and what's not.
Does anybody know of any websites with straight forward introductions..

Thanks,
Techguy

MathsManiac

I did a bit of that kind of stuff in college, so I MIGHT be able to answer a specific question, if that's any use.

Haven't looked at websites on it, so can't recommend one. Sorry!

LeixlipRed

Logic, eh. I'd probably be able to answer a specific question on it too. Never done it in college but gave grinds in CS last year to some guy and part of it was logic

techguy

Cool thanks guys. I am looking to prove these laws. I suppose we could start with the first one, probably the easiest.How would I go about it?

I've been looking on the net for the last half an hour but can't find anything that is straight forward.

MathsManiac

Normally, before starting to study "predicate calculus" from a mathematical-logic perspective, you would first of all do a thing called "propositional calculus", because a predicate calculus is an extension of propositional calculus.

Have you studied propositional calculus already?

You might need to give us more of a background to where this material is coming from.

Also, to answer your last question, you don't start by trying to prove the first one. If these are the only rules of the system, then note that the first 8 and no 11 are lebelled as "postulates". This is basically the same as "axioms". You cannot prove anything in a logical system unless you assume some initial statements without proof. These are called "postulates" or "axioms". The task then is to prove everything else you want on the basis of these and these alone.

However, if these rules are being given here as an extension of an underlying theory, such as the propositional calculus, there may be other axioms in the background that you can also use. I wouldn't like to assert any more about what you're supposed to be doing without more background.

techguy

Ok, I am studying a module called Discrete Mathematics in a computing course. First we studied "Algoryhtmic Problem Solving" and now we're on to this. We were just handed about four pages with lots of statements as shown above. We were told what the signs meant like AND,OR,EQUIVAL etc..Then we more or less just dived straight in and started proving theoroms..

I sort of shut off shortly after that because I felt I wasn't being explained the whole story. I said i'd try and teach it to myself like I have done in the past from the internet. This seems to be harder than I thaught.

Also, propositional calculus was never mentioned. Should this have been thaught beforehand?

Thanks.

LeixlipRed

I doubt you're being asked to prove the postulates themselves from underlying axioms as MathsManiac mentioned. The course I gave grinds in was titled Discrete Maths as well. Have you a specific question you were asked to do?

techguy

This is the assignment. I havent a clue where to start.. I've been off college for the last week but I will as my lecturer about it in the morning..

Note:- I am not looking for answers to these questions.. I am just uploading it to give you an idea of what i'm after..

LeixlipRed

I'm very busy with a project at the moment so might take me a couple of days before I can glance at this. Maybe PM MathsManiac and draw his attention towards it?

techguy

Thanks LeixlipRed but I have class on this in the morning so I will bring it to the lecturers attention and he should be able to help me.. I was just hoping that there was a quick fix last week when I was off..

Thanks again everybody..

MathsManiac

If you still have trouble after talking to the lecturer, get back to us. We all live to please!

cunnins4

have you heard of true false tables?

here's an example of one for theorem 13, hope it helps:
(unfortunately, my lecturer in first year did everything backwards-so "v" in first year meant "or" to us, but I think it's supposed to be and-either way the logic is the same, just change the sign)

cunnins4

that first highlighted box should read xn(ynz) sorry. hope this guides you a little.

hivizman

I don't think truth tables are what is required here. The first question asks whether the reflexive rule or theorem can be proved from some or all of the previous three theorems. First of all, I have inserted parentheses in the identity theorem (which I think should have been there in the first place):

Identity theorem: (X≡true) ≡X

Then the symmetry theorem allows you to swap over the two expressions on either side of the final equivalence sign:

Symmetry theorem: X≡(X≡true)

Finally the associative theorem allows you to move the parentheses:

Associative theorem: (X≡X) ≡true

And that's QED:)

It looks trivial, but that's discrete mathematics for you. Remember, it took Bertrand Russell and Alfred North Whitehead over 60 pages in Principia Mathematica to prove that 1+1=2.

MathsManiac

The absence of brackets is quite disconcerting in the first list of posulates/theorems you gave. These expressions are not well-formed, unless there's a clear directive regarding which connectives take precedence over which, and how one is to handle expressions with connectives of equal precedence.

For example, it's not at all clear which of the following is intended by postulate 2:
[(X = Y)=(Y = X)]
[((X = Y)= Y)= X ]
[ X =((Y = Y)= X)]
[(X =(Y = Y))= X ]
[ X =(Y =(Y = X))]
Similarly, unless you're told that OR has a higher priority than =, you don't know whether number 5 is meant to mean: [(X^Y)=(Y^X)] or [(X^(Y=Y))^X] or [X^((Y=Y)^X]. Of course I can suspect that the first of these is what was meant, (just as I might suspect that the first of the possible interpretations above of postulate 2 was meant,) but i shouldn't have to make such guesses.

Did you get a list of precedence for the logical connectives (e.g. were you told that AND takes precedence over OR, and that both take precedence over EQUIVALENT?), and directions as to whether to read connectives of equal priority from right to left or from left to right?

techguy

Jeez, just thaught about this thread now forgot to return to post on it.. Sorry!

Anyway a couple of days after my last post I got a grind from another lecturer and he sorted most of it out for me.. I've sent in the assignment and the lecturer said he is pleased with me..

I'm delighted with my progress..

Thanks for all your help lads..