Discrete Mathematics

Front 1

The Rule of Sum

Back 1

If the first task can be performed in m ways, while a second task can be performed in n ways, and two task can not be performed simultaneously, then performing either task can be accomplished in any one of m+n ways.

Front 2

The Rule of Product

Back 2

If a procedure can be broken down into first and second stages, and if there are m possible outcomes for the first stage, and n possible outcomes for the second stage, then the total procedure can be carried out in mn ways.

Front 3

Factorial

Back 3

For an integer n ≥ 0, n factorial is defined by

0! = 1,

n! = n(n-1)(n-2)(n-3)...(3)(2)(1).

Front 4

Permutation

Back 4

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

The number of permutation of size r for n objects is

P(n,r)=n!/(n−r)!, 0 ≤ r ≤ n

Front 5

Arrangement with Repeated Symbols

Back 5

If there are n objects with n1 indistinguishable objects of a first type, n2 indistinguishable objects of a second type,..., and nr indistinguishable objects of an rth type, where n1+n2+...+nr = n, then there are,

n!
------------------

n1!n2!....nk!

Front 6

Combination

Back 6

A combination is a selection of all or part of a set of objects, without regard to the order in which objects are selected.

Front 7

Binomial Theorem

Back 7

If x and y are variables and n ∈ ℤ+, then,

Front 8

Multinomial Theorem

Front 9

Statement

Back 9

A statement (proposition) is a sentence that is either true or false, but not both.

Front 10

Tautology

Back 10

A statement is a tautology iff it is true for all truth values assignments of its components.

Example : p → (p v q)

Front 11

Contradiction

Back 11

A statement is a contradiction iff it is flase for all truth value assignment of its component.

Example: p ᴧ ⌐p

Front 12

Valid Argument

Back 12

Statement of the form (p1ᴧ p2ᴧ ···ᴧ pn)→q that is also a tautology is called a valid argument.

Front 13

Logical Equivalence

Back 13

Two propositions are logically equivalent if they have the same truth table for every possible assignment of primitive components.

Example: p Vs ⌐⌐p

Front 14

De Morgan's Law

Back 14

For statements p and q,

⌐(p ᴧ q) ⇔ ⌐p v ⌐q

⌐(p v q) ⇔ ⌐p ᴧ ⌐q

Front 15

Distributive Laws

Back 15

p ᴧ (q v r) ⇔ (p ᴧ q) v (p ᴧ r)

p v (q ᴧ r) ⇔ (p v q) ᴧ (p v r)

Front 16

Transitivity

Back 16

For any primitive statement p,q,r:

p ⇔ q and q ⇔ r imply p ⇔ r.

Front 17

Implication

Back 17

p → q

Front 18

Contrapositive

Back 18

⌐q → ⌐p

Front 19

Converse

Back 19

q → p

Front 20

Inverse

Back 20

⌐p → ⌐q

Front 21

Modus Ponens

Back 21

p

p → q OR (p ᴧ (p → q)) → q

-----------

q

Front 22

Syllogism

Back 22

p → q

q → r OR ((p → q ) ᴧ (q → r)) → (p → r)

-----------

p → r

Front 23

Modus Tollens

Back 23

p → q

⌐q OR ((p → q) ᴧ (⌐q)) → ⌐p

-----------

⌐p

Front 24

Conjuction

Back 24

p

q

-------

p ᴧ q

Front 25

Disjunctive Syllogism

Back 25

p v q

⌐q OR ((p v q) ᴧ ⌐q ) → p

---------

p

Front 26

Contradiction

Back 26

⌐p → F

-------------

p

Front 27

Quantifiers

Back 27

An open sentence contains variables, is neither true or false and when the variables are replaced with an actual quantity (from some universe), becomes true or false.

Front 28

Set

Back 28

A set is an unordered collection of objects. The objects in the set are called the ELEMENTS of the set. If x is an element of a set S, we denote this by x Є S. If x is not an element of a set S, we denote this by x Ɇ S.

Front 29

Empty Set

Back 29

The empty set is the set with no elements, and it is denoted by Ø.

Front 30

Subset

Back 30

A set B is said to be a subset of a set A if every element of B is also an element of A. In other words, x Є B implies x Є A. To denote that B is a subset of A, we write B ⊆ A.

Front 31

Equal Sets

Back 31

Two Sets A and B are equal (A = B) iff A ⊆ B and B ⊆ A.

Front 32

Cardinality

Back 32

If A is the finite set, then the cardinality of A is the number of distinct elements in A, and is denoted by |A|.

Front 33

Power Set

Back 33

Power Set of A is the set containing all the subsets of A.

Front 34

Union

Back 34

The union of two sets A and B is the set whose elements are elements of A, B, or both. It is denoted by A U B.

Therefore, A U B= {x | x Є A or x Є B}.

Front 35

Intersection

Back 35

The intersection of two sets A and B is the set whose elements are elements of both A and B. It is denoted by A ∩ B.

Therefore, A ∩ B = { x | x Є A and x Є B}.

Front 36

Difference

Back 36

Let A and B be sets. The diffence of A and B is the set whose elements are elements of A but not elements of B. It is denoted by A - B.

Therefore, A - B = { x |x Є A and x Є B }.

Front 37

Complement

Back 37

The complement of a set A is the set U - A whose elements are the elements of the universal set U that are not elements of A. It is denoted by Ā. Therefore, Ā = { x | x Ɇ A }.

Front 38

Sequence

Back 38

A Sequence is a list with items separated by commas.

Front 39

Sample Space

Back 39

A set of all possible outcomes is called sample space.

Front 40

Event

Back 40

An event is a subset of Sample Space.

Front 41

Principle of Mathematical Induction

Back 41

Let P(n) be a statement involving some integer n ≥ 1. If,

1. P(1) is true, and (Base Step)

2. ∀k ≥ 1, P(k) → P(k+1) (Inductive Step)

then ∀n ≥ 1, P(n) is true.

Front 42

Pascal's Identity

Front 43

Recursive Definition of Function

Back 43

A recursive definition of a function defines values of the function for some inputs in terms of the values of the same function for other inputs.

Front 44

Principle of Strong

Mathematical Induction

Back 44

Let P(n) be a statement involving some integer n ≥ N. If,

1. P(N) is true, and

2. if P(N), P(N+1),..., P(k) all hold, then P(K+1) must hold, then for all n ≥ N, P(n) is true.

Front 45

Divides

Back 45

If a and b are integers and there is an integer c such that b = a • c, then we say a divides b or b is divisible by a, and write a|b. In this case, we say that a is a factor or divisor of b and that b is a multiple of a. If a does not divide b, we write a ł b.

Front 46

Properties of Divisibility

Back 46

For all integers a, b and c, the following properties hold.

1) If a | b and b | c, then a | c

2) if a | b and a | c, then a | ( b + c)

3) if a | b, then a | bc

Front 47

Prime Number

Back 47

A prime Number is an integer greater than 1 whose only positive divisors are 1 and itself. An integer greater than 1 that is not prime is called a composite number.

Front 48

Test for Primality

Back 48

If n is a compiste number, then n has a prime divisor that is less than or equal to √n.

Front 49

The Division Algorithm

Back 49

Given any integer a and positive integer d, there exists unique integers q and r such that

a = dq + r with 0 ≤ r < d.

Front 50

Greatest Common Divisor

Back 50

Let a and b be integers that are not both 0. The greatest common divisor of a and b, denoted gcd(a,b), is the largest integer d such that d | a and d | b.

Front 51

Relatively Prime

Back 51

Two integers a and b are said to be relatively prime if gcd(a,b) = 1.

Front 52

Euclidean Algorithm

Back 52

Used to find the greatest common divisor of a and b. It is the last nonzero number.

Front 53

Common Multiple

Back 53

For a, b, c Є ℤ+, c is called common multiple of a, b if c is multiple of both a and b.

Front 54

Finite Set

Back 54

A set X is finite if ∃n∈Z+ and a bijection (1-to-1 and onto function) f:X→{1,..., n}.