IS2 Course Description for Revision Purposes
IS2 Course Description for Revision Purposes
The main topics that were covered in this course are:
- Simple Logic
Proposition, conjunction, disjunction, negation, truth table,
conditional proposition, biconditional proposition, tautology, contradiction,
inverse, converse, contrapositive, logical equivalence, laws of logic, de Morgan's
laws, testing the validity of an argument, predicate, quantifier, negation of
quantifiers.
- Set Theory
Enumerated form, predicate form, null set, universal set, venn diagram,
subset, equality of sets,
proper subsets, intersection, union, disjoint, complement, laws of sets, de Morgan's
law for sets, cardinality, the principle of inclusion and exclusion, power set,
ordered n-tuple, Cartesian product, bitwise AND, bitwise OR, bitwise NOT.
- Relations
Binary relations, directed graphs, relation matrices, properties of relations,
equivalence relation, partition, equivalence classes, partial order, total order.
- Functions
Function, domain, codomain, image, range, onto, one-to-one, composition of
functions, identity function, inverses, theorem on inverses.
- Induction and Recursion
Real valued sequence, recursion, recursive and non-recursive definitions,
proof by induction,
the theorem of matematical induction, induction and recursion, functions in
programming languages.
You will be expected to know the relevant definitions for the above.
The tutorial sheets you have been given as well as last years exam papers
(from both the summer and supplemental exams) should prove very useful for
revision purposes. In previous years the course covered combinatorics and
modus ponens, these did not form part of the syllabus this year.
Pseudocode
This is a structured form of English that allows us to express algorithms in an
unambiguous way.
| Main Commands | Example | |
| 1. Input | 1. Input m | take in value for m |
| 2. Output | 2. Output m | output value of m |
| 3. <- (assignment) | 3. f <- 1 | f is assigned the value 1 |
| 4. { } (comments) | 4. {this text is ignored} | |
| | |
| | |
| Main Structures | | |
| 1. For ... to ... do | For i = 0 to n do |
| 2. If ... then ... else ... | if x < 0 then ... else ...
| |
The indentation and line numbering indicate the tasks to be performed within a loop.
A piece of pseudocode to evaluate n!:
| 1. Input n |
| 2. f <- 1 |
| 3. For i = 1 to n do |
| 3.1 f <- i ×f |
| 4. Output f
|
A piece of pseudo code to output the first m terms of the recursive sequence
t(1) = 4, t(n) = t(n-1) +2 , n>1.
| 1. Input m |
| 2. t <- 4 |
| 3. Output t {outputs the first term} |
| 4. For n = 2 to m do |
| 4.1 t <- t+2 |
| 4.2 Output t |
File translated from TEX by TTH, version 2.10.
On 20 Apr 1999, 17:48.