COMP 2411 Logic and Logic Programming

      The University of

      New South Wales

      School of

      Computer Science

      and Engineering

_________________________________________________________________________________________

Contents

1 Aims and learning outcomes

1.1 Aims

Logic pervades many fields of computer science. It plays a key role in:

• formal program specification and verification;
• program synthesis;
• high level programming languages;
• formalisms in artificial intelligence;
• theoretical foundations of computer science.

The aim of the course is to help you master the theoretical notions and develop the practical skills related to logic that you will use from when you study those fields or some of them.

1.2 Learning outcomes

By the end of the course you will be able to:

• formalise and give semantic arguments using the language of propositional and first-order logic;
• produce formal proofs in various systems (semantic tableaux, Hilbert style proof systems, natural deduction, resolution) of propositional and first-order logic;
• know how the previous notions can be specialised to logic programming and SLD-resolution;
• write programs in Prolog that
  • implement most of the fundamental semantic and proof-theoretic logical concepts covered in this course or
  • solve some of the simple classical problems encountered in artificial intelligence;
• appreciate the advantages of declarative programming;
• know how to extend the formalisation and semantics of first-order logic to the semantics of programming languages;
• apply your knowledge of first-order logic in formal arguments used in program specification and verification.

1.3 Relevance to other courses

There is no prerequisite for this course. It is a core subject if you are a software engineering student, and an elective otherwise. You will find this course especially useful in relation to the following courses:

• COMP 2110 Software System Specification
• COMP 3411 Artificial Intelligence
• COMP 4173 Logical Foundations of Artificial Intelligence

1.4 Approach to learning

At university, the focus is on your self-directed search for knowledge. Lectures, tutorials, labs, textbook and recommended reading, assignments and exams are all provided as a service to assist you in this endeavour. It is your choice as to how much work you do in this course, whether it be preparation for classes, completion of assignments, study for exams or seeking assistance or extra work to extend and clarify your understanding. You must choose the approach that best suits your learning style and goals in this course. The course is designed in such a way that passing the course will only require a good understanding of the fundamental notions as well as good practical skills, thanks to regular but limited work. If your aim is to obtain a high distinction then you will have to face more uncertainty, in the form of a broader range of questions and problems, of a more difficult type, and you will need to invest more time in this course.

2 Assessment

2.1 Assignments and exams

The course will be assessed as follows.

The whole material presented in lecture notes, tutorials and labs is assessable.

Please see Section 4 to find out on which week each of the five assignments is due. An assignment should be handed out to the School office and possibly part of it electronically submitted by 3 pm on Monday of the week when it is due. Late assignments will not be considered and no mark will be awarded. Assignment questions will be posted on the web at least one week before the assignment is due. For instance, Assignment 1 is due on Week 4, hence should be handed out to the School office and possibly part of it electronically submitted by 3 pm on Monday the 22th of March. It will be posted on the web by 3 pm on Monday the 15th of March (possibly earlier). For more information on the course’s web site see Section 3.

Every assignment will consist of a small number of questions. An assignment can be purely theoretical, or purely practical, or have both a theoretical and a practical component. An example would be an assignment with 5 questions, each worth 2 marks, with 3 theory questions plus 2 programming questions where you would have to write, modify, or analyse a Prolog program.

In each assignment, most groups of questions will be directly related to lecture notes, tutorial exercises and lab exercises, and 1 or 2 groups of questions will go beyond that material.

Your solutions to the theoretical components can be hand-written, but we appreciate when you type them; they should be handed out to the School office. Each assignment paper will specify whether your solutions to the practical components should be in the form of a program and output printout, also to be handed out to the School office, or submitted electronically.

The mid-term exam will consist of 30 multiple choice questions, all for 0.5 marks, with no negative marks awarded to incorrect answers. This exam will test your understanding of the fundamental notions that will be introduced during the first half of the session.

The final exam will have two components, for a total of 7 groups of questions, with a maximum of 5 marks awarded to each group:

• a theoretical component, with 4 groups of questions directly related to lecture notes, tutorial exercises and assignments, and a more difficult question that goes beyond that material;
• a practical component, where you will have to write, modify, or analyse a Prolog program, with one question directly related to lecture notes, lab exercises and assignments, and a more difficult question that goes beyond that material.

2.2 Marking criteria

Marks for theory questions will be awarded on the basis of the following criteria:

• correctness of solutions;
• clarity of explanations;
• quality of presentation.

Marks for programming questions will be awarded on the basis of the following criteria:

• correctness of solutions;
• clarity and sufficiency of comments;
• readability of code, with consistent indenting and good choice of variable and procedure names.

2.3 Final mark and grade

The final mark will be the sum of the assessment items. Your final mark will determine your grade as follows.

3 Student resources

Learning is the focus of this course. To help you learn, the following resources are made available. The documents mentioned below will be available in the form of .txt or .pdf files at the course’s web page:

3.1 Lectures

Two lectures will be presented each week, as shown in the next table.

The material that will be covered during a given lecture will be posted on the web as lecture notes and Prolog programs, on the day before that lecture. Attendance to lectures is recommended but not compulsory.

3.2 Tutorials

You should be enroled in one of the following tutorials. Attendance to tutorials is highly recommended but not compulsory.

Tutorials commence in Week 2 (beginning 8 March 2004).

Tutorials are small group learning environments in which you have the opportunity to explore the course matter actively and in-depth. The structure of the course is such that lecture material for one week is, generally, the focus of the tutorial in the next week. Tutorial questions will be posted on the web on the week before that tutorial, and you are asked to look at the questions and try and answer them. In this way, tutorials will be more productive in targeting problems and issues. Solutions to tutorial questions will be posted on the web on the week after that tutorial.

3.3 Lab exercises

Every week, starting in Week 2, lab exercises and solutions to the previous week’s questions will be posted on the web. But there is neither any lab booking nor any lab supervision for this course. It is your responsibility to work on the lab exercises, and either make your own lab booking or work on your personal computer. Lab exercises will give you the opportunity to develop programming skills in Prolog.

3.4 Textbook

The textbook for this course is:

It can be purchased from the UNSW bookshop. You are expected to read and work from the textbook as a complement to the other material that is made available. The textbook contains fragments of Prolog programs, with complete versions that can be downloaded from

Still you do not need to download these programs, since revised versions of those of the programs that are relevant for this course will be posted on the course’s web page.

The following reference books are listed as other sources you might wish to consult. You are encouraged but not expected to read them or part of them.

3.5 Prolog implementation

SWI-Prolog is a free implementation of Prolog that will be used for this course. SWI-Prolog is installed on the School machines, and is started with the swipl command. It is also included on the Home computing CD. Source code and binaries for most operating systems as well as various other resources (editor, etc.) can be downloaded from

When you have to make electronic submissions that will be auto-marked, you have to test your solutions on the School machines. Passing a test means passing a test with the version installed on the School machines on the submission date.

3.6 Additional resources

You might find useful the following web sites.

• UNSW library: http://www.library.unsw.edu.au
• UNSW Learning center: http://www.lc.unsw.edu.au
• UNSW Communications unit: http://www.comms.unsw.edu.au
• CSE yellow form: http://www.cse.unsw.edu.au/~studentoffice/policies/yellowform.html
• Computer ergonomics: http://do.cse.unsw.edu.au/ergonomics/ergoadjust.html
• UNSW OHS responsability and accountability for students: http://do.cse.unsw.edu.au/ergonomics/ohs.html

4 Course structure 

The following table outlines the structure of the course. Note that some material in the textbook won’t be covered in lectures, and some material presented during lectures is not in the textbook. The last column of the table mentions only what is to some extent common to textbook and lecture notes.

5 Teaching staff

You may seek consultation and send questions by email with any teaching staff for this course. However, you first point of reference should, where possible, be the lecturer in charge or your tutor.

Teaching staff will be answering e-mails related to the course, provided that they do not request extensive or substantive answers. These questions are best raised in tutorials or consultation.

The lecturer in charge will be available for consultation on Mondays from 10 am to 12 am, in K17 room 409.

6 Administrative matters

6.1 Academic misconduct

Students are reminded that the University regards academic misconduct as a very serious matter. Students found guilty of academic misconduct are usually excluded from the University for two years. However, because of the circumstances in individual cases, the period of expulsion can range from one session to permanent explusion from University.

The following are some of the actions which have resulted in students being found guilty of academic misconduct in recent years:

• taking unauthorised materials into an examination;
• submitting work for assessment knowing to be the work of another person;
• improperly obtaining prior knowledge of an examination and using that knowledge in the examination;
• failing to acknowledge the source of material in an assignment.

6.2 Supplementary assessment

Students are reminded that the School’s policies on originality of assignment submissions and supplementary assessment are described in:

In particular, it should be noted that no supplementary midterm will be offered. Students unable to attend the midterm exam due to illness should submit a request for special consideration within seven days after the exam. Students whose requests are granted will have their midterm component computed on the basis of their results in the final exam. Students whose requests are denied will receive zero mark for the midterm. A supplementary final exam will be offered only to students who submit a request for special consideration meeting the School’s usual criteria (see the above) within seven days of the final exam, and perform at 50% or better in the midterm exam. (Students who were offered special consideration on the midterm exam and also request special consideration on the final will be handled at the discretion of the lecturer in charge, but will be expected to prove exceptional circumstances for both the midterm and final.) Please note that lodging an application for special consideration does not guarantee that you will be granted the opportunity to sit the supplementary exam. A supplementary final exam will only be offered to students who have been prevented from taking an end of session examination, and whose circumstances have improved considerably in the period since the exam was held. Students who apply for special consideration must be available during this period to sit the exam. No other opportunities to sit the final exam will be offered.