COS1501 - Theoretical
Computer Science I
Summary Study Notes
, COS1501
1. Number Systems
Study unit 1 The development of
number systems:
Z+, Z≥ and Z
Positive integers: Z+
Z+ = {1, 2, 3, …} Law 1-7
Non-negative integers: Z≥
Z≥ = {0, 1, 2, 3, …} Law 1-9
Integers: Z
Z = {... ,-3, -2, -1, 0, 1, 2, …} Law 1-10 (Law 6 is different) and Def 1-3
The Laws for Z+ and Z≥
Law 1 (commutativity):
For all non-negative integers m and n,
m + n = n + m and
mn = nm.
Law 2 (associativity):
For all non-negative integers m, n and k,
m + (n + k) = (m + n) + k and
m(nk) = (mn)k.
Law 3 (distributivity):
For all non-negative integers m, n and k,
m(n+k) = (mn) + (mk).
Law 4 (existence of a multiplicative identity element):
For all non-negative integers m,
m⋅1 = m.
Law 5 (linearity):
For all non-negative integers m and n, exactly one of the following
statements are true:
m < n, m = n, m > n.
Law 6 (monotonicity of + and × respectively):
For all non-negative integers m, n and k,
if m = n, then m + k = n + k and mk = nk;
,if m < n, then m + k < n + k; and
if k > 0, mk < nk.
Law 7 (transitivity of = and < respectively):
For all non-negative integers m, n and k,
if m = n and n = k, then m = k, and
if m < n and n < k, then m < k.
Law 8 (existence of an additive identity element):
For all non-negative integers m,
m + 0 = m.
Law 9 (absence of zero-divisors):
For all non-negative integers m and n,
mn = 0 if and only if m = 0 or n = 0.
What about Z?
All the laws listed above hold forZ, except for the monotonicity law, which looks slightly
different for Z:
Law 6 (monotonicity):
For all integers m, n and k,
if m = n, then m + k = n + k and mk = nk;
if m < n, then m + k < n + k;
if k > 0, then mk < nk; and
if k < 0, then mk > nk (negative numbers must also be taken into
account).
Z has one law thatZ≥ does not have:
Law 10 (existence of additive inverses):
For every integer m there exists an integer n such that
m + n = 0.
Definition 1 (Absolute value):
For any integer x, the absolute value of x (denoted by |x|) is defined to be
either:
x if x is non-negative, or
-x if x is negative.
Definition 2 (Prime number):
A positive integer p greater than 1 is defined to beprime
a number if its only factors
are 1 and p.
Definition 3 (n factorial (n!)):
If n is any positive number, then n factorial, denoted by n!, is calculated as follows:
n! = n(n–1)(n–2)…(4)(3)(2)(1)
, Study unit 2 Rational and real
numbers: Q and R
The rational numbers: Q
Set of all numbers of the form p/q where p and q are integers and q is not zero
p
q where p, q ∈ Z and q ≠ 0
Law 1-11
Definition 4 (Multiplicative inverses):
For every non-zero rational number x there exists a rational number called the
multiplicative inverse, denoted by 1/x which is such that (x)(1/x) = 1.
Law 11 (the existence of multiplicative inverses):
For every non-zero rational number x there exists a rational number y such that xy = 1
The real numbers: R
The expanded number system that consists of the combination of the rational
plus the irrational numbers is called R, i.e. the set of the
real numbers.
