# Maths & Logic (Fall 2015)

## Marks

These are posted on Omnivox.
For an explanation of the PFM and RTP marks, please read this explanation of the "alternate marking scheme" and what students at risk of failing should do.
The PFM mark should be the average of the four tests (each expressed as a percentage) written so far. I suggest you check this calculation yourself.

The main readings for this course come from my text Principles of Mathematics and Logic. Individual chapters are cited below, unit by unit, so you know when you should read each chapter (two chapters per unit). A copy of an older edition of the text is also available on reserve in the library, and also in the Maths Lab (H203). (Use this when you need to but be sure to check with your copy of the current edition afterwards - changes have been made and typos fixed.)
In addition, some sections of another text, the Alberta Notes may also be useful - I have made two chapters available suitably linked in the units where they are relevant. You should be aware that this and other texts may treat the material differently from my text - in cases where there are differences, my text is definitive for the purposes of this course.
You should also look at the Entertainments section below.

Problems? Click here if you are having trouble with PDF files.
Note: When you read mathematics, it is important to engage the text actively, not passively. You should have pencil and paper beside you, and try to follow each statement, doing the suggested calculations or reasoning yourself. It is not a novel or short story, whose meaning will just flow over you, but a dialogue, only one side of which is on the page. You must provide the other side yourself!
Here is an excellent article on how to read mathematics if you want more "advice".

(BTW: the book [Emblems of Mind by Edward Rothstein] from which the quotes are taken is one I recommend in the Entertainments below. It's about Maths & Music, and might give you a different insight into the nature of maths.)

NOTE: If you find typos or other errors, or if you have questions about the text, please let me know. Older editions of the text have a typo on p.28 -- the corrected truth table may be seen here. This has been corrected in recent editions, including the on-line version of Chp 1. In addition there are also some minor typos in earlier editions of the text in some of the exercises (especially in Chapters 3 and 5). This has also been fixed in recent editions of the text, so please check this if you are using an older edition.

Unit 1

• Chapter 1: Introduction
• Chapter 2: Formal Proof
• Other references that might be of interest:
• History of logic, filling in the sketchy remarks I made on the history of logic (by King & Shapiro)
• Alberta Notes on translation from English into symbolic language and on truth tables.

Unit 2

• Chapter 3: Fitch-style Natural Deduction Rules
• The next two items may help you should you want even more text to read. BUT: read this first!

• Chapter 4: Analytic Tableaux
• If you want some extra material on Analytic Tableau:
• Interlude (Notes on various other logics.)

Unit 3

Unit 4

Unit 5

• Chapter 9: The Axiomatic Method (Boolean and Heyting algebras)
• Extra reading for this section:

We shall cover the second of the following topics this semester

1. Gödel's Incompleteness Theorem
Chapter 10, section 1: Gödel's Incompleteness Theorems

Extra reading for this section:

2. Categories, logics, & linguistics
Chapter 10, section 2: Categorial Grammar

Extra reading for this section:

3. Probability and Statistics
Chapter 11 etc. (by G. LaValley)

### Entertainments (further readings)

General

Unit 1

Unit 2,3

Unit 4

Unit 5

Unit on Gödel's Incompleteness Theorem

Unit on Categories, logics, & linguistics

## Assignments and Answers

The most important part of the course - in fact, the core of the course - is the assignments you will find in the text. Nothing is more important: they are the means whereby you teach yourself the relevant material, which is far more important than anything I might try to teach you!

Note: If you find typos or other errors, or if you have questions about my answers (e.g. at the end of each chapter), please let me know.

Additional assignments, comments, solutions, and helpful hints will be posted in this section of the webpage, as relevant. I'll alert you to any additions in class.

Unit 1: Your first reading assignment is Chapter 1
You should do the exercises in Chp 1, especially (Parsing) Exercise 1.3.6; (Substitution) Exercise 1.3.8; (Truth tables) Exercise 1.3.10; (Tautology) Exercise 1.3.15; (Translation) Exercises 1.4.1, 1.4.2.

Next, try the Knights & Knaves Problems (Exercises 1.5.1).

In addition, you will need to read Chapter 2 before the first test.

Unit 2: The main emphasis in this section is Chapter 3. Be sure to read this chapter carefully, and to do all the exercises. This is a tricky topic - some find it the hardest of the course - but if you pay attention to what you can learn from the exercises, you will succeed. Ask me for help if you need it.

Step-by-step explanation of the "Vulcans, Romulans, and Klingons" problem. (End of section 3.2)
Summary sheet for natural deduction   (Big print version for those with poor eyesight)
(For now - till Chp 5 - ignore the bits about ∀ and ∃.)
The exercises done in class (with answers) (These also appear in the book.)

Chapter 4 is somewhat less technically demanding, but again, do the exercises to get a feel for this topic.
Erratum in the Text, version 2015.4.16 (only):
A printer's "glitch" caused page 93 to be printed sideways (you need to read it sideways, but it shouldn't have been printed that way!).
The correct full page appears here.

We did a worksheet on tableaux (and more derivations!) in Friday's class:   Here are the exercises and solutions to that worksheet done in class.
NOTE: Some folks in the morning class had a copy of the worksheet with a (small!) typo in the last question, which made the problem more complicated than intended. Most of you got the corrected sheet. You can tell easily by comparing your question with the one on the correct pdf here.
[The typo had a conjunction instead of a disjunction - the resulting tableau has lots of open paths, which essentially boil down to giving the truth values as follows: either A or B is false, and C is false, and either D and E are true or F is true.]

Just for fun(!): Some more logic puzzles  (the same with answers)

Unit 3: Read Chapter 5 carefully.
This unit continues Unit 2 - in particular, you still need to be able to construct derivations for arguments, but now in predicate logic as well. There is a lot of help in the examples in the text - do them carefully, and of course, do the exercises.
(There is a very minor typo on p.124 of old editions of the text: the reference in Exercise 5.5.6 Q2 should be to #8 in Exercise 3.3.1. The correct text is is here. This is fixed in the current edition.)
Solutions to the workshop problems (and the problems themselves if you've lost your copy)
The strategy sheet is still useful as it includes the quantifier rules.   (Similarly, for the 2-pages-in-1 version.)

You are required also to read the book/article On Bullshit by Harry Frankfurt. You should also look at some of the other readings about his article, as given above.

Read Chapter 6 - Set theory. This should be somewhat less stressful, after the rigours of predicate logic. As ever: do the exercises.

Unit 4: Read Chapters 7 and 8 (Numbers and Number Theory).

Remember: you will need a simple (cheap!) calculator, able to do simple arithmetic. (Or else you can do the calculations in your head!)
Please do not plan to use your cell phone as a calculator, as this will not be permitted on the next test (indeed as it is not permitted on any test).

I have put 2 copies of some extra text on the current material (chapters 7-8) in my "binder" in the Maths Lab (H 203). This should help you if you are having problems with mathematical induction, as it contains more worked out examples. You can borrow a copy (from the Maths Lab) and xerox it if you want.

As always, be sure to do all the exercises.

Unit 5: Read Chapter 9 and section 10.2 of Chapter 10.
As ever, there are exercises in my text; try them (solutions and/or hints at solutions are given at the end of the section). They will be the basis of Test 5.

You may also find it helpful (even essential!) to look at the extra readings in the Entertainments section.

## Practice Tests

What to study for Test 1 (11 Sept 2015)
Practice Test 1

Practice Test 2 (2 Oct 15)

Practice Test 3 (23 Oct 15)
Some possible essay questions

Practice Test 4 (13 Nov 15)
Check out the Worksheet and Solutions above for Test 4.
Remember to bring your calculator (and to know how to use it!)

Test 5 (4 Dec 15)
Hints for Test 5

You are permitted to bring to the test an index card (or piece of paper) 5in by 3in (13cm by 8cm) with whatever notes you want written on it (but just one side please, and don't write microscopically!). Plan it carefully!
I do insist the notes are written by you - no xeroxes!; do not use somebody else's notes, although you may plan notes together.
Write your name on your notes card - you must hand in your notes with your test, when you finish it Friday.