Models of Computation

Formal logic and discrete mathematics provide the theoretical foundations for computer science. This subject uses logic and discrete mathematics to model the science of computing. It provides a grounding in the theories of logic, sets, relations, functions, automata, formal languages, and computability, providing concepts that underpin virtually all the practical tools contributed by the discipline, for automated storage, retrieval, manipulation and communication of data.

• 1Use propositional and predicate logic as tools to reason about non-trivial computational problems
• 2Explain basic principles of mechanised reasoning, including resolution proof, and apply these to reason about computational problems
• 3Reason about properties of mathematical objects such as functions and relations, and apply them to computational problems
• 4Apply discrete mathematical techniques to problems in computer science
• 5Synthesise context-free grammars from less formal language specifications
• 6Design abstract computational devices, such as finite-state automata and pushdown automata
• 7Analyse and reason about computational models, including finite-state automata, pushdown automata and Turing machines.