• Partial order: a relation that is:
    • Reflexive ($x \leq x$)
    • Transitive ($a \leq b \land b \leq c \Rightarrow a \leq c$)
    • Antisymmetric ($a \neq b \Rightarrow a \leq b \nRightarrow b \leq a$)
  • Strict partial order: transitive and asymmetric (and irreflexive and antisymmetric)
  • Partially ordered set (poset): $(A, R)$ if $R$ is a partial order on $A$
  • Dual poset: $(A, R^{-1})$ is the dual poset of $(A, R)$

Hasse Diagrams #

  • No self-loops
  • No edges implied by transitivity
  • Its relfexive, transative closure is the digraph
  • Arrows upwards, no heads

Operations #

  • Product poset: $(a, b) \preccurlyeq (a', b') \Leftrightarrow a \leq_A a' \land b \leq_B b'$
  • Topological sorting: all items listed from bottom to top, row by row
  • Lexicographic order
  • Isomorphism
    • A function $f$ is a iosomorphism between two posets if:
      • $f$ is a bijection
      • $f$ is a homomorphism: $\forall a, b \in A: a \leq b \Leftrightarrow f(a) \leq f(b)$
    • Posets are isomorphic if they have the same Hasse diagram when you relabel the nodes

Poset Properties #

  • Linear / total order (chain): a partial order that is also connected
    • Connected: $\forall a, b, \in A: a \neq b \Rightarrow a\ R\ b \lor b\ R\ a$ (all elements are comparable)
    • Hasse diagram is a vertical line
  • Minimal/maximal elements: no elements below/above
    • $a \in A$ is mimimal if there is no element $c$ such that $c < a$
    • $b \in A$ is maximal if there is no element $c$ such that $b < c$
  • Least/greatest elements: element where everything is above/below it (at most one of both)
    • Greatest element: $I$ Unit, if for all $x \in A: x \leq a$
    • Least element: $0$ Zero, if for all $x \in A: I \leq x$:
  • Bounded: if it has a least and greatest element
  • Upper/lower bounds: Let $(A,\leq)$ and $B \subseteq A$,
    • $a \in A$ is an upper bound of B if for all $b \in B: b \leq a$
    • $a \in A$ is a lower bound of B if for all $b \in B: a \leq b$
  • Least upper/greatest lower bound
    • Least Upper Bound ($lub$), the least element in the upper bound poset
    • Greatest Lower Bound ($glb$), the greatest element of the lower bound poset

Lattices #

Lattice: a poset in which every two elements $a$ and $b$ have a join and meet:

  • Join: $a \lor b$ = Least Upper Bound ($lub$) (upwards)
  • Meet: $a \land b$ = Greatest Lower Bound ($glb$) (downards)

Properties #

  • Bounded: if it has greatest element (unit) $I$ and a least element (zero) $0$
  • Complete: every sublattice has a join and meet
  • Sublattice
    • Must also be a lattice
    • Join/meet must be the same
  • Complemented: if all elements have a complement
    • Complement: if join top and meet bottom
  • Distributive:
    • Definition: if for all $a, b, c \in L$:
      1. $a \land (b \lor c) = (a \land b) \lor (a \land c)$
      2. $a \lor (b \land c) = (a \lor b) \land (a \lor c)$
    • Non-distributive: if and only if a (sub)lattice is isomorphic to diamond ($M_3$) or pentagon ($M_5$)

Special lattices #

  • Powerset lattice
    • Join: union
    • Meet: intersect
    • Is bounded, distributive & complemented

Boolean algebra #

  • Binary lattice $(B_n, \leq)$

    • Set $B_n$: set of bitstring length $n$
    • Order: $a \leq b$
    • Meet: $a \land b = min$
    • Join: $a \lor b = max$
    • Count: $2^n$ elements
  • Boolean algebra: if a lattice $L$ is isomorphic with $B_n$

    • Checking for boolean algebra:
      1. Isomorphism between $L$ and $B_n$
      2. Check wether Hasse diagram statisfies properties of boolean algebra (e.g. $2^n$ elements)
    • Substitution rule
  • Boolean function: $f: B_n \rightarrow B$

    • Truth table: lists f based on input combination
  • Boolean polynomials: formulas of proppositional logic

    • Can be represented as logic diagrams
    • All boolean functions can be implemented using logic circuits
    • The same properties of propositional logic apply