Course co-ordinator(s): Prof Jennie C Hansen (Edinburgh).
Aims:
To provide an introduction to, and grounding in, the basic principles and techniques of logic and discrete mathematics that are fundamental to Computer Science.
Detailed Information
Pre-requisites: none.
Location: Edinburgh.
Semester: AY.
Syllabus:
Set Theory and Combinatorics:Set algebra, Elementary counting methods, Permutations and Combinations, The Inclusion-Exclusion Principle. Congruences and affine ciphers
Functions and relations, total and partial, domain and range, inverses of functions/relations.
Properties: Injection, surjection, bijection (for functions) and ordering/equivalence (relation). Reflexive/transitive/symmetric closures.
Integer division and modular arithmetic
Recurrence Relations :Solving problems by iteration, First and second order recurrence relations.
Propositional logic:Definition of the connectives by means of truth tables; truth tables of compound propositions; graphs for propositional formulae; order of precedence rules and brackets; contradictions, satisfiable formulae, tautologies; valid arguments; equivalence relations and logical equivalence;
First-order logic:relations; names and predicates; quantification; syntax; semantics; truth-trees.
Learning Outcomes: Subject Mastery
By the end of the course, students should be able to:
- Solve simple recurrence relations
- Solve elementary counting problems
- Perform calculations that require an understanding of
- sets and operations on sets
- functions and relations
- integer division and modular arithmetic
- Prove statements
- by induction
- by contradiction
- Construct truth tables of compound propositions.
- Determine whether a proposition is a contradiction, satisfiable or a tautology.
- Convert an argument into symbolic form and determine whether it is valid.
- Solve problems in propositional logic using truth-trees.
- Be able to interpret first order formulae.
- Solve problems in first order logic using truth-trees.
Learning Outcomes: Personal Abilities
• Demonstrate the ability to learn independently
• Demonstrate knowledge of an area of mathematics.
• Manage time, work to deadlines and prioritise workloads
- Demonstrate careful mathematical reasoning
Assessment Methods: Due to covid, assessment methods for Academic Year 2021-22 may vary from those noted on the official course descriptor. Please see the Computer Science Course Weightings and the Maths Course Weightings for 2020-21 Semester 1 assessment methods.
SCQF Level: 7.
Credits: 15.