Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Blake canonical form
Résumé
In Boolean logic, a formula for a Boolean function f is in Blake canonical form (BCF), also called the complete sum of prime implicants, the complete sum, or the disjunctive prime form, when it is a disjunction of all the prime implicants of f.
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. 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, so is NP-hard.
Archie Blake presented his canonical form at a meeting of the American Mathematical Society in 1932, and in his 1937 dissertation. He called it the "simplified canonical form"; it was named the "Blake canonical form" by Frank Markham Brown and Sergiu Rudeanu in 1986–1990. Together with Platon Poretsky's groundlaying work it is also referred to as "Blake–Poretsky laws".
Blake discussed three methods for calculating the canonical form: exhaustion of implicants, iterated consensus, and multiplication. The iterated consensus method was rediscovered by Edward W. Samson and Burton E. Mills, Willard Quine, and Kurt Bing.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.