CS311 - Discrete and Combinatorial Mathematics

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

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