Skip Navigation LSS Home | CECS Home | ANU Home | Search ANU | HORUS | Staff Home

Course Description

---

Fundamentals of Metalogic

---

Content: Completeness theorems, Model theory and proof theory.

Course Description: This course provides an introduction to the metatheory of elementary logic. Following a "refresher" on the basics of notation and the use of classical logic as a representation language, we concentrate on the twin notions of models and proof. An axiomatic system of first order logic is introduced and proved complete for the standard semantics, and then we give an overview of the basic concepts of proof theory and of formal set theory. The material in this course is presupposed by other courses in the Summer School, which is why it is presented first.

Software: An hour each day in the first week will be set aside for students to use the Logic for Fun site for web-based exercises in formalisation. This gives an opportunity for some more active "hands-on" activity to break up and complement the lectures.

Pre-requisites: it is assumed that students are at least familiar with logical notation for connectives and quantifiers, and can manipulate truth tables, some kind of proof system or semantic tableaux or the like. Normally they will have done a first logic course at tertiary level.

Lecturer:

John Slaney is the founder and convenor of the Logic Summer school. He originated in England, ever so long ago, and discovered Australia in 1977. Undeterred by the fact that it had been discovered before, he gradually moved here, joining the Automated Reasoning Project in 1988 on a three-year contract because he could not think of anywhere better to be a logician. He is still here and still can't. His research interests pretty much cover the waterfront, including non-classical logics, automated deduction and all sorts of logic-based AI. He was formerly the leader of the Logic and Computation group at the ANU, and of the NICTA program of the same name.

---

Introduction to Modal Logic

---

Content: Kripke models, Hilbert calculi, Frame correspondences, Tableaux-based decisions procedures and Propositional linear-time temporal logic

Course Description: We cover the syntax, Kripke semantics, correspondence theory and tableaux-style proof theory of propositional modal and temporal logics. These logics have important applications in a diverse range of fields incuding Artificial Intelligence, Theoretical Computer Science and Hybrid Systems.

Pre-requisites: You should have a good grounding in classical propositional and first-order logic, including material covered in the "Fundamentals of Metalogic" course. Some very basic notions from graph theory would also be useful, but are not essential.

Lecturer:

Rajeev Goré is currently a a Senior Fellow in the ANU, and leader of the Logic and Computation research group. He was an Australian Research Council Queen Elizabeth II Fellow at the ANU from 1997-2001, a Research Fellow at the ANU from 1994-1996, and a Research Associate at the University of Manchester from 1992-1993. He obtained his PhD in Modal Theorem Proving from the University of Cambridge in 1992.

---

Overview of Automated Reasoning

---

Content: Automated propositional theorem proving, Automated first-order theorem proving and Interactive theorem proving

Course Description:In many applications, we expect computers to reason logically. We might naively expect this to be what computers are good at, but in fact they find it extremely difficult. In this overview course, we look at various methods to automate logical reasoning, which are needed to support a variety of application domains.

Automated reasoning procedures are parametrized by the logic they are capable of reasoning with. We distinguish between propositional logic and first-order logic. Development and application of propositional logic procedures, also called SAT solvers, received considerable attention in the last ten years, e.g., for solving constraint satisfaction problems, applications in hardware design, verification, and planning and scheduling. Regarding automated deduction in first-order logic, we discuss applications, standard deductive procedures such as resolution, and basic concepts, such as unification. We also examine the dual problem of theorem proving, viz., generating models of a given theory, which has applications to finding counterexamples for non-theorems, and we provide an overview of some recent trends (instance-based methods, satisfiability modulo theories). Finally, we describe in some depth so-called quantifier elimination methods for theorem proving in decidable fragments of arithmetics over the reals and the integers.

Pre-requisites: Elementary logic, as provided by the "Fundamentals of Metalogic" course of this Summer School.

Lecturers:

Peter Baumgartner is the manager of NICTA's "Managing Complexity" theme at the Canberra Laboratory. Previous employments were at the Max Planck Institute for Computer Science and the University of Koblenz, both in Germany. His research interest is automated deduction, particularly for first-order logic, and its applications. He holds a PhD and a Habilitation degree in Computer Science.

---

Computability and Incompleteness

---

Contents: Computability, Recursive Functions and Turing Machines, Diagonalisation, Peano Arithmetic and Goedel numbering, Undecidability of first-order logic, Incompleteness of Peano Arithmetic. Completeness Theorems, Model Theory and Proof Theory.

Course Description: We begin with two formal accounts of the intuitive notion of computability: recursive functions and Turing machines. They turn out to be the same, hence Church's Thesis: functions that can be computed by any means are precisely the recursive functions. Then we revisit the old Cretan who says that all Cretans always lie, and other forms of diagonalisation argument such as Halting Problem. Next we look at an axiomatic theory of arithmetic, known as Peano Arithmetic (PA), and show how we can represent all recursive functions in PA. This will lead to Goedel numbering: a neat trick enabling us to effectively encode notions like "theorem", "proof" and "provability in PA" within PA itself. We spend a while discussing Diagonalisation Lemma and Derivability Conditions. Finally, in one fell swoop we prove undecidability of first-order logic (Church's Theorem), undefinability of truth (Tarski's Theorem), incompleteness of PA given consistency of PA (First Goedel's Theorem) and unprovability of consistency of PA given consistency of PA (Second Goedel's Theorem).

Pre-requisites: Foundations of First-order Logic

Background Reading: G. Boolos and R. Jeffrey, Computability and Logic.

Lecturer:

Michael Norrish is a Senior Researcher in NICTA's Canberra Laboratory. He is originally from Wellington, New Zealand, and is very happy to be back in the southern hemisphere, after an extended stint in Cambridge, England. It was there that he did his PhD, and then spent three years as a research fellow at St. Catharine's College. His research interests are in interactive theorem-proving, and the application of this technology to areas of theoretical computer science, particularly the semantics of programming languages.

---

Programming in Higher-Order Logic

---

Contents: Simply typed lambda calculus, (higher-order) intuitionistic logic, (higher-order) unification, goal-directed proof search, modules and abstraction in higher-order logic programming, lambda-Prolog, programming examples.

Course Description: n this course we examine the use of logic as a programming language. Logic programming, in its commonly known manifestation in the Prolog language, uses only a simple fragment of first-order logic, i.e., the Horn fragment. There has been an active research area, called "abstract logic programming", that broadens the scope of logic programming beyond Horn clauses. Underlying this notion of abstract logic programming is the equation:

Computation = Proof Search.

More specifically, computation is modelled as a certain kind of complete proof search strategy, called goal-directed proof search. A wide range of proof systems, e.g., sequent calculi for intuitionistic logic, fragments of classical logic and various fragments of linear logic, have been shown to be complete under this notion of goal-directed proof search. In this course, we will examine the notion of goal-directed proof search in a sequent calculus for higher-order intuitionistic logic, and a logic programming language, called lambda-Prolog, that arises from a fragment of higher-order logic under this notion of goal-directed proof search. In particular, we will see that certain notions in programming languages, i.e., modules and abstract datatypes, arise naturally from the behaviors of logical connectives. A wide range of examples of lambda-Prolog programs which exploit the higher-order features of the language will be presented, e.g., we will look at an encoding of a lazy data structure (streams) using higher-order prediates, and an implementation of an interpreter for a mini functional language in lambda-Prolog.

Pre-requisites: It is assumed that students are familiar with first-order logic and sequent calculus, which are covered in the first week of the summer school. Some familiarity with lambda calculus will be helpful but not neccessary, as a brief overview will be given in the first lecture. Familiarity with Prolog and logic programming in general will also be helpful.

Lecturer:

Alwen Tiu is a research fellow at the Australian National University since 2006. He did his PhD at the Pennsylvania State University from 2001 - 2004, but he spent the last two years of his PhD at Ecole Polytechnique, France. Prior joining ANU, he spent one year at LORIA (France) as a postdoc. His research interests include proof theory, logical frameworks, process calculi and theorem proving.

---

Answer Set Programming: The KRR* Solving Paradigm

---

Contents: Answer Set Programming, Knowledge Representation and Reasoning, Boolean Constraint Solving, Logic Programming.

Course Description: Answer Set Programming (ASP) is a new (Boolean) constraint solving paradigm, combining an expressive declarative modeling language with high performance solving technology. Formally, it is well-suited for solving problem in NP or NP^NP, respectively, like bounded model-checking and planning, classical combinatorial problems, among them time tabling and product configuration, as well as many problems in bio-informatics and knowledge representation in general. The course will start from an informal short introduction to syntax, semantics, modeling, and algorithms. These topics are then detailed in the remainder, while putting a particular emphasis an the theoretical foundations and practical implementation of modern ASP solving technology. The latter is made precise by detailing the clasp system, winner of the ASP solver competition in 2007 and 2009, as well as the SAT competition in 2009 in the crafted category.

(* KRR = The field of Knowledge Representation and Reasoning)

Pre-requisites: no special prerequisites.

Lecturer:

Torsten Schaub is a University Professor for knowledge processing and information systems at the University of Potsdam, Germany, as well as an Adjunct Professor at the School of Computing Science at Simon Fraser University, Canada, and the Institute for Integrated and Intelligent Systems at Griffith University, Australia. His research interests range from the theoretic foundations to the practical implementation of methods for reasoning from incomplete and/or inconsistent information in general, and ASP in particular.

---

Logic and Complexity

---

Contents: Turing Machines and computability (again); important complexity classes such as NP or PSPACE; NP- or PSPACE-complete problems; problem reductions; relevance of complexity theory for formal logic

Course Description: This course provides an introduction to and a broad overview on the area of complexity theory. We discuss various formal classes of decision problems, such as NP- and PSpace-complete problems, show how to determine whether or not a given problem belongs to a particular class, and highlight their relevance to many other areas of computer science, in particular, formal logic.

Background Reading: The course will somewhat lean on the material covered in M. R. Garey and D. S. Johnson: Computers and Intractability - A Guide to the Theory of NP-Completeness (Freeman, New York, 1979).

Lecturer:

Andreas Bauer is a currently a Senior Research Engineer with NICTA and an Adjunct Research Fellow at the ANU. He obtained his PhD in 2007 from the Software and Systems Engineering group of the Technische Universitaet Muenchen in Germany.

---

Reasoning in Discrete Event Systems

---

Contents: logical reasoning about transition systems; planning; solution techniques.

Course Description: Reasoning about discrete state/transition systems is common to many problems in AI, such as diagnosis and planning, as well as in other areas of computer science (e.g., model checking or parsing). This course is intended to give a basic introduction to some of these problems, show how they are related and describe some of the methods that can be used to solve them.

Lecturer:

Patrik Haslum is a research fellow at the Australian National University. He did his PhD at Linköping University and did a post-doc with NICTA (in Canberra). His research has focused mainly on heuristic search methods for optimal planning.

---

Non-classical Logic

---

Contents: TBA

Course Description: TBA

Lecturer:

Errol Martin took degrees in philosophy and mathematics at the University of Queensland and University of New South Wales before undertaking a PhD in mathematical logic at ANU, supervised by Richard Routley and Robert K. Meyer. His thesis studied weak contraction free logics and provided the first solution of the P-W problem, showing that no instances of the implicational law of Identity can be proved in a system with just the 'syllogistic' principles of Prefixing and Suffixing. Errol has held teaching positions at the University of New South Wales, the University of Queensland, and the University of Canberra. He has held research positions at the University of Melbourne and the Australian National University. Errol was Head of the Information Systems and Computing Departments at the University of Canberra in the period 1988 -1995. From 1999 he has been a freelance consultant, providing strategic advice to government on the design of information systems.