Wednesday, October 24, 2018

Boolean formulas as lattice polynomials

Given any lattice ordered set, we can form lattice polynomials from the use of variables like x,y,z and so on as well as the lattice operations $\wedge$ and $\vee$. On two elements we have lattice polynomials like $$a \wedge b$$ $$a \vee b$$ Which shows that in general, on two elements the types of lattice polynomials that we can form on them are not that interesting. On three elements we can form a wide variety of lattice polynomials like $$a \vee (b \wedge (c \vee d))$$ $$a \wedge (b \vee (c \wedge d))$$ In general, for any given lattice, these lattice polynomials can be arbitrary trees that can be expanded to any given depth. In a distributive lattice, on the other hand, the lattice polynomials can be reduced to only two elements which can be expressed one of two ways, either as the meet normal form or as the join normal form of their variables. $$ (a \vee b \vee c) \wedge (d \vee e \vee f) \wedge (g \vee h \vee i) $$ $$ (a \wedge b \wedge c) \vee (d \wedge e \wedge f) \vee (g \wedge h \wedge i)$$ A boolean algebra is a special case of a lattice, therefore boolean formulas can be expressed as a special case of lattice polynomials, with the only adjustment being that variables can be either negated or not. Boolean algebras are distributive, therefore every boolean formula can be expressed as either the conjunctive normal form or the disjunctive normal form. This shows that propositional logic deals with a subset of lattice theory.

No comments:

Post a Comment