# COMP109

## Foundations of Computer Science

### Aims

- To introduce the notation, terminology, and techniques underpinning the discipline of Theoretical Computer Science.
- To provide the mathematical foundation necessary for understanding datatypes as they arise in Computer Science and for understanding computation.
- To introduce the basic proof techniques which are used for reasoning about data and computation.
- To introduce the basic mathematical tools needed for specifying requirements and programs

### Syllabus

- Number systems and proof techniques: natural numbers, integers, rationals, real numbers, prime numbers, proof by contradiction and proof by induction.
- Approaches to describing collections of objects: sets and set operations, unary and binary relations, properties of binary relations, partial orders and equivalence relations, inverse relations, and compositions of relations.
- Functions: properties of functions, inverse functions and compositions of functions, the pigeonhole principle.
- Propositional logic: syntax and construction of formulas, semantics, interpretations and truth tables, tautologies, contradictions, semantic consequence and logical equivalence
- Combinatorics: notation for sums, products, and factorials, Binomial coefficients, counting permutations, subsets, subsequences and functions.
- Discrete Probability: sample spaces, events, conditional probability, independence, random variables and expectation.

### Learning Outcomes

- Understand how a computer represents simple numeric data types; reason about simple data types using basic proof techniques;
- Interpret set theory notation, perform operations on sets, and reason about sets;
- Understand, manipulate and reason about unary relations, binary relations, and functions;
- Apply logic to represent mathematical statement and digital circuit, and to recognise, understand, and reason about formulas in propositional and predicate logic;
- Apply basic counting and enumeration methods as these arise in analysing permutations and combinations.