The Department of Computer Science & Engineering
CSE 463/563:
Spring 2005


(This is a living document; the latest version will always be available on the Web at: )

Last Update: 22 April 2005

Note: NEW or UPDATED material is highlighted

Index: Other Relevant Links:
  • Course Description
  • CSE 463/563 homepage
  • Prerequisites
  • Directory of Documents
  • Staff
  • Email Archive
  • Class Meetings
  • Texts
  • Important Dates & Tentative Schedule
  • Reading
  • Attendance, Homeworks, Projects, Exams, Listserv
  • Homeworks
  • Projects
  • How to Study
  • Grading
  • Incompletes
  • Academic Integrity
  • Classroom Disruptions


    Knowledge representation and reasoning (KRR) is the part of AI that is concerned with the techniques for representing and reasoning about the information to be used by an AI program. If, as
    Nicklaus Wirth has said, programs = algorithms + data structures, then AI programs = AI algorithms + KRR techniques.

    This course is the first semester of a 2-semester sequence (followed by CSE 663), but will be self-contained, concentrating on logic as a universal, basic, "core" KRR formalism.

    You will be introduced to the issues and techniques of representing and reasoning about knowledge and belief in a computer system and to the syntax and semantics of various representational and reasoning formalisms including classical propositional and first-order predicate logic and semantic networks.

    Some Useful Quotes about KRR:



    Dr. William J. Rapaport, 214 Bell Hall, 645-3180 x 112,
    Office Hours: Mondays, 2:00--2:50 p.m.; Tuesdays, 2:30--3:20 p.m.; and by appointment.

    Teaching Assistant:
    Albert Goldfain; Trailer E8, 645-3771,
    Office Hours: Mondays, 11:00 a.m.--12:00 noon; Tuesdays, 1:30--2:30 p.m.; and by appointment.


    LectureRapaport463: 356350
    563: 417467
    MWF1:00 - 1:50 p.m. NSC 228
    Recitation B1 Goldfain 463: 035498
    563: 479916
    M 2:00 - 2:50 p.m. Baldy 125
    Recitation B2 Goldfain 463: 445529
    563: 063312
    W 4:00 - 4:50 p.m. Talbert 113

    NOTE: Recitations begin Mon., January 24



    Note: UPDATED I have adjusted some of the dates below to reflect what we actually did in class, rather than on what I had hoped to do:-)

    (from B&L, unless otherwise noted
    W Jan. 19 Introduction to KRR Preface; Ch. 1
    F   21   Shapiro 2003
    M   24   Reddy 2003
    Recommended: Friedland et al. 2004
    M   31 SNePSLOG as an example of a real KRR system Ch. 2 (initial reading)
    W Feb.  2 Toy ontology: Blocks world;
    Syntax vs. Semantics
    F Feb.  4 Classical Logic: Propositional Logic
    syntax and semantics
    Rapaport 1992#1;
    plus one of:
    Bender 1996,
    Nilsson 1998,
    Coppin 2004
    M    7 propositional logic:

    syntax and semantics (continued)
    & proof theory

    see above
    W    9   Ch. 3 (initial reading)
    F   11 propositional logic:
    proof theory (cont'd.)
    & natural deduction
    see online readings, above
    W   16 propositional logic:
    natural deduction (cont'd.)
    & semantic inference (truth tables)
    see above
    F   18 Classical Logic: First-Order Logic (FOL) Ch. 2 (re-read carefully);
    Rapaport 1992#2
    M   21 Programming Project 1 assigned

    FOL syntax

    Re-read Ch.2: pp.15-18 carefully
    F   25 FOL:
    representation of English sentences
    parts of Ch.3
    "Representing English Sentences in FOL"
    W Mar.  2 Review for Exam  
    F    4 *** MIDTERM EXAM ***  
    W    7 FOL:
    model-theoretic semantics
    Re-read Ch.2, pp.18-24 carefully
    M    9 Review of Exam  
    F   11 FOL: model theory (cont'd.)
    NOTE: proof theory covered in recitation!

    Last R Day

    M   14 Spring Break  
    W   16 Spring Break  
    F   18 Spring Break  
    M   21 Automated Theorem Proving:
    Clause Form
    Re-read Ch.4 carefully
    W   23 Clause Form (concluded),
    Resolution, Refutation
    F   25 Resolution (concluded)  
    M   28 Unification  
    W   30 Unification (cont'd)  
    F Apr.  1 Unification (concluded)  
    M    4 Problems with FOL Shapiro 2000
    W    6 The SNePS KRRA System:
    SNePSLOG demos
    (see /projects/rapaport/563/)
    Martins 2002
    F Apr.  8 semantic networks
    SNePS: propositional representation
    Shapiro & Rapaport 1987
      OR (inclusive! :-)

    Shapiro & Rapaport 1995
    M   11 SNePS: propositional representation (cont'd) Recommended:
    Shapiro & Rapaport 1995
      OR (inclusive! :-)

    Shapiro & Rapaport 1987
    W   13 SNePS: SNeBR belief revision Recommended:
    Martins 2002

    Martins & Shapiro 1988
    F Apr 15 Project 1 Due
    Project 2 assigned!

    SNePS: node-based, path-based inference
    Martins 2002;
    Shapiro & Rapaport 1987
    M   18 SNePS: intensional KR Recommended:
    Shapiro & Rapaport 1987;
    SNePS readings on intensionality
    W   20 SNePS: ontology (case frames) Recommended:
    Shapiro et al. 1996
    F   22 SNePS: ontology (concluded) NEW
    Shapiro & Kandefer 2005
    M   25 Ontology Re-read Ch. 3;
    Smith 2003
    W   27 NEW
    Ontology (cont'd.)
    Mark & Turk 2003
    F   29 Project 2 due!;

    Is KR necessary?
    Brooks 1991
    M May  2 Last Class:
    Summary & Review
    Davis et al. 1993
    T    3 Reading Day  
    W    4 Reading Day  
    Th    5 Final Exam
    11:45 a.m.-2:45 p.m.
    Knox 4


    "Teachers open the door, but you must enter by yourself." -- Chinese Proverb

    "You can lead a horse to water, but you can't make him drink." -- American Proverb


    1. You will be expected to attend all lectures and recitations, and to complete all readings and assignments on time. There will be (more-or-less) weekly homework assignments, 2 programming projects, a mid-term exam, and a final exam (during exam week). Taking both the exams is a necessary condition for passing the course (i.e., you must take both exams in order to pass the course).

    2. All homeworks will be announced in lecture. Therefore, be sure to get a classmate's phone number (for instance, 1 or 2 people sitting next to you in class, whoever they are!) so that you will not miss assignments in the unlikely event that you miss a class. There may be occasional extra assignments and quizzes in recitations.

    3. Email list:

      You will automatically be placed on an email list (a "Listserv") for the course. If you do not normally read email at the email address that UB has as your official address, please either do so for this course, or else have your mail forwarded. I will use this list as my main means of communicating with you out of class, and you can use it to communicate with the rest of us.

      You may send questions and comments that are of general interest to the entire class using the Listserv: Just send them to:

      You can also send email just to me, at:

      In any case, be sure to fill in the subject line, beginning with "CSE 563: " so that my mailer doesn't think it's spam.

      If you send email to me that I deem to be of general interest, I will feel free to remail it anonymously to the email list along with my reply unless you explicitly tell me otherwise.

      I will archive the emails at

      For more information, read the Listserv Information webpage.

    4. Just as you cannot expect to learn how to drive a car by reading about it or by watching other people do it, the same holds true for doing computer science. Do your work on time--this is one course you simply cannot cram for at the last minute, so don't even try! I cannot stress this strongly enough. Homeworks and--especially--projects may be fairly time-consuming, so please consider your other commitments, and plan your time accordingly.

    5. Students should notify Prof. Rapaport within the first two weeks of class if they have a disability which would make it difficult to carry out course work as outlined (requiring note-takers, readers, extended test time).


    1. HW assignments will generally be of the "paper-and-pencil" variety, to be done at home.

    2. The purposes of homeworks are:

      • to give you practice in applying the concepts covered in the course
      • to give you a chance to assess the level of your understanding

    3. There will be approximately 1 HW each week.

    4. Due dates will be announced in lecture when the homework is assigned. HWs will be collected at the start of lecture on the due date. This is so that the homework can be discussed in the class period when it is due.

      If they are turned in after the start of lecture, your grade will be discounted by one full letter grade (e.g., A becomes B, A- becomes B-, etc.).

      If they are turned in after the start of the next lecture, your grade will be discounted by two full letter grades (e.g., A becomes C, A- becomes C-, etc.).

      If you turn in a HW after the start of the class after that, your grade will be discounted by three full letter grades (e.g., A becomes D, etc.).

      No HWs will be accepted after that.

    5. Put your full name, date, and your recitation number and day (B1/Mon or B2/Wed) at the top right-hand side of each page, and secure all pages with a staple in the top left-hand corner.

    6. Note: The lowest homework grade will be dropped. You should assume that you will fail to turn in one homework (oversleep, get stuck in traffic, etc.)--that's the one that will be dropped. If you know now that you will regularly be late, see me to make alternative arrangements for turning in your work. Your graded HW will be returned in recitation. Occasional extra assignments or quizzes from lab can be used to replace low HW grades, at your TA's discretion.


    1. Programming Languages, Lisp, and Unix: The prerequisite for this course is knowledge of any high-level programming language.

      But you are strongly advised to (learn and) use Lisp if you intend to do any research in AI. Moreover, there are good reasons and easy ways to learn Lisp!

      CSE 463 students will have accounts on the CSE undergraduate machines; CSE 563 students will have accounts on the Grad Lab machines. If you do not have access to these machines, please let me know as soon as possible! You will be expected to learn how to use Unix, emacs, etc., on your own. CIT offers short courses on Unix, etc. To contact CIT:

      in person:216 Computing Center
      by phone:645-3542
      by fax:645-3617
      on the Web:

    2. Project Policies:


      For general advice on how to study for any course, see my web page,
      "How to Study".


      Undergrads (in 463) and grads (in 563) will be graded on different bases. All graded work will receive a letter grade: 'A', 'A-', 'B+', 'B', 'B-', 'C+', 'C', 'C-' (463 only), 'D+' (463 only), 'D', or 'F'. Your course grade will be calculated as a weighted average of all letter grades according to the following weights:

      Recitation grade
      (including attendance, homeworks, quizzes, etc.)
      Midterm Exam25%
      Final Exam25%

      For further information, see my web document on "How I Grade"


      It is University policy that a grade of Incomplete is to be given only when a small amount of work or a single exam is missed due to circumstances beyond the student's control, and that student is otherwise doing passing work. And it is CSE departmental policy that Incompletes cannot be made up merely by auditing another section of this course. I will follow these policies strictly! Thus, you should assume that I will not give incompletes :-) (This is even more important since I expect to be on sabbatical next semester and, thus, unavailable to handle Incompletes.) Any incompletes that I might have to give, in a lapse of judgment :-), will have to be made up by the end of the Fall 2005 semester. For more information on Incomplete policies, see the web page, "Incompletes".


      While it is acceptable to discuss general approaches with your fellow students, the work you turn in must be your own. It is the policy of this department that any violation of academic integrity will result in an F for the course, that all departmental financial support including teaching assistanceship, research assistanceship, or scholarships be terminated, that notification of this action be placed in the student's confidential departmental record, and that the student be permanently ineligible for future departmental financial support. If you have any problems doing the assignments, consult Prof. Rapaport. Please be sure to read the webpage,
      "Academic Integrity: Policies and Procedures", which spells out all the details of this, and related, policies.


      In large classes (such as this), students have been known to be disruptive, either to the instructor or to fellow students. The university's policies on this topic, both how the instructor should respond and how students should behave, may be found in the document
      "Obstruction or Disruption in the Classroom - Policies".

      Copyright © 2005 by William J. Rapaport (
      file: 563S05/syl-2005-04-22.html