Discrete Math

Question 1

Counting: Rule of sum

Answer 1

If task A can be performed in m ways And If task B can be performed in n ways, And both tasks cannot be performed simultaneously, Then there are m+n ways to perform one of these tasks.

Question 2

Counting: Rule of Product

Answer 2

If a process can be broken down Into two stages, say stage A and stage B, And stage A can be performed in m ways And stage B can be performed in n ways, And the stages are independent (a choice for A does not affect a choice for B),

Then the number of ways to complete the process (in order) is m*n.

Question 3

Counting: A bijection definition (non-formal)

Answer 3

A bijection between two sets X, Y is a “matching up”, or “pairing “.

Question 4

Counting: formal definition of bijection

Answer 4

A bijection between two sets X, Y is a function f: X->Y that is both 1:1 and onto.

or

A function f (from set A to B) is bijective if, for every y in B, there is exactly one x in A such that f(x) = y

Alternatively, f is bijective if it is a one-to-one correspondence between those sets, in other words both injective and surjective.

Question 5

One - to- one function ( or injective)

Answer 5

A function f: A → B is:

one-to-one If different elements of A always result in different images in B.

Question 6

What is the exact definition of an Injective Function

Answer 6

What this means is that it never maps distinct elements of its domain to the same element of its codomain.

or

Injective means that every member of “A” has its own unique matching member in “B”.

and

But we can have a “B” without a matching “A”.

Question 7

What is a function?

Answer 7

A function is a way of matching the members of a set “A” to a set “B”.

Question 8

Injective, Surjective and Bijective

What do those terms tell us about the function?

Answer 8

“Injective, Surjective and Bijective” tells us about how a function behaves

Question 9

Surjective function definition (non-formal)

Answer 9

Surjective means that every “B” has at least one matching “A” (maybe more than one).

There won’t be a “B” left out.

Question 10

Can a one-to-one function be reversed?

Answer 10

Injective functions can be reversed!

If “A” goes to a unique “B” then given that “B” value we can go back again to “A” (this does not work when two or more “A”s pointed to one “B” like in the “General Function”)

Question 11

a domain of a function ?

Answer 11

is the same as asking

“What are all the possible x guys
that I can stick into this thing?”

Domain is all possible input values for a given function.

Usually looking for what is NOT in the domain.

Question 12

range of the function?

Answer 12

is the set of all values that f (function) takes.

Question 13

Bijective means…

Answer 13

Bijective means both Injective and Surjective together.

So there is a perfect “one-to-one correspondence” between the members of the sets.

(But don’t get that confused with the term “One-to-One” used to mean injective)

Question 14

Surjective (Also Called “Onto”)… (formal definition)

Answer 14

A function f (from set A to B) is surjective if and only if for every y in B, there is at least one x in A such that f(x) = y, in other words f is surjective if and only if f(A) = B.

So, every element of the range corresponds to at least one member of the domain.

Question 15

general, injective, surjective, bijective graphic meaning in Cartesian coordinates

Answer 15

general f-n: for every value x (in domain) there might be more then one value of y (in range).

injective f-n: for every value of x in A (domain) there is one and only one value y in B (range).

surjective f-n: if the range of f equals the codomain of f. I.e. f is a surjection if for every y € Y there exists x € X such that f(x) = y.

Question 16

⇔ (iff)

meaning?

Answer 16

‘if and only if’

Question 17

f: X → Y means?

Answer 17

means the function f maps the set X into the set Y

Question 18

∀

Answer 18

∀ x, P(x) means P(x) is true for all x.

Question 19

∃!

∃

∈

∋

Answer 19

• there exists exactly one
• there exists;

there is;
there are

• is an element of;
• such that

Question 20

Permutation definition (formal)

Answer 20

A permutation of a set X is a bijection from X to itself.

Question 21

Informal definition of a permutation

Answer 21

A linear arrangement of (distinct) objects is called a permutation of the objects.

Question 22

{ } indicate… which set?

Answer 22

unordered

Question 23

(1, 2, 3) indicate which set?

Answer 23

ordered

Question 24

the formula for linear arrangements count (no repetitions of objects are allowed)

Answer 24

P(n,r) = n!/(n-r)!

Question 25

the formula for linear arrangements count if repetitions are allowed

Answer 25

P(n,r) = n^r

Question 26

the formula for linear arrangements count if there are indistinguishable objects

Answer 26

P(n,r) = n!/(n₁! n₂! ··· n_r!)