Discrete Mathematics with Applications (Epp), Chapter 1

72 flashcards · Mathematics · by charlie42

1. 3 most important mathematical statements

   universal statement conditional statement existential statement

2. A universal statement says that

   a certain property is true for all elements in a set

3. Example of a universal statement

   "All positive numbers are greater than zero"

4. A conditional statement says that

   if one thing is true then some other thing also has to be true

5. An existential statement says that

   there is at least one thing for which the property is true

6. "For every animal, if a is a dog, then a is a mammal" is what kind of statement?

   Universal conditional

7. If you introduce a variable in the first part of the sentence,

   be sure to use it in the second part of the sentence

8. "Every real number has an additive inverse" is what kind of statement?

   Universal existential

9. "There is a positive integer that is less than or equal to every positive integer" is what kind of statement?

   Existential universal

10. Set ℝ

    Set of all real numbers

11. Set ℤ

    Set of all integers (Zahlen)

12. Set ℚ

    Set of all rational numbers (quotents of integers)

13. Quotent

    Result of devision

14. Let A = {1, 2, 3}, B = {3, 2, 1}, C = {1, 1, 2, 3, 3, 4}. What are the elements of A, B, C. How are A, B and C related?

    1, 2 and 3. A = B.

15. Set-roster notation 3 examples

    {1, 2, 3} {1, 2, 3, ..., 100} {1, 2, 3, ...} (infinite set of all positive integers)

16. Set-builder notation and pronunciation

    { x ∈ S | P(x) } The set of all x such that P(x)

17. ∈

    "is an element of"

18. ⊆

    "is a subset of"

19. A ⊆ B means that

    for every element of x, if x ∈ A then x ∈ B

20. A is a proper subset of B if, and only if,

    every element of A is in B, but there is at least one element of B that is not in A I.e. A is a subset of A but not a proper subset

21. Is 2 ⊆ {1, 2, 3}? Why?

    No, 2 is not a set

22. Ordered pair notation

    (a, b)

23. Two ordered pairs (a, b) and (c, d) are equal if, and only if,

    a = c and c = d

24. Ordered pair (a, b) in a set notation

    {a, {a, b}}

25. What's this: (a, b, c)

    Ordered triple

26. What's this: (x1, x2, x3, ...)

    Ordered n-tuple

27. Given sets A1, A2, ..., An, the Cartesian product of A1, A2, ..., An is denoted as

    A1 x A2 x ... x An

28. Given sets A1, A2, ..., An, the Cartesian product of A1, A2, ..., An is

    the set of all ordered n-tuples (a1, a2, ..., an), where a1 ∈ A1, a2 ∈ A2, ..., an ∈ An

29. Symbolic representation of Cartesian product

    A1 x A2 x ... x An = { (a1, a2, ..., an) | a1 ∈ A1, a2 ∈ A2, ..., an ∈ An }

30. What is the Cartesian plane

    plane with coordinate system R x R

31. A string of length n over A

    ordered n-tuple of elements of A written without parentheses or commas

32. S = { n ∈ Z | n = (-1)k }

    S = {1, -1}

33. First element of A x (B x C), A = {1, 2, 3}, B = {u}, C = {m, n}

    (1, (u, m))

34. How to read x R y

    x is related to y

35. Notation for "x is not related to y"

36. By the definition of C. S. Pierce: if A and B are sets, a relation R from A to B is...

    a subset of A x B

37. By the definition of C. S. Pierce: Given an ordered pair (x, y) in A x B, x is related to y by R, if, and only if...

    (x, y) is in R

38. Symbolically, x R y means that

    (x, y) ∈ R

39. If R is a relation from A to B, what's the sets A and B called respectively?

    Domain, co-domain

40. F is a function from a set A to a set B, then given any element x in A, property (1) from the function definition guarantees that... and property (2) guarantees that...

    there is at least one element of B that is related to x by F there is at most one such element

41. Definition of a function: A function F from a set A to a set B is a relation with domain A and co-domain B that satisfies the following two properties:

    1. For every element x in A, there is an element y in B such that (x, y) ∈ F. 2. For all elements x in A and y and z in B, if (x, y) ∈ F and (x, z) ∈ F, then y = z.

42. If A and B are sets, and F is a function from A to B, what's F(x)?

    The unique element in B that is related to x by F

43. Let A = {2, 4, 6} and B = {1, 3, 5}. Is R = {(2, 5), (4, 1), (4, 3), (6, 5)} a function from A to B? Show on a diagram.

    No, it doesn't satisfy the property (2). The pairs (4, 1) and (4, 3) have the same first element, but different second elements (1 != 3)

44. Let A = {2, 4, 6} and B = {1, 3, 5}. Is S a function from A to B: For every (x, y) ∈ A x B, (x, y) ∈ S means that y = x + 1 ? Show on a diagram.

    No, it doesn't satisfy the property (1). Not every element of A is the first value of an ordered pair in S.

45. Is this a function?

    Yes, Every value in A is related to a value in B Every value in A is related to only one value in B You can write F(2) = 5, F(4) = 1, and F(6) = 1

46. The successor function g from Z to Z is defined by the formula:

    g(n) = n + 1

47. An example of a constant function

    h(r) = 2

48. If f and g are functions from a set A to a set B, f equals g, written f = g, if, and only if...

    f(x) = g(x) for all x in A

49. Does f = g?

    Yes,

50. Singular form of the word vertices

    Vertex

51. A graph G consists of...

    two finite sets: a nonempty set V(G) of vertices and a set E(G) of edges

52. Each edge of graph is associated with...

    a set consisting of either one or two vertices called its endpoints

53. The correspondence from edges to endpoints is called...

    the edge-endpoint function.

54. Loop definition (graphs)

    An edge with just one endpoint

55. When are two or more edges called parallel?

    When two or more edges have the same set of endpoints

56. An edge is said to ... its endpoints

    connect

57. Two vertices that are connected by an edge are called...

    adjacent

58. A vertex that is an endpoint of a loop is said to be...

    adjacent to itself

59. An edge is said to be ... on each of its endpoints

    incident

60. Two edges incident on the same endpoint are called

    adjacent

61. A vertex on which no edges are incident is called

    isolated

62. Although a given graph may have more than one pictorial representation, a given pictorial representation...

    uniquely determines a graph

63. A metaphor for how to represent the same graph in multiple ways visually

    Put one end of a piece of string at the top of the first vertex (call this vertex v1) Lay the string to the next adjacent vertex (v2) Continue laying the string to each adjacent vertex Call the first edge e1, the second e2, and so forth Now pick up the piece of string, together with its labels, and reposition it.

64. What's a digraph

    Directed graph

65. Each directed graph has an associated...

    ordinary (undirected) graph

66. A directed graph, or digraph, consists of:

    two finite sets: a nonempty set V(G) of vertices and a set D(G) of directed edges

67. Each directed edge of a directed graph is associated with...

    an ordered pair of vertices called its endpoints

68. If edge e is associated with the pair (y, w) of vertices, then e is said to be the...

    (directed) edge from y to w.

69. Let G be a graph and v a vertex of G. The degree of v, denoted deg(v), equals...

    the number of edges that are incident on v, with an edge that is a loop counted twice.

70. 5

71. Degree of a vertex notation

    deg(v)