# Discrete Mathematics

- StudyBlue
- Iowa
- Cornell College
- Discrete Mathematics

**Created:**2011-11-29

**Last Modified:**2011-12-08

2) ¬

3) ∧

4) ∨

5) ⟶ or ⟵

6) ⟷

Converse: Q ⟶ P

Inverse: ¬P ⟶ ¬Q

Contrapositive: ¬Q ⟶ ¬P

Logical Equivalences of Conditionals

Logical Equivalences of Conditionals

DeMorgan's Law

DeMorgan's Law

Replace this/with this:

∧ / ∨

∨ / ∧

T / F

F / T

Statement involving variables

Propositions produced from predicates

Propositional Function

P(x)

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

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

≡ ∃x ¬P(x)

DeMorgan's Law for Quantifiers

≡ ∀x ¬P(x)

DeMorgan's Law for Quantifiers

≡ ¬∀x P(x)

DeMorgan's Law for Quantifiers

≡ ¬∃x P(x)

DeMorgan's Law for Quantifiers

≡ ¬Q ⟶ ¬P

Logical Equivalences of Conditionals

Logical Equivalences of Conditionals

Logical Equivalences of Conditionals

Logical Equivalences of Conditionals

Logical Equivalences of Conditionals

Logical Equivalences of Conditionals

≡ ¬P ⟷ ¬Q

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

Logical Equivalences of Bi-conditionals

Logical Equivalences of Bi-conditionals

DeMorgan's Laws

DeMorgan's Laws

Logical Equiaalences of Conditionals

Logical Equivolences of Conditionals

Logical Equivolences of Conditionals

Logical Equivolences of Conditionals

Logical Equivolences of Conditionals

Logical Equivolences of Conditionals

Logical Equivolences of Conditionals

Logical Equivolences of Conditionals

Logical Equivolences of Conditionals

Logical Equivolences of Biconditionals

Logical Equivolences of Biconditionals

Logical Equivolences of Biconditionals

Logical Equivolences of Biconditionals

P ≡ Q denotes logical equivAlence

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 ≡ ¬ P ⟷ ¬Q

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

¬(P ⟷ Q) ≡ P ⟷ ¬Q

S ≡ T indicates 2 statements that are logically equivalent

¬∀x P(x)

∃x ¬P(x)

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

Q

__________

∴ P

Affirming the conclusion

P ⟶ Q

¬P

____________

∴ ¬Q

Denying the hypothesis

Q

__________

∴ P

¬P

____________

∴ ¬Q

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

_______________________

∴ ∀x P(x)

_______________________

∴ ∀x P(x)

____________________________

∴ ∃x P(x)

____________________________

∴ ∃x P(x)

____________________________

∴ ∃x P(x)

____________________________

∴ ∃x P(x)

_________________

∴ P(a) for some a

_________________

∴ P(a) for some a

P

_______

∴ Q

P

_______

∴ Q

¬Q

_________

∴ ¬P

¬Q

_________

∴ ¬P

Q ⟶ R

_________

∴ P ⟶ R

Q ⟶ R

_________

∴ P ⟶ R

________

∴ P ∧ Q

________

∴ P ∧ Q

¬P

_____

∴ Q

¬P

_____

∴ Q

______

∴ P

______

∴ P

Q

________

∴ P ∧ Q

Q

________

∴ P ∧ Q

¬P ∨ R

________

∴ Q ∨ R

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

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

Counting numbers

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

Counting numbers

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

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

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

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

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

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

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

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

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

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

A = {a, b, c}, ∴ |A| = 3

∀x (x ∈ A ⟷ x ∈ B)

_{n)}

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

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

Complement of B with respect to A

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

^{c}

U-A = A

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

^{c}

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

Complement of A

Domination Laws

Idempotent Laws

Complement Laws

Commutative Laws

Associative Laws

Distributive Laws

DeMorgan's Laws

Absorption Laws

Complement Laws

A ∩ U = A

A ∪ U = U

A ∩ A = A

^{c})

^{c}= A

A ∪ B = B ∪ A

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

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

^{c}= A

^{c}∪ B

^{c}

(A ∪ B)

^{c}= A

^{c}∩ B

^{c}

A ∪ (A ∩ B) = A

^{c}= U

A ∩ A

^{c}= ∅

Non-ambiguous

It finishes

Relationship

Pairing

Mapping

Subset of codomain

_{s}of S is the function form U ⟶ {0, 1} such that:

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

_{m}, a

_{m+1}, a

_{m+2}, ... , a

_{n}

^{n}

_{j=m}a

_{j}

^{n}

_{j=0}ar

^{j}= {[(ar

^{n+1}-a)/(r-1)], if r ≠ 1; (n+1)⋅a, if r = 1}

^{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}

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

^{4}

_{i=1}∑

^{3}

_{j=1}i⋅j = ∑

^{4}

_{i=1}(i+2i+3i) = ∑

^{4}

_{i=1}6i = 6+12+18+24 = 60

_{m}, a

_{m+1}, a

_{m+2}, ... , a

_{n}

∏

^{n}

_{j=m}a

_{j}= a

_{m}×a

_{m+1}×a

_{m+2}×...×a

_{n}

^{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)

**procedure**

*maximum*(L: list of integers)

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

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

ex)

**begin**

statement 1

statement 2

statement 3

.

.

.

statement n

**end**

**if**condition

**then**statement

or

**if**condition

**then**

begin

begin

block of statements

**end**

**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**condition

statement

__or__

**while**condition

**begin**

block of statements

**end**

__or__

*sum*≔ 0

**while**

*n*> 0

**begin**

*sum*≔

*sum*+

*n*

n≔

n

*n -*1

**end**

#### Words From Our Students

"StudyBlue is great for studying. I love the study guides, flashcards, and quizzes. So extremely helpful for all of my classes!"

Alice, Arizona State University

"I'm a student using StudyBlue, and I can 100% say that it helps me so much. Study materials for almost every subject in school are available in StudyBlue. It is so helpful for my education!"

Tim, University of Florida

"StudyBlue provides way more features than other studying apps, and thus allows me to learn very quickly! I actually feel much more comfortable taking my exams after I study with this app. It's amazing!"

Jennifer, Rutgers University

"I love flashcards but carrying around physical flashcards is cumbersome and simply outdated. StudyBlue is exactly what I was looking for!"

Justin, LSU