jnc-tutorial

What is mathematical logic? A survey1John N. CrossleySchool of Computer Science and Software Engineering,Monash University, Clayton, Victoria, Australia 3800John.Crossley@infotech.monash.edu.au1 IntroductionWhatismathematicallogic?Mathematicallogicistheapplicationofmathemat-ical techniques to logic.Whatislogic?IbelieveIamfollowingtheancientGreekphilosopherAristotlewhen I say that logic is the (correct) rearranging of facts to find the informationthat we want.Logic has two aspects: formal and informal. In a sense logic belongs to ev-eryone although we often accuse others of being illogical. Informal logic existswhenever we have a language. In particular Indian Logic has been known for avery long time.Formal(oftencalled,‘mathematical’)logichasitsoriginsinancientGreeceintheWestwithAristotle.Mathematicallogichastwosides:syntaxandsemantics.Syntax is how we say things; semantics is what we mean.By looking at the way that we behave and the way the world behaves, Aris-totle was able to elicit some basic laws. His style of categorizing logic led to thenotion of the syllogism.The most famous example of a syllogism isAll men are mortalSocrates is a man[Therefore] Socrates is mortalNowadays we mathematicians would write this as∀x(Man(x)→ Mortal (x))Man(S) (1)Mortal (S)One very general form of the above rule isA (A→B)(2)Botherwise know as modus ponens or detachment: the A is ‘detached’ from theformula (A→B) leaving B. This is just one example of a ...