Logic I (Phil 279)

What is this course about?

The course will introduce you to the semantics and proof-theory of first-order logic (FOL). We will learn how to “speak” the language of FOL, study the method of truth tables, become proficient in giving formal proofs, and learn how to construct and argue about first-order interpretations. These methods will enable you 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 truth-functional 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.

The kinds of things you will learn are mainly of three sorts: (1) symbolize sentences of English in a formal language, (2) give counterexamples (truth tables, interpretations) that show various things, (3) give formal proofs. Much of this will be completely new and not something that’s like anything you’ve done before. It will not feel like what you might think of as philosophy. There will be lots of symbols. This is a course in formal logic, not a course on how to think or how to avoid fallacies.

How will the course be run?

The course will be delivered in a hybrid synchronous/asynchronous model. There will be readings, prerecorded lecture videos, discussion boards, and quizzes on the course website (D2L). You can read, watch, and participate in discussions more or less when you choose, so that part of the course will not happen at the same time for everyone (i.e., it is asynchronous). There will also be weekly Zoom sessions where everyone will participate at the same time (i.e., those are synchronous):

What?When?Who?
LectureTR 14–14:50Instructor
TutorialsF 9–10:50, 13–14:50TAs

In lecture, we will go through exercises, review material, ask and answer questions, sometimes in small groups (breakout rooms). In tutorial you will have a choice between doing more exercises, or working in small groups on your problem sets.

What prerequisites do I need for this course?

None. There are no prerequisites.

What will I learn in this course?

By the end of the course, you should be able to …

  1. work with the formal languages of truth-functional and first-order logic, with the ability to symbolize natural language sentences in a formal language.
  2. use truth tables to evaluate sentences and arguments in truth-functional logic.
  3. understand the basic semantic concepts such as validity, entailment and logical equivalence, when they apply and how they can be used.
  4. construct correct derivations in a natural deduction system for truth-functional and first-order logic, with and without identity.
  5. use a proof system to determine whether or not a sentence is a logical truth, whether an argument is valid, and whether two formal sentences are equivalent.
  6. construct interpretations that make first-order sentences true or false and use them to show that arguments are invalid.
  7. appreciate some basic metatheoretic results, such as truth-functional completeness, and soundness and completeness of a natural deduction system for truth-functional logic.
  8. be able to articulate clear questions, explain logical concepts, and guide others through logical problems.

What will I have to do in this course?

Visit the D2L/Brightspace site

The course has a D2L/Brightspace site. You will find (information on) course readings, videos, scheduled Zoom meetings, assignments, quizzes, tests, grades, and a discussion board there. Any updates, including revisions to the course schedule, PASS sessions, course schedule, will be posted there. To make sure you don’t miss a deadline or an important update, please review your notification settings.

Read the textbook

The textbook is:

P.D. Magnus, et. al., forall x: Calgary. An Introduction to Formal Logic (Fall 2020 edition). forallx.openlogicproject.org

It is free and available on D2L in PDF. It comes in two formats, and many of the exercises in it have solutions in the accompanying solutions manual. You may also purchase a paper copy if you like.

You should read along as we cover the topics in the course. Each unit in the Content section on D2L will tell you which chapters of the books to read. We won’t cover, and you won’t be tested on, everything in the book, but we will also cover a few topics not in it.

Watch some lecture videos

Each week, there will be a few lecture videos. You should watch these videos in preparation for the synchronous class meetings, i.e., before Tuesday. The videos are posted on D2L, as are the slide decks that go with them.

Attend Zoom sessions

We’ll have Zoom sessions every week on Tuesdays and Thursdays, 14:00–14:50. During these meetings, we will work on problems related to the week’s material, often in small groups. I’ll assume that you’re prepared (i.e., have watched the lecture videos and done the reading). There will also be opportunity for Q&A and discussion. Recordings will be available; attendance is strongly recommended but not strictly mandatory.

Work on practice problems

Every week you will complete a few practice problems. Problem sets are designed to practice the techniques covered in class and deepen your understanding of the topics covered that week. They will all be completed online, either on D2L or on a site called carnap.io. There will be plenty of these: some ungraded problems for practice, problems we work on together in lecture or tutorial, but especially a weekly problem set.

You should complete these problem sets by midnight Friday. Feel free to work on them with other students! TAs will be available Fridays (during scheduled tutorial times) on Zoom to help with problem sets and to answer questions. You do not have to go to the session corresponding to your assigned tutorial time, however, to balance attendance, it is recommended that you do.

You only get proficient in logic with practice, so make sure you put in effort and don’t just let your friends or the TAs tell you the solutions. (If you do, you won’t be able to complete the quizzes and challenge problems…)

Ask and answer questions on the D2L discussion board

Every weekly topic will have a dedicated discussion board where you can ask questions. You might want clarification on something in lecture or the textbook, or you’re stuck on an exercise and need a hint or have someone to tell you what the problem with your proposed solution is. Your instructor and TAs will help. One of the course outcomes, however, is to make you a better, more collaborative learner and teacher yourself. So feel free to attempt to explain things others ask questions about, and provide hints for those who get stuck yourself.

Complete quizzes and challenge problems

The reading, videos, in-class groupwork, and work on problem sets will prepare you for the weekly quizzes and challenge problems. Quizzes are multiple-choice and are given on D2L. They will be open book, untimed, and you have three attempts at each. In addition, each major learning outcome has a challenge problem associated with it: this is like a problem (or short set of problems) on the problem set, except that it is timed and you must solve it on your own. Quizzes and challenge problems are due Sundays at midnight (for topics covered the preceding week).

A typical week

Every week has the same schedule:

  • Monday: Review the lecture videos and read the assigned textbook sections.
  • Tuesday: Attend Zoom session.
  • Wednesday: Start problem set, quiz.
  • Thursday: Attend Zoom session.
  • Friday: Attend tutorial. Finish problem set.
  • Sunday: Finish quiz and challenge problem.

PASS sessions will be held on Monday, Tuesday, and Wednesday.

What do I need for all that?

This course will be delivered online. Two hours a week will take place via Zoom at the set lecture times, but most content will be delivered asynchronously (that means: not at a specific time). To access the material and complete the assignments you will need a computer and access to the internet (for some things a smartphone or tablet are enough, but a desktop or laptop with a keyboard, mouse, and large-ish screen will be much more comfortable).

You will need an account with the UCalgary IT service, without which you cannot access D2L.

To participate in synchronous groupwork sessions, and to communicate with your instructor, TAs, and fellow students, you need a Zoom account. To participate with audio and video, you need a microphone and webcam, ideally on a computer with keyboard and mouse. However, attending the synchronous Zoom sessions is not required to pass the course.

Instructions for getting IT and Zoom accounts, accessing D2L, and additional tips for how to best learn online are available at:

taylorinstitute.ucalgary.ca/learning-continuity

How will my grade be determined?

There will be no registrar-scheduled final exam.

Completing activities

The aim of this course is for you to become proficient in the learning objectives listed below. Your success in this will be assessed by the number of activities (problem sets, quizzes, and challenge problems) you complete successfully. There are a total of 12 activities of each kind, one per week. Each activity has a minimum level of performance that counts as “complete ().” Completing an activity roughly corresponds to earning at least a B on that activity. Problem sets and quizzes have a higher level of performance that earns you a “complete+ (✓+).” Completing a quiz or problem set at this level roughly corresponds to an A.

Instead of earning point scores on each, and then determining your final grade based on some frankly arbitrary system of weights, averages, and cutoffs, your final grade will be determined on the basis of how many activities you complete. This means, more or less, that your final grade is determined by how many of the learning objectives you show proficiency in by the end of term.

Problem sets: You have to score 80% on a problem set for it to count as complete. If you score 95%, you earn a “complete+.”

Quizzes: A quiz counts as complete if you score at least 80% on it, and complete+ if you score 95%.

Challenge problems: Each week you have a challenge problem to complete. Challenge problems will be timed (usually 30 minutes), but you will have several days during which you can complete them.

You get immediate feedback on your activities, so you will know right away if you have completed it.

Collaboration: In addition to the learning outcomes, an objective of the course is the development of collaborative study habits. You should become able to ask clear questions about the course material and problem sets in class and on the discussion board, to explain topics to and answer questions of your peers, and to work with others in small groups during class time. You will not formally be assessed on this learning outcome.

Final grades

Your final grade is a record of how many learning objectives you have achieved, based on how many activities (problem sets, quizzes, challenge problems) you have completed. This mapping of performance on activities to letter grades is more complicated than a points system with percentage cutoffs, but it captures more accurately how much you’ve shown to have learned in the course.

The following table lists how many activities of each type you have to complete in order to earn a given grade). “Total” is the overall number of activities you must complete at least. For A-range grades, you must also earn complete+ marks on a sufficient number of activities. The given numbers are minimum requirements. You earn the highest grade you qualify for on the basis of the number of ✓’s and ✓+’s you have earned in each category, and the total number you have earned.

GradePSQCPTotal
A+12✓+12✓+12✓36
A12✓/10✓+12✓/10✓+12✓36
A−11✓/8✓+11✓/8✓+11✓33
B+10✓10✓10✓32
B10✓10✓10✓30
B−8✓8✓8✓28
C+8✓8✓8✓26
C8✓8✓8✓24
C−6✓6✓6✓22
D+6✓6✓6✓20
D6✓6✓6✓18

For instance, to earn a B−, you must complete 8 of each activity (that’s 24 total) but overall must complete at least 28 activities (so e.g., an additional two problem sets and two quizzes, or two problem sets, a quiz, and a challenge problem). For an A, you must complete all activities, and for 10 problem sets and 10 quizzes you must receive a ✓+. (An A+ requires 12 ✓+ on problem sets and quizzes, and an A− requires 11 problem sets and quizzes completed, of which 9 must be ✓+.)

Note that the number of activities alone does not guarantee a higher grade. E.g., if you have completed all 12 problem sets and 12 challenge problems, but only 8 quizzes, this earns you only a B−, not a B+ even though you have 32 activities completed in total. Also, ✓+ only play a role in earning A-range grades. So 8 ✓+ on problem sets, 8 ✓+ on quizzes, and 8 ✓ on challenge problems is still just a C.

Partial credit, retakes, tokens

Grades in this class are based on how many learning objectives you show proficiency in. Proficiency is an all-or-nothing affair: for instance, you have either completed a truth table correctly or you did not. You can think of a learning objective as a hurdle you have to clear; either you clear it or you don’t. Your overall performance is determined by how many hurdles you clear throughout the course, and how high those hurdles are.

For this reason, there will be no partial credit. You won’t get half the marks for jumping half as high as necessary. There are deadlines, since the course needs some structure, but mainly because otherwise the logistics of marking and recording three dozen activities for 200 students would be unmanageable.

However, what matters is that you achieve the learning objectives, not when you achieve them or how long you have to work at it. It’s also very important in this class that you don’t fall behind and that if you do, you catch up soon (otherwise you will not be able to understand the subsequent material).

So, we allow you to revise or repeat activities, within limits. Every student gets five tokens to spend during the term. You can spend a token to do any of the following, in any order and as many times as you have tokens left:

  1. extend the deadline for all weekly activities by 48 hours;
  2. complete a problem set after the deadline;
  3. buy three additional attempts on a quiz;
  4. buy a chance to repeat a challenge problem.

To extend a deadline, send an email to . For the other possibilities, you will be able to request spending a token once a week (by Friday midnight) and will then have one week (until the following Sunday) to complete the activity. You have two chances to spend a token on any given activity, i.e., a total of 3 weeks after the original deadline to complete any activity. (In order to meet the grade submission deadline, the activities of the last week can only be repeated once, and you’ll have less than three weeks to re-do activities of the last three weeks.)

For instance, say you don’t manage to complete a challenge problem in one week, or you score a ✓ on a quiz but would like a ✓+. The following week, before Friday, you tell us you’d like a chance to retake it. We will set you a new challenge problem (or give you three additional attempts on the quiz) on Saturday, and you have until the following Sunday to complete it. If you don’t complete the activity on the re-take, you can request another re-take. (Since you have to tell us that you want another re-take by Friday, you have to attempt the first re-take before Friday, of course. But you will know immediately whether you have passed or not.)

Note that re-takes of challenge problems have different questions than the originals, and quizzes have randomized questions.

Are there PASS sessions for this course?

Yes, this course is supported by the PASS (Peer Assisted Study Sessions) program. PASS provides students with free, organized study groups facilitated by a student who has been successful in the course before. Attending PASS can help you build your understanding of course content as well as learn valuable study skills which will help you to succeed in the course. You will meet your PASS leader and receive more information in the first weeks of classes.

What course policies should I be aware of?

Recording Zoom sessions

In order to allow students to review synchronous sessions, these Zoom sessions will be recorded and the recordings made available to students in the course. Recorded sessions will not be used for any other purpose. Nevertheless, if you object to your image or voice being recorded, you should make sure to turn your video off and set your microphone to mute. (You can use the Zoom chat function to ask questions.) Breakout rooms (small groups) will not be recorded, and as a courtesy to your fellow students, you are encouraged to use video and audio while in a breakout rooms. Tutorials will also not be recorded.

Conduct

Learning can only happen well if everyone feels like they belong and are free to ask questions and participate in discussions. It is partly on you to make sure our course is such a space. So please be respectful, positive, and constructive in your participation in the course. It should go without saying, but do not post (links to) anything racist, mysogynist, or homophobic, or NSFW, and don’t stalk or harrass your fellow students or instructors. Also, do not share links or passwords to live or recorded Zoom sessions outside the course.

Late policy

If you do not complete an assignment by its deadline, it counts as not completed. However (see above) you can spend tokens to extend a deadline by 48 hours, or to complete an assignment after the deadline.

If there are factors beyond your control, and which you could not reasonably have planned for, which prevent you from completing activities (illness, family emergency, etc.) please contact the instructor so we can make arrangements. Please do so as soon as possible. You will not have the opportunity to make up work you missed early in the term if you don’t tell me until the last week of term.

Checking your grades and reappraisals of work

University policies for reappraisal of term work and final grades apply (see the Calendar section “Reappraisal of Graded Term Work”). In particular, term work will only be reappraised within 10 calendar days of the date you are advised of your marks. Please keep track of your assignments and your marks (check them on D2L). Grades do not automatically update on D2L; we will typically post an announcement when new grades are available. You should save work you submit, e.g., by taking a screenshot.

Ok, what are those learning objectives you’ve been talking about?

The following learning objectives are divided into twelve general topics. Each of these topics will be covered in the respective week of term. (Approximately: especially Topic 4 requires a bit more time so we’ll start it in week 3 and will still talk about it in week 5. We’ll start topic 11 already in week 8. So, lecture videos and readings might preview some content covered in detail later. Problem sets for a particular week may include problems from those previewed topics or review and continue topics covered earlier, and similarly quiz questions. The challenge problems, however, will only test the topic covered the week before.)

Learning objectives numbered (a) and (b) correspond to a basic level of proficiency. Learning objectives numbered (c) are more advanced (roughly, you are expected to show proficiency in them to earn an A). Two harder questions on each problem set and quiz test for learning objectives numbered (c).

  1. Arguments and validity in English
    1. I can correctly state the definitions of validity, equivalence, and joint possibility of English sentences and arguments, and identify premises and conclusions.
    2. I can correctly assess an English argument for validity.
    3. I can clearly and cogently explain why an argument is or is not valid.
  2. Symbolization in TFL
    1. I can identify correctly symbolized English sentences involving “and”, “or”, “not”, and “if-then”, given a symbolization key.
    2. I can correctly symbolize English sentences involving “neither nor”, “not both”, “unless”, “only if”, and exclusive “or.”
    3. I can recognize English sentences that are ambiguous and symbolize different readings in TFL.
  3. Notions of logic in TFL
    1. I can correctly state and apply the definitions of entailment, equivalence, joint satisfiability, and tautology in TFL.
    2. I can construct the complete truth table for a sentence or sentences of TFL and use it to determine entailment, satisfiability, equivalence, and tautologies, and to find satisfying valuations.
    3. I can correctly and clearly state and explain relationships between entailment, satisfiability, equivalence, and tautologies.
  4. Proofs in TFL
    1. I can apply the rules of inference of natural deduction for TFL, identify correct and incorrect proofs, and complete partial proofs.
    2. I can give correct formal proofs of arguments and theorems involving ∧, ∨, →, ¬, ⊥, and nested subproofs, using proof construction strategies.
    3. I can give correct formal proofs of theorems requiring the IP rule.
  5. Symbolization in FOL without nested quantifiers
    1. I can identify correctly symbolized sentences of English involving the quantifier determiners “all”, “some”, “no”, “any”, and the indefinite article involving no quantifier nesting.
    2. I can symbolize sentences of English including the quantifiers, indefinite articles, pronouns with quantified antecedents, truth-functional combinations of clauses, and comparatives.
    3. I can construct a key suitable for the symbolization in FOL of English sentences, symbolize complex sentences of English involving “only,” and use connectives of TFL to express properties and relations without predicate symbols given in the symbolization key.
  6. Interpretations
    1. I can identify the extensions of English predicates given a domain, present them as enumerations and graphical diagrams, determine the truth value of sentences of FOL without nested quantifiers or identity in a given interpretation, and identify witnesses and counterexamples to quantifiers.
    2. I can construct interpretations that make given sentences true or false and apply this to show non-entailment, satisfiability, and non-equivalence.
    3. I can determine entailment, non-satisfiability, and validity by arguing about interpretations.
  7. Proofs for FOL without quantifier nesting
    1. I can apply the rules of inference of natural deduction for FOL, identify correct and incorrect proofs, and complete partial proofs.
    2. I can construct formal proofs of arguments in FOL without nested quantifiers and not requiring IP.
    3. I can construct formal proofs in FOL requiring IP.
  8. Symbolization with nested quantifiers
    1. I can identify correctly symbolized sentences involving multiple determiners.
    2. I can symbolize sentences with multiple determiners and Donkey sentences.
    3. I can recognize scope ambiguity and symbolize all possible readings.
  9. Identity
    1. I can identify correctly symbolized sentences involving identity and definite descriptions.
    2. I can symbolize sentences with “else,” singular “only,” numerical quantifiers, and definite descriptions.
    3. I can symbolize complex sentences with “both” and “neither” used as determiners.
  10. Interpretations for full FOL
    1. I can determine the truth value of sentences involving nested quantifiers and identity in given interpretations.
    2. I can construct interpretations to make sentences with nested quantifiers and identity true or false and apply this to show non-entailment, satisfiability, non-equivalence, and non-validity.
    3. I can identify symmetric, reflexive, transitive, and anti-symmetric relations and apply symbolization and interpretations to illustrate these properties and their relationships.
  11. Proofs with multiple quantifiers, many-place predicates, and identity
    1. I can apply the rules of inference of natural deduction for FOL, identify correct and incorrect proofs, and complete partial proofs.
    2. I can construct proofs with nested quantifiers and identity.
    3. I can construct proofs with many-place predicates, nested quantifiers and identity, including the IP rule.
  12. Functional completeness and normal forms
    1. I can determine if a sentence is in CNF or DNF.
    2. I can convert a sentence into CNF or DNF using a chain of equivalences and find a sentence in CNF or DNF from its truth table.
    3. I can show that a set of connectives is functionally complete, and I can prove that some connectives are not functionally complete.