PHIL 428/526, Pelletier

Fall 2011

The syllabus for this course is here. A (tentative) order in which we will cover the topics is here. Please continue to monitor this web page. I will have assignments and readings posted on this page (or linked from this page).

The first readings are from Priest’s book: the “set theory background” and Chapter 1 “Classical Propositional Logic”. You might also review whatever elementary logic book you used in your first symbolic logic class. While we are on the topic of classical logic, you might also read Priest’s Chapter 12 “Classical Predicate Logic”. (There is somewhat more advanced material about classical logic in the Goble book, if you wanted to read it. The course “schedule” has details.)

I will be presenting material about classical logic that is not in either of these books, starting with propositional logic. I will be interested in differing proof systems, in the notions of soundness and completeness, and (following Priest) in so-called semantic tableaux (which you may know as Truth Trees). I will also be interested in expressive completeness, and in various difficulties there are in representing natural language in symbolic form.

In this week’s class (Sept. 13) I remarked on some difficulties that are acknowledged in elementary symbolic logic textbooks when it comes to translating natural language English into symbolic notation. Usually the textbooks say that two (or more) different phrases are “merely stylistic variants” of one another, and do not “really” differ in semantic content. Thus they should be translated the same way. However, when you consider the English statements from which they are derived, it often seems that there is a difference in meaning. The textbook response to this is that such differences are not due to the meaning of the phrases, but rather to some other factor.

A standard description of this difference is to say that the “meaning” is semantics whereas these other factors are due to pragmatics. (Pragmatics being an account of “why you would say such-and-so in this-or-that manner in the context so-and-so”.) For instance, if you say “Let me show you how to hammer a nail efficiently”, the semantics (the “literal meaning”) is to offer a demonstration of how to hammer a nail in an efficient manner. But in some circumstances this might instead be a way of insulting the addressee, or of showing off, or speaking metaphorically, etc. The literal meaning is semantics, whereas these other things that are conveyed are pragmatic effects. A classical place to find this distinction made is H.P. Grice’s “Logic and Conversation”, which is now probably the most well-known-and-employed-outside-of-philosophy thing about philosophy of language that there is.

Here are some things that I have culled from elementary logic textbooks concerning stylistic variants of the sentence connectives, and passed out in Phil 467 that I taught at SFU some years ago: (this one about negation and conditionals; this one about other binary connectives). Look them over to remind yourselves of how these different English phrases are said to be translated into the symbolic notation of propositional logic. And here are some problems to practice your translation skills with.

Another topic we covered was (propositional) semantic tableaux (“truth trees” they are often called). Here are the branching rules in use for our signed tableaux method. And here is an algorithm for applying the method. Practice this with a few problems in an elementary logic book. This is the main proof method we will use, since it is what Graham Priest uses throughout his book. [He of course alters it to accommodate his “funny logics”.] Here are some “knight-knave” problems (truth-teller/liar problems) to practice your tableaux skills with.

The last time I taught elementary logic was at Simon Fraser University in 2007 (“Phil 210”), using the Bergman, Moor, Nelson The Logic Book. One of the things we did was to use tableaux to solve logic puzzles. The first is about using tableaux to evaluate arguments and to do funny things with “truth tellers/liars”. As a part, it also has some practice translations into propositional logic…give them a try! Here are a couple more symbolic arguments to try proving with tableaux. I also talked about using tableaux for somewhat more complex truth-teller/liar problems. Here is one direction that the complications can go.

I’ve also got some “translation hints” and stylistic variants for Predicate Logic from the 2007 class. Note that in Bergman, Moor, Nelson’s book, they use & for “and”, whereas Priest uses Ù, as will we. (Hmmm…that’s supposed to be a caret; I see that it doesn’t get rendered correctly by my Firefox). Here are the three translating hint pages: I, II, and III. Here are some practice translation problems for predicate logic…give them a try. We can discuss any issues in class.

In the lecture, I had an overhead transparency of a classification of different types of logics, categorized into “standard” and “non-standard”. Here is that classification. I also gave a categorization of the various proof methods (or proof theories). Here is that categorization. Here is an example of a proof done in an axiomatic system (the proof of (pÉp) in Whitehead & Russell Principia Mathematica (Hmmm…that was supposed to be a horseshoe). Here are some examples done in what their authors call “natural deduction”. The first one should be familiar—it is what some 65% of all modern elementary textbooks do. The second one is done in a style that about 30% of all modern elementary textbooks do. The third (last) one is done in Gentzen’s (1934) original tree-style.

Not all of the lecture material about Post’s Theorem was in electronic form. In particular, the proofs of two parts of Post’s Theorem were only done as overhead transparencies. But the parts that were electronic can be gotten here. In the lectures, I broke the proof of Post’s theorem into two parts: (a) if a set of connectives is functionally complete, then there are the requisite types of connectives, and (b) if you have the requisite types of connectives, then the set must be functionally complete. I offered a “constructive proof” of the (b) direction, by showing how to actually construct negation, then the constants, and finally some binary connective that would work (with negation) to be functionally complete. I didn’t do more than gesture at how the (a) direction works. It works by proving the contrapositive of (a): If you don’t have the requisite connectives (i.e., if, for any of the five properties, all the connectives have that property), then the set can’t be functionally complete. I indicated that the proof proceeded by showing that each of the five properties was “upward inherited” (well, the counting property was special), and so any combination of such functions would have that property too. But not every truth function has those properties, so those types of functions couldn’t be defined. Here is a paper that has some of the details in it.

In class I also mentioned a major paper by Alasdair Urquhart (U. Toronto), who wrote a piece that gave Post’s biography (which is interesting) along with some detailed descriptions of the amazingly wide group of things that Post wrote. Some of this paper is difficult, but certainly the biography and an account at a “high level” of Post’s accomplishments is easy to follow and most definitely worth your while.

The FIRST ASSIGNMENT is due on Tuesday, October 4^th. You can get it from here. In discussing the answers to the first assignment, some questions came up about how to “reduce” long formulas. This is not a topic of the course, but is interesting in itself. And for those who want a method, here is a website that explains Karnaugh maps, which is probably the most effective way to do it “by hand”. (As the author remarks, modern computerized reducing programs often have other methods. But this is the most plausible way for non-computerized solutions of small-ish problems—ones with four variables.) This website was for a computer science course, so it is phrased in a way somewhat different from our course. Here is a set of answers for the first assignment. (Keep in mind that, for many of the problems, there are a number of different equally-correct answers. This set only gives one possibility.)

We started the discussion of modal logic with the description of the “Basic Normal Logic”, system K. System K is generated from ordinary propositional logic by adding two new unary sentence connectives, the box and the diamond, and some rules that govern them. If one is developing this axiomatically, then the new principles are (a) the interdefinability of box and diamond, by using negation (“p is necessary iff it is not possible for ¬p to be true”), (b) a rule of inference (“necessitation”) which says that if a formula p is provable then its necessitation (“box p”) is also provable, and (c) an axiom (the K-axiom) that says: if a conditional is necessary, then if its antecedent is also necessary, then so is its consequent.

Priest does not do an axiomatic development of his logics, but rather uses tableaux. These tableaux have a special symbol attached to them, indicating the “world” in which the sentences at a node are being evaluated. By convention he starts with 0 as the actual world. Priest captures the interdefinability of the modal operators with his two rules that move negations to the inside of modal operators (and changing the operator). The rule of necessitation and the K-axiom are captured by the interplay of the “diamond p” and the “box p, irj” rules. You should try to do some tableaux in system K, just to get the feel of it. Priest has some problems at the end of Chapter 2 for you to try. I’ve copied a few of them onto this page, for easy access to you. Recall that Priest uses negation as his way of saying that a formula is false. So for him, writing “¬A, 2” is a way of saying that A is false at world 2. We could instead use signs for the truth values, and thus explicitly talk about truth and falsity at a world. We might put that formula as “A: F, 2”, saying that A is False at world 2. Then we would be using signed tableaux not only for the worlds, but also for the truth values. (From the point of view of this class, it doesn’t matter at all which one you prefer.)

Chapter 3 of Priest is about the class of “normal modal logics”, of which K is the basic member. All the others are generated by adding more axioms to K, until we get to the strongest of the normal systems, which is historically called S5 (or S₅), but if you use the nomenclature that is now common—where you start with K and then add on names of the axioms—you might call it KT5 or one of the other equivalent combinations of axioms (Priest does it as KTB4). Here is a writeup about these axiom systems and their names. (Note that this writeup has the G-axiom in it, whereas Priest doesn’t consider this axiom. G here stands for Geach--the philosopher Peter Geach. There is another axiom that is also called G, and is named after Gödel. But that does not generate a “normal modal logic”.) Here is a diagram of the systems that are generated by these axioms, which the proper inclusion relations indicated by arrows.

Priest gives tableaux rules for the various normal modal logic systems that he considers. You need to learn them. (Of course, they don’t include system G. Can we think of any rules for G?) And here are some more slides explaining the rules (also contains the tableaux rules for the non-normal logics).

Chapter 4 of Priest is about (some) “non-normal modal logics”, including the C.I. Lewis systems S₁, S₂, and S₃. He also mentions systems S_0.5 and S_3.5—which Lewis didn’t consider, but which were described later and put into his listings in terms of strength of the systems. Priest calls these systems N-systems, starting with the basic N and then adding conditions on the accessibility relation among possible worlds…just like with the normal K-systems However, these non-normal systems are described in terms of a distinction between normal and non-normal possible worlds, and tableaux systems are described for system N, Nr, Nrt, and Nrst. (Hmmm…those are supposed to be Greek letters rho, tau, and sigma. Stupid Microsoft.) Here is a writeup explaining these logics and the tableaux methods. It also has a few problems for you to try out. And here is a repeat of the document mentioned in the last paragraph as having the tableaux rules for both the normal and non-normal logics.

One of Priest’s main concerns in the book is with the proper formalization of the natural language “if—then”. Here are some slides about the “paradoxes of the material conditional” and arguments for/against using the horseshoe. Priest is also keen to discuss whether a “strong implication” connective of Lewis’ is adequate for representing the natural language “if—then”. He thinks not, and here is a summary of his reasoning. Instead, Priest is in favour of some kinds of conditional logics (particularly ceteris paribus conditionals) – although in later chapters he tries to merge this with relevant logic conditionals [a topic we won’t cover in this class]. Here are some slides about conditional logics.

The next topic to be covered is (propositional) many-valued logic. This is the topic of Priest’s Chapter 7. Although we will cover the material Priest discusses – so you should be sure to read it – I will be introducing some other topics, such as a wider range of “intended uses” for many-valued logics and tableaux methods for them. One of the uses (perhaps the main linguistically-oriented use) of many-valued logics is to give an account of the formal properties of vagueness in language. There are a number of places where you might read up on the background to vagueness and its logical properties. I recommend Rosanna Keefe’s (2000) Theories of Vagueness, which is available through our library as an electronic text: http://www.library.ualberta.ca/permalink/opac/3897993/WUAARCHIVE.

ASSIGNMENT #2 is due on Tuesday, Nov. 1^st, and can be downloaded from here. As before, you can submit it in advance electronically, or at the beginning of class on Nov. 1^st.

The Midterm Exam was held on November 8^th. Because I was at a conference in Spain, I was not able to grade it before the November 15^th class, but will return them at the November 22^nd class.

The remainder of the course will concern topics in predicate logic. Priest’s chapter 12 is a review of various things in predicate logic, including tableaux (with a section on identity towards the end). But it does not really consider issues of translation of ordinary language into predicate logic. I repeat here the links from above: Three items on translating into predicate logic – I, II, and III. And also some translation problems to practice on.

We will also consider the issues involved with definite descriptions – a topic that Priest does not cover. Here is a pre-publication version of a paper that Bernie Linsky and I wrote (in N. Griffin & D. Jacquette One Hundred Years After On Denoting: Russell vs. Meinong [Cambridge UP], pp. 40-64]) about Russell’s criticisms of Frege (and Meinong), arguing that they didn’t really touch Frege. (Of interest to this class are the various theories that have been attributed to Frege, and the different theorems that the various different theories will make valid.) And I will mention the issue of “sortal predication” together with the idea of inventing a “sortal logic”.

In class I mentioned a number of topics concerning the appropriate way to formally represent constructions in English. Here are the slides with those topics. Each of the topics could form a term paper (for the grad students in the class)…indeed, could form a pretty reasonable MA thesis. For either project, you would take a look at the various proposals that are in the literature that are designed to avoid the problems mentioned on these slides and then evaluate which seems best (and for what reason best). One topic in particular that takes up the last section of these slides concerns sortal predicates and sortal logics. The last slide is a very short bibliography of work done on that topic. Two items I forgot to mention, but which are very relevant are: Anil Gupta (1980) A Logic for Common Nouns (Yale UP), and Manfred Krifka (2004) “Four Thousand Ships Passed Through the Lock” in Linguistics and Philosophy 13: 487-520. Related to both of these is the following puzzle: The Edmonton Transit System says “239,800 passengers use the ETS every day”. And although ETS doesn’t say it, it is nonetheless true that every passenger is a human. But it is not the case that 239,800 humans use the ETS every day. It thus seems that x can be the same human as y, but be a different passenger than y. Such considerations form one of the basic planks in the search for a sortal logic.

These topics will soon involve a move into issues of free logic, which is the topic of Priest’s Chapter 13 …which you should start to read. (It’s pretty simple). Here are the slides I showed in class about free logic.

The third (and final) assignment will be available by November 29^th and is due on Dec. 6^th. This is the same day as the second term exam, so it not possible for you to have graded assignments to consult for this exam.

The final lecture will (unfortunately) only briefly cover topics in quantified modal logic and vagueness. In Priest these are discussed in Chapters 14-16 (for modal logic) and Chapter 21 (for many-valued logics). Of course, we won’t cover all this material. The main things for you to read are: Chapter 14.1—14.5, 15.1—15.4, 15.6.9—15.8, 16.1—16.5, 17.1—17.3, 21.1—21.4, 21.8—21.10. You might also find it interesting to read Priest’s “methodological coda” at the end of his book (pp. 584—586). [Although this mentions an argument given in a part of the book that has not been assigned, I think you can get the point of his “coda” without needing to look it up.]

Keep in mind that the second term exam will be open book, open note (with the same restrictions as the midterm: no phones, etc. etc). I will supply exam booklets; you supply writing implements.

A final reminder: the term papers (required of grad students, optional for undergrads) are due Monday, December 13^th.