• Wrong document? Swap it for free
  • Written by students who passed
  • Immediately available after payment
  • Read online or as PDF
Sell
Where do you study
Your language
Document preview thumbnail
Preview 4 out of 41 pages
Other

COS1501 - Theoretical Computer Science I Summary Study Notes

Document preview thumbnail
Preview 4 out of 41 pages

COS1501 - Theoretical Computer Science I Summary Study Notes. A positive integer p greater than 1 is defined to be a prime 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. Study unit 3 Sets Set A well-defined collection of distinct objects. Set-builder notation { x | x is a positive integer} The set of all x’s such that x is a positive integer. Set membership 3 is a member of Z, 3 ∈ Z ,3 is an element of Z -2 is not a member of Z+, -2 ∉ Z+ Subset If A and B are sets from a universal set U, we say that A is a subset of B if and only if every element of A is also an element of B. A ⊆ B - A is a subset of B Proper subset If C and D are sets from a universal set U, and if every element of C is an element of D, but D has some element(s) that is/are not in C, we call C a proper subset of D. C ⊂ D - C is a proper subset of D Set union The union of sets A and Bis the set of all those elements, which belong to A or to B (or to both). A ∪ B = {x | x ∈ A or x ∈ B} - x ∈ A ∪ B iff x ∈ A or x ∈ B Set intersection The intersection of sets A and B is the set of all those elements, which belong to both A, and B at the same time. A ∩ B = {x | x ∈ A and x ∈ B} - x ∈ A ∩ B iff x ∈ A and x ∈ B Set difference The complement of B relative to A is the set of all those elements of A, which do not belong to B. A − B = {x | x ∈ A and x ∉ B} - x ∈ A − B iff x ∈ A and x ∉ B Set complement Let A be a subset of a universal set U. Then the complement of A is defined as the set of all elements that belong to U but do not belong to A. A′ = {x | x ∈ U and x ∉ A} or A′ = {x | x ∉ A} or A′ = U – A Symmetric set difference The symmetric difference between two sets A and B is defined as the set of all elements that belong to A or to B but not to both. A + B = { x | x ∈ A or x ∈ B, but not both.} - x ∈ A + B iff x ∈ A or x ∈ B, but not both Set disjointness Two sets A and B are called disjoint if they have no elements in common. A ∩ B = ∅ Set cardinality Let A be a set with k distinct elements that can be counted. The number of elements in A is called the cardinality of the set. The cardinality of A is denoted by n(A), and n(A) = k. n(A) or |A| Power set Given a set A with n distinct elements, the power set of A, denoted by Ƥ(A), is the set that has as its members all the subsets of A. |Ƥ(A)| = 2n. I offer online tutoring, help with class Assignments, essay writing, dissertations, thesis, Copywriting Et al., for all Majors with a guaranteed PASS and QUALITY. For assistance Contact Tutor Lucas:

Content preview

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.

Document information

Uploaded on
December 13, 2022
Number of pages
41
Written in
2022/2023
Type
Other
Person
Unknown
R70,46

Wrong document? Swap it for free Within 14 days of purchase and before downloading, you can choose a different document. You can simply spend the amount again.
Written by students who passed
Immediately available after payment
Read online or as PDF

Seller avatar
Reputation scores are based on the amount of documents a seller has sold for a fee and the reviews they have received for those documents. There are three levels: Bronze, Silver and Gold. The better the reputation, the more your can rely on the quality of the sellers work.
ExcelAcademia2026
3,7
(389)
Sold
2308
Followers
1650
Items
8967
Last sold
3 days ago



Why students choose Stuvia

Created by fellow students, verified by reviews

Quality you can trust: written by students who passed their exams and reviewed by others who've used these notes.

Didn't get what you expected? Choose another document

No worries! You can immediately select a different document that better matches what you need.

Pay how you prefer, start learning right away

No subscription, no commitments. Pay the way you're used to via credit card or EFT and download your PDF document instantly.

Student with book image

“Bought, downloaded, and aced it. It really can be that simple.”

Alisha Student

Working on your references?

Create accurate citations in APA, MLA and Harvard with our free citation generator.

Working on your references?

Frequently asked questions