CSI 2101 - midterm

negating quantifiers

equivalent to the opposite quantifier with a negated predicate

how to verify two propositions are equivalent

prove one proposition implies the other and vice versa

rational numbers

can be written in the form n/d

proof by cases

split all logical possibilities into disjoint cases and prove these cases cover all possibilities. prove each case implies the proposition

proof by contrapositive

turn a proposition of the form P → Q into NOT Q → NOT P, which is logically equivalent. this is useful for proving the converse of IFF statements and proving propositions involving rational numbers

proof by contradiction

assume the proposition is false and prove how this assumption leads to falsehood. NOT P → F. Useful for proving propositions involving rational numbers, and proving uniqueness. Use as a last resort.

proofs with irrational numbers

rearrange the proposition so it does not claim a number is irrational, but rather rational

proof by induction

first prove the base case where n is the lowest is can possibly be (typically 1). the assume the inductive hypothesis of P(n), taking the inductive step, and prove that if P(n) is true, that P(n+1) is true. This is used for proving propositions of the form “For all n, P(n)”

strong induction

A type of induction where the inductive step assumes all values up to n are true, rather than just n being true.

invariant

a predicate that is true for all states over all transitions throughout the lifetime of a state machine. invariants only tell us what is unreachable, not necessarily what is reachable

combination

a number c is a combination of two other numbers a,b if there exists integers x,y such that c=xa+yb

facts about combinations (3)

• combinations of combinations of initial numbers are also combinations of those initial numbers

• if d divides a and b, then d divides all combinations of a and b

• the gcd of a and b is a combination of a and b

euclid’s slgorithm

E(n,d) where n>=d>=0

1. if d=0, return n

2. otherwise, write n=qd+r where q is as large as possible while keeping r positive. Return E(d,r)

extended euclid’s algorithm

used to find the combination of n and d equaling their gcd. X(n,d) where n>=d>=0

1. if d=0, return (1,0)

2. otherwise, return n=qd+r having q as large as possible while r remains possible. Get (s,t) from X(d,r), and return (t, s-(q*t))

modulus

represented as y mod x, it returns the positive remainder y when divided by x. for negative numbers, consider that you must always move right to get the remainder

modular addition

done by adding the modulus of each addend together, and then getting the modulus of that

congruent modulo

written as a ≡ a’ (mod n) if a mod n = a’ mod n. a and a’ have the same remainder when divided by n

facts about congruency (3)

• two numbers are congruent if n divides a-a’

• if a ≡ a’ (mod n) and b ≡ b’ (mod n), then

  • a + b ≡ a’ + b’ (mod n)

  • ab ≡ a’b’ (mod n)

• n is even translates to n ≡ 0 (mod 2), odd translates to n ≡ 1 (mod 2)

modular multiplication

done by multiplying the modulo of each factor together and then taking the modulo of that product

modular exponentiation

given a^e mod n, if e is large enough use Power(a,e,n)

1. if e = 1, return a mod n

2. if e is even, return Power(a² mod n, e/2, n)

3. if e is odd, return a Power(a, e-1, n)mod n

modular division

you can find the multiplicative inverse of a divisor using X(n,a) if 1<=a<=n-1 and the gcd(a,n)=1. The inverse of a’ is s mod n, where s is from sa + tn from X(n,a)

fermat’s little theorem

assume n is prime. then xⁿ ≡ x (mod n) for every n