433-255 Logic and Computation

433-172 Algorithmic Problem Solving or equivalent (prior to 2003, 433-141 Computing Fundamentals A)

The objective of this subject is for students to be able to reason formally about the properties of simple specifications and programs; to be able to reason formally about simple models of computation; to appreciate the variety of applications of discrete mathematical techniques in computer science; and to gain working experience with a logic programming language.

Topics include logic: propositional and predicate calculus, proof structures; logic programming languages (Prolog); formal specification, refinement and program proof; and selected topics from the Chomsky hierarchy of languages, computability, and computational complexity.

Project work (expected to take about 36 hours) during semester and one written examination (not exceeding three hours) at the end of the semester. The project work must be completed satisfactorily to pass the subject. Weighting of assessment components will be advised at the commencement of the subject.