Cheatography

# asdf Cheat Sheet (DRAFT) by j24

kjnjnkbkjnlkjblkjblkjbljkbl

This is a draft cheat sheet. It is a work in progress and is not finished yet.

### Old

 Countable. A set that is either finite or has the same cardin­ality as the set of positive integers (ℤ!) is called countable. To be countable, there must exist a 1-1 and onto (bijec­tion) between the set and ℕ! (i.e. ℤ!) Show that the set of positive even integers E is countable. Let f(x) = 2x, E = {1,2,3­,4,...}, f(x) = {2,4,6­,8,...}. Then f is a bijection from N to E since f is both one-to-one and onto. To show that it is one-to­-one, suppose that f(n) = f(m). All integers between 10 and 10000: Finite. All integers less than 10: Countably infinite. S = {(x,y) | x, y in N}: Countably inf. All real numbers between 0 and 1: Uncoun­table. All rational numbers between 0 and 1: Countably inf. All integers that are multiples of 8: Countably inf. Induction. To prove that P(n) is true for all positive integers n, we complete these steps:  Basis Step: Show that P(1) is true.  Inductive Step: Show that P(k) → P(k + 1) is true for all positive integers k. To complete the inductive step, assuming the inductive hypothesis that P(k) holds for an arbitrary integer k, show that P(k + 1) must be true. Template for Proofs by Mathem­atical Induction 1. Express the statement that is to be proved in the form “for all n ≥ b, P (n)” for a fixed integer b. 2. Write out the words “Basis Step.” Then show that P (b) is true, taking care that the correct value of b is used. This completes the first part of the proof. 3. Write out the words “Inductive Step.” 4. State, and clearly identify, the inductive hypoth­esis, in the form “assume that P (k) is true for an arbitrary fixed integer k ≥ b.” 5. State what needs to be proved under the assumption that the inductive hypothesis is true. That is, write out what P (k + 1) says. 6. Prove the statement P (k + 1) making use the assumption P (k). Be sure that your proof is valid for all integers k with k ≥ b, taking care that the proof works for small values of k, including k = b. 7. Clearly identify the conclusion of the inductive step, such as by saying “this completes the inductive step.” 8. After completing the basis step and the inductive step, state the conclu­sion, namely that by mathem­atical induction, P (n) is true for all integers n with n ≥ b. Strong Induction: To prove that P(n) is true for all positive integers n, where P(n) is a propos­itional function, complete two steps:  Basis Step: Verify that the propos­ition P(1) is true.  Inductive Step: Show the condit­ional statement  [P(1) ∧ P(2) ∧∙∙∙ ∧ P(k)] → P(k + 1) holds for all positive integers k. Ordina­ry/weak induction • Rule 1: P(0) (or any other base case) • Rule 2: P(n) -> P(n+1) Strong induction • Rule 1: P(0) (or any other base case) • Rule 2: P(1),P(2), P(3),....P(n) -> P(n+1) The general rule. 1. If P(n+1) can be proven from P(n) only, then weak/o­rdinary induction is sufficient 2. If P(n+1) requires other propos­itions prior to P(n) (e.g. P(n-1) or P(n-2)) then strong induction may be approp­riate Example: Show that if n is an integer greater than 1, then n can be written as the product of primes. Solution: Let P(n) be the propos­ition that n can be written as a product of primes.  BASIS STEP: P(2) is true since 2 itself is prime.  INDUCTIVE STEP: The inductive hypothesis is P(j) is true for all integers j with 2 ≤ j ≤ k. To show that P(k + 1) must be true under this assump­tion, two cases need to be consid­ered:  If k + 1 is prime, then P(k + 1) is true.  Otherwise, k + 1 is composite and can be written as the product of two positive integers a and b with 2 ≤ a ≤ b < k + 1. By the inductive hypothesis a and b can be written as the product of primes and therefore k + 1 can also be written as the product of those primes. Hence, it has been shown that every integer greater than 1 can be written as the product of primes. Example: Prove that every amount of postage of 12 cents or more can be formed using just 4-cent and 5-cent stamps. Solution: Let P(n) be the propos­ition that postage of n cents can be formed using 4-cent and 5-cent stamps.  BASIS STEP: P(12), P(13), P(14), and P(15) hold.  P(12) uses three 4-cent stamps.  P(13) uses two 4-cent stamps and one 5-cent stamp.  P(14) uses one 4-cent stamp and two 5-cent stamps.  P(15) uses three 5-cent stamps.  INDUCTIVE STEP: The inductive hypothesis states that P(j) holds for 12 ≤ j ≤ k, where k ≥ 15. Assuming the inductive hypoth­esis, it can be shown that P(k + 1) holds.  Using the inductive hypoth­esis, P(k − 3) holds since k − 3 ≥ 12. To form postage of k + 1 cents, add a 4-cent stamp to the postage for k − 3 cents. Hence, P(n) holds for all n ≥ 12.

### Turing Machine

 A Turing machine T = (S, I, f, s 0) consists of  a finite set S of states,  an alphabet I that includes the blank symbol B,  a partial function f from (S × I)→ (S × I ×{R,L})  a starting state s0 .  For some (state, symbol) pairs the partial function f may be undefined, but for a pair for which it is defined, there is a unique (state, symbol, direction) triple associated to this pair.  The five-t­uples corres­ponding to the partial function in the definition of a TM are called the transition rules of the machine. 1. At the beginning of its operation a TM is assumed to be in the initial state s0 and to be positioned over the leftmost nonblank symbol on the tape. This is the initial position of the machine. 2. At each step, the control unit reads the current tape symbol x. 3. If the control unit is in state s and if the partial function f is defined for the pair (s, x) with f(s, x) = (s′, x′, d), the control unit:  enters the state s′,  writes the symbol x′ in the current cell, erasing x, and  moves right one cell if d = R or moves left one cell if d = L. 4. This step is written as the five-tuple (s, x, s′, x′, d). Turing machines are defined by specifying a set of such five-t­uples. If the partial function f is undefined for the pair (s, x) then T will halt. 5. The Turing Machine outputs the revised tape. Let V be a subset of an alphabet I.  A TM T = (S, I, f, s0 ) recognizes a string x in V if and only if T, starting in the initial position when x is written on the tape, halts in a final state.  T is said to recognize a subset A of V if it is the case that a string x is recognized by T if and only if x belongs to A.  Note that to recognize a subset A of V* we can use symbols not in V. This means that the input alphabet I may include symbols not in V. We will see that these extra symbols are used as markers.  A TM operating on a tape containing the symbols of a string x in consec­utive cells, does not recognize x if it does not halt or halts in a state that is not final.

### Number Theory

 Let a = b mod (m) • a is the remainder when b is divided by m Reflexive: 𝑎 ≡ 𝑎 mod 𝑚 Symmetric: If 𝑎 ≡ 𝑏 mod 𝑚, then 𝑏 ≡ 𝑎 mod 𝑚 Transi­tivity: If 𝑎 ≡ 𝑏 mod 𝑚 and 𝑏 ≡ 𝑐 mod 𝑚, then 𝑎 ≡ 𝑐 mod 𝑚 Additive inverse For any 𝑎, there exists a b such that 𝑎 + 𝑏 = 0 (𝑚𝑜𝑑 𝑚) In this case, the b is called the additive inverse of a and vice versa Multip­lic­ative inverse. For any 𝑎 relatively prime to 𝑚 where gcd 𝑎, 𝑚 = 1, there exists a 𝑏 such that 𝑎𝑏 = 1 (𝑚𝑜𝑑 𝑚) In this case, the b is called the multip­lic­ative inverse of a and vice versa. 𝑎 ≡ 𝑏 𝑚𝑜𝑑 𝑚 is equivalent to 𝑎 − 𝑏 = 𝑘𝑛 for some 𝑘 ∈ ℤ If 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑛) and c ≡ 𝑑 (𝑚𝑜𝑑 𝑛), then 𝑎𝑐 ≡ 𝑏𝑑 (𝑚𝑜𝑑 𝑛) Example. 5 ~ 3 (mod 2) Congruent Class. The congruent class of an integer a, denoted [a] is defined as [a] = { b in Z | a is congruent to b} Base Conver­sions Convert 1011 0111 to decimal, octal, and hexade­cimals Decimal • 2' ∗ 1 + 2( ∗ 0 + 2) ∗ 1 + 2 ∗ 1 + 2! ∗ 0 + 2# ∗ 1 + (2" ∗ 1) + (2% ∗ 1) • 183 10 • 183 = 822+7 • 22 = 82+6 • 0 = 80+2 • 267. From Decimals to Binary, Octal and Hexade­cimals Convert 24680 to Binary, Octal and Hexade­cimals To convert to binary, divide by 2 repeatedly and record the remainder at each stage. 24680 = 212340 + 0 12340 = 26170 + 0 6170 = 23085 + 0 3085 = 21542 + 1 1542 = 2771 + 0 771 = 2385 + 1 385 = 2192 + 1 192 = 296 + 0 96 = 248 + 0 48 = 224 + 0 24 = 212 + 0 12 = 26 + 0 6 = 23 + 0 3 = 21 + 1 1 = 20 + 1 110000­001­101­000_2. From Decimals to Binary, Octal and Hexade­cimals Convert 24680 to Binary, Octal and Hexade­cimals 24680 = 83085 + 0 3085 = 8385 + 5 385 = 848 + 1 48 = 86 + 0 6 = 80+6 60150 8 24680 = 161542+8 1542 = 1696+6 96=166+0 6=160+6 6068_16 GCD and LCM Greatest Common Divisor (GCD) – is the largest number that divides both a and b Least Common Multiple (LCM) – Is the smallest positive integer that is divisible by a and b To find LCM Obviously, LCM(a,b) is no more than ab Start by finding the prime factors of a and b Build LCM using the largest power of each prime that is in a or b. Least Common Multiple Find lcm(40,12) • 40 = 2! 5" • 12 = 2# 3" For each prime base, use the largest exponent between the two numbers • 2! 3" 5" = 120 lcm(40­,12­)=120 Find lcm(52­92,810) • 5292 = 2# 3! 7# • 810 = 2" 3 5" • 2# 3 5" 7# = 79380 lcm(52­92,­810­)=7­9380. GCD as a linear combin­ation If a and b are positive integers, the gcd(a, b) can be written as gcd(a, b) = am + bn for some integers m and n. Note. Multiples of GCD are Linear Combin­ations of a and b E.g. write gcd(312, 125) as a linear combin­ation 312 m + 125 n Solution. gcd(312, 125) = gcd(312, 62) è 312 = 2125 + 62 ---(1) gcd(312, 62) = GCD(62, 1) è 125 = 262 + 1 ---(2) gcd(62,1) = 1 Using (2). 1 = 125 + (-2)62 = 125 + (-2) (312- 2125) using (1) = 5125 + (-2)*312.

### FSM FSA NFA

 A finite­-state machine M =(S, I, O, f, g, s 0 ) consists of  a finite set S of states  a finite input alphabet I  a finite output alphabet O  a transition function f that assigns to each state and input pair a new state  an output function g that assigns to each state and input pair an output  an initial state s 0 .  A state table is used to represent the values of the transition function f and the output function g for all (state, input).  Altern­ati­vely, a finite­-state machine can be repres­ented by a state diagram, which is a directed graph with labeled edges. Each state is repres­ented by a circle, and arrows labeled with the input and output pair represent the transi­tions.  The state table and state diagram both represent the finite state machine with S = {s 0 ,s 1 ,s 2 ,s 3 }, I = {0, 1}, and O = {0, 1}. FSMs with no output, but with some states designated as accepting states, are specif­ically designed for recogn­izing languages.  A finite­-state automaton M = (S, I, f, s0, F) consists of a finite set S of states, a finite input alphabet I, a transition function f that assigns a next state to every pair of state and input (so that f: S × I → S), an initial or start state s 0, and a subset F of S consisting of final (or accepting) states.  FSAs can be repres­ented using either state tables or state diagrams, in which final states are indicated with a double circle.  A finite state machine (FSM) with no output is called a finite state automata (FSA). A string x is said to be recognized (or accepted) by the machine M = (S, I, f, s 0, F) if it takes the initial state s 0 to a final state, that is, f(s 0, x).  The language recognized (or accepted) by M, denoted by L(M), is the set of all strings that are recognized by M.  Two finite­-state automata are called equivalent if they recognize the same language. The final state of M 3 are s 0 and s 3 . The strings that take s 0 to itself are λ, 0, 00, 000,... . The strings that take s 0 to s 3 are a string of zero or more consec­utive 0s, followed by 10, followed by any string. Hence, L(M 3 ) = {0n ,0n 10x | n = 0, 1, 2, ...., and x is any string} A nondet­erm­inistic finite­-state automaton M = (S, I, f, s 0, F) consists of  A finite set S of states  A finite input alphabet I  A transition function f that assigns a set of states to every pair of state and input (so that f: S × I → P(S))  An initial or start state s0  A subset F of S consisting of final (or accepting) states. For every NFA there is an equivalent DFA. That is, if the language L is recognized by a NFA M 0, then L is also recognized by a DFA M 1. We construct the DFA M 1 so that  The start symbol of M 1 is {s 0}.  The input set of M 1 is the same as the input set of M 0.  Each state in M 1 is made from of a set of states in M 0. Construct new states in M 1 by interp­reting each unique output in the M 0 transition table as a its singular own state, e.g. s ! , 𝑠" , 𝑠# , ∅  Given a state {𝑠\$ ! , 𝑠\$ " ,..., 𝑠\$ # } in M 1 and an input symbol x, the transi­tions from this state to the next is the union of transi­tions f(𝑠\$ ! , x), f(𝑠\$ " ,x), ... , f(𝑠\$ # ,x) from M 0 for the states that compose the state from 𝑀"  The final states of M 1 are any sets that contain a final state of M 0. A vocabulary (or alphabet) V is a finite, nonempty set of elements called symbols. A word (or sentence) over V is a string of finite length of elements of V . The empty string or null string, denoted by λ, is the string containing no symbols. The set of all words over V is denoted by V ∗. A language over V is a subset of V ∗. A phrase­-st­ructure grammar G = (V , T , S, P ) consists of a vocabulary V , a subset T of V consisting of terminal symbols, a start symbol S from V , and a finite set of pro- ductions P . The set V − T is denoted by N. Elements of N are called nonter­minal symbols. Every production in P must contain at least one nonter­minal on its left side. Let G = (V , T , S, P ) be a phrase­-st­ructure grammar. The language generated by G (or the language of G), denoted by L(G), is the set of all strings of terminals that are derivable from the starting state S. In other words, L(G) = {w ∈ T ∗ | S ∗ *⇒ w}. EXAMPLE 5 Give a phrase­-st­ructure grammar that generates the set {0n1n | n = 0, 1, 2, . . . }. The solution is the grammar G = (V , T , S, P ), where V = {0, 1, S}, T = {0, 1}, S is the starting symbol, and the produc­tions are S → 0S1 S → λ. A type 0 grammar has no restri­ctions on its produc­tions. A type 1 grammar can have produc­tions of the form w1 → w2 , where w1 = lAr and w2 = lwr, where A is a nonter­minal symbol, l and r are strings of zero or more terminal or nonter­minal symbols, and w is a nonempty string of terminal or nonter­minal symbols. It can also have the production S → λ as long as S does not appear on the right-hand side of any other produc­tion. A type 2 grammar can have produc­tions only of the form w1 → w2 , where w1 is a single symbol that is not a terminal symbol. A type 3 grammar can have produc­tions only of the form w1 → w2 with w1 = A and either w2 = aB or w2 = a, where A and B are nonter­minal symbols and a is a terminal symbol, or with w1 = S and w2 = λ. EXAMPLE 9 It follows from Example 5 that {0n1n | n = 0, 1, 2, . . . } is a contex­t-free language, because the produc­tions in this grammar are S → 0S1 and S → λ.

### Relations

 A binary relation R on a A and B is defined as R is a subset of A x B. A relation is a subset of the cartesian product of two sets A and B, which is a set of ordered pairs. A x B = {(a,1), (a,2), (a,3), (b,1), (b,2), (b,3), (c,1), (c,2), (c,3), (d,1), (d,2), (d,3)}. A relation is usually written in set format: R = {(a,2)­,(b­,1)­,(c­,1)­,(d­,3)­,(c­,2)}. We say that a is related to 2 in one of the following notations: (a,2) is e R, or a R 2. 1) A relation R on a set A is called reflexive if (a, a) ∈ R for every element a ∈ A. 2) A relation R on a set A is called symmetric if (b, a) ∈ R whenever (a, b) ∈ R, for all a, b ∈ A. A relation R on a set A such that for all a, b ∈ A, if (a, b) ∈ R and (b, a) ∈ R, then a = b is called antisy­mme­tric. 3) A relation R on a set A is called transitive if whenever (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R, for all a, b, c ∈ A. 4) Let R be a relation from a set A to a set B and S a relation from B to a set C. The composite of R and S is the relation consisting of ordered pairs (a, c), where a ∈ A, c ∈ C, and for which there exists an element b ∈ B such that (a, b) ∈ R and (b, c) ∈ S. We denote the composite of R and S by S ◦R. 5) Let R be a relation on the set A. The powers R n , n = 1, 2, 3, . . . , are defined recurs­ively by R1 = R and R n+1 = R n ◦ R. 6) The relation R on a set A is transitive if and only if R n ⊆ R for n = 1, 2, 3, ... Because this relation contains R, is reflexive, and is contained within every reflexive relation that contains R, it is called the reflexive closure of R. This new relation is symmetric and contains R. Furthe­rmore, any symmetric relation that contains R must contain this new relation, because a symmetric relation that contains R must contain (2, 1) and (1, 3). Conseq­uently, this new relation is called the symmetric closure of R. Let R be a relation on a set A. The connec­tivity relation R∗ consists of the pairs (a, b) such that there is a path of length at least one from a to b in R. The transitive closure of a relation R equals the connec­tivity relation R∗. A relation on a set A is called an equiva­lence relation if it is reflexive, symmetric, and transi­tive. Two elements a and b that are related by an equiva­lence relation are called equiva­lent. The notation a ∼ b is often used to denote that a and b are equivalent elements with respect to a particular equiva­lence relation. Let R be an equiva­lence relation on a set A. The set of all elements that are related to an element a of A is called the equiva­lence class of a. The equiva­lence class of a with respect to R is denoted by [a]R . When only one relation is under consid­era­tion, we can delete the subscript R and write [a] for this equiva­lence class. Let R be an equiva­lence relation on a set A. These statements for elements a and b of A are equiva­lent: (i) aRb (ii) [a] = [b] (iii) [a] ∩ [b] =/= ∅. A relation R on a set S is called a partial ordering or partial order if it is reflexive, antisym- metric, and transi­tive. A set S together with a partial ordering R is called a partially ordered set, or poset, and is denoted by (S, R). Members of S are called elements of the poset. When every two elements in the set are compar­able, the relation is called a total ordering.

### Boolean functions

 The complement of an element, denoted with a bar, is defined by bar0 = 1 and bar1 = 0. The variable x is called a Boolean variable if it assumes values only from B, that is, if its only possible values are 0 and 1. A function from B n to B is called a Boolean function of degree n. x | y (or x NAND y): the expression that has the value 0 when both x and y have the value 1 and the value 1 otherwise. x ↓ y (or x NOR y): the expression that has the value 0 when either x or y or both have the value 1 and the value 0 other- wise barbarx = x Law of the double complement x + x = x Idempotent laws x · x = x x + 0 = x Identity laws x · 1 = x x + 1 = 1 Domination laws x · 0 = 0 x + y = y + x Commut­ative laws xy = yx x + (y + z) = (x + y) + z Associ­ative laws x(yz) = (xy)z x + yz = (x + y)(x + z) Distri­butive laws x(y + z) = xy + xz bar(xy) = barx + bary De Morgan’s laws bar(x + y) = barx bary. x + xy = x Absorption laws x(x + y) = x x + barx = 1 Unit property xbarx = 0 Zero property A literal is a Boolean variable or its comple­ment. A minterm of the Boolean variables x1, x2, . . . , xn is a Boolean product y1y2 · · · yn, where y i = xi or yi = x i . Hence, a minterm is a product of n literals, with one literal for each variable. The sum of minterms that represents the function is called the sum-of­-pr­oducts expansion or the disjun­ctive normal form of the Boolean function. Find the sum-of­-pr­oducts expansion for the function F (x, y, z) = (x + y)z. Solution: We will find the sum-of­-pr­oducts expansion of F (x, y, z) in two ways. First, we will use Boolean identities to expand the product and simplify. We find that F (x, y, z) = (x + y)z = xz + yz Distri­butive law = x1z + 1yz Identity law = x(y + y)z + (x + x)yz Unit property = xyz + xy z + xyz + xyz Distri­butive law = xyz + xy z + xy z. Idempotent law. The resulting expansion is called the conjun­ctive normal form or produc­t-o­f-sums expansion of the function. These expansions can be found from sum-of­-pr­oducts expansions by taking duals. Because every Boolean function can be repres­ented using these operators we say that the set {·, +,− } is functi­onally complete