Thursday, November 15, 2012

Logical operations

The values true and false form a boolean lattice with logical disjunction and logical conjuction as meet and join operators and not as complement: (lattice. #{false true} or and not). This lattice induces the total ordering relation false < true which corresponds to logical implication. There is a dual lattice based upon the ordering relation true < false which uses converse implication.

The disjunction and conjunction operators are commutative monoids with a single non-trivial idempotent element. We can also form abelian groups with a single non-trivial involution element: logical biconditional and exclusive disjunction.

These abelian groups can be extended with a multiplication operation to form the finite field. The logical biconditional uses disjunction as multiplication and the exclusive disjunction uses conjunction as multiplication.

Exponentation has no effect in this finite field, so all polynomials can be reduced to binomials. Using zero as false and one as true all the polynomials in this field can be expressed as 0, 1, x, and x+1.

No comments:

Post a Comment