Introduction to Logic CS157 Autumn 2024 Lectures TTh 13:30 - 14:50 Gates B1

Goodbye

The course is now over. Students finishing the course: 130; mean of overall scores: 87.8; standard deviation: 15. 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 126; mean 83.2; standard deviation 34.5. Many, many more perfect scores than 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 10). Note that no submissions will be accepted after 10:00 pm PST under any circumstances.

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 on Term 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 8) 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 correct solution.)

Week 10

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

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

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 quiz. Happy Thanksgiving.

Week 9

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. And, in case you would like to learn more about logic, we will suggest some follow-on courses you might want to consider.

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

Week 8

Quiz 2 is now over. Students 127; mean 78.7; Median 91; standard deviation 25.2. 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 would have to write infinitely many sentences.

Luckily, there is an alternative to Relational Logic, called Term 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 Term 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 Term 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 Term Logic, is not complete for Term Logic. 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 Term 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. 131 takers; mean 72.0; median 76; standard deviation 21.5. 19 perfect scores and almost as many 96 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 our solutions for the 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. 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 review session 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.)

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 simple 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 from 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 Term 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 CGOE for those of you attending lectures in Gates: 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

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 Term 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, Term Logic (Logic with function symbols). See the table below for a tentative schedule of lessons, quizzes, and reviews.

This year, the lectures will take place in Gates B1 on Tuesdays and Thursdays form 1:30 to 2:50. There will be in-person office hours with the teaching staff. Times and locations will be posted on this page when they are finalized. 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 Term 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.