COS1501 - Theoretical Computer Science I (COS1501)
Overig
COS1501 - Theoretical Computer Science I Summary Study Notes
12 keer bekeken 0 keer verkocht
Vak
COS1501 - Theoretical Computer Science I (COS1501)
Instelling
University Of South Africa
Boek
Theoretical Computer Science
COS1501 - Theoretical Computer Science I Summary Study Notes.
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 ...
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.
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper STUDYLAB2023. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor $4.00. Je zit daarna nergens aan vast.
