CS311 - Discrete and Combinatorial Mathematics

The flashcards below were created by user bendable on FreezingBlue Flashcards.

  1. Law of Double Negation
    Image Upload
  2. Image Upload
    Law of Double Negation
  3. DeMorgan's Laws
    Image Upload
  4. Image Upload
    DeMorgan's Laws
  5. Commutative Laws
    Image Upload
  6. Image Upload
    Commutative Laws
  7. Associative Laws
    Image Upload
  8. Image Upload
    Associative Laws
  9. Distributive Laws
    Image Upload
  10. Image Upload
    Distributive Laws
  11. Idempotent Laws
    Image Upload
  12. Image Upload
    Idempotent Laws
  13. Identity Laws
    Image Upload
  14. Image Upload
    Identity Laws
  15. Inverse Laws
    Image Upload
  16. Image Upload
    Inverse Laws
  17. Domination Laws
    Image Upload
  18. Image Upload
    Domination Laws
  19. Absorption Laws
    Image Upload
  20. Image Upload
    Absorption Laws
  21. Implication
    Image Upload
  22. Image Upload
    Implication
  23. Inverse
    Image Upload
  24. Image Upload
    Inverse
  25. Converse
    Image Upload
  26. Image Upload
    Converse
  27. Contrapositive
    Image Upload
  28. Image Upload
    Contrapositive
  29. Useful Equivalence:
    Image Upload
    Image Upload
  30. Useful Equivalence:
    Image Upload
    Image Upload
  31. Useful Equivalence:
    Image Upload
    Image Upload
  32. Rule Modus Ponens
    Image Upload
  33. Image Upload
    Rule of Modus Ponens
  34. Law of the Syllogism
    Image Upload
  35. Image Upload
    Law of the Syllogism
  36. Modus Tollens
    Image Upload
  37. Image Upload
    Modus Tollens
  38. Rule of Conjunction
    Image Upload
  39. Image Upload
    Rule of Conjunction
  40. Rule of Disjunctive Syllogism
    Image Upload
  41. Image Upload
    Rule of Disjunctive Syllogism
  42. Rule of Contradiction
    Image Upload
  43. Image Upload
    Rule of Contradiction
  44. Rule of Conjunctive Simplification
    Image Upload
  45. Image Upload
    Rule of Conjunctive Simplification
  46. Rule of Disjunctive Amplification
    Image Upload
  47. Image Upload
    Rule of Disjunctive Amplification
  48. Rule of Conditional Proof
    Image Upload
  49. Image Upload
    Rule of Conditional Proof
  50. Rule for Proof by Cases
    Image Upload
  51. Image Upload
    Rule for Proof by Cases
  52. Rule of the Constructive Dilema
    Image Upload
  53. Image Upload
    Rule of the Constructive Dilema
  54. Rule of the Destructive Dilemma
    Image Upload
  55. Image Upload
    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.
    • Image Upload
  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.
    • Image Upload
  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)
Author:
bendable
ID:
292988
Card Set:
CS311 - Discrete and Combinatorial Mathematics
Updated:
2015-02-03 18:50:18
Tags:
computer science discrete combinatorial mathematics
Folders:
computer science
Description:
CS311
Show Answers: