Discrete Math

Propositional and predicate logic

78 flashcards · Mathematics · by Athena Papkouf

1. De Morgan's laws

   ¬(p∧q)≡¬p∨¬q¬(p∨q)≡¬p∧¬q\begin{array}{l} \neg(p \wedge q) \equiv \neg p \vee \neg q \\ \neg(p \vee q) \equiv \neg p \wedge \neg q \end{array}¬(p∧q)≡¬p∨¬q¬(p∨q)≡¬p∧¬q​

2. Distributive laws

   p∨(q∧r)≡(p∨q)∧(p∨r)p∧(q∨r)≡(p∧q)∨(p∧r)\begin{array}{l} p \vee(q \wedge r) \equiv(p \vee q) \wedge(p \vee r) \\ p \wedge(q \vee r) \equiv(p \wedge q) \vee(p \wedge r) \end{array}p∨(q∧r)≡(p∨q)∧(p∨r)p∧(q∨r)≡(p∧q)∨(p∧r)​

3. p→qp \to qp→q equivalences

   p→q≡¬p∨qp→q≡¬q→¬p\begin{array}{l} p \rightarrow q \equiv \neg p \vee q \\ p \rightarrow q \equiv \neg q \rightarrow \neg p \end{array}p→q≡¬p∨qp→q≡¬q→¬p​ (contrapositive)

4. p↔qp \leftrightarrow qp↔q equivalences

   p↔q≡(p→q)∧(q→p)p↔q≡¬p↔¬q\begin{array}{l} p \leftrightarrow q \equiv(p \rightarrow q) \wedge(q \rightarrow p) \\ p \leftrightarrow q \equiv \neg p \leftrightarrow \neg q \end{array}p↔q≡(p→q)∧(q→p)p↔q≡¬p↔¬q​

5. p⊕qp \oplus qp⊕q equivalence

   (p∧¬q)∨(¬p∧q)(p \wedge \neg q) \vee(\neg p \wedge q)(p∧¬q)∨(¬p∧q)

6. De Morgan's laws for quantifiers ¬∃xP(x)¬∀xP(x)\begin{array}{l} \neg \exists x P(x) \\ \neg \forall x P(x) \end{array}¬∃xP(x)¬∀xP(x)​

   ∀x¬P(x)∃x¬P(x)\begin{array}{l} \forall x \neg P(x) \\ \exists x \neg P(x) \end{array}∀x¬P(x)∃x¬P(x)​

7. ∑i=1ni\sum_{i=1}^{n} i∑i=1n​i

   ∑i=1ni=n(n+1)2\sum_{i=1}^{n} i=\frac{n(n+1)}{2}∑i=1n​i=2n(n+1)​

8. ∑i=0n−1ai\sum_{i=0}^{n-1} a^{i}∑i=0n−1​ai , a ≠1a ~ \neq 1a ̸​=1

   ∑i=0n−1ai=1−an1−a\sum_{i=0}^{n-1} a^{i}=\frac{1-a^{n}}{1-a}∑i=0n−1​ai=1−a1−an​

9. equality of sets

   If A and B are sets, then A and B are equal if and only if ∀x(x∈A↔x∈B)\forall x(x \in A \leftrightarrow x \in B)∀x(x∈A↔x∈B)

10. Showing that A is a Subset of B

    To show that A ⊆ B, show that if xxx belongs to A then xxx also belongs to B.

11. Showing that A is Not a Subset of B

    To show that A̸⊆A \not \subseteqA̸​⊆ BBB , find a single x∈Ax \in Ax∈A such that x∉Bx \notin Bx∈/​B .

12. Theorem for subsets

    For every set SSS , (i) ∅⊆S\emptyset \subseteq S∅⊆S and (ii) S⊆SS \subseteq SS⊆S

13. Showing Two Sets are Equal

    To show that two sets A and B are equal, show that A ⊆ B and B ⊆ A.

14. Power Set

    Given a set S, the power set of S is the set of all subsets of the set S. The power set of S is denoted by P (S).

15. Cartesian product

    A×B={(a,b)∣a∈A∧b∈B}A \times B=\{(a, b) \mid a \in A \wedge b \in B\}A×B={(a,b)∣a∈A∧b∈B}

16. If f is a function from A to B, we say that A is the domain of f and B is the codomain of f. If f (a) = b, we say that b is the image of a and a is a preimage of b. The range, or image, of f is the set of all images of elements of A. Also, if f is a function from A to B, we say that f maps A to B.

17. binary relation for set A to set B

    Let A and B be sets. A binary relation from A to B is a subset of A × B.

18. reflexive relation

    A relation R on a set A is called reflexive if (a, a) ∈ R for every element a ∈ A.

19. symmetric and antisymmetric relation

    A relation R on a set A is called symmetric if (b, a) ∈ R whenever (a, b) ∈ R, for all a, b ∈ A. A relation R on a set A such that for all a, b ∈ A, if (a, b) ∈ R and (b, a) ∈ R, then a = b is called antisymmetric.

20. transitive relation

    A relation R on a set A is called transitive if whenever (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R, for all a, b, c ∈ A.

21. composite relation

    Let R be a relation from a set A to a set B and S a relation from B to a set C. The composite of R and S is the relation consisting of ordered pairs (a, c), where a ∈ A, c ∈ C, and for which there exists an element b ∈ B such that (a, b) ∈ R and (b, c) ∈ S. We denote the composite of R and S by S ◦ R.

22. To show that f is not surjective

    Find a particular y ∈ B such that f(x)≠yf (x) \neq yf(x)̸​=y for all x ∈ A.

23. To show that f is surjective

    Consider an arbitrary element y ∈ B and find an element x ∈ A such that f (x) = y.

24. To show that f is not injective

    Find particular elements x, y ∈ A such that x≠yx \neq y x̸​=y and f(x)=f(y)f (x) = f (y)f(x)=f(y) .

25. To show that f is injective

    Show that if f (x) = f (y) for arbitrary x, y ∈ A with x≠yx \neq yx̸​=y , then x = y.

26. surjective function

    A function f from A to B is called onto, or a surjection, if and only if for every element b ∈ B there is an element a ∈ A with f (a) = b. A function f is called surjective if it is onto.

27. injective function

    A function f is said to be one-to-one, or an injunction, if and only if f (a) = f (b) implies that a = b for all a and b in the domain of f. A function is said to be injective if it is one-to-one.

28. partial ordering (poset)

    A relation R on a set S is called a partial ordering or partial order if it is reflexive, antisymmetric, and transitive. A set S together with a partial ordering R is called a partially ordered set, or poset, and is denoted by (S, R). Members of S are called elements of the poset.A relation R on a set S is called a partial ordering or partial order if it is reflexive, antisymmetric, and transitive. A set S together with a partial ordering R is called a partially ordered set, or poset, and is de…

29. equivalence relation

    A relation on a set A is called an equivalence relation if it is reflexive, symmetric, and transitive.

30. comparable and incomparable elements of a poset

    The elements a and b of a poset (S, ⪯\preceq⪯ ) are called comparable if either a ⪯\preceq⪯  b or b  ⪯\preceq⪯ a. When a and b are elements of S such that neither a  ⪯\preceq⪯ b nor b ⪯\preceq⪯  a, a and b are called incomparable.

31. linearly ordered set

    If (S,  ⪯\preceq⪯ ) is a poset and every two elements of S are comparable, S is called a totally ordered or linearly ordered set, and ⪯\preceq⪯  is called a total order or a linear order. A totally ordered set is also called a chain.

32. well-ordered set

    (S, ⪯\preceq⪯  ) is a well-ordered set if it is a poset such that ⪯\preceq⪯  is a total ordering and every nonempty subset of S has a least element.

33. lattice

    A partially ordered set in which every pair of elements has both a least upper bound and a greatest lower bound is called a lattice.

34. How many relations are there on a set A?

    A ⨉ A has ∣A∣2|A|^2∣A∣2 elements when A has |A| elements.

35. equivalence class

    Let R be an equivalence relation on a set A. The set of all elements that are related to an element a of A is called the equivalence class of a, denoted by [a]R[a]_R [a]R​ .

36. representative of equivalence class.

    if b∈[a]Rb \in [a]_Rb∈[a]R​ , then b is called a representative of this equivalence class.

37. Big O

    f(x)f(x)f(x) is O(g(x))O(g(x))O(g(x)) if there are constants 0"> C>0C > 0C>0 and k≥0k ≥ 0k≥0 such that f(x)≤Cg(x)f(x) ≤ C g(x)f(x)≤Cg(x) whenever k"> x>kx > kx>k .

38. Linear Search Algorithm

    1. First compare x with a 1 . If they are equal, return the position 1. 2. If not, try a 2 . If x = a 2 , return the position 2. 3. Keep going, and if no match is found when the entire list is scanned, return 0.

39. Binary Search Algorithm

    The algorithm begins by comparing the element to be found with the middle element. • If the middle element is lower, the search proceeds with the upper half of the list. • If it is not lower, the search proceeds with the lower half of the list (including the middle position). • Repeat this process until we have a list of size 1. • If the element we are looking for is equal to the element in the list, the position is returned. • Otherwise, 0 is returned to indicate that the element was not found.

40. Bubble sort algorithm

    In one pass, every pair of elements that are found to be out of order are interchanged. • Since the last element is guaranteed to be the largest after the first pass, in the second pass it needs no more to be inspected. • In every pass one more element at the end needs to be no more inspected.

41. Insertion Sort

    Insertion sort begins with the 2 nd element. • It compares the 2 nd element with the 1 st and puts it before the first if it is not larger. • Next the 3 rd element is put into the correct position among the first 3 elements. • In each subsequent pass, the j+1 st element is put into its correct position among the first j+1 elements. • Linear search is used to find the correct position.

42. greedy algorithm

    algorithm that makes the “best” choice at each step. • Making the “best choice” at each step does not necessarily produce an optimal solution to the overall problem • but in many instances, it does.

43. Cashier’s Algorithm

44. matching

    Given a finite set A, a matching of A is a set of (unordered) pairs of distinct elements of A where any element occurs in at most one pair (such pairs are called independent).

45. maximum matching

    A maximum matching is a matching that contains the largest possible number of pairs.

46. Stable and unstable matching

    A matching is unstable if there are two pairs (x, y), (v, w) in the matching such that x prefers v to y and v prefers x to w. A stable matching is a matching that is not unstable.

47. Matching of sets

    Given a set with even cardinality, partition A into two disjoint subsets A1A_1A1​ and A2A_2A2​ with A1∪A2=AA_1 \cup A_2 = AA1​∪A2​=A and ∣A1∣=∣A2∣|A _1| = |A_2 |∣A1​∣=∣A2​∣ . A matching is a bijection from the elements of one set to the elements of the other set.

48. Gale-Shapley Algorithm

49. Insertion sort algorithm

50. Big O

    Let f and g be functions from the set of integers or the set of positive real numbers to the set of real numbers. We say that f(x) is O(g(x)) if there are constants 0"> C>0C > 0C>0 and k≥0k ≥ 0k≥0 such that ∣f(x)∣≤C∣g(x)∣|f(x)| ≤ C |g(x)|∣f(x)∣≤C∣g(x)∣ whenever k"> x>kx > kx>k .

51. Big O of a polynomial

    The leading term anxna_n x^nan​xn of a polynomial dominates its growth.

52. Big O of polynomial and logarithm

    v, ~ v"> ∀u>v, v\forall u>v, ~ v∀u>v, v constant nvn^v nv is O(nu)O(n^u)O(nu) but nun^unu is not O(nv)O(n^v)O(nv) 0, b>0, u>v"> ∀a>0,b>0,u>v\forall a>0, b>0, u>v∀a>0,b>0,u>v and a,b, u, v constant logb(nv)=O(loga(nu))log_b(n^v) = O(log_a(n^u))logb​(nv)=O(loga​(nu)) loga(nu)=O(logb(nv))log_a(n^u)=O(log_b(n^v))loga​(nu)=O(logb​(nv)) and they are all O(log(n))O(log(n))O(log(n))

53. If d > c > 1, then nc is O(nd ), but nd is not O(nc)

54. Big O If b > 1 and c and d are positive, then (logbn)c is

    O(nd ), but nd is not O((logb n)c )

55. Big O If b > 1 and d is positive, then nd is

    O(bn ), but bn is not O(nd )

56. Big O If c > b > 1, then bn

    is O(cn ), but cn is not O(bn )

57. Big O of log(n!)

    O(nlog(n)) with C=1, k=1

58. If f(x) is O(g(x)) and g(x) is O(h(x)) then

    f(x) is O(h(x))

59. Big O of product of functions

    If f1 (x) is O(g1(x)) and f2(x) is O(g2(x)) then ( f1 *f2 )(x) is O(g1 (x)*g2 (x))

60. Big O of sum of functions

    If f1(x) and f2 (x) are both O(g(x)) then (f1 + f2 )(x) is O(g(x)) If f1 (x) is O(g1 (x)) and f2(x) is O(g2(x)) then ( f1 + f2 )(x) is O(max(∣g1(x)∣,∣g2(x)∣))O(max(|g_1 (x)|,|g_2 (x)|))O(max(∣g1​(x)∣,∣g2​(x)∣))

61. The Generalized Pigeonhole Principle

    If N objects are placed into k boxes, then there is at least one box containing at least ⌈N/k⌉ objects

62. The number of r-combinations of a set with n elements, where n ≥ r ≥ 0, equals

    C(n,r)=C(n,r)=C(n,r)= n!((n−r)!r!\frac{n!}{((n-r)!r!}((n−r)!r!n!​ An r-combination of elements of a set is an unordered selection of r elements from the set. Thus, an r-combination is simply a subset of the set with r elements.

63. number of permutations

    n!

64. Combinations with Repetition

    An r-combination with repetition of elements of a set is an unordered selection of r elements from the set, where elements can occur multiple times The number of r-combinations from a set with n elements when repetition of elements is allowed is C(n + r – 1, r) = C(n + r – 1, n –1).

65. Permutations with Repetition

    An r-permutation with repetition of a set of distinct objects is an ordered arrangement of r elements from the set, where elements can occur multiple times. nr

66. Permutations with Indistinguishable Objects

    The number of different permutations of n objects, where there are n 1 indistinguishable objects of type 1, n 2 indistinguishable objects of type 2, ...., and nk indistinguishable objects of type k, is: n!n1!n2!...nk!\frac{n!}{n_1!n_2!...n_k!}n1​!n2​!...nk​!n!​

67. random variable

    A random variable X is a function X: S → R from the sample space S of an experiment to the set of real numbers R. • A random variable assigns a real number to each possible outcome

68. distribution of a random variable

    the set of pairs (r, p(X = r)) for all r ∊ X(S), where p(X = r) is the probability that X takes the value r p(X=r)p(X=r)p(X=r) =Σ=Σ=Σ s∈S:X(s)=r_{s\in S: X(s)=r}s∈S:X(s)=r​ p(s)p(s)p(s)

69. Bernoulli Trial

    The number of successes in n Bernoulli trials is p(X=k)=C(n,k)pkqn−k=b(k:n,p)p(X=k)=C(n,k)p^k q^{n-k}=b(k:n,p)p(X=k)=C(n,k)pkqn−k=b(k:n,p)

70. Expected Value

    The expected value (or expectation or mean) of the random variable X on the sample space S is equal to E(X)=Σs∈Sp(s)X(s)E(X)=Σ_{s\in S} p(s)X(s)E(X)=Σs∈S​p(s)X(s)

71. Expected Value of Bernoulli trials

    The expected number of successes when n mutually independent Bernoulli trials are performed, where p is the probability of each trial, is np.

72. Linearity of Expectations

    If X i , i = 1, 2, ...,n with n a positive integer, are random variables on S, and if a and b are real numbers, then (i) E(X1 + X2 + .... + Xn ) = E(X1 ) + E(X2 ) + .... + E(Xn ) (ii) E(aX + b) = aE(X) + b. expected values are linear.

73. Independent Random Variables

    The random variables X and Y on a sample space S are independent if p(X = r1 ∧ Y = r2 ) = p(X = r1 ) ⋅ p(Y = r2 ) If X and Y are independent variables on a sample space S, then E(X ⋅ Y ) = E(X) ⋅ E(Y )

74. Variance

    Let X be a random variable on the sample space S. The variance of X , denoted by V(X) is V(X)=Σs∈S(X(s)−E(X))²p(s)V(X)=Σ_{s\in S} (X(s)-E(X))²p(s)V(X)=Σs∈S​(X(s)−E(X))²p(s) The standard deviation of X, denoted by σ(X) is defined as V(X)\sqrt{V(X)}V(X) ​

75. Characterisation of Variance

    If X is a random variable on a sample space S, then V(X) = E(X2 ) − E(X)2 If X is a random variable on a sample space S and E(X) = μ , then V(X) = E((X − μ)2 )

76. Bienaymé‘s Formula

    If X and Y are two independent random variables on a sample space S, then V(X + Y) = V(X) + V(Y) Furthermore, if X i , i = 1,2, ...,n, with n a positive integer, are pairwise independent random variables on S, then V(X 1 + X 2 + ··· + X n ) = V(X 1 ) + V(X 2 ) + ··· + V(X n ).

77. Markov’s Inequality

    0 "> ∃sX(s)>0\exists s X(s)>0 ∃sX(s)>0 and ∀sX(s)≥0\forall s X(s)\geq 0∀sX(s)≥0 Let p(X ≥ a) denote the probability that the variable attains a value larger than a Then 0 P(X\geq M \cdot E(X))\leq \frac{1}{M}"> ∀M>0P(X≥M⋅E(X))≤1M\forall M>0 P(X\geq M \cdot E(X))\leq \frac{1}{M}∀M>0P(X≥M⋅E(X))≤M1​

78. Chebyshev’s Inequality

    Let X be a random variable on a sample space S with probability function p. If r is a positive real number, then p( | X(s) − E(X) | ≥ r) ≤ V(X)/r 2