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