CIS 301, Logical Foundations of Programming, Fall 2013

Prerequisites: CIS200 or equivalent experience. Please see the instructor if you have questions.
A computer is not required for the course; you may do the computerized exercises in any of the KSU labs.

Objectives and Topics: We will learn how circuits and software are founded on symbolic logic, and we will see how every computer program contains a ``logical skeleton'' that forecasts the program's computation. We can use the logical skeleton as a mathematical proof of the program's correctness. We will also study symbolic logic itself --- what it looks like, what it means, and how to manipulate it within formal proofs. As time allows, we will learn useful programming techniques (that you are unlikely to see elsewhere) based on grammars, dynamic data structures, and logic programming.

Here is a summary of the topics covered; these are listed in the order that they will be covered from the course lecture notes:

  1. boolean operators and truth tables for analyzing simple circuits; equations as a circuit-design language; algebraic laws for equational systems
  2. deduction laws for imperative assignment; laws for conditional (if) commands; deducing logical properties of imperative programs
  3. logical properties of functions and procedures: pre- and post-conditions; global-variable invariants; invariants for functions that are recursively defined (call themselves)
  4. deduction law for while-loops; loop invariants; simple examples of quantification
  5. propositional symbolic logic in natural-deduction format; tactics for applying deduction laws; introduction to soundness and completeness; normal forms and resolution theorem proving
  6. logical laws for the quantifiers and their application to programs that manipulate data structures
  7. first-order unification and resolution theorem proving; logic programming in Prolog
  8. semantics of recursively defined data structures (e.g., trees) and the functions that process them; grammars and parsing; mathematical induction
Grading Class participation involves not just being physically present, but also actively contributing to the learning climate, by answering questions, doing simple exercises on the board, asking interesting questions, etc.

Final letter grades are not based on strict percentage cutoffs but are "curved" by taking into account the difficulty of the exercises and exams. Usually, but with no guarantee that it will apply also this year, it requires 80 % to earn an A, and 60 % to earn a B; 40 % to earn a C, and 20 % to earn a D. In general, my approach to grading is expressed well by this piece by S.A. Miller.

Homeworks are due almost every week and are to be submitted through K-State Online. Assignments that are late will not be graded, unless in case of documented medical or family emergencies.

Exams will be closed-book but you can bring up to two sheets (double-paged) of hand-written notes. The final will be comprehensive, but with emphasis on the last part of the course.

Grievances: If you think the instructor or the TA has made an oversight when grading your test or your homework, you are of course very welcome to ask for clarification. But complaints about judgment calls, like how much credit to give for a partially correct solution, are not encouraged (it is like arguing balls and strikes).

Drop policy: It is your responsibility to drop the course if you are enrolled but decide not to complete the course --- there are no ``automatic'' drops due to nonattendance. September 16 is the last day to drop for a 100 % refund; September 23 is the last day to drop for a 50 % refund; September 30 is the last day to drop a course without a "W" recorded on your transcript; November 1 is the last day to drop a course (with a "W"). [You should double-check these dates!]

Statement Regarding Academic Honesty
Kansas State University has an Honor System based on personal integrity, which is presumed to be sufficient assurance that, in academic matters, one's work is performed honestly and without unauthorized assistance. Undergraduate and graduate students, by registration, acknowledge the jurisdiction of the Honor System. The policies and procedures of the Honor System apply to all full and part-time students enrolled in undergraduate and graduate courses on-campus, off-campus, and via distance learning. The honor system website can be reached via the following URL: A component vital to the Honor System is the inclusion of the Honor Pledge which applies to all assignments, examinations, or other course work undertaken by students. The Honor Pledge is implied, whether or not it is stated: "On my honor, as a student, I have neither given nor received unauthorized aid on this academic work." A grade of XF can result from a breach of academic honesty. The F indicates failure in the course; the X indicates the reason is an Honor Pledge violation.

The homework exercises are meant to develop your skills. It is OK to discuss them with others and to ask for help with the tricky bits, but what you submit must be written/typed by you, and you must be able to reproduce it from memory, from scratch, whenever asked. That is, whatever you submit must be saved in your brain as well.

If you are in doubt about what is permissible, please ask me.

Statement Regarding Students with Disabilities
Students with disabilities who need classroom accommodations, access to technology, or information about emergency building/campus evacuation processes should contact the Student Access Center and/or their instructor. Services are available to students with a wide range of disabilities including, but not limited to, physical disabilities, medical conditions, learning disabilities, attention deficit disorder, depression, and anxiety. If you are a student enrolled in campus/online courses through the Manhattan or Olathe campuses, contact the Student Access Center at, 785-532-6441; for Salina campus, contact the Academic and Career Advising Center at, 785-826-2649.

Statement Defining Expectations for Classroom Conduct
All student activities in the University, including this course, are governed by the Student Judicial Conduct Code as outlined in the Student Governing Association By Laws, Article V, Section 3, number 2. Students who engage in behavior that disrupts the learning environment may be asked to leave the class.

Statement for Copyright Notification
Copyright 2013[Torben Amtoft] as to this syllabus and all lectures. During this course students are prohibited from selling notes to or being paid for taking notes by any person or commercial firm without the express written permission of the professor teaching this course.

Acknowledgment: The course material, including this syllabus, is adapted from the class taught by David Schmidt, and also inspired by the class taught by John Hatcliff and Andrew Cousino.

Torben Amtoft