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
  42. Rule of Contradiction
  43. Rule of Contradiction
  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
  60. Contradiction Method

    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