# CS311 - Discrete and Combinatorial Mathematics

### Card Set Information

 Author: bendable ID: 292988 Filename: CS311 - Discrete and Combinatorial Mathematics Updated: 2015-02-03 13:50:18 Tags: computer science discrete combinatorial mathematics Folders: computer science Description: CS311 Show Answers:

Home > Flashcards > Print Preview

The flashcards below were created by user bendable on FreezingBlue Flashcards. What would you like to do?

1. Law of Double Negation
2. Law of Double Negation
3. DeMorgan's Laws
4. DeMorgan's Laws
5. Commutative Laws
6. Commutative Laws
7. Associative Laws
8. Associative Laws
9. Distributive Laws
10. Distributive Laws
11. Idempotent Laws
12. Idempotent Laws
13. Identity Laws
14. Identity Laws
15. Inverse Laws
16. Inverse Laws
17. Domination Laws
18. Domination Laws
19. Absorption Laws
20. Absorption Laws
21. Implication
22. Implication
23. Inverse
24. Inverse
25. Converse
26. Converse
27. Contrapositive
28. Contrapositive
29. Useful Equivalence:
30. Useful Equivalence:
31. Useful Equivalence:
32. Rule Modus Ponens
33. Rule of Modus Ponens
34. Law of the Syllogism
35. Law of the Syllogism
36. Modus Tollens
37. Modus Tollens
38. Rule of Conjunction
39. Rule of Conjunction
40. Rule of Disjunctive Syllogism
41. Rule of Disjunctive Syllogism
44. Rule of Conjunctive Simplification
45. Rule of Conjunctive Simplification
46. Rule of Disjunctive Amplification
47. Rule of Disjunctive Amplification
48. Rule of Conditional Proof
49. Rule of Conditional Proof
50. Rule for Proof by Cases
51. Rule for Proof by Cases
52. Rule of the Constructive Dilema
53. Rule of the Constructive Dilema
54. Rule of the Destructive Dilemma
55. Rule of the Destructive Dilemma
56. 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.
57. 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.
58. Forward-Backward 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
59. 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

When to use?
What to assume?
What to conclude?
How to use?
• When to use: When B contains negation, or when Forward-Backward 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
61. 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
62. 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
63. 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
64. 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
65. 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
66. 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
67. 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
68. 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
69. 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
70. 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)
71. 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)

What would you like to do?

Home > Flashcards > Print Preview