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.
How will the course be run?
The course will be delivered in a hybrind 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 at specific times where everyone will participate at the same time (i.e., those are synchronous):
|Group work||W 12–12:50||Instructor|
|Q&A/Office hours||F 12–12:50||Instructor|
|Problem workshops||WF 9–9:50, 10–10:50||TAs|
The group work session Wednesdays 12–12:50 is highly recommended, the others are optional. Some weeks group work may spill over to the Friday 12–12:50 session.
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 …
- work with the formal languages of truth-functional and first-order logic, with the ability to translate natural language sentences into a formal language.
- use truth tables to evaluate sentences and arguments in truth-functional logic.
- understand the basic semantic concepts such as validity, entailment and logical equivalence, when they apply and how they can be used.
- construct correct derivations in a natural deduction system for truth-functional and first-order logic, with and without identity.
- 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.
- construct interpretations that make first-order sentences true or false and to use them to show that arguments are invalid.
- appreciate some basic metatheoretic results, such as truth-functional completeness, and soundness and completeness of a natural deduction system for truth-functional logic.
- 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 office hours, PASS sessions, course schedule, and deadlines, 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)
It is available electronically on D2L. You should read it along as we cover the topics in the course.
Watch some lecture videos
Each week, there will be a few lecture videos posted on the D2L. You should watch these videos in preparation for the synchronous class meetings, i.e., before Wednesday. The videos are posted on D2L.
Attend Zoom meetings
We’ll have Zoom meetings every week on Wednesday, 12:00–12:50. During these meetings, we will work on problems related to the week’s material, often in small groups. There will also be opportunity for Q&A and discussion during the Wednesday and Friday Zoom sessions.
Work on practice problems
Every week you will complete a few practice problems. Most of the time these problems are completed online, but sometimes you will have to type or write your solutions up and turn in a PDF document on D2L. You should complete these problem sets by midnight Friday. Feel free to work on them with other students! TAs will be available Wednesdays and Fridays 9–10:50 (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 challenge quizzes and 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 two attempts at each. In addition, each major learning outcome has a challenge problem associated with it: this is like a problem (or set of problems) on the exercise set, except that it is timed and you must solve it on your own. Quizzes and challenge problems are due Mondays at midnight (for topics covered the preceding week).
What do I need for all that?
This course will be delivered online. One or 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 setting these things up and additional tips for how to best learn online are available at:
How will my grade be determined?
There will be no registrar-scheduled final exam.
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 you complete successfully. Each activity has a minimum level of performance that counts as “complete ().” Instead of earning point scores on each, and then determining your final grade based on some more-or-less 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: Each week you will be assigned a short set of problems designed to practice the techniques covered in class and deepen your understanding of the topics covered that week. You have to solve all required problems on the problem set correctly for it to count as complete. Typically there will be optional problems; if you solve those too you will get a “complete+.”
Quizzes: Each week you are given a short online quiz, consisting of about 10 multiple choice or matching questions. These quizzes test basic understanding and recall of the topics covered the week before. A quiz counts as complete if you score at least 80% on it, and complete+ if you score 100%.
Challenge problems: Each week you have a challenge problem to complete. Challenge problems will be timed (usually 30 minutes), but you will have 72 hours during which you can complete them.
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 be assessed on your participation on the discussion board by asking questions or answering other students’ questions. Every discussion board post or reply with at least 5 “upvotes” earns you a “complete” mark for the respective discussion topic (week), as does participating in the week’s group exercise.
Your final grade is a record of how many learning objectives you have shown to have mastered, 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 straightforward 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 (your “base grade”).
|Problem sets (12)||6||8||10||12 (6 ✓+)|
|Quizzes (12)||6||8||10||12 (6 ✓+)|
|Challenge problems (12)||6||8||10||12|
If you satisfy the criteria of a base grade either:
- You satisfy two of the criteria of the next higher grade; or
- You earn complete+’s on all problem sets and quizzes required for your base grade,
you earn a + after your grade. If you meet both of these conditions, you get the next higher grade, with a − after it.
For instance, to earn an A+ you have to meet the conditions for the A and also earn complete+ on all problem sets and quizzes. To earn an A−, for instance, you could complete 12 problem sets and 12 quizzes (two of the criteria for an A), complete 10 challenge problems (base grade is B), and earn complete+ on 10 of the problem sets and quizzes (the number required for a B).
If you earn at least 6 collaboration points, in (2) above, complete+ grades are only required on half the problem sets and quizzes for your base grade (10 for an A+). So, if you get 6 collaboration points, you could earn an A− with complete+ on only 6 problem sets and quizzes.
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. So, we allow you to revise or repeat activities, within limits. Every student gets three tokens to spend during the term. You can spend a token to:
- extend a deadline 48 hours;
- complete a problem set up to two weeks after its deadline;
- (re-)take a quiz or challenge problem, up to two weeks after its deadline.
To use a token to extend a deadline, or complete a problem set after the deadline, send an email to when you have completed the corresponding item. To use a token to (re-)take a quiz or challenge problem, complete the weekly re-take request (a D2L “quiz”).
Note that re-takes of quizzes and challenge problems have different questions than the originals.
Peer Assisted Study Sessions
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.
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.
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.
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 (extended illness, family emergency, etc.) please contact the instructor.
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 that will be tested by the weekly multiple-choice quizzes. Learning objectives numbered (b) are intermediate objectives which you’re expected to master to count as proficient in the respective topic (so, roughly, if you want a B you should show proficiency in them). They are tested in the weekly challenge problems. Learning objectives numbered (c) are more advanced (roughly, you are expected to show proficiency in them to earn an A). The optional problems on the weekly problem sets will mainly cover those.
- Arguments and validity in English
- I can correctly state the definitions of validity, equivalence, and joint possibility of English sentences and arguments, and identify premises and conclusions.
- I can correctly assess an English argument for validity.
- I can clearly and cogently explain why an argument is or is not valid.
- Symbolization in TFL
- I can correctly symbolize English sentences involving “and”, “or”, “not”, and “if-then”, given a symbolization key.
- I can correctly symbolize English sentences involving “neither nor”, “not both”, “unless”, “only if”, and exclusive “or.”
- I can recognize English sentences that are ambiguous and symbolize different readings in TFL.
- Notions of logic in TFL
- I can correctly state and apply the definitions of entailment, equivalence, joint satisfiability, and tautology in TFL.
- 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.
- I can correctly and clearly state and explain relationships between entailment, satisfiability, equivalence, and tautologies.
- Proofs in TFL
- I can apply the rules of inference of natural deduction for TFL, identify correct and incorrect proofs, and complete partial proofs.
- I can give correct formal proofs of arguments and theorems involving ∧, ∨, →, ¬, ⊥, and nested subproofs, using proof construction strategies.
- I can give correct formal proofs of theorems requiring the IP rule.
- Symbolization in FOL without nested quantifiers
- I can identify correctly symbolized sentences of English involving the quantifier determiners “all”, “some”, “no”, “any”, and the indefinite article involving no quantifier nesting.
- I can symbolize sentences of English including the quantifiers, indefinite articles, pronouns with quantified antecedents, truth-functional combinations of clauses, and comparatives.
- 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.
- 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.
- I can construct interpretations that make given sentences true or false and apply this to show non-entailment, satisfiability, and non-equivalence.
- I can clearly and correctly explain and prove statements about entailment, non-satisfiability, and validity by arguing about interpretations.
- Proofs for FOL without quantifier nesting
- I can apply the rules of inference of natural deduction for FOL, identify correct and incorrect proofs, and complete partial proofs.
- I can construct formal proofs of arguments in FOL without nested quantifiers and not requiring IP.
- I can construct formal proofs in FOL requiring IP.
- Symbolization with nested quantifiers
- I can identify correctly symbolized sentences involving multiple determiners.
- I can symbolize sentences with multiple determiners and Donkey sentences.
- I can recognize quantifier scope ambiguity and symbolize all possible readings.
- Interpretations for multiple quantifiers
- I can determine the truth value of sentences involving nested quantifiers in given interpretations.
- I can construct interpretations to make sentences with nested quantifiers true or false and apply this to show non-entailment, satisfiability, non-equivalence, and non-validity.
- I can identify symmetric, reflexive, transitive, and anti-symmetric relations and apply symbolization and interpretations to illustrate these properties and their relationships.
- I can determine the truth value of sentences involving identity in a given interpretation, and identify correctly symbolzied sentences involving identity and definite descriptions.
- I can symbolize sentences with “else,” singular “only,” numerical quantifiers, and definite descriptions.
- I can symbolize complex sentences with “both” and “neither” used as determiners, and construct interpretations for sentences involving identity.
- Proofs with multiple quantifiers, many-place predicates, and identity
- I can apply the rules of inference of natural deduction for FOL, identify correct and incorrect proofs, and complete partial proofs.
- I can construct proofs with nested quantifiers and identity.
- I can construct proofs with many-place predicates, nested quantifiers and identity, including the IP rule.
- Normal forms
- I can determine if a sentence is in CNF or DNF.
- 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.
- I can show that a set of connectives is truth-functionally complete, and I can prove that some connectives are not truth-functionally complete.