Algebra of Normal Forms
Andrzej Trybulec · 1991
Summary. We mean by a normal form a finite set of ordered pairs of subsets of a fixed set that fulfils two conditions: elements of it consist of disjoint sets and element of it are incomparable w.r.t. inclusion. The underlying set corresponds to a set of propositional variables but it is arbitrary. The correspondents to a normal form of a formula, e.g. a disjunctive normal form is as follows. The normal form is the set of disjuncts and a disjunct is an ordered pair consisting of the sets of propositional variables that occur in the disjunct non-negated and negated. The requirement that the element of a normal form consists of disjoint sets means that contradictory disjuncts have been removed and the second condition means that the absorption law has been used to shorten the normal form. We construct a lattice 〈N,⊔,⊓〉, where a ⊔ b = µ(a ∪ b) and a ⊓ b = µc, c being set of all pairs 〈X1 ∪Y1,X2 ∪Y2〉, 〈X1,X2 〉 ∈ a and 〈Y1,Y2 〉 ∈ b, which consist of disjoiny sets. µa denotes here the set of all minimal, w.r.t. inclusion, elements of a. We prove that the lattice of normal forms over a set defined in this way is distributive and that /0 is the minimal element of it.