COMP4415

First-Order Logic

**Session 1
2010**

- Contents
- Objectives
- Learning Outcomes
- Units of Credit
- Recent Revisions -- Course Evaluation and Development
- Required Knowledge
- Organisation & Schedule
- Lecturers and Contact Information
- Lectures
- Assignments
- Assessment
- Plagiarism
- Reference Books

This course is a rigorous introduction to the logics that have been shown to be useful for knowledge representation and a wide range of reasoning in formal computer science, particularly artificial intelligence and proving the correctness of algorithms. The first part covers propositional logic. We start with the semantics of propositional logic, i.e. the formal meaning of logic formulas, and the formal meaning of logical consequence. Then we consider different ways of doing formal inference in propositional logic. In each case we discuss the soundness and completeness of an inference system. A system is sound in which all conclusions drawn are correct. It is complete if it is able to draw all correct conclusions. The second part of the course covers predicate logic (or first-order logic), which can be seen as an extension of propositional logic: everything expressed in propositional logic can also be expressed in predicate logic, but not the other way around. We start with the semantics of predicate logic and then cover different ways of doing formal inference in predicate logic. The third part of the course covers logic programming and nonmonotonic reasoning. We'll have a look at the theoretical basis of logical programming and then move on to discuss practical logic programming languages. Nonmonotonic reasoning is the formalisation of the idea of "defaults", which are used informally to jump to reasonable conclusions in the absence of information. Finally, there will be one lecture on description logics.

Throughout the course, students will be developing analytical skills as they investigate the underpinnings of logical systems they are already acquainted with, and see a similar development of unfamiliar logics. This provides a basis for students to design a logical system to suit specific requirements, although this activity will not be performed within this course. The skills developed should also help in the design of other formalisms. Through multiple assignments students will develop problem-solving skills, especially in the analysis of knowledge representation formalisms.

COMP4415 earns you 6 Units of Credit. This signifies 25% of a full-time study load for one semester, and involves 12 weeks × 3 hours/week of lectures, plus assignment work, as detailed below.

The course will consist of one three-hour lecture per week during session.

The lecturer-in-charge for this course is Michael Maher. The lecturers are:

Students with academic questions and/or problems relating to this course should contact the lecturer-in-charge, preferably by email, at

RoleNamePhoneLecturer-in-charge Michael Maher mmaher@cse.unsw.edu.au 8306 0462

All lecturers have offices in the L5 Building (223 Anzac Parade).
To get access to L5, go to reception on the fourth floor, and ask the receptionist
to contact the person you have come to see. It is **strongly** advisable
to make an appointment, either by email, or during class,
before coming to see a lecturer.

Students are also advised to check the web page of the course frequently:

http://www.cse.unsw.edu.au/~cs4415as many of the common problems you're experiencing may have already been resolved.

The lecture times are:

If you do not attend lectures, then it is your responsibility to discover any announcements and/or supplemental information that's given. Current outline (this is flexible and will be subject to minor changes):

DayTimeLocationMonday 15:00 - 18:00 Australian School of Business, Room 118 (K-E12-118)

BlockTopicLecturerDates1-4 Propositional logic Michael Maher 01/03 - 22/03 Mid-session Break05/04 - 05/04 5-9 Predicate Logic Michael Maher 29/03 - 03/05 8 Anzac Day26/04 - 26/04 10-12 Nonmonotonic Reasoning and Logic Programming Michael Maher 10/05 - 24/05 13 Introduction to Description Logic Michael Maher 31/05 - 31/05

Note that dates may be revised.

Assignments give you the chance to practice what you have learnt.
Assignments are a very important part of this course and constitute the sole means of assessment. **There is no
exam for this course.**
Therefore it is essential that you attempt them yourself.

To maximise the learning benefits from doing assignments, it is essential that you start work on assignments early. Do not leave your assignments until the last minute. Assignments must be submitted on time, to allow discussion in class of issues arising from the assignment. If a lecturer relaxes this requirement, the maximum available mark for a late assignment is reduced by 10% per day that it is late.

The assessable topics of the course are given below. This is subject to some change over the course of the semester. Any change will be announced in class and on the course web page.

This course may involve both undergraduate and postgraduate students. Postgraduate students will be held to a higher standard, and will sometimes receive extra or different assignment work.

TopicMarkPropositional Logic 30% Predicate Logic 30% Nonmonotonic Reasoning and Logic Programming 30% Introduction to Description Logic 10%

All work submitted for assessment **must be your own work**.
Assignments **must be completed individually**.
We regard copying of assignments, in whole or part, as a
very serious offence.
**We may use plagiarism detection software to search
for multiply-submitted work.**
Be warned that:

- the submission of work derived from another person, or jointly written with someone else will, at the very least, result in automatic failure for COMP4415 with a mark of zero.
- allowing another student to copy from you will, at the very least, result in a mark of zero for your own assignment; and
- severe or second offences will result in automatic failure, exclusion from the University, and possibly other academic discipline.

http://www.cse.unsw.edu.au/~studentoffice/policies/yellowform.html.Where required, follow-up interviews will be conducted by a Panel to decide on an appropriate course of action (if any). The decisions of the panel will be final.

(see also http://www.cse.unsw.edu.au/help/doc/primer/node42.html)

Students are strongly advised to protect their work. Do not leave your terminal/computer unattended, or leave printouts at the printer for others to take.

You should already have seen the Student Code of Conduct, but you should also make your self aware of the new Student Misconduct Procedures.

Notes will be distributed for the non-monotonic reasoning section.

23-02-2010