Orders

• 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