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

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 Tests 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 quiz day), 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 Tests 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 understand Hilbert proofs; and you should be ready to opine about the strengths of the Hilbert system (sound, complete, and conceptually simple) and its weaknesses (difficult to use and 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 Symbolic 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 represented 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, reasoning with equality, 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 from 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 will almost certainly do the same this year.