Английская Википедия:Blake canonical form

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Short description Шаблон:Use dmy dates Шаблон:Use list-defined references

Файл:Karnaugh map KV 4mal4 Gruppe01a.svg
Karnaugh map of Шаблон:OverlineB + Шаблон:Overline + Шаблон:Overline, a sum of all prime implicants (each rendered in a different color). Deleting Шаблон:Overline results in a minimal sum.

Шаблон:Multiple image 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]

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 Шаблон:Ill and Шаблон:Ill in 1986–1990.[13][1] Together with Platon Poretsky's work[14] it is also referred to as "Blake–Poretsky laws".[15]Шаблон:Clarify

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]

See also

References

Шаблон:Reflist

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ 1,0 1,1 1,2 1,3 Ошибка цитирования Неверный тег <ref>; для сносок Brown_2012 не указан текст
  2. ↑ Ошибка цитирования Неверный тег <ref>; для сносок Sasao_1996 не указан текст
  3. ↑ 3,0 3,1 Ошибка цитирования Неверный тег <ref>; для сносок Kandel_1998 не указан текст
  4. ↑ Ошибка цитирования Неверный тег <ref>; для сносок Knuth_2011 не указан текст
  5. ↑ Ошибка цитирования Неверный тег <ref>; для сносок Feldman_2009 не указан текст
  6. ↑ Ошибка цитирования Неверный тег <ref>; для сносок Gimpel_1965 не указан текст
  7. ↑ Ошибка цитирования Неверный тег <ref>; для сносок Paul_1974 не указан текст
  8. ↑ Ошибка цитирования Неверный тег <ref>; для сносок Blake_1932 не указан текст
  9. ↑ Ошибка цитирования Неверный тег <ref>; для сносок Blake_1937 не указан текст
  10. ↑ Ошибка цитирования Неверный тег <ref>; для сносок Blake_1938_1 не указан текст
  11. ↑ Ошибка цитирования Неверный тег <ref>; для сносок Blake_1938_2 не указан текст
  12. ↑ Ошибка цитирования Неверный тег <ref>; для сносок Kinsey_1938 не указан текст
  13. ↑ Ошибка цитирования Неверный тег <ref>; для сносок Brown_1986 не указан текст
  14. ↑ Ошибка цитирования Неверный тег <ref>; для сносок Poretsky_1884 не указан текст
  15. ↑ Ошибка цитирования Неверный тег <ref>; для сносок Vasyukevich_2011 не указан текст
  16. ↑ Ошибка цитирования Неверный тег <ref>; для сносок Samson_1954 не указан текст
  17. ↑ Ошибка цитирования Неверный тег <ref>; для сносок Quine_1955 не указан текст
  18. ↑ Ошибка цитирования Неверный тег <ref>; для сносок Bing_1955 не указан текст
  19. ↑ Ошибка цитирования Неверный тег <ref>; для сносок Bing_1956 не указан текст
Источник — http://wikihandbk.com/ruwiki/index.php?title=Английская_Википедия:Blake_canonical_form&oldid=13549622