|Fees||Look up fees|
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.
- Logic: Propositional and predicate logic, resolution proofs, mathematical proof
- Discrete mathematics: Sets, functions, relations, order, well-foundedness, induction and recursion
- Automata: Regular languages, finite-state automata, context-free grammars and languages, parsing
- Computability briefly: Turing machines, computability, decidability.
A functional programming language will be used to implement and illustrate concepts.
Intended learning outcomes
On completion of this subject students are expected to be able to:
- 1. Use propositional and predicate logic as tools to reason about non-trivial computational problems
- 6. Design abstract computational devices, such as finite-state automata and pushdown automata.
- 2. Explain basic principles of mechanised reasoning, including resolution proof, and apply these to reason about computational problems
- 3. Reason about properties of mathematical objects such as functions and relations, and apply them to computational problems
- 4. Apply discrete mathematical techniques to problems in computer science
- 5. Synthesize context-free grammars from less formal language specifications
- 7. Analyze and reason about computational models, including finite-state automata, pushdown automata and Turing machines
On completion of this subject students should have developed the following skills:
- Analytical skills
- Reasoning and problem-solving skills
- Ability to communicate with precision, rigour and efficacy
- Ability to apply knowledge of science and engineering fundamentals
- Capacity for creativity and innovation
- Ability to undertake problem identification, formulation and solution
Last updated: 10 November 2019