Discrete Mathematics

About this deck

By: Morgan Rawson
Created: 2011-11-29
Size: 204 flashcards
Views: 62

About StudyBlue

STUDYBLUE makes things that make you better at school. Things like online flashcards with photos and audio. Things like personalized quizzes and friendly reminders about when (and what) to study next. Think of it as a digital backpack™: access to all of your study materials online and on your phone. STUDYBLUE exists to make studying efficient and effective for every student, for free. Join us.

“Simply amazing. The flash cards are smooth, there are many different types of studying tools, and there is a great search engine. I praise you on the awesomeness.”
Dennis

Sign up (free) to study this.

Order of Logical Operators

1) ∃ or ∀
2) ¬
3) ∧
4) ∨
5) ⟶ or ⟵
6) ⟷

Converse

If P ⟶ Q
Converse: Q ⟶ P

Inverse

If P ⟶ Q
Inverse: ¬P ⟶ ¬Q

Contrapositive

If P ⟶ Q
Contrapositive: ¬Q ⟶ ¬P

Dual Command

Dual Compound of S is denoted by S*
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)

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

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

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)

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

Transitive Property

Fallacies

P ⟶ Q
Q
__________
∴ P
Affirming the conclusion

P ⟶ Q
¬P
____________
∴ ¬Q
Denying the hypothesis

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

Universal Generalization

P(a) for all a in domain
_______________________
∴ ∀x P(x)

Universal General

Existential Generalization

P(a) for some a in the domain
____________________________
∴ ∃x P(x)

Exis

Universal Instantiation

P(a) for some a in the domain
____________________________
∴ ∃x P(x)

Universal Instat

Existential Instantiation

∃x P(x)
_________________
∴ P(a) for some a

Existential Instantiation

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

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

ℕ

Natural numbers
{0, 1, 2, 3, ...}
Counting numbers

Integers

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

ℤ

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

ℚ

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

Real Number

ℝ

Real Number

∅ or { }

Empty 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 has
A = {a, b, c}, ∴ |A| = 3

Set

An unordered collection of objects

Set

U (sets)

Universal Set

Truth Set

P(x) = {x ∈ D∣P(x)}
The set of elements x in the domain such that P(x) is true

Disjoint (sets)

If the A ∩ B = ∅

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

Set Identities

Identity Laws
Domination Laws
Idempotent Laws
Complement Laws
Commutative Laws
Associative Laws
Distributive Laws
DeMorgan's Laws
Absorption Laws
Complement Laws

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

Injection

Surjection

Onto

Surjection

Bijection

Both one-to-one and onto

Bijection

Arithmetic Progression

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

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

Range of a function

Values of b ∈ B that get hit are in the range
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ⁿ

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 of S is the function form U ⟶ {0, 1} such that:

Χ_s(x) = {1, if x ∈ S; or 0, if x ∉S}

Formula for a Sum of a Geometric Series

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

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

Other Sum of Series Formulas

∑ⁿ_j=1 j = [n(n+1)]/2

∑ⁿ_j=1 j² = [n(n+1)(2n+1)]/6

∑ⁿ_j=1 j³ = [n2(n+1)²]/4

∑^∞_j=0 x^k, |x| < 1 = 1/(1-x)

∑^∞_j=1 jx^j-1, |x| < 1 = 1/(1-x)²

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.

∑⁴_i=1 ∑³_j=1 i⋅j = ∑⁴_i=1 (i+2i+3i) = ∑⁴_i=1 6i = 6+12+18+24 = 60

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)

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

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

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

Conditional Constructions

if condition then statement
or
if condition then
begin
block of statements
end

"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

"While" Loop Construction

while condition
statement
or
while condition
begin
block of statements
end
or
sum ≔ 0
while n > 0
begin
sum ≔ sum + n
n ≔ n - 1
end

About this deck

By: Morgan Rawson
Created: 2011-11-29
Size: 204 flashcards
Views: 62

About StudyBlue

“Simply amazing. The flash cards are smooth, there are many different types of studying tools, and there is a great search engine. I praise you on the awesomeness.”
Dennis