Logic

Module aims

To introduce the language and semantics of propositional and first order predicate logic, and natural deduction. To apply concepts of first order logic to program specification.

Learning outcomes

Knowledge and understanding 

To know the specific material covered in the Syllabus, including the ability to do the following:

  • To recall the definitions of the logics and logical systems presented in the course
  • To avoid confusing syntax with semantics
  • To demonstrate understanding of the meanings of the basic logical symbols
  • To read and understand logical formulas
  • To understand the mechanisms of proof systems presented in the course
  • To understand and use correctly terms and notation commonly used in elementary logic texts

Intellectual skills 

  • To parse logical formulas correctly
  • To evaluate logical formulas in given situations
  • To translate logical formulas into English
  • To write logical formulas expressing ideas given in English
  • To construct proofs using proof systems presented in the course

Practical skills 

  • To understand and construct pre- and post-conditions for simple programs

Transferable skills 

  • To be able to deploy logic when reasoning about programs

Module syllabus

Propositional and predicate logic:

  • Syntax
  • Informal and formal semantics
  • Validity, satisfiability
  • Semantic entailment
  • Equivalence
  • Many-sorted logic
  • Reasoning methods
  • Applications in program specification

Pre-requisites

None

Teaching methods

Lectures, tutorials, PMT small-group tutorials, unassessed exercises (full model answers are made available 1-2 weeks after the questions), lab session with Pandora natural deduction proof assistant (students are expected to continue to use Pandora for self-study).

Students hand in PMT work approximately four times during the course.  The work is marked and returned to them during the PMT tutorial within a few days, for feedback.  They can ask questions on the spot about the marking and written comments.

Assessments

One Christmas test question (approx 30 mins).

Examination in May.

Reading list

Supplemental Reading

Module leaders

Dr Dalal Alrajeh
Professor Alessandra Russo