跳转至

Basic Structures

Basic Structures

2.1 Sets

  • elements or members : \(a ∈ A\) or \(a ∉ A\)
  • describe a set : use roster method or set builder notation
  • equal if and only if have the same elements
  • subject : \(A ⊆ B\) or \(A ⊈ B\)
  • superset : \(B ⊇ A\)

  • proper subset : \(A ⊂ B\)

  • If there are exactly \(n\) distinct elements in \(S\) where \(n\) is a nonnegative integer, we say that \(S\) is a finite set and that \(n\) is the cardinality of \(S\). The cardinality of \(S\) is denoted by \(|S|\)

  • A set is said to be infinite if it is not finite

  • The power set of \(S\) is the set of all subsets of the set \(S\), which is denoted by \(P(S)\)

  • ordered n-tuple : \((a_1, a_2, … , a_n)\)

  • ordered pairs : \((a_1, a_2)\)
  • Cartesian product : \(A1 × A2 × ⋯ × An = \{(a_1, a_2, … , a_n) ∣ a_i ∈ A_i \; for \; i = 1, 2, … , n\}\)

  • A subset \(R\) of the Cartesian product \(A × B\) is called a relation from the set \(A\) to the set \(B\)

  • \(∀x ∈ S(P(x))\) is shorthand for \(∀x(x ∈ S → P(x))\)

  • \(∃x ∈ S(P(x))\) is shorthand for \(∃x(x ∈ S ∧ P(x))\)
  • We define the truth set of \(P\) to be the set of elements \(x\) in \(D\) for which \(P(x)\) is true, which is denoted by \(\{x ∈ D ∣ P(x)\}\)


2.2 Set Operations

  • union : \(A ∪ B\)
  • intersection : \(A ∩ B\)
    • Two sets are called disjoint if their intersection is the empty set
  • difference of A and B or complement of B with respect to A : \(A − B\)
  • complement : \(\bar{A}\)
Identity Name
\(A ∩ U = A\)
\(A ∪∅= A\)		 Identity laws
\(A ∪ U = U\)
\(A ∩∅=∅\)		 Domination laws
\(A ∪ A = A\)
\(A ∩ A = A\)		 Idempotent laws
\(\overline{(\bar A)} = A\) Complementation law
\(A ∪ B = B ∪ A\)
\(A ∩ B = B ∩ A\)		 Commutative laws
\(A ∪ (B ∪ C) = (A ∪ B) ∪ C\)
\(A ∩ (B ∩ C) = (A ∩ B) ∩ C\)		 Associative laws
\(A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)\)
\(A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)\)		 Distributive laws
\(\overline{(A ∩ B)} = \bar A ∪ \bar B\)
\(\overline{(A ∪ B)} = \bar A ∩ \bar B\)		 De Morgan's laws
\(A ∪ (A ∩ B) = A\)
\(A ∩ (A ∪ B) = A\)		 Absorption laws
\(A ∪ \bar A = U\)
\(A ∩ \bar A = ∅\)		 Complement laws
  • A multiset (short for multiple-membership set) \(\{m_1 ⋅ a_1, m_2 ⋅ a_2, … , m_r ⋅ a_r\}\) is an unordered collection of elements where an element can occur as a member more than once. The numbers \(m_i , i = 1, 2, … , r\), are called the multiplicities of the elements \(a_i , i = 1, 2, … , r\)
  • In the union of the multisets P and Q, the multiplicity is the maximum
  • In the intersection of the multisets P and Q, the multiplicity is the minimum
  • In the difference of P and Q, the multiplicity is the difference of P less Q unless this difference is negative
  • In the sum of P and Q, the multiplicity is the sum of multiplicities in P and Q


2.3 Functions

  • A function \(f\) from \(A\) to \(B\) is an assignment of exactly one element of \(B\) to each element of \(A\).
  • We write \(f(a) = b\) if \(b\) is the unique element of \(B\) assigned by the function \(f\) to the element \(a\) of \(A\), and 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\)
  • If \(f\) is a function from \(A\) to \(B\), we write \(f : A → B\) and we say that \(A\) is the domain of \(f\) and \(B\) is the codomain of \(f\).
  • Let \(f_1\) and \(f_2\) be functions from \(A\) to \(R\). Then \(f_1 + f_2\) and \(f_1 f_2\) are also functions from \(A\) to \(R\) defined for all \(x ∈ A\) by
    • \((f_1 + f_2)(x) = f_1(x) + f_2(x)\)
    • \((f_1f_2)(x) = f_1(x)f_2(x)\)

  • The image of \(S\) : \(f(S) = \{t ∣ ∃s∈S (t = f(s))\}\) or \(\{f(s) ∣ s ∈ S\}\)

  • A function \(f\) is said to be one-to-one, or an injection, 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

  • 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 is called surjective if it is onto

  • The function f is a one-to-one correspondence, or a bijection, if it is both one-to-one and onto. We also say that such a function is bijective

  • The inverse function of \(f\) is denoted by \(f^{−1}\)

  • Let \(g\) be a function from the set \(A\) to the set \(B\) and let \(f\) be a function from the set \(B\) to the set \(C\), then the composition of the functions \(f\) and \(g\) is denoted by \(f \circ g\)
  • The value of the floor function at \(x\) is denoted by \(⌊x⌋\)
  • The value of the ceiling function at \(x\) is denoted by \(⌈x⌉\)
  • A partial function \(f\) from \(A\) to \(B\) is an assignment to each element \(a\) in a subject of \(A\), called the domain of definition of \(f\) , of a unique element \(b\) in \(B\). We say that \(f\) is undefined for elements in \(A\) that are not in the domain of definition of \(f\). When the domain of definition of \(f\) equals \(A\), we say that \(f\) is a total function


2.5 Cardinality of Sets

  • The sets \(A\) and \(B\) have the same cardinality if and only if there is a one-to-one correspondence from \(A\) to \(B\), and this is denoted by \(|A| = |B|\)
  • If there is a one-to-one function from \(A\) to \(B\), we write \(|A| ≤ |B|\)

  • A set that is either finite or has the same cardinality as the set of positive integers is called countable, and we denote the cardinality of this set by \(ℵ_0\). We write \(|S| = ℵ_0\) and say that \(S\) has cardinality "aleph null"

  • If \(A\) and \(B\) are countable sets, then \(A ∪ B\) is also countable

  • Schröder-Bernstein theorem : If \(A\) and \(B\) are sets with \(|A| ≤ |B|\) and \(|B| ≤ |A|\), then \(|A| = |B|\). In other words, if there are one-to-one functions \(f\) from \(A\) to \(B\) and \(g\) from \(B\) to \(A\), then there is a one-to-one correspondence between \(A\) and \(B\)


2.6 Matrices

Zero-One Matrices - Let \(A = [a_{ij}]\) and \(B = [b_{ij}]\) be \(m × n\) zero–one matrices, then: - The join of \(A\) and \(B\) is the zero–one matrix with \((i, j)\)th entry \(a_{ij} ∨ b_{ij}\). The join of \(A\) and \(B\) is denoted by \(A ∨ B\). - The meet of \(A\) and \(B\) is the zero–one matrix with \((i, j)\)th entry \(a_{ij} ∧ b_{ij}\). The meet of \(A\) and \(B\) is denoted by \(A ∧ B\). - Let \(A = [a_{ij}]\) be an \(m × k\) zero–one matrix and \(B = [b_{ij}]\) be a \(k × n\) zero–one matrix. Then the Boolean product of \(A\) and \(B\), denoted by \(A \odot B\), is the \(m × n\) matrix with \((i, j)\)th entry \(cij\) where $$ c_{ij} = (a_{i1} ∧ b_{1j}) ∨ (a_{i2} ∧ b_{2j}) ∨ ⋯ ∨ (a_{ik} ∧ b_{kj}) $$ - The \(r\)th Boolean power of \(A\) is the Boolean product of \(r\) factors of \(A\). The \(r\)th Boolean product of \(A\) is denoted by \(A^{[r]}\). - We also define \(A^{[0]}\) to be \(I_n\).