# COMP67010: Foundations of Computing (2007-2008)

## This is an archived syllabus from 2007-2008

Foundations of Computing
Level: 6
Credit rating: 15
Pre-requisites: No Pre-requisites
Co-requisites: No Co-requisites
Lectures: 26
Examples classes: 10
Course lecturer: not assignedAdditional staff: view all staff
Timetable
SemesterEventLocationDayTimeGroup
Sem 1 w1-5,7-11 Lecture LF17 Wed 13:00 - 17:00 -
Assessment Breakdown
Exam: 80%
Coursework: 20%
Lab: 0%

## Aims

To introduce the main concepts of set theory and logic, for themselves and as the universal foundations of the main stages of software development
To describe basic number representation and arithmetic operations in digital computers
To develop students? skills in applying set theory and logic to the specification of real-life software systems

Demonstrate a full understanding of the concepts of set theory and logic and of their application in modelling practical situations and systems
Show fluency in the notation of first-order predicate logic and set theory

### Intellectual skills

Illustrate concepts by simple, concrete applications
Solve substantial problems
Explain given set-theoretical models of information systems, reason about them informally, adapt them to elementary changes in requirements, and devise models of similar systems
Accurately translate set-theoretical descriptions from English into formal notation and vice-versa

### Subject practical skills

Gather observations of practical situations and systems, and systematically record such observations
Separate pure mathematical theory from modelling, i.e. the formalisation of empirical observations of system properties

### Transferable Skills

Apply a rigorous and systematic approach to the description of any type of system and to problem-solving
Discern situations amenable to descriptions in formal notation and understand the value and effective use of such descriptions

## Syllabus

Sets and set operations. Specification of a set by enumeration and by abstraction. Membership inclusion and subsets. Extensionality and the empty set. Set operations: pair, union, intersection and relative complement. Powerset. Venn diagrams. Notation summary: symbolic categories of predicate logic.
Representation of information in digital computers by finite types (byte, char, etc.) and lists of members of such types; number representations: decimal, binary, octal, hexadecimal. Representation of arithmetic operations. Floating point numbers and operations.
Ordered pairs and cartesian product. Relations: definition; domain, codomain and graph of a relation. Functions: definition, total and partial functions, injections, surjections and bijections. N-ary cartesian products, relations and functions. Practical examples.
Formalisation of evolving systems as modelling applications: I. An evolving set model: application domain, objects and operations on objects II. An evolving dictionary model: application domain, objects and operations on objects. III. A model of an evolving organisation.
Introduction to logic and deductive reasoning. Propositional logic. Notion of formal language. Syntax of propositional logic: alphabet and well -formed formulas (wffs). Semantics of propositional logic. Examples. Truth tables, tautological implication and tautologies. Applications.