Proof, Computation and Agency Logic at the Crossroads

Proof, Computation and Agency: Logic at the Crossroads provides an overview of modern logic and its relationship with other disciplines. As a highlight, several articles pursue an inspiring paradigm called 'social software', which studies patterns of soci

  • PDF / 366,420 Bytes
  • 15 Pages / 439.37 x 666.142 pts Page_size
  • 5 Downloads / 200 Views

DOWNLOAD

REPORT


What Is Mathematical Logic? A Survey John N. Crossley

1.1 Introduction What is mathematical logic? Mathematical logic is the application of mathematical techniques to logic. What is logic? I believe I am following the ancient Greek philosopher Aristotle when I say that logic is the (correct) rearranging of facts to find the information that we want. Logic has two aspects: formal and informal. In a sense logic belongs to everyone although we often accuse others of being illogical. Informal logic exists whenever we have a language. In particular Indian Logic has been known for a very long time. Formal (often called, “mathematical”) logic has its origins in ancient Greece in the West with Aristotle. Mathematical logic has two sides: syntax and semantics. 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, Aristotle was able to elicit some basic laws. His style of categorizing logic led to the notion of the syllogism. The most famous example of a syllogism is All men are mortal Socrates is a man [Therefore] Socrates is mortal Nowadays we mathematicians would write1 this as ∀x(Man(x) → Mortal (x)) Man(S) Mortal (S)

(1.1)

John N. Crossley School of Information Technology, Monash University, Clayton, VIC 3800, Australia, e-mail: [email protected] 1

A list of the symbols used is included in the appendix.

J. van Benthem et al. (eds.), Proof, Computation and Agency, Synthese Library 352, c Springer Science+Business Media B.V. 2011 DOI 10.1007/978-94-007-0080-2 1,

3

4

J.N. Crossley

One very general form of the above rule is A

(A → B) B

(1.2)

otherwise know as modus ponens or detachment: the A is “detached” from the formula (A → B) leaving B. This is just one example of a logical rule. This rule, and other rules of logic such as A B (A ∧ B)

or

(A ∧ B) A

where ∧ is read “and”, have obvious interpretations. These rules come from observing how we use concepts. This analytic approach was that taken by George Boole, an Irish mathematician in the 19th century. It is from his work that we have Boolean algebra or Boolean logic or, as it is often known today, propositional calculus. Later in the 19th century Gottlob Frege developed a small suite of logical laws that are with us today and suffice for all of mathematics. These are the rules of the predicate calculus. The rules relate only to the syntax. Although they are abstracted from the way we talk and think, the meaning, the semantics, is something quite separate. The most familiar example of semantics is given by truth-tables such as the one for conjunction (or “and”, ∧): ∧T F T T F FFF Here we are given the truth-values of the formulae A and B and we work out the truth of the conjunction (A ∧ B) by taking the value for A at the side and the value for B at the top and finding the value where column and row intersect. In general, determining the truth of a syntactic expression (formula) A requires looking carefully at its constituents. At this point we should pause because we