Discrete Mathematics Exam 2

Proof by Contradiction

Proof by Contradiction

1. Suppose the statement to be proved is false. That is, suppose that the negation of the statement is true.

2. Show that this supposition lead logically to a contradiction.

3. Conclude that the statement to be proved is true.

Method of Proof by Contraposition

1. Express the statement to be proved in the form ∀x in D ,if P (x ) then Q (x )

2. Rewrite this statement in the contrapositive form ∀x in D ,if ∼Q (x ) then ∼P (x )

3. Prove the contrapositive by direct proof. a. Suppose x is a (particular but arbitrarily chosen) element in D such that Q (x ) is false. b. Show that P (x ) is false.

The Irrationality of √2

By the Pythagorean Theorem, the length of the diagonal equals the square root of 2. So the square root of 2 is irrational!

Are There Infinitely Many Prime Numbers?

The number of primes is infinite

variable

In computing, refers to a storage location in the computer’s memory.

assignment statement

value to a variable: x := e.

x := e.

x is assigned the value e

Conditional statements

using current values of variables to determine which statement is executed next

If then else

If condition is true, then s1 is executed and execution moves to the next algorithm statement If condition is false, then s2 is executed and execution moves to the next algorithm statement

Iterative statements

when a sequence of algorithm statements is to be executed over and over again

While loop

while (condition) [statements that make up the body of the loop] end while

Trace Table

to trace the execution of the following algorithm by finding the values of all the algorithm variables each time they are changed during execution

For-next loop

for variable := initial expression to final expression [statement that make up the body of the loop] next (same) variable

Division Algorithm

or an integer a and a positive integer d , the quotient-remainder theorem guarantees the existence of integers q and r such that a = dq + r and 0 ≤r <d .

gcd(a,b)

greatest common divisor.

1. d is a common divisor of both a and b. In other words, d |a and d |b.

2. For every integer c , if c is a common divisor of both a and b, then c is less than or equal to d .

Euclidean Algorithm

a way to find the greatest common divisor of two positive integers, a and b

Sequence

A function whose domain is either all the integers between two given integers or all the integers greater than or equal to the integer

Term

individual element ak (read: “a sub k ”)

Subscript/Index

The k in ak is called

Initial term

m is the subscript of the

Final term

n is the subscript of the

Infinite Sequence

notation am ,am+1,am+2,...

explicit formula or general formula

a rule that shows how the values of ak depend on k

the summation from k equals m to n of a-sub-k

n ∑ak k =m

Telescoping sum

Some sums can be written so that successive cancellation of terms collapses the final result

product from k equals m to n of a-sub-k

n ∏ak k =m

Dummy variable

The variable used to represent the index of summation

factorial

the product of all the integers up to and including a given integer. n!

Zero factorial

denoted 0! is defined to be 1: 0! = 1

n choose r

(n/r) without the /

Proving an equality

1. Transform the left hand side and the right hand side independently until they are seen to be equal

2. Transform one side of the equation until it is seen to be the same as the other side of the equation.

Ordinary induction

assume P (k ) is true and show P (k + 1) is true.

Strong induction

Assume P (i ) is true for i ≤k , show P (k + 1) is true.

Well-Ordering Principle for the Integers

Let S be a set of integers containing one or more integers all of which are greater than some fixed integer. Then S has a least element,

Quotient-Remainder Theorem

Given any integer n and any positive integer d , there exist integers q and r such that n = dq + r and 0 ≤r <d .

AXB

Let A and B be sets. A relation from A to B

x is related to y by R

xRy if and only if (x ,y ) ∈R .

arrow diagram for R

1. Represent the elements of A as points in one region and elements of B as points in another.

2. For each x ∈A, y ∈B , draw an arrow from x to y if and only if (x ,y ) ∈R .

function F from a set A to a set B

a relation with domain A and co-domain B that satisfies the following two properties:

1. For every element x in A, there is an element y in B such that (x ,y ) ∈F .

2. For all elements x in A and y in B , if (x ,y ) ∈F and (x ,z ) ∈F ,then y = z

congruent modulo 2

mEn if, and only if, m mod 2 = n mod 2

reflexive

referring back to itself. or every x ∈A, xRx

symmetric

for every x , y ∈A, if xRy then yRx

transitive

or every x, y, z ∈A, if xRy and yRz then xRz

transitive closure

R is the relation R ton A that satisfies the following three properties:

1. R tis transitive.

2. R ⊆R t.

3. If S is any other transitive relation that contains R , then R t⊆S .

Union

A ∪B , is the set of all elements that are in at least one of A and B .

Intersection

A ∩B , is the set of all elements that are common to both A and B .

partition

a finite or infinite collection of nonempty, mutually disjoint subsets whose union is A.

m ≡ n(mod d )

m is congruent to n modulo d , d |(m −n)

encryption

the method by which information is converted into secret code that hides the information's true meaning

Plaintext

A message before conversion

ciphertext

The converted plaintext

Decryption

To convert the ciphertext back into plaintext

Caeser Cipher

Encrypts messages by changing each letter of the alphabet to the one three places farther along with wrapping X to A, Y to B, and Z to C.

public key cryptography

potential recipient of encrypted messages openly distributes a public key containing encryption information

RSA Cryptography

M = C^d mod pq, where d >0 and d is an inverse to e modulo (p −1)(q −1). p=5, q=11

Subset

A ⊆B ⇔∀x ,if x ∈A then x ∈B .

proper subset

1. A ⊆B , and

2. there is at least one element in B that is not in A.

venn diagram

a diagram that uses circles to represent mathematical or logical sets pictorially inside a rectangle

Union, denoted A ∪B

is the set of all elements that are in at least one of A or B .

intersection, denoted A ∩B

is the set of all elements that are common to both A and B

difference, denoted B −A

the set of all elements that are in B and not A

complement, denoted A^c

the set of all elements in U that are not in A

empty set, ∅

the set with no elements

disjoint

A ∩B = ∅

mutually disjoint

Ai ∩Aj = ∅ whenever i /= j

partition

a. A is the union of all the Ai b. the sets A1,A,2A3,...are mutually disjoint.