Logic I (Phil 279)

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

Fall 2011 official course outline (PDF).

Contents

• General Information
  • Course description
  • Evaluation and Requirements
  • Required Textbook
  • Assignments and Policies
  • Course Website
  • Syllabus
• Frequently Asked Questions and software help, including
  • How do I get overloaded?
  • How hard is this course?
  • What's with the grading scale?
  • Why can't I sell the book or buy it used?

Course Description

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? We will also look at some results and notions which are important for the applications of formal logic, such as normal forms and expressive power of propositional and first-order logic, and prove, in outline, some important theorems relating semantics and proof theory (soundness, completeness). We will touch on some applications of logic to philosophy and mathematics.

Evaluation and Course Requirements

6 homework assignments, a midterm exam, a Registrar-scheduled final exam, 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 midterm counts 20%, the final 25%, and discussion participation counts 5%. You must hand in all 6 assignments, and you must take the midterm and final exams to pass the course. You must receive a D or better on the final to receive a D or better in the course.

Each assignment 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.

Required Text

Jon Barwise and John Etchemendy, Language, Proof and Logic, CSLI/Chicago University Press

Available at the University of Calgary Bookstore.

The text comes with a CD and 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.

Contents of the Software CD

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 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.  LPL is also installed in the Arts Faculty Computer Lab (a.k.a the TRI 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 in order to use the grading service.

LPL Website

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

http://lpl.stanford.edu/

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.

Assignments and Policies

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 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.

Late work and extensions

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 make-up exams under normal circumstances; for the final exam, university policies for deferral of exams apply.

Collaboration

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 midterm and final exams, of course. Midterm and final will be closed-book. Be aware that cheating on an exam is a serious academic offense and can result in suspension or expulsion.

Participation

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.

Lecture and Tutorial

This class is accompanied by a scheduled tutorial. Tutorials are led by Teaching Assistants, who guide you through the material in a more hands-on manner than is possible in lecture. This is where you should go to pick up tips for the assignments, ask questions, go over problems in detail.

Some students find the material relatively easy to pick up on their own, and the software makes self-directed study particularly easy. Note, however, that only the best 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 lacture and tutorial is not mandatory, it is highly encouraged. Although, generally, studying the textbook is sufficient for completing the homework assignments and tests, you are nevertheless responsible for knowing what is covered in lecture and tutorial. Conversely, you are also responsible for studying the assigned chapters in the textbook.

Course Website

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

blackboard.ucalgary.ca

To access the BlackBoard site, you can either go directly to blackboard.ucalgary.ca and log in withyour 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

What You Have to Do Now

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 a UCID 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.

Syllabus

This is a tentative syllabus to give you a rough idea what parts of the book we will cover when. The assignment and midterm 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.

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: Chains of equivalences and normal forms. 1 lecture : Chapter 4.

Learning goals: Tautological equivalences: De Morgan’s Laws and other equivalent trans-formations. Proving tautological equivalence by a chain of equivalences. Negation, conjunctive and disjunctive normal forms.

Formal and informal proofs using Boolean connectives. 1 lecture: Chapters 5 and 6.

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

Week 5: Formal and informal proofs using Boolean connectives (cont’d). 2 lectures: Chapter 6.

Learning goals: Basic properties of ¬ . Indirect proof and formal proofs with ¬ . Arguments with inconsistent premises. Informal proofs about FOL. Formal proofs of tautologies. Strategies for formal proofs.

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

Week 6: 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 ↔ .

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 ¬ . The Sheffer stroke.

Reading week: Feb 18–26.

Week 7: Introduction to Quantification. 2 lectures: Chapter 9

Learning goals: Understanding syntax and semantics of quantifiers: well-formed formulas, free and bound variables, satisfaction. The Aristotelian forms. Simple translations.

Assignment 3 due (covers Ch. 6–8)

Week 8: First-order validity and consequence. 1 lecture: Sections 10.1, 10.2.

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

Midterm exam in class

Week 9: First-order validity and first-order interpretations continued. 1 lecture: Chapter 10.

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

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. Expressing complicated properties using quantifiers, in particular in the language of arithmetic.

Assignment 4 due (covers Ch. 9–10)

Week 10: Multiple quantification continued. 1 lecture: Section 11.4, 11.5

Learning goals: Understanding and translating anaphora. Recognizing ambiguity and translating ambiguous sentences.

Week 11: Formal proofs with quantifiers. 2 lectures: Chapter 13

Learning goals: Understanding and applying the introduction and elimination rules for ∀, ∃ . Strategies for proofs with quantifiers. Proofs with multiple and mixed quantifiers. Proofs with equality.

Assignment 5 due (covers Ch. 10–11)

Week 12: 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.

Basic metatheory. 1 lecture: Section 8.3

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

Week 13: Catchup, Outlook, Review. 2 lectures

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

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

Official Outlines

Attachment	Size
Outline Fall 2002	22.97 KB
Outline Winter 2004	26.52 KB
Outline Winter 2006	79.27 KB
Outline Winter 2009	70.14 KB
Outline Fall 2009	91.02 KB
Outline Fall 2010	163.5 KB
Outline Fall 2011	166.21 KB