Introduction to Logic
CS157 Autumn 2023-2024
Lectures TTh 13:30 - 14:50 Nvidia Auditorium
Lessons Lecture Slides Lecture Recordings Ed Discussion Exams

Weekly Office Hours
Monday Tuesday Wednesday Thursday Friday
9:00 am - 11:00 am
Dominic
Zoom
11:00 am - 1:00 am
Constance
Zoom
4:00 pm - 6:00 pm
Olivia Lee
Zoom
4:00 pm - 5:00 pm
Mike
Gates 308
6:00 pm - 8:00 pm
Amelia
Zoom
12:45 pm - 2:45 pm
Josh
Zoom
2:30 pm - 4:30 pm
Olivia Weiner
Zoom
6:30 pm - 8:30 pm
Thomas
Zoom
1:00 pm - 3:00 pm
Chaitanya
Huang Basement
3:00 pm - 5:00 pm
Rahul
Wu Tsai 252

Goodbye

The course is now over. Students finishing the course: 185; mean of overall scores: 86.1; standard deviation: 21.> As always, you can see solutions to all problems by clicking on the links at the bottoms of the quiz and exam pages. And you can review your submissions and see the scores for those submissions by clicking on the Profile link in the upper right corner of the exam pages. If you want to see your letter grade, you can check Axess after Thursday.

Those of you who made it to the end should feel pretty good - you have seen a lot of material, covered more rapidly and at a deeper level than in most introductory courses in Logic. If you want to learn about how this course differs from other Logic courses, take a look at The Herbrand Manifesto - Thinking Inside the Box. It is a little technical but summarizes the key differences without going into too much detail.

The course materials will remain accessible online in perpetuity. Go to http://intrologic.stanford.edu and click on Learners. If you want a hardcopy version of the notes, you can purchase the book from Amazon. However, there is nothing there that is not available online.

We put together the course website with the idea of making the materials available for free and accessible to all. Over the years, we have improved these materials with the help of students like you. However, there is always more to be done. If you have specific suggestions on how to improve the course, please send suggestions (email: genesereth@stanford.edu).

Finally, I want to thank those of you who participated in the Ed discussions. There is only so much one can teach in the form of online notes and exercises and extras and puzzles and quizzes. Experience has shown that students benefit from the help of others and benefit from helping others. Hopefully, those of you who helped others learned something in the process. And, in any case, you did a good thing.


Final Week

Quiz 3 is now over. Takers 179; mean 81.2; standard deviation 32.4. Many, many more perfect scores that on past quizzes. For those who did not ace the quiz, remember that you get another chance this coming week on the final.

The exams will be administered online, as in the past, accessible via the Exams link above. You may do as many or as few exams as you like, in any order that you like. You will have 75 minutes to complete each exam you choose to take. You will be able to take each exam any time during the 12 hour period from 10:00 am PST through 10:00 pm PST on Tuesday (December 12). Note that no submissions will be accepted after 10:00 pm PST.

Each of the three exams will cover material from one of the three units of the course - one on Propositional Logic, one on Relational Logic, and one of Functional Logic. There will be five questions on each exam, and the difficulty will be approximately the same as on the quizzes.

The exams are completely optional. If you take an exam and your score is higher than the score on the corresponding quiz, we will use your exam score in place of your quiz score in computing your final grade. Otherwise, we will use your quiz score. There is no penalty for not taking the exams.

Finally, for those of you hoping to earn discretionary credit by doing puzzles, note that the deadline for submitting solutions is this Sunday (December 10) at midnight. (As always, you can submit by private post via Ed. We cannot reply to every post, but we will notice if you submit a solution.)


Week 10

This is the last week of the course (except for the final exams). The only thing on the schedule this week is a quiz on Functional Logic. The quiz will take place on Thursday at the usual time (unless you have made prior arrangements). The format will be the same as that of the previous quizzes. Your timer will start when you click on the link labeled "Quiz 3" on the Exams page. The quiz will cover the material in Lessons 11, 12, 13, and 15 plus the coverage of the "rational equation" and "rational induction" rules of inference from the last lecture.


Week 9

Welcome back. Hopefully, you had a good Thanksgiving break and are refreshed and ready to finish up your coursework for the quarter.

We are just about done with our last Unit. There is just one more topic to be covered, viz. equality. The basic idea is simple. And it should be familiar; it connects the things we have been talking about with the sorts of mathematics you have been learning for years. Moreover, we get to see how induction can be applied to solve problems involving "recurrence relations" that arise frequently in Computer Science.

In order to make time for this topic, we have decided to forego the material on Resolution Proofs, i.e. Lesson 14. You should feel free to read through that material and ask questions, but we will not be covering that topic in lecture or on the quiz / exam. Instead, we recommend you look at the lesson on equality. We will also have a lecture on this topic on Tuesday of this coming week.

On Thursday, we will have our final regular class session. We will review the material from the third unit of the course. We may also take a peek at extensions to what we have seen.

A reminder that we will have a quiz on Functional Logic on Thursday, December 7. The logistics will be the same as in the past quizzes. Also, we will have an optional final on Tuesday, December 12 in case you want to improve your quiz scores. (Or in case just want to do more Logic!). Details to follow.

Meanwhile, in case you want something to do, there are two new puzzles - the game of Nim (impress your friends by always beating them) and our final puzzle, appropriately entitled Enlightenment. For those of you who have done the others, these two should be relatively easy.


Thanksgiving

It is Thanksgiving week in the US. Time to step back and think about all of the good things in life - the things for which we are grateful and the things we can do to help others in return. Something for which you can be grateful - no work on the course this week. Unless, of course, you want to spend some time working on more proofs. Great way to have fun with friends and family! We will be back again next week with our last lecture and a review. Happy Thanksgiving.


Week 8

Quiz 2 is now over. Students 182; mean 80.1; Median 90; standard deviation 25.4. Some people did very well; there were quite a few perfect and near-perfect scores. Others struggled with some of the questions. As always, you can check your profile to review your work, see your scores, and view solutions to all of the problems. In any case, remember that, if you did not do as well as you hoped, you get another chance to show off your mastery of the material by taking the alternate quiz during Finals week.

Relational Logic allows us to axiomatize worlds with varying numbers of objects. The main restriction is that the worlds must be finite (since we have only finitely many constants to refer to these objects). Often, we want to describe worlds with infinitely many objects. For example, it would be nice to axiomatize arithmetic over the integers or to talk about sequences of objects of varying lengths. Unfortunately, this is not possible due to the finiteness restriction of Relational Logic.

One way to get infinitely many terms is to allow our vocabulary to have infinitely many object constants. While there is nothing wrong with this in principle, it makes the job of axiomatizing some concepts effectively impossible, as we might have to write out infinitely many sentences.

Luckily, there is an alternative to Relational Logic, called Functional Logic, in which we can name infinitely many objects with a finite vocabulary. The trick is to expand our language to include not just object constants but also function constants. By writing complex terms using these constants, we get infinitely many names for objects; and, because our vocabulary is still finite, we can finitely axiomatize some things in a way that would not be possible with infinitely many object constants.

In dealing with Functional Logic, we proceed through the same stages as in Propositional Logic and Relational Logic. We start with syntax and semantics. We then discuss evaluation and satisfaction. We see how to use Fitch with Functional Logic, and we see a new type of inference - mathematical induction.

A cautionary note. As we have seen, there is a sound and complete proof procedure for Relational Logic (i.e. Fitch). Unfortunately, this proof procedure, while sound for Functional Logic, is not complete. Moreover, even if we add in induction, the procedure is still not complete. In fact, it is possible to show that there is no such sound and complete proof procedure for Functional Logic. As so often happens, increases in expressiveness lead to decreases in completeness and computability.

New puzzles this week - Logicians (master logician Mike is back), Nations (solve problems in World politics), and Zoom (an education-related puzzle).


Week 7

Here we go again - another week of reckoning - our second midterm quiz. The quiz will take place on Thursday. The format and timing of this quiz will be the same as for the first. No changes.

You can access the quiz page by clicking on the Exams link in the command bar above. The Exams page provides details about the quiz format and the procedures for taking the quiz. At the appropriate time, there will be a link to the actual quiz. And, a day or so after you have taken the quiz, there will be a link to review solutions and your scores.

As before, in order to access this page, you need to sign in. If you already have a passcode, sign in using your email address and this passcode. If you do not yet have a passcode, press the Sign Up button on the Sign In page; enter your Stanford email address on the resulting form; and check your email for your passcode. If you have any problems, let us know immediately.


Week 6

We have finally begun our discussion of Relational Logic. Relational Logic is more complex than Propositional Logic, but it is also more useful. Useful in thinking and communicating and useful in interacting with logic-enabled Computer Systems.

On Tuesday of this week, we will look at a natural deduction proof system for Relational Logic - an extension of the Fitch system we saw for Propositional Logic. And, on Thursday, we will have a review session in preparation for our next quiz.

Based on our discussion of Propositional Logic proofs, I think I can say with confidence that at least some of you have found that generating proofs is not easy. Exactly so. Proving things, even very simple things, can be difficult. It depends on the proof system. What is easy in one system is often difficult in another and vice versa. There is no best proof system for all problems.

One thing you should take away from these proof exercises is that finding proofs is a process of search in a space of possibilities. Another is a growing sense of confidence that everything that is logically entailed by one's premises *can* be proved (albeit with some difficulty). And perhaps a belief that this search process can be automated (which by and large is correct).

Once, again there are puzzles for you to work on this week. The first (Prisoners) is a bit tricky but doable with a bit of careful thought. Think logically and save as many of your fellow prisoners as possible. The second puzzle (Chessboard) is much more difficult. A few people get it right away. However, most do not. In fact, there are reports of mathematicians spending months on this problem without getting a fully satisfactory answer. Upshot: You might want to skip this one. Of course, if you are obsessed with puzzles and have lots of spare time on your hands, feel free to give it a go.


Week 5

First quiz out of the way. 182 takers; mean 75.2; median 76; standard deviation 20.8. 41 perfect scores! You can find your scores by going to the exams page, signing in, and clicking on the "Profile" link in the upper right hand corner. You can view your submissions by clicking on the appropriate row of the table at the bottom of this page. You can check the solutions for all problems by clicking on the solutions links at the bottom of the Quiz page.

We know that the quiz was tough for some of you. Not so much for others. For some of you, proofs were the hardest part. No surprise there. Doing proofs can be challenging. But practice helps. Doing the proofs in the exercises is the best preparation. (Really doing the proofs, not just looking at the answers.) You can develop the skill, but you need to practice, practice, practice. Do those exercise proofs; prove the results in the libraries. Remember to use the reasoning tips when you get stuck. For those of you who did not succeed, take heart - we will offer an *optional* final exam that will give you another chance to show what you have learned. More on that later.

The first part of the course is now done. We have reached the end of our treatment of Propositional Logic. Propositional Logic is simple and elegant. It has limitations, but it also has many applications. It is pedagogically valuable in that it provides us with a simple setting in which to look at the main concepts of Logic - syntax and semantics, validity and contingency and unsatisfiability, logical equivalence and entailment and consistency, and proofs. In the weeks ahead, we will be revisiting these concepts in the context of a more complicated logic, and it will be good that we have already examined these concepts in this simpler setting.

This coming week, we begin our look at Relational Logic. Relational logic is more natural than Propositional Logic, and it has more practical uses. For some, the material may be more difficult. Start early; don't wait till the next quiz. Read the notes. Do the exercises. Attend the discussion sessions or use Ed to talk about things you find confusing.

You should try to get through the sections and exercises of Lessons 7 and 8 and 9 this week. There is also some optional material in the lessons, and we recommend that you take a look. At the very least, you should solve the Minefinder problem in Lesson 7. And pay particular attention to Exercise 8.3! Many people have trouble with this exercise.

Now that the first quiz is out of the way, there are also some new puzzles for you to consider. Cards is slightly challenging, but it has an especially elegant solution. And then there is the Safecracking puzzle. Yet another practical application of Logic!


Week 4

This is it - the week of reckoning - our first quiz. There will be a review session in class on Tuesday. The quiz will take place on Thursday. Best preparation - read the notes and do the exercises. Good luck! (Actually, if you can do the exercises, you won't need luck.)

For those of you who want more practice, we have made the quiz and exam questions from prior years available. Click here to access these questions. In some cases, you can submit your answers, get grades, and see the solutions. For quizzes and exams from earlier years, you can see the questions, but there are no answers. Note that these questions and solutions will be hidden during quizzes and exams.

As previously mentioned, the quiz will be entirely online. You can access the quiz page by clicking on the Exams link in the command bar above. This page provides details about the quiz format and the procedures for taking the quiz. There is a link to a practice quiz; and, at the appropriate time (on Thursday), there will be a link to the actual quiz. And, starting on Friday, there will be links to review the solutions and your scores.

Note that, in order to access this page, you will be need to sign in. If you already have a passcode, you can sign in using your email address and this passcode. If you do not yet have a passcode, press the Sign Up button on the Sign In page; enter your Stanford email address on the resulting form; and check your email for your passcode. If you have any problems, let us know immediately.

We suggest you look at the Exams page as soon as possible. Ideally, in the next day or so, you will have gotten your passcode, you will have read the instructions, you will have taken the practice quiz, and you will be ready for the actual quiz. Do it now!


Week 3

The Hilbert proof system is conceptually quite simple. However, it is not particularly practical. Most people find it difficult to decide which schemas to consider and how to instantiate them. The upshot is that it is difficult to produce proofs of even the simplest of results, and the proofs are often more verbose than they need to be.

The good news is that there are more useful proof systems, and this week we look at two such systems - Fitch and Robinson. Fitch simplifies the creation of proofs of implications by allowing one to make assumptions, derive consequences, and then conclude implications involving those assumptions and consequences. Robinson simplifies the creation of proofs by mapping all sentences form Propositional Logic into "clausal form" and then applying just a single rule of inference to these expressions. None of these proof systems makes the creation of proofs easy, but experience suggests that Fitch and Robinson make things easier than Hilbert.

Many of you will find that creating proofs is more challenging than the exercises in preceding lessons. Just remember, when you are doing a proof, first formulate a plan for the proof. Often, this means starting at the end and thinking about how to derive the desired conclusion and then figuring out how to prove the intermediate results you need to prove the final result.

In case you need a break from proofs, there are two new puzzles for you to work on this week - Counterfeit and Pills. Counterfeit is quite easy; Pills is more difficult.


Week 2

By this point, you should have mastered the material in Lessons 1 and 2. From Lesson 1, you should be familiar with the main topics of the course - logical languages, logical entailment, and logical reasoning. From Lesson 2, you should understand the syntax and semantics of Propositional Logic and the notions of evaluation and satisfaction.

In fact, you should be more than familiar with this material - ideally, you should be saying to yourself (and others) that, when all is said and done, this stuff is pretty easy. In fact, it *is* easy. There is more difficult material to come. Including material that is likely to be less familiar; but, hopefully, after we have gone through it all, you will think that that is easy too!

We start this week with a discussion of the material in Lesson 3. This lesson deals with the logical properties of sentences, e.g. validity and satisfiability. And it introduces and distinguishes the central notions of logical equivalence and logical entailment and logical consistency. These ideas are all fairly simple in the context of Propositional Logic; they are more subtle in the context Relational Logic and Functional Logic. It is a good idea to ensure you understand the nuances in this simple setting before we get to more complicated logics later in the course.

This week, we also begin our discussion of proofs - rules of inference, direct proofs, and the Hilbert proof system. After this week, you should be comfortable doing Hilbert proofs; and you should be ready to opine about the strengths of the Hilbert system (sound, complete, and conceptually simple) and its weaknesses (not very practical).

Remember that there are some useful tools available under the Tools tab, notably Babbage (for generating simple truth tables) and Boole (for generating multicolumn truth tables); and there is a proof editor for the Hilbert system, which offers features not found in the exercises.

There are also two new puzzles for you to consider. Rotors is easy, once you see the trick. Wine is a little more difficult but should not be a problem for computer scientists.


Week 1

Okay. We are on our way! The course begins now. On Tuesday, we will have an introductory lecture on the subject matter of the course and course logistics. On Thursday, we will have an introduction to Propositional Logic.

Lesson 1 is just an overview, and it is easy. That said, you should not shortchange the material. The lesson talks about the main ideas of Logic and how they relate to each other, and it provides a framework for organizing the rest of the material in the course.

Lesson 2 introduces the syntax and semantics of Propositional Logic as well as the essential concepts of evaluation and satisfaction. You should get comfortable with the language and you should get comfortable evaluating sentences and finding truth assignments that satisfy those sentences.

Be sure to do the online exercises. This week's exercises are easy. They are there mostly for you to get experience with the technology so that you will be ready to deal with the exercises and quizzes to come. However, the exercises become more difficult as the course progresses, and they are good preparation for the questions on the course quizzes. (Hint. Hint.)

You should also drop by Ed Discussion to check out what others in the class are saying. There are some subtleties in Logic that you can miss and that can lead to confusion. Communicating with others on the Ed Discussion forum is a good way to deal with these subtleties. And, even if you think you understand everything, you might consider using Ed Discussion to help others and thus consolidate your understanding of the issues.

Finally, you should check out the puzzles. There are fifteen of these in all, one per lesson. Some of the puzzles (like the first) are extremely easy; others are more difficult; and one is very hard. The puzzles are not a required part of the course. However, in the past, students have found them worthwhile and enjoyable. Also, your work on the more difficult puzzles may earn you discretionary credit.

Note from SCPD for those of you attending lectures in Nvidia: Video cameras located in the back of the room will capture the instructor presentations in this course. For your convenience, you can access these recordings by logging into Canvas. These recordings might be reused in other Stanford courses, viewed by other Stanford students, faculty, or staff, or used for other education and research purposes. Note that while the cameras are positioned with the intention of recording only the instructor, occasionally a part of your image or voice might be incidentally captured. If you have questions, please contact a member of the teaching team.


Welcome


Niels Bohr to Albert Einstein: "You are not thinking; you are just being logical."

Bertrand Russell: Mathematics (including Logic) may be defined as the subject in which we never know what we are talking about nor whether what we are saying is true".

CS 157 is a rigorous introduction to Logic from a computational perspective. It focusses on the encoding of information in the form of logical sentences; it covers various methods for reasoning with information in this form; and it provides an overview of logic technology and its applications (in mathematics, science, engineering, business, law, and so forth). Topics include the syntax and semantics of Propositional Logic, Relational Logic, and Functional Logic, validity, contingency, unsatisfiability, logical equivalence, entailment, consistency, direct deduction (Hilbert), natural deduction (Fitch), refutation reasoning (Resolution), mathematical induction, compactness, soundness, completeness.

The course is divided into three main sections - Propositional Logic, Relational Logic, Functional Logic (Logic with function symbols). See the table below for a tentative schedule of lessons, quizzes, and reviews.

WeekTuesdayThursday
1 September 26
Introduction
September 28
Propositional Logic
2 October 3
Propositional Analysis
October 5
Direct Proofs
3 October 10
Natural Deduction
October 12
Refutation Proofs
4 October 17
Review
October 19
Quiz 1

5 October 24
Relational Logic
October 26
Relational Analysis
6 October 31
Fitch Proofs
November 2
Review
7 November 7
No Class
November 9
Quiz 2

8 November 14
Functional Logic
November 16
Induction
Thanksgiving Week
9 November 28
Equality
November 30
Review
10 December 5
No Class
December 7
Quiz 3

11 December 12   3:30-6:30
Optional Final
 

This year, the lectures will take place in Nvidia Auditorium, and there will be in-person office hours with the teaching staff. All of the materials for the course are online. Click on the "Lessons" tab at the top of this page to access these materials. There are links to textbook chapters, lecture slides, interactive exercises, puzzles, and sundry other items.

Note that, as you proceed through the online materials, you may occasionally encounter technical problems. Apologies in advance if this happens to you. We are constantly working on the course. You may get extra credit for reporting such problems (especially if your reports are more constructive than irate).

Collaboration with your fellow students is acceptable and strongly encouraged. Feel free to discuss the subject matter and the problems either directly or using Ed Discussion. Our experience has shown that it is useful for students to work together to understand the material of the course and to solve problems. That said, you are expected to do quizzes in this course on your own; and you are responsible for understanding and being able to explain your answers.

Your grade for the course will be based on your scores on three online quizzes - one on Propositional Logic, one on Relational Logic, and one on Functional Logic. The first quiz will count for 40% of your grade; the second will count for 30%; and the third quiz will count for 30%. We will also award a few points of extra credit based on discretionary factors, such as class attendance, participation in the Forum, and work on the puzzles. As preparation for the quizzes, we highly recommend that you review the online exercises, as the problems on the quizzes will closely resemble these exercises. In the past, we have offered an optional final for those who wish to make up for weak performance on the quizzes. We are likely to do the same this year.

Safecracking Puzzle: There is a combination safe with four switches on the front, each with three positions (low, medium, and high). If the switches are set into an opening combination, then when you try to open the safe, it will open; otherwise, no dice. In general, there are 3^4 (i.e. 81) possible combinations. However, this is a cheap safe; and only two of the switches actually matter; if you set those two switches right, the safe will open. Unfortunately, you do not know which are the important switches or which positions work. What is the minimum number of combinations you must try that will *guarantee* to open the safe?

Suarez Puzzle: Suarez is a (slowly) recovering liar. He lies on six days of the week, but on the seventh day he always tells the truth. One week, he made the following statements on three successive days. Day 1: "I lie on Mondays and Tuesdays. Day 2: "Today, it's Thursday, Saturday, or Sunday. Day 3: "I lie on Wednesdays and Fridays." On which day does Suarez tell the truth?

Michael Genesereth
genesereth@stanford.edu
Office Hours: Tue 4:00 pm - 5:00 pm
Location: Gates 308
 
Dominic DeMarco
demarcod@stanford.edu
Office Hours: Mon 9:00 am - 11:00 am
Location: Zoom
Amelia Hardy
ahardy@stanford.edu
Office Hours: Tue 6:00 pm - 8:00 pm
Location: Zoom
 
Constance Horng
constanh@stanford.edu
Office Hours: Mon 11:00 am - 1:00 pm
Location: Zoom
Olivia Lee
oliviayl@stanford.edu
Office Hours: Mon 4:00 pm - 6:00 pm
Location: Zoom
 
Thomas Mayer
mayert@stanford.edu
Office Hours: Thu 6:30 pm - 8:30 pm
Location: Zoom
Chaitanya Patel
chpatel@stanford.edu
Office Hours: Fri 1:00pm-3:00pm
Location: Huang Basement outside Nvidia
 
Josh Singh
jsingh5@stanford.edu
Office Hours: Wed 12:45 pm - 2:45 pm
Location: Zoom
Rahul Mysore Venkatesh
rmvenkat@stanford.edu
Office Hours: Fri 3:00 pm - 5:00 pm
Location: Wu Tsai 252
 
Olivia Weiner
oweiner@stanford.edu
Office Hours: Wed 2:30 pm - 4:30 pm
Location: Zoom

Feedback