Blake canonical form
Standard form of Boolean function From Wikipedia, the free encyclopedia
In Boolean logic, a formula for a Boolean function f is in Blake canonical form (BCF),[1] also called the complete sum of prime implicants,[2] the complete sum,[3] or the disjunctive prime form,[4] when it is a disjunction of all the prime implicants of f.[1]
ABD + ABC + ABD + ABC
ACD + BCD + ACD + BCD
Boolean function with two different minimal forms. The Blake canonical form is the sum of the two.
Relation to other forms
The Blake canonical form is a special case of disjunctive normal form.
The Blake canonical form is not necessarily minimal (upper diagram), however all the terms of a minimal sum are contained in the Blake canonical form.[3] On the other hand, the Blake canonical form is a canonical form, that is, it is unique up to reordering, whereas there can be multiple minimal forms (lower diagram). Selecting a minimal sum from a Blake canonical form amounts in general to solving the set cover problem,[5] so is NP-hard.[6][7]
History
Archie Blake presented his canonical form at a meeting of the American Mathematical Society in 1932,[8] and in his 1937 dissertation. He called it the "simplified canonical form";[9][10][11][12] it was named the "Blake canonical form" by Frank Markham Brown and Sergiu Rudeanu in 1986–1990.[13][1] Together with Platon Poretsky's work[14] it is also referred to as "Blake–Poretsky laws".[15][clarification needed]
Methods for calculation
Blake discussed three methods for calculating the canonical form: exhaustion of implicants, iterated consensus, and multiplication. The iterated consensus method was rediscovered[1] by Edward W. Samson and Burton E. Mills,[16] Willard Quine,[17] and Kurt Bing.[18][19] In 2022, Milan Mossé, Harry Sha, and Li-Yang Tan discovered a near-optimal algorithm for computing the Blake canonical form of a formula in conjunctive normal form.[20]
See also
References
Wikiwand - on
Seamless Wikipedia browsing. On steroids.