University of Calgary

UofC Navigation

Logic I (Phil 279) is an introduction to formal logic.

**Important note: Do not buy a used copy of the text! And: You can now buy an electronic version of the text online!**

**Official Fall 2013 Course Outline (PDF)**

This course will introduce you to the semantics and proof-theory of first-order logic. We will learn how to 'speak' the language of FOL, study the method of truth tables, become proficient in giving formal and informal proofs, and learn how to construct and argue about first-order interpretations. These methods will enable us to answer, in particular cases, the questions that logic is primarily concerned with: When does something follow from something else? What are logical truths? Which arguments are logically valid? But the main payoff will be to get you to become comfortable with formal methods, and to use them to clarify and make precise logical relationships that are hard to understand or express otherwise. We will also look at some results and notions which are important for the applications of formal logic, such as the expressive power of propositional and first-order logic, as well as some important theorems relating semantics and proof theory (soundness, completeness). We will touch on applications of logic to philosophy, mathematics, and computer science.

6 homework assignments, 3 tests, and participation in lecture, tutorial, and in discussions on the class website. The lowest homework score will be dropped, the remaining 5 assignments each count 10% towards the final grade. The tests count for 15, 20, and 10%, respectively. Participation counts 5%. You must hand in all 6 assignments.

Each assignment and test will be graded on a scale of 0–100. The final score is then computed according to the percentages given above. The following table will be used to convert the final score to letter grades (the ranges include the lower percentage and exclude the upper, e.g., 83 earns a B, not a B–):

98–100 | A+ | 87–90 | B+ | 77–80 | C+ | 65–70 | D+ |

93–98 | A | 83–87 | B | 73–77 | C | 60–65 | D |

90–93 | A– | 80–83 | B– | 70–73 | C– | < 60 | F |

If you think this is harsh, see "What's with the grade scale?" below.

These are absolute scores, i.e., grades will not be curved.

If you are in the Computer Science BA or BSc Honours program or in the Philosophy BA Honours program, you must pass Phil 279 with a C– or better to register in required courses for which it is a prerequisite.

Dave Barker-Plummer, Jon Barwise and John Etchemendy,

Language, Proof and Logic, CSLI/Chicago University Press (2nd ed.)Available at the University of Calgary Bookstore

and an electronic version online.

The physical version of the text comes with a CD which has on it a non-transferable use license for software which you will be using to prepare your homework assignments. (For this reason, **you have to buy a new copy of the text.**) On the CD you find a registration ID. **Write this ID down in a safe place**—without it, you will not be able to turn in your assignments. If you buy the text online, you will also get a non-transferrable registration ID.

If you have previously purchased a copy of the text and the ID is registered to you, or if you have a new copy of the 1st edition of the text, you can download the second edition of the book in PDF format as well as the new version of the software from lpl.stanford.edu. You do not need to buy another new copy of the text.

The software CD that comes with the text contains three programs (Tarski's World, Boole, and Fitch) which you will use to complete homework problems. The program Submit lets you turn in your completed solutions to the Grade Grinder, which in turn sends reports on what you did correctly and incorrectly to your TAs. The CD also contains the entire textbook as well as the software manual in PDF format. **Please take the time to read the software manual.** It contains useful information, in particular, keyboard shortcuts for logical symbols, which will make typing formulas much easier.

**Because the text is bundled with software, the book cannot be returned once the seal is broken.** The LPL software is also installed in the Arts Faculty Computer Lab in the basement of Social Sciences (018 SS). You can check out the textbook and the software there before buying it, and during term you can use it to complete your homework assignments on campus. You will, however, have to buy a new copy of the textbook y the third week of classes in order to turn in your homework assignments.

The LPL team maintains a website with helpful information. Check it out at:

Among other things, the website contains hints and solutions to selected exercises, and a download area where you can obtain the contents of the CD with your registration ID. Thus, if you lose your CD, you will still have access to the software.

Exercise sets will in general be due on Fridays at 12 noon. Written parts of the assignment should be dropped off in a box just inside the Philosophy Department (Social Sciences, 12th floor), electronic parts have to be submitted online using Submit (one of the four programs in LPL). The written parts of the assignments must be submitted on paper; emailed copies will not be accepted.

Your TAs are in charge of homework marking; please pick up your marked assignmetns during tutorial or in office hours from them. All questions regarding homework marks should be directed to them.

The lowest homework score is dropped, this allows you to hand in one assignment late without penalty. Therefore, no late assignments will be accepted for credit. However,** you have to turn in all six assignments** within one week of the due date.

There will be no extensions or make-up tests under normal circumstances.

Collaboration on exercises is encouraged. However, you must write up your own solutions. This means that for the electronic parts,** you must create solution files completely from scratch**. The LPL software can tell if you've copied someone else's exercise files. You are also required to list the names of the students with whom you've collaborated on the assignment. **If the Grade Grinder flags an exercise on your assignment as not being created independently (i.e., it is "similar" or "identical" to another student's), your assignment and those of whoever you received the file from or gave the file to will receive a score of 0.**

You're not allowed to collaborate on the tests, of course. Tests will be closed-book. Be aware that cheating on an exam is a serious academic offense and can result in suspension or expulsion.

5% of your grade will be determined by class participation. This includes in particular participation in discussions on the class website. Five serious posts on the website (asking a question, giving a hint, providing an answer to someone else’s question) over the course of the term will earn you full marks (5 points) for the participation part of your final grade. Only posts made before the time of the final exam count. If all your posts occur within one 7-day period, you will receive a maximum of 3 points. Consistent participation in class discussions during lecture or tutorials of course also counts.

Some students have no problem picking up the material on their own, and the software makes self-directed study particularly easy. Note, however, that only very good students can get away with that. Many students who don't attend lecture or tutorial just end up failing the class; thus, although attendance in lecture and tutorial is not mandatory, it is highly encouraged. Although, generally, studying the textbook and class

handouts is sufficient for completing the homework assignments and passign the exams, you are nevertheless * responsible for knowing what is covered in lecture*. Conversely, you are also responsible for studying the assigned chapters in the textbook.

This class is accompanied by scheduled tutorials. Tutorials are led by the Teaching Assistants, who guide you through the material in a more in-depth manner than is possible in lecture. This is where you should go to pick up tips for the assignments, ask questions, and go over problems in detail. ** Tutorials begin in the second week of classes.** Starting the third week of classes, you will have a choice between a regular classroom tutorial led by a TA, and a workshop in the AFCL (SS 018), supervised by a TA. In the classroom tutorial, the TA will lead the discussion, review material from lecture, go over problems for the homework assignment. In the workshop, you will be able to work on the assignments in small groups, directly on the computer, and with a TA present who can help and explain things.

A course website on U of C's BlackBoard server will be set up. You should be automatically signed up on the first day of class if you're registered in the class. You can find the website at

To access the BlackBoard site, you can either go directly to blackboard.ucalgary.ca and log in with your IT account name and password, or you can access it through the myUofC portal (my.ucalgary.ca; log in with your eID, then click on the "Blackboard" link on the right). If you don’t have an eID or IT account, see www.ucalgary.ca/it/gettingstarted/student

**You must log on at least once before the end of the second week of class.**

If you are not registered in the course on the first day of class, you will be added to the website within a day of registering.

We will use the email function on BlackBoard to send out important notices. Therefore, **please make sure your email address on file with the University is current**. See here for instructions on how to change it: elearn.ucalgary.ca/blackboard/email

1. Attend lecture and tutorial the first two weeks of class (tutorial starts the second week).

2. Buy the textbook (remember, you need a new copy).

3. Register for an IT account and eID, and make sure your email address is current in myUofC.

4. Log on to the class website and familiarize yourself with the discussion board.

5. If you register your email address with Submit, make sure you choose an email address which will be working throughout the semester.

This is a tentative syllabus to give you a rough idea what parts of the book we will cover when. The assignment and test dates are firm, however.

**Week 1: The Language of FOL.** 2 lectures; Chapter 1.

Learning goals: Understanding formal first-order languages. Syntax of FOL: Predicate symbols, individual constants, function symbols. Examples of first-order languages: the blocks language, the language of arithmetic. First-order structures.

**Week 2: The Logic of Atomic Sentences.** 1 lecture; Chapter 2.

Learning goals: Understanding logical validity of arguments. How to show arguments are valid: Basic properties of the identity predicate: reflexivity, principle of the substitutability of identicals. Basic properties of other predicate symbols (transitivity, reflexivity, symmetry, inverse relations). Informal proofs. Fitch and formal proofs. How to show that arguments are not valid: the method of counterexamples.

**Introduction to the Boolean connectives.** 1 lecture; Chapter 3.

Learning goals: Syntax and semantics of Boolean connectives: Formation rules for sentences of FOL using ?, ? , ¬ . Truth tables for the Boolean connectives.

Tutorials start in the second week.

**Week 3: The Boolean Connectives (cont’d).** 1 lecture; Chapter 3.

Learning goals: Translating sentences from English into FOL using the Boolean connectives. Expressive power of the Boolean connectives: “neither . . . nor —” and “not both . . . and —”; how to express complicated things using the blocks language and the Boolean connectives.

**The Logic of Boolean Connectives.** 1 lecture : Chapter 4.

Learning goals: Understanding logical truth, tautologies, and TW-necessities. Tautological equivalence, consequence, and validity. The method of truth tables (Ch. 4)

You must complete the “You try it” exercise on pp. 8–10 of the text and submit “World Submit Me 1” by Tuesday of the 3rd week, midnight.

Assignment 1 due (covers Ch. 1–3)

**Week 4: Formal and informal proofs for ? and ?.** 1 lecture: Chapters 5 and 6.

Learning goals: Proving arguments valid by informal and formal proofs. Basic properties of ? and ? . Formal rules for ? and ?.

**Formal and informal proofs for the Boolean connectives.** 1 lecture: Chapter 6.

Learning goals: Proof by cases. Basic properties of ¬ . Indirect proof and formal proofs with ¬ .

Assignment 2 due (covers Ch. 4–5, parts of 6)

**Week 5: Advanced proofs for the Boolean connectives.** 1 lecture: Chapter 6.

Learning goals: Arguments with inconsistent premises. Informal proofs about FOL. Formal proofs of tautologies. Strategies for formal proofs.

**The Conditionals.** 1 lecture: Chapter 7 and 8.

Learning goals: Truth tables for ? and ? . Translations from English to FOL using the conditionals. Conversational implicature. Rules for formal proofs involving ? and ? . The semantic deduction theorem.

**Week 6: Introduction to Quantifiers.** 1 lecture: Chapter 9

Learning goals: Syntax of quantifiers: well-formed formulas, free and bound variables, scope. Satisfaction, semantics of quantifiers. Everything, something, nothing. Determiner phrases.

**Test 1**, in class, covers Chapters 1-5

**Week 7: Single Quantifiers.** 1 lecture: Chapter 9

Learning goals: Restricted quantification: the Aristotelian forms. Expressing simple sentences involving no nested quantifiers. Quantifiers and function symbols.

**First-order validity and consequence.** 1 lecture: Chapter 10

Learning goals: The truth-functional form algorithm: when are sentences of FOL tautologies? The replacement method. First-order structures. First-order validity and consequence.

Assignment 3 due (covers Chapters 6-8)

**Week 8: First-order interpretations.** 1 lecture: Chapter 10.

Learning goals: Constructing first-order interpretations. Using diagrams to specify interpretations. Relations between logical notions.

**Intro to Multiple quantification.** 1 lecture: Chapter 11

Learning goals: Meaning and use of multiple occurrences of the same quantifier. Translation mistakes: different variables does not mean different objects. Meaning and use of mixed quantifiers. The step-by-step method of translation. Understanding why the order of quantifiers matter, ambiguity.

**Week 9: Expressive Power, Anaphora and Ambiguity.** 1 lecture: Chapter 11

Learning goals: Expressing complicated properties using quantifiers, in particular in the language of arithmetic. Recognizing ambiguity and translating ambiguous sentences. Understanding and formalizing anaphora.

**Formal proofs with quantifiers.** 1 lecture: Chapter 13

Learning goals: Understanding and applying the introduction and elimination rules for ?, ? . Strategies for proofs with quantifiers.

Assignment 4 due (covers Ch. 9–10)

**Week 10: Test 2**, in class, covers Ch. 6-11** **

**Week 11: Advanced formal proofs with quantifiers.** 1 lecture: Chapter 13

Learning goals: Proofs with multiple and mixed quantifiers. Proofs with equality.

**Numerical Quantification and Definite Descriptions.** 1 lecture: Sec. 14.1, 14.3

Learning goals: Understanding numerical quantification: how to express ‘there are exactly/at most/at least n things of a certain kind.’ Russell’s and Strawson’s analyses of definite descriptions. How to express ‘both’ and ‘neither’ in FOL.

Assignment 5 due (covers Ch. 10–11)

**Week 12: Truth-functional completeness.** 1 lecture: Section 7.4.

Learning goals: Understanding the aims of meta-theory. Definition and proof of truth-functional completeness for ?, ?, and ¬ . Truth-functional completeness of "neither - nor".

**Basic metatheory.** 1 lecture: Section 8.3

Learning goals: Understanding the significance of soundness and completeness. Sketch of a soundness proof.

**Week 13: Outlook.** 1 lecture

Learning goals: Understanding the ‘big picture.’ Significance and application of logic. Limitations of logic: undecidability, incompleteness.

**Test 3**, in class, covers Ch. 7.4, 11, 13, 14

Assignment 6 due (covers Ch. 13, Sec. 14.1–2, Sec. 8.3)