COS1501 - Theoretical Computer Science I Summary Study Notes

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 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 followingstatements 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 for Z, 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 that Z≥ 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 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. 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: