# 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

## 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