|Year of offer||2017|
|Subject level||Undergraduate Level 3|
|Fees||Subject EFTSL, Level, Discipline & Census Date|
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
INTENDED LEARNING OUTCOMES (ILO)
- On completion of this subject the student is expected to:
- Use propositional and predicate logic as tools to reason about non-trivial computational problems
- Explain basic principles of mechanised reasoning, including resolution proof, and apply these to reason about computational problems
- Reason about properties of mathematical objects such as functions and relations, and apply them to computational problems
- Apply discrete mathematical techniques to problems in computer science
- Synthesize context-free grammars from less formal language specifications
- Design abstract computational devices, such as finite-state automata and pushdown automata.
- 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