CS311  Discrete and Combinatorial Mathematics
Home > Flashcards > Print Preview
The flashcards below were created by user
bendable
on
FreezingBlue Flashcards. What would you like to do?





























Useful Equivalence:

Useful Equivalence:

Useful Equivalence:









Rule of Disjunctive Syllogism

Rule of Disjunctive Syllogism



Rule of Conjunctive Simplification

Rule of Conjunctive Simplification

Rule of Disjunctive Amplification

Rule of Disjunctive Amplification

Rule of Conditional Proof

Rule of Conditional Proof



Rule of the Constructive Dilema

Rule of the Constructive Dilema

Rule of the Destructive Dilemma

Rule of the Destructive Dilemma

The Rule of Universal Specification
 If an open statement becomes true for all replacements by the members in a given universe, then that open statement is true for each specific individual member in that universe.

The Rule of Universal Generalization
 If an open statement p(x) is proved to be true when x is replaced by an arbitrarily chosen element c from our universe, then the universally quantified statement for all x, p(x) is true.

ForwardBackward Method
When to use?
What to assume?
What to conclude?
How to use?
 When to use: As a first attempt
 What to assume: A
 What to conclude: B
 How to use: Work forward from A, and backward from B

Contrapositive Method
When to use?
What to assume?
What to conclude?
How to use?
 When to use: When B contains negation
 What to assume: NOT B
 What to conclude: NOT A
 How to use: Work forward from NOT B, and backward from NOT A

Contradiction Method
When to use?
What to assume?
What to conclude?
How to use?
 When to use: When B contains negation, or when ForwardBackward and Contrapositive methods fail.
 What to assume: A AND NOT B
 What to conclude: Some contradiction
 How to use: Word forward from A AND NOT B

Construction Method
When to use?
What to assume?
What to conclude?
How to use?
 When to use: When B contains existence
 What to assume: A
 What to conclude: That there is the desired object
 How to use: Construct the object, then show that it has the certain property and that something happens

Choose Method
When to use?
What to assume?
What to conclude?
How to use?
 When to use: When B contains forall
 What to assume: A, and choose an object with the certain property
 What to conclude: That something happens
 How to use: Work forward from A and the fact that the object has the certain property, also backwards from the something that happens

Specialization Method
When to use?
What to assume?
What to conclude?
How to use?
 When to use: When A contains forall
 What to assume: A
 What to conclude: B
 How to use: Work forward by specializing A to one particular object having the certain property

Forward Uniqueness Method
When to use?
What to assume?
What to conclude?
How to use?
 When to use: When A contains "unique"
 What to assume: That there is such an object, X
 What to conclude: That X and Y are the same, that is, X=Y
 How to use: Look for another object Y with the same properties as X

Direct Uniqueness Method
When to use?
What to assume?
What to conclude?
How to use?
 When to use: When B contains "unique"
 What to assume: That there are two such objects, and A
 What to conclude: The two objects are equal
 How to use: Work forward using A and the properties of the object, also work backward to shoe the objects are equal

Indirect Uniqueness Method
When to use?
What to assume?
What to conclude?
How to use?
 When to use: When B contains "unique"
 What to assume: There are two different objects, and A
 What to conclude: Some contradiction
 How to use: Work forward from A using the properties of the two objects and the fact that they are different

Induction Method
When to use?
What to assume?
What to conclude?
How to use?
 When to use: When a statement P(n) is true for each integer n >= n0
 What to assume: P(n) is true for n
 What to conclude: P(n0) is true, P(n+1) is true
 How to use: First prove P(n0), then use the assumption P(n) is true to prove that P(n+1) is true

Proof by Cases
When to use?
What to assume?
What to conclude?
How to use?
 When to use: When A has the form "C OR D"
 What to assume: Case 1: C / Case 2: D
 What to conclude: B
 How to use: First prove that C > B, then prove D > B

Proof by Elimination
When to use?
What to assume?
What to conclude?
How to use?
 When to use: When B has the form "C OR D"
 What to assume: (A AND NOT C) or (A AND NOT D)
 What to conclude: D or C
 How to use: Work forward from (A AND NOT C), and backward from D; or work forward from (A AND NOT D), and backward from C

Max/Min 1 Method
When to use?
What to assume?
What to conclude?
How to use?
 When to use: When A or B has the form "max S <= z" or "min S >= z"
 What to assume: (nothing)
 What to conclude: (nothing)
 How to use: Convert to "for all s in S, s <= z or s >= z", then choose (if in B) or specialization (if in A)

Max/Min 2 Method
When to use?
What to assume?
What to conclude?
How to use?
 When to use: When A or B has the form "max S >= z" or "min S <= z"
 What to assume: (nothing)
 What to conclude: (nothing)
 How to use: Convert to "there is an s in S such that s >= z or s <= z", then work forward (if in A) or use construction (if in B)