Instructor: Kumar Madhukar (madhukar)
Office address: 516, Bharti Building

Teaching Assistants:

• Abhay Pratap Singh Rathore (cs5190414)
• Anjali Sharma (cs5190422)
• Ramneet Singh (cs5190445)
• Bommakanti Venkata Naga Sai Aditya (cs5190471)

Lecture Schedule

Mondays and Thursdays, 09:30-10:50 AM, in LT 2, Block VI

Announcements

• Quiz papers: Quiz 1, Quiz 2, Quiz 3, Quiz 4, Quiz 5, Quiz 6, Quiz 7
  
  
• Here is your third assignment for the course. The due date is Nov. 21st. It is a firm deadline; will not be extended. You are free to use your (unused) penalty-free days if you need to.
  
  
• I have uploaded the slides/reference material for all the lectures that have happened till November 6th. Please see the Lectures section below.
  
  
• Here is your second assignment for the course. The due date is Nov. 02nd 06th. It is a firm deadline; will not be extended. You are free to use your (unused) penalty-free days if you need to.
  
  
• Here is your first assignment for the course. The due date is Sept. 10th. It is a firm deadline; will not be extended. You are free to use your penalty-free days if you need to.
  
  
• As informed earlier, via Teams, there won't be any quiz on August 31st.
  
  
• No lecture on August 24th. This will be compensated later with an online lecture.
  
  
• We will be using gradescope for evaluation of assignments, quizzes and exams. Please register yourself for this course on Gradescope (Entry Code: DJNBV3).
  
  
• We won't have a lecture on July 27th. This will be compensated with an online lecture, the details of which will be announced later.
  
  
• The best way for you to get in touch with me would be to send me an email. I will not be replying to questions or comments on Teams. You are also welcome to meet me in my office. I would prefer that you set up an appointment over email before coming, but that is not a necessity.
  
  
• We will be using the Teams channel of this course for all the important announcements (some of which may re-appear here). This section of the page will primarily be used to inform you of updates made here, e.g. link to reference material or slides, any changes in the assessment policy, planned rescheduling of a lecture, etc. You should visit this section of this page at least once every day.

Suggested Books and Reference Material

• Logic in Computer Science (Michael Huth and Mark Ryan)
• Mathematical Logic for Computer Science (Mordechai Ben-Ari)
• (some more may be added as we go along)

Evaluation and Assessment

• Assignments (21 marks): There will be 3 assignments in the course, of 7 marks each. The submission deadlines for these assignments will be firm. However, I will allow each one of you a total of 9 days of penalty-free delay that you may use anyway you like. Delays beyond 9 days will cost you 1 mark every three hours.
  
  
• Quizzes (24 marks): There will be 7 surprize quizzes in the class (at any time during the class), of 4 marks each. There cannot be any make-up surprize quizzes, of course, but I will count the best 6. To make things slighlty better, I will apply an off-day discount before I count your best 6. This is how the off-day discount would work -- I will replace your lowest quiz mark, but only amongst those quizzes that you have attended, with your highest quiz mark.
  
  
• Minor exam (20 marks): If you miss the minor exam, we will scale your major exam marks to calculate your marks for the minor. There won't be a re-minor.
  
  
• Major exam (35 marks): The syllabus for the major exam will include everything that is covered in the entire course. A re-major exam will be held, if necessary.
  
  
• Grading: We will adopt a relative grading scheme.
  
  
• Attendance policy: We will not be tracking your attendance in every lecture. However, you must have attended at least 3 quizzes in order to pass/audit-pass.
  
  
• Pass and Audit Pass criteria: You need a total of at least 30 marks in order to pass the course. For an audit pass, you must have 45 marks excluding any marks that you get in your assignments (we will not be evaluating the assignments for students who choose to audit the course). The attendance policy, mentioned above, will obviously be applied in addition to this.
  
  
• There will be zero tolerance for dishonest means like copying solutions from others, and even letting others copy your solution, in any quiz/exam/assignment. If you are found indulging in such an activity, your answer paper will not be evaluated and your participation/submission will not be counted. Second-time offenders will be summarily awarded an F grade.

Lectures

• Week 1 (July 24th and 27th 31st)
  Topics: Propositional Logic, Natural Deduction Proofs
  Additional Remarks: Here are the slides that we have used in the class. You may look at Chapter 1 of the book by Huth and Ryan for reference.
  
  
• Week 2 (July 31st and August 3rd and 7th)
  Topics: Syntax, Semantics, Soundness and Completeness
  Additional Remarks: Here are the slides that we have used in the class. You may look at Chapter 1 of the book by Huth and Ryan for reference.
  
  
• Week 3 (August 7th and 10th and 14th)
  Topics: Normal Forms and Propositional Resolution
  Additional Remarks: Here are the slides that we have used in the class. You may take a look at these lecture notes on propositional resolution by James Worrell.
  
  
• Week 4 (August 14th and 17th and 21st)
  Topics: Hilbert's Axiomatization, Soundness, Completeness, Compactness
  Additional Remarks: Here are the slides that we have used in the class. You may look at these logic notes (see Chapter 1 on Propositional Logic) by Madhavan Mukund and S P Suresh.
  
  
• Week 5 (August 21st and 24th 28th and 31st)
  Topics: Horn-SAT, 2-SAT, DPLL
  Additional Remarks: Here are the slides that we have used in the class. You may take a look at these lecture notes on DPLL algorithm by James Worrell.
  
  
• Week 6 (August 28th and 31st) (September 4th and 11th)
  Topics: Open-discussion (on 4th), Binary Decision Diagrams (online, on 11th)
  Additional Remarks: I wrote an email to Dean Academics with three concrete suggestions based on our discussion in the class. I urged him to consider two of the suggestions, while I will be implementing the third one myself. I will give you another update on this in a month's time (by October 11th) [Update: I have decided to set aside 30 mins on every working day for any IIT Delhi student who wishes to come and have a friendly chat. You may send me an email to set-up an appointment, or simply drop by my office during 6:30-7 pm. I will try my best to be available in my office during this time, unless I am travelling or have some other unavoidable commitment.] For BDDs, here are the slides used in the class, and here is a note on the uniqueness proof of ROBDDs. You may also refer to Chapter 6 of the Huth and Ryan book, up to Sect. 6.2.4 (pages 358-379) and the recorded lecture on Teams.
  
  
• Week 7 (September 4th and 11th) (September 18th and 21st)
  Topics: Predicate Logic (Syntax, Natural deduction)
  Additional Remarks: Here are the slides that we have used in the class. You may refer to the relevant parts of the second chapter in the book by Huth and Ryan, as indicated in the slides.
  
  
• Week 8 (September 18th and 21st) (September 25th and 27th)
  Topics: Predicate Logic (Semantics)
  Additional Remarks: Here are the slides that we have used in the class.
  
  
• Week 9 (September 25th and 27th) (October 9th and 12th)
  Topics: Soundness and Completeness of Semantic Tableaux
  Additional Remarks: This part was covered from the book by Ben-Ari. The relevant sections have been uploaded on the Teams channel for the course.
  
  
• Week 10 (October 9th and 12th) (October 16th and 19th)
  Topics: Normal forms, Herbrand's Theorem
  Additional Remarks: Here are the slides that we have used in the class. You may take a look at these lecture notes on FOL Normal Forms and Herbrand's Theorem by James Worrell.
  
  
• Week 11 (October 16th and 19th) (October 26th and 30th)
  Topics: Herbrand Expansion, Ground Resolution
  Additional Remarks: Here are the slides that we have used in the class. You may take a look at these lecture notes on Ground Resolution, and Undecidability by James Worrell.
  
  
• Week 12 (October 26th and 30th) (November 2nd and 6th)
  Topics: Predicate Resolution
  Additional Remarks: Here are the slides that we have used in the class. You may take a look at these lecture notes on Predicate Resolution by James Worrell.
  
  
• Week 13 (November 2nd and 6th) (November 9th and 16th)
  Topics: Prolog, Encoding states/transitions as BDDs
  Additional Remarks: For the prolog part, there are plenty of resources available on the internet. The examples used in the class have been uploaded on the Teams channel. For BDDs related content, you may refer to the Huth and Ryan book, Sections 6.3.1-6.3.3.