- StudyBlue
- Discrete Mathematics

Morgan R.

Order of Logical Operators

1) ∃ or ∀

2) ¬

3) ∧

4) ∨

5) ⟶ or ⟵

6) ⟷

2) ¬

3) ∧

4) ∨

5) ⟶ or ⟵

6) ⟷

Converse

If P ⟶ Q

Converse: Q ⟶ P

Converse: Q ⟶ P

Advertisement

Inverse

If P ⟶ Q

Inverse: ¬P ⟶ ¬Q

Inverse: ¬P ⟶ ¬Q

Contrapositive

If P ⟶ Q

Contrapositive: ¬Q ⟶ ¬P

Contrapositive: ¬Q ⟶ ¬P

P ∨ Q

≡ ¬P ⟶ Q

Logical Equivalences of Conditionals

Logical Equivalences of Conditionals

P ∧ Q

≡ ¬(P ⟶ ¬Q)

Logical Equivalences of Conditionals

Logical Equivalences of Conditionals

¬(P ∧ Q)

≡ ¬P ∨ ¬Q

DeMorgan's Law

DeMorgan's Law

¬(P ∨ Q)

≡ ¬P ∧ ¬Q

DeMorgan's Law

DeMorgan's Law

Dual Command

Dual Compound of S is denoted by S*

Replace this/with this:

∧ / ∨

∨ / ∧

T / F

F / T

Replace this/with this:

∧ / ∨

∨ / ∧

T / F

F / T

Predicate

The action part of a sentence

Statement involving variables

Propositions produced from predicates

Propositional Function

P(x)

Statement involving variables

Propositions produced from predicates

Propositional Function

P(x)

DeMorgan's Laws

¬(P ∧ Q) ≡ ¬P ∨ ¬Q

¬(P ∨ Q) ≡ ¬P ∧ ¬Q

¬(P ∨ Q) ≡ ¬P ∧ ¬Q

Advertisement

DeMorgan's Law for Quantifiers

¬∀x P(x) ≡ ∃x ¬P(x)

¬∃x P(x) ≡ ∀x ¬P(x)

¬∃x P(x) ≡ ∀x ¬P(x)

¬∀x P(x)

Negation

≡ ∃x ¬P(x)

DeMorgan's Law for Quantifiers

≡ ∃x ¬P(x)

DeMorgan's Law for Quantifiers

¬∃x P(x)

Negation

≡ ∀x ¬P(x)

DeMorgan's Law for Quantifiers

≡ ∀x ¬P(x)

DeMorgan's Law for Quantifiers

∃x ¬P(x)

Equivalent Statement

≡ ¬∀x P(x)

DeMorgan's Law for Quantifiers

≡ ¬∀x P(x)

DeMorgan's Law for Quantifiers

∀x ¬P(x)

Equivalent Statement

≡ ¬∃x P(x)

DeMorgan's Law for Quantifiers

≡ ¬∃x P(x)

DeMorgan's Law for Quantifiers

P ⟶ Q

≡ ¬P ∨ Q

≡ ¬Q ⟶ ¬P

Logical Equivalences of Conditionals

≡ ¬Q ⟶ ¬P

Logical Equivalences of Conditionals

¬(P ⟶ Q)

≡ P ∧ ¬Q

Logical Equivalences of Conditionals

Logical Equivalences of Conditionals

(P ⟶ Q) ∧ (P ⟶ R)

≡ P ⟶ (Q ∧ R)

Logical Equivalences of Conditionals

Logical Equivalences of Conditionals

(P ⟶ R) ∧ (Q ⟶ R)

≡ (P ∨ Q) ⟶ R

Logical Equivalences of Conditionals

Logical Equivalences of Conditionals

(P ⟶ Q) ∨ (P ⟶ R)

≡ P ⟶ (Q ∨ R)

Logical Equivalences of Conditionals

Logical Equivalences of Conditionals

(P ⟶ R) ∨ (Q ⟶ R)

≡ (P ∧ Q) ⟶ R

Logical Equivalences of Conditionals

Logical Equivalences of Conditionals

P ⟷ Q

≡ (P ⟶ Q) ∧ (Q ⟶ P)

≡ ¬P ⟷ ¬Q

≡ (P ∧ Q) ∨ (¬P ∧ ¬Q)

Logical Equivalences of Bi-conditionals

≡ ¬P ⟷ ¬Q

≡ (P ∧ Q) ∨ (¬P ∧ ¬Q)

Logical Equivalences of Bi-conditionals

¬(P ⟷ Q)

≡ P ⟷ ¬Q

Logical Equivalences of Bi-conditionals

Logical Equivalences of Bi-conditionals

¬P ∨ ¬Q

≡ ¬(P ∧ Q)

DeMorgan's Laws

DeMorgan's Laws

¬P ∧ ¬Q

≡ ¬(P ∨ Q)

DeMorgan's Laws

DeMorgan's Laws

¬P ∨ Q

≡ P ⟶ Q

Logical Equiaalences of Conditionals

Logical Equiaalences of Conditionals

¬Q ⟶ ¬P

≡ P ⟶ Q

Logical Equivolences of Conditionals

Logical Equivolences of Conditionals

¬P ⟶ Q

≡ P ∨ Q

Logical Equivolences of Conditionals

Logical Equivolences of Conditionals

¬(P ⟶ ¬Q)

≡ P ∧ Q

Logical Equivolences of Conditionals

Logical Equivolences of Conditionals

P ∧ ¬Q

≡ ¬(P ⟶ Q)

Logical Equivolences of Conditionals

Logical Equivolences of Conditionals

P ⟶ (Q ∧ R)

≡ (P ⟶ Q) ∧ (P ⟶ R)

Logical Equivolences of Conditionals

Logical Equivolences of Conditionals

(P ∨ Q) ⟶ R

≡ (P ⟶ R) ∧ (Q ⟶ R)

Logical Equivolences of Conditionals

Logical Equivolences of Conditionals

P ⟶ (Q ∨ R)

≡ (P ⟶ Q) ∨ (P ⟶ R)

Logical Equivolences of Conditionals

Logical Equivolences of Conditionals

(P ∧ Q) ⟶ R

≡ (P ⟶ R) ∨ (Q ⟶ R)

Logical Equivolences of Conditionals

Logical Equivolences of Conditionals

(P ⟶ Q) ∧ (Q ⟶ P)

≡ P ⟷ Q

Logical Equivolences of Biconditionals

Logical Equivolences of Biconditionals

¬P ⟷ ¬Q

≡ P ⟷ Q

Logical Equivolences of Biconditionals

Logical Equivolences of Biconditionals

(P ∧ Q) ∨ (¬P ∧ ¬Q)

≡ P ⟷ Q

Logical Equivolences of Biconditionals

Logical Equivolences of Biconditionals

P ⟷ ¬Q

≡ ¬(P ⟷ Q)

Logical Equivolences of Biconditionals

Logical Equivolences of Biconditionals

Bit String

A sequene of zero or more bits. The length of this string is the number of bits in the string

Contradiction

A compound proposition that is always false

Logically Equivalent

The compound propositions P and Q are logically equivalent if P ⟷ Q is a tautology

P ≡ Q denotes logical equivAlence

P ≡ Q denotes logical equivAlence

Logical Equivolence of Conditional Statements

P ⟶ Q ≡ ¬P ∨ Q

P ⟶ Q ≡ ¬Q ⟶ ¬P

P ∨ Q ≡ ¬P ⟶ Q

P ∧ Q ≡ ¬(P ⟶ ¬Q)

¬(P ⟶ Q) ≡ P ∧ ¬Q

(P ⟶ Q) ∧ (P ⟶ R) ≡ P ⟶ (Q ∧ R)

(P ⟶ R) ∧ (Q ⟶ R) ≡ (P ∨ Q) ⟶ R

(P ⟶ Q) ∨ ( P ⟶ R) ≡ P ⟶ (Q ∨ R)

(P ⟶ R) ∨ (Q ⟶ R) ≡ (P ∧ Q) ⟶ R

P ⟶ Q ≡ ¬Q ⟶ ¬P

P ∨ Q ≡ ¬P ⟶ Q

P ∧ Q ≡ ¬(P ⟶ ¬Q)

¬(P ⟶ Q) ≡ P ∧ ¬Q

(P ⟶ Q) ∧ (P ⟶ R) ≡ P ⟶ (Q ∧ R)

(P ⟶ R) ∧ (Q ⟶ R) ≡ (P ∨ Q) ⟶ R

(P ⟶ Q) ∨ ( P ⟶ R) ≡ P ⟶ (Q ∨ R)

(P ⟶ R) ∨ (Q ⟶ R) ≡ (P ∧ Q) ⟶ R

Logical Equivolence of Conditional Statements

P ⟷ Q ≡ (P ⟶ Q) ∧ (Q ⟶ P)

P ⟷ Q ≡ ¬ P ⟷ ¬Q

P ⟷ Q ≡ (P ∧ Q) ∨ (¬P ∧ ¬Q)

¬(P ⟷ Q) ≡ P ⟷ ¬Q

P ⟷ Q ≡ ¬ P ⟷ ¬Q

P ⟷ Q ≡ (P ∧ Q) ∨ (¬P ∧ ¬Q)

¬(P ⟷ Q) ≡ P ⟷ ¬Q

When is ∀x P(x) true

P(x) is true for every x

When is ∀x P(x) false

There is an x where P(x) is false

Counterexample

When ∀x P(x) is false

When is ∃x P(x) true

There is an x for which P(x) is true

When is ∃x P(x) false

P(x) is false for every x

Logical Equivalences on Quantifiers

Statements involving predicates and quantifiers are logically equivalent iff they have the same truth value

S ≡ T indicates 2 statements that are logically equivalent

S ≡ T indicates 2 statements that are logically equivalent

Negations for DeMorgan's Laws for Quantifiers

¬∃x P(x)

¬∀x P(x)

¬∀x P(x)

Equivalent Statements for DeMorgan's Laws for Quantifiers

∀x ¬P(x)

∃x ¬P(x)

∃x ¬P(x)

When is the negation ¬∃x P(x) true

For every x, P(x) is false

When is the negation ¬∃x P(x) false

There is an x for which P(x) is true

When is the negation ¬∀x P(x) true

There is an x for which P(x) is false

When is the negation ¬∀x P(x) false

P(x) is true for every x

Prolog Facts

Define predicates by specifying the elements that satisfy these predicates

Prolog Rules

Used to define new predicates using those already defined by Prolog Facts

Nested Quantifiers

Two quantifiers are nested if one is within scope of the other

ex) ∀x ∀y P(x, y)

ex) ∀x ∀y P(x, y)

When is ;∀x ∀y P(x, y) true

P(x, y) is true for pair x, y

When is ∀x ∀y P(x, y) false

There is a pair x, y for which P(x, y) is false

When is ∀y ∀x P(x, y) true

P(x, y) is true for every pair x, y

When is ∀y ∀x P(x, y) false

There is a pair x, y for which P (x, y) is false

When is ∀x ∃y P(x, y) true

For every x there is a y for which P(x, y) is true

When is ∀x ∃y P(x, y) false

There is an x such that P(x, y) is false for every y

When is ∃x ∀y P(x, y) true

There is an x for which P(x, y) is true for every y

When is ∃x ∀y P(x, y) false

For every x there is a y for which P(x, y) is false

When is ∃x ∃y P(x, y) true

There is a pair x, y for which P(x, y) is true

When is ∃x ∃y P(x, y) false

P(x, y) is false for every pair x, y

When is ∃y ∃x P(x, y) true

There is a pair x, y for which P(x, y) is true

When is ∃x ∃y P(x, y) false

P(x, y) is false for every pair x, y

Transitive Property

If a=b and b=c, then a=c

If a=b and b=c, then a=c

Transitive Property

Fallacies

P ⟶ Q

Q

__________

∴ P

Affirming the conclusion

P ⟶ Q

¬P

____________

∴ ¬Q

Denying the hypothesis

Q

__________

∴ P

Affirming the conclusion

P ⟶ Q

¬P

____________

∴ ¬Q

Denying the hypothesis

Affirming the Conclusion

P ⟶ Q

Q

__________

∴ P

Q

__________

∴ P

Denying the Hypothesis

P ⟶ Q

¬P

____________

∴ ¬Q

¬P

____________

∴ ¬Q

Rules of Inference for Quantified Statements

Universal Generalization

P(a) for all a in domain

_______________________

∴ ∀x P(x)

Existential Generalization

P(a) for some a in the domain

____________________________

∴ ∃x P(x)

Universal Instantiation

∀x P(x)

________________

∴ P(a) for any a

Existential Generalization

∃x P(x)

_________________

∴ P(a) for some a

P(a) for all a in domain

_______________________

∴ ∀x P(x)

Existential Generalization

P(a) for some a in the domain

____________________________

∴ ∃x P(x)

Universal Instantiation

∀x P(x)

________________

∴ P(a) for any a

Existential Generalization

∃x P(x)

_________________

∴ P(a) for some a

Universal Generalization

P(a) for all a in domain

_______________________

∴ ∀x P(x)

_______________________

∴ ∀x P(x)

P(a) for all a in domain

_______________________

∴ ∀x P(x)

_______________________

∴ ∀x P(x)

Universal General

Existential Generalization

P(a) for some a in the domain

____________________________

∴ ∃x P(x)

____________________________

∴ ∃x P(x)

P(a) for some a in the domain

____________________________

∴ ∃x P(x)

____________________________

∴ ∃x P(x)

Exis

Universal Instantiation

P(a) for some a in the domain

____________________________

∴ ∃x P(x)

____________________________

∴ ∃x P(x)

P(a) for some a in the domain

____________________________

∴ ∃x P(x)

____________________________

∴ ∃x P(x)

Universal Instat

Existential Instantiation

∃x P(x)

_________________

∴ P(a) for some a

_________________

∴ P(a) for some a

∃x P(x)

_________________

∴ P(a) for some a

_________________

∴ P(a) for some a

Existential Instantiation

Rules of Inference

Modus Ponens

P ⟶ Q

P

_______

∴ Q

P

_______

∴ Q

P ⟶ Q

P

_______

∴ Q

P

_______

∴ Q

Modus Ponens

Modus Tollens

P ⟶ Q

¬Q

_________

∴ ¬P

¬Q

_________

∴ ¬P

P ⟶ Q

¬Q

_________

∴ ¬P

¬Q

_________

∴ ¬P

Modus Tollens

Hypothetical Syllogism

P ⟶ Q

Q ⟶ R

_________

∴ P ⟶ R

Q ⟶ R

_________

∴ P ⟶ R

P ⟶ Q

Q ⟶ R

_________

∴ P ⟶ R

Q ⟶ R

_________

∴ P ⟶ R

Hypothetical Syllogism

Addition

P

________

∴ P ∧ Q

________

∴ P ∧ Q

P

________

∴ P ∧ Q

________

∴ P ∧ Q

Addition

Disjunctive Syllogism

P ∨ Q

¬P

_____

∴ Q

¬P

_____

∴ Q

P ∨ Q

¬P

_____

∴ Q

¬P

_____

∴ Q

Disjunctive Syllogism

Simplification

P ∧ Q

______

∴ P

______

∴ P

P ∧ Q

______

∴ P

______

∴ P

Simplification

Conjunction

P

Q

________

∴ P ∧ Q

Q

________

∴ P ∧ Q

P

Q

________

∴ P ∧ Q

Q

________

∴ P ∧ Q

Conjunction

Resolution

P ∨ Q

¬P ∨ R

________

∴ Q ∨ R

¬P ∨ R

________

∴ Q ∨ R

Even

N is even if there exists k ∈ ℕ such that n=2k

Odd

N is odd if there exists k ∈ ℕ such that n-=2k+1

Rational Number

ℚ

The number n is rational if it can be expressed in the n=p⁄q where p, q ∈ ℤ and q≠0

The number n is rational if it can be expressed in the n=p⁄q where p, q ∈ ℤ and q≠0

Direct Proof

P ⟶ Q, assume that P is true and prove Q with rules of inference

Proof by Contraposition

P ⟶ Q, use contrapositive ¬Q ⟶ ¬P and prove with rules of inference

Proof by Contradiction

P ⟶ Q, suppose ¬P and prove Q, if ¬P ⟶ Q is true then it's false

Set Notation

{n∣n=2k+1 for k=0, 1, 2, 3,...}

Natural Numbers

ℕ

{0, 1, 2, 3, ...}

Counting numbers

{0, 1, 2, 3, ...}

Counting numbers

ℕ

Natural numbers

{0, 1, 2, 3, ...}

Counting numbers

{0, 1, 2, 3, ...}

Counting numbers

Integers

ℤ

{... , -2, -1, 0, 1, 2, ...}

{... , -2, -1, 0, 1, 2, ...}

ℤ

Integers

{... , -2, -1, 0, 1, 2, ...}

{... , -2, -1, 0, 1, 2, ...}

ℚ

Rational Number

{p⁄qp ∈ ℤ, q ∈ ℤ, q ≠ 0}

{p⁄qp ∈ ℤ, q ∈ ℤ, q ≠ 0}

Real Number

ℝ

ℝ

Real Number

A ∈ B

A is an element of B

A is an element of B

A ∈ B

A ∉ B

A is not an element of B

A is not an element of B

A ∉ B

A ⊂ B

A is a proper subset of B

If A ⊆ B and there must be an element of B that is not an element of A

If A ⊆ B and there must be an element of B that is not an element of A

A is a proper subset of B

A ⊂ B

A ⊆ B

A is a subset of B

A is a subset of B if every element of A is also in B

A is a subset of B if every element of A is also in B

A is a subset of B

A ⊆ B

A ⊈ B

A is not a subset of B

A is not a subset of B

A ⊈ B

A ∪ B

Union of A and B

A ∪ B = {x | x ∈ A ∨ x ∈ B}

A ∪ B = {x | x ∈ A ∨ x ∈ B}

Union of A and B

A ∪ B

A ∪ B = {x∣x ∈ A ∨ x ∈ B}

A ∪ B = {x∣x ∈ A ∨ x ∈ B}

A ∩ B

Intersection of A and B

A ∩ B = {x∣x ∈ A ∧ x ∈ B}

A ∩ B = {x∣x ∈ A ∧ x ∈ B}

Intersection of A and B

A ∩ B

A ∩ B = {x∣x ∈ A ∧ x ∈ B}

A ∩ B = {x∣x ∈ A ∧ x ∈ B}

∅ or { }

Empty Set

Empty Set

∅ { }

Power Set

P(A) = {B∣B ⊆ A}

P(a, b, c} = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}

P(a, b, c} = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}

P(A) = {B∣B ⊆ A}

Power set

Cardinality of a Set

The sets A and B have the same cardinality if and only if there is a one-to-one correspondence from A to B

|A| = n, how many elements A hasA = {a, b, c}, ∴ |A| = 3

Set

An unordered collection of objects

An unordered collection of objects

Set

A = B

If they have the same elements

∀x (x ∈ A ⟷ x ∈ B)

∀x (x ∈ A ⟷ x ∈ B)

U (sets)

Universal Set

Universal Set

U

Ordered n-tuples

(a₁, a₂, a₃, a₄, ..., a_{n)}

Cartesian Product

A×B = {(a, b)∣a ∈ A ∧ b ∈ B}

A×B= {(a, b)∣a ∈ A ∧ b ∈ B}

Cartesian Product

Truth Set

P(x) = {x ∈ D∣P(x)}

The set of elements x in the domain such that P(x) is true

The set of elements x in the domain such that P(x) is true

P(x) = {x ∈ D∣P(x)}

Truth Set

The set of elements x in the domain such that P(x) is true

The set of elements x in the domain such that P(x) is true

Disjoint (sets)

If the A ∩ B = ∅

A ∩ B=∅

Disjoint

A-B

A-B = {x∣x ∈ A ∧ x ∉ B}

The set containing the elements that are in A but not B

Complement of B with respect to A

The set containing the elements that are in A but not B

Complement of B with respect to A

Complement of B with respect to A

A-B = {x∣x ∈ A ∧ x ∉ B}

The set containing the elements of A that are not in B

The set containing the elements of A that are not in B

Complement of A

A^{c}

U-A = A^{c }= {x∣x ∈ U, x ∉ A}

U-A = A

A^{c}

A^{c }= {x∣x ∈ U, x ∉ A}

Complement of A

Complement of A

Set Identities

Identity Laws

Domination Laws

Idempotent Laws

Complement Laws

Commutative Laws

Associative Laws

Distributive Laws

DeMorgan's Laws

Absorption Laws

Complement Laws

Domination Laws

Idempotent Laws

Complement Laws

Commutative Laws

Associative Laws

Distributive Laws

DeMorgan's Laws

Absorption Laws

Complement Laws

Identity Laws

A ∪ ∅ = A

A ∩ U = A

A ∩ U = A

Domination Laws

A ∩ ∅ = ∅

A ∪ U = U

A ∪ U = U

Idempotent Laws

A ∪ A = A

A ∩ A = A

A ∩ A = A

Complementation Law

(A^{c})^{c} = A

Commutative Laws

A ∩ B = B ∩ A

A ∪ B = B ∪ A

A ∪ B = B ∪ A

Associative Laws

A ∩ (B ∩ C) = (A ∩ B) ∩ C

A ∪ (B ∪ C) = (A ∪ B) ∪ C

A ∪ (B ∪ C) = (A ∪ B) ∪ C

Distributive Laws

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

DeMorgan's Laws

(A ∩ B)^{c} = A^{c} ∪ B^{c}

(A ∪ B)^{c} = A^{c} ∩ B^{c}

(A ∪ B)

Absorption Laws

A ∪ (A ∩ B) = A

A ∪ (A ∩ B) = A

A ∪ (A ∩ B) = A

Complement Laws

A ∪ A^{c} = U

A ∩ A^{c} = ∅

A ∩ A

Union Collection

The set that is the collection of sets and contains the elements that are members of at least one set

Intersection Collection

The set that is the collection of sets and contains the elements that are members of all the sets in the collection

Injection

One-to-one

One-to-one

Injection

Surjection

Onto

Onto

Surjection

Bijection

Both one-to-one and onto

Both one-to-one and onto

Bijection

Arithmetic Progression

a, a+d, a+2d, a+3d, ..., a+nd

a, a+d, a+2d, a+3d, ..., a+nd

Arithmetic progression

Algorithm

A step by step process for accomplishing a task

Non-ambiguous

It finishes

Non-ambiguous

It finishes

A step by step process for completing a task

Algorithm

Algorithm Complexity

The number of steps is the combination of the number of comparisons and the number of swaps/assignments

Function

A function f: A ⟶ B is a(n): where each member of A is paired with exactly one member of B.

Relationship

Pairing

Mapping

Relationship

Pairing

Mapping

Domain of a function

A

Codomain of a function

B

Range of a function

Values of b ∈ B that get hit are in the range

Subset of codomain

Subset of codomain

One-To-One Function

A function f: A ⟶ B is one-to-one if x₁, x₂ ∈ A and f(x₁) = f(x₂) implying x₁= x₂

Onto Function

A function f: A ⟶ B is onto if and only if for every b ∈ B there is an element a ∈ A with f(a) = b.

Composition Function

Let g: A ⟶ B and f: B ⟶ C. The composition of f and g, denoted by f ◦ g, is defined by (f ◦ g)(a) = f(g(a)).

Geometric Progression

a, ar, ar², ar³, ..., arⁿ

Computational Complexity

[(n-1)n]/2

Big-Ο Notation

Let f ∈ ℤ, g ∈ ℤ. We say that f(x) is Ο(g(x)) if there are constants C and k such that f(x) ≤ C⋅g(x) for all n ≥ k

Floor Function

Assigns to the real number x the largest integer that is less than or equal to x. The value of the floor function at x is denoted by ⎣x⎦.

Ceiling Function

Assigns to the real number x the smallest integer that is greater than or equal to x. The value of the ceiling function at x is denoted by ⎡x⎤.

Properties of Floor and Ceiling Functions (n is and integer)

⎣x⎦ = n if and only if n ≤ x < n+1

⎡x⎤ = n if and only if n-1 < x ≤ n

⎣x⎦ = n if and only if x-1 < n ≤ x

⎡x⎤ = n if and only if x ≤ n < x+1

x-1 < ⎣x⎦ ≤ x ≤ ⎡x⎤ < x+1

⎣-x⎦ = -⎡x⎤

⎡-x⎤ = -⎣x⎦

⎣x+n⎦ = ⎣x⎦+n

⎡x+n⎤ = ⎡x⎤+n

Inverse Functions

Let f be a one-to-one function in A ⟶ B. The inverse function of f is the function that assigns to b ∈ B some a ∈ A such that f(a) = b. The inverse of the function f is denoted by f⁻¹. Hence f⁻¹(b) = a when f(a) = b.

f⁻¹ ≠ 1/f(x).

Characteristic Function

S ⊆ U

The characteristic function ΧΧ_{s}(x) = {1, if x ∈ S; or 0, if x ∉S}

Summation Notation

a_{m}, a_{m+1}, a_{m+2}, ... , a_{n}

∑^{n}_{j=m} a_{j}

Formula for a Sum of a Geometric Series

If a and r are real numbers and r ≠ 0, then:

∑^{n}_{j=0} ar^{j} = {[(ar^{n+1}-a)/(r-1)], if r ≠ 1; (n+1)⋅a, if r = 1}

Other Sum of Series Formulas

∑^{n}_{j=1} j = [n(n+1)]/2

∑^{n}_{j=1} j^{2} = [n(n+1)(2n+1)]/6

∑^{n}_{j=1} j^{3} = [n2(n+1)^{2}]/4

∑^{∞}_{j=0} x^{k}, |x| < 1 = 1/(1-x)

∑^{∞}_{j=1} jx^{j-1}, |x| < 1 = 1/(1-x)^{2}

Countable

A set that is either finite or has the same cardinality as the set of positive integers.

Double Summations

1^{st} expand the inner summation, then continue computing.

∑
Product Notation

a_{m}, a_{m+1}, a_{m+2}, ... , a_{n}

∏^{n}_{j=m} a_{j} = a_{m}×a_{m+1}×a_{m+2}×...×a_{n}

∏

Palindrome

String that reads the same forward and backward

Selection Sort

Find the least element and move it to the front of the list. Then find the least among the remaining elements and put it in the 2^{nd} position, etc.

EX)

(3) 5 7 (1) 2

(1) (5) 7 (3) (2)

1 (2) (7) (3) (5)

1 2 (3) (7) (5)

1 2 3 (5) (7)

EX)

(3) 5 7 (1) 2

(1) (5) 7 (3) (2)

1 (2) (7) (3) (5)

1 2 (3) (7) (5)

1 2 3 (5) (7)

Cantor Diagonalization Argument

Proved that the ℝ is not countable.

Procedure Statement

Pseudocode (algorithm) starts with procedure statement naming the algorithm, listing input variables and type of each.

ex)**procedure** *maximum* (L: list of integers)

meaning: algorithm is named maximum and it finds the maximum of a list of integers

ex)

meaning: algorithm is named maximum and it finds the maximum of a list of integers

Assignment Statement

Assigns values to variables. In statement, the left hand side is the name of the variable and the right hand side is an expression.

ex) variable ≔ expression; max ≔ a; x ≔ largest integer in L

ex) variable ≔ expression; max ≔ a; x ≔ largest integer in L

Block of Statements

Statements can be grouped into block that are set off using begin and end statements. Statements are executed sequentially

ex)**begin**

statement 1

statement 2

statement 3

.

.

.

statement n

**end**

ex)

statement 1

statement 2

statement 3

.

.

.

statement n

Conditional Constructions

or

begin

block of statements

"For" Loop Constructions

**for** *variable* ≔ *initial value* **to** *final value*

statement

__or__

**for ***variable* ≔ *initial value* **to ***final value*

**begin**

block of statements

**end**

__or__

*sum* ≔ 0

**for** *i* ≔ 1 **to** *n*

*sum* ≔ *sum* +* i*

__or__

**for** all elements with a certain property

statement

block of statements

"While" Loop Construction

statement

block of statements

n

"The semester I found StudyBlue, I went from a 2.8 to a 3.8, and graduated with honors!"

Jennifer Colorado School of Mines© 2014 StudyBlue Inc. All rights reserved.