Current postgraduate taught students
COMP67010: Foundations of Computing (2007-2008)
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
Academic knowledgeDemonstrate 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 skillsIllustrate 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 skillsGather 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 SkillsApply 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
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.
Title: Foundations of Computing
Author: Scheurer, T.,
Publisher: Addison Wesley,