Каноническая форма Блейка - Blake canonical form

В Логическая логика, а формула для булевой функции ж в Каноническая форма Блейка (BCF),[1] также называется полная сумма простых импликант,[2] в полная сумма,[3] или дизъюнктивная простая форма,[4] когда это дизъюнкция из всех основные импликанты из ж.[1]

Отношение к другим формам

Карта Карно из АB + до н.э + AC, сумма всех простых импликантов (каждая отображается разным цветом). Удаление AC приводит к минимальной сумме.

Каноническая форма Блейка - частный случай дизъюнктивная нормальная форма.

Каноническая форма Блейка не обязательно минимальный, однако все члены минимальной суммы содержатся в канонической форме Блейка.[3] С другой стороны, каноническая форма Блейка уникальна, тогда как минимальных форм может быть несколько. Выбор минимальной суммы из канонической формы Блейка в целом сводится к решению установить проблему прикрытия,[5] так это NP-жесткий.[6][7]

История

Арчи Блейк представил свою каноническую форму на собрании Американского математического общества в 1932 году.[8] и в его диссертации 1937 года. Он назвал это «упрощенной канонической формой»;[9][10][11] Фрэнк Маркхэм Браун и Серджиу Рудяну назвали ее «канонической формой Блейка» в 1986–1990 годах.[12][1]

Методы расчета

Блейк обсудил три метода вычисления канонической формы: исчерпание импликант, повторение консенсус, и умножение. Повторный метод консенсуса был открыт заново[1] Эдвард В. Самсон и Бертон Э. Миллс,[13] Уиллард Куайн,[14] и Курт Бинг.[15][16]

Смотрите также

Рекомендации

  1. ^ а б c d Браун, Фрэнк Маркхэм (2012) [2003, 1990]. «Глава 3: Каноническая форма Блейка». Булевы рассуждения - логика булевых уравнений (переиздание 2-го изд.). Минеола, Нью-Йорк: Dover Publications, Inc. С. 4, 77 и далее, 81. ISBN  978-0-486-42785-0. [1]
  2. ^ Сасао, Цутому (1996). «Диаграммы троичных решений и их приложения». В Сасао, Цутому; Фудзита, Масахира (ред.). Представления дискретных функций. п. 278. Дои:10.1007/978-1-4613-1385-4_12. ISBN  978-0792397205.
  3. ^ а б Кандел, Абрахам (1998). Основы цифрового логического дизайна. п. 177. ISBN  978-9-81023110-1.
  4. ^ Кнут, Дональд Эрвин (2011). Комбинаторные алгоритмы, часть 1. Искусство программирования. 4А. п. 54.
  5. ^ Фельдман, Виталий (2009). «Трудность приближенной двухуровневой минимизации логики и обучения PAC с запросами членства». Журнал компьютерных и системных наук. 75: 13–25 (13–14). Дои:10.1016 / j.jcss.2008.07.007.
  6. ^ Гимпель, Джеймс Ф. (1965). «Метод создания булевой функции, имеющей произвольно заданную простую импликантную таблицу». Транзакции IEEE на компьютерах. 14: 485–488.
  7. ^ Пол, Вольфганг Якоб (1974). "Boolesche Minimalpolynome und Überdeckungsprobleme". Acta Informatica (на немецком). 4 (4): 321–336. Дои:10.1007 / BF00289615. S2CID  35973949.
  8. ^ Блейк, Арчи (ноябрь 1932 г.). «Канонические выражения в булевой алгебре». Бюллетень Американского математического общества. Тезисов докладов: 805.
  9. ^ Блейк, Арчи (1937). Канонические выражения в булевой алгебре (Диссертация). Кафедра математики, Чикагский университет: Библиотеки Чикагского университета.
  10. ^ Блейк, Арчи (сентябрь 1938). "Исправления к Канонические выражения в булевой алгебре". Журнал символической логики. 3 (3): 112–113. Дои:10.2307/2267595. JSTOR  2267595.
  11. ^ McKinsey, Джон Чарльз Ченовет, изд. (Июнь 1938 г.). «Блейк, Арчи. Канонические выражения в булевой алгебре, математический факультет Чикагского университета, 1937». Журнал символической логики (Рассмотрение). 3 (2:93): 93. Дои:10.2307/2267634. JSTOR  2267634.
  12. ^ Браун, Фрэнк Маркхэм; Рудяну, Серджиу (1986), Функциональный подход к теории основных импликантов, Publication de l'institut mathématique, Nouvelle série, 40, стр.23–32
  13. ^ Самсон, Эдвард Уолтер; Миллс, Бертон Э. (апрель 1954 г.). Минимизация схем: алгебра и алгоритмы для новых булевых канонических выражений (Технический отчет). Бедфорд, Массачусетс, США: Кембриджский исследовательский центр ВВС. AFCRC TR 54-21.
  14. ^ Куайн, Уиллард Ван Орман (Ноябрь 1955 г.). «Способ упростить функции истины». Американский математический ежемесячник. 62 (9): 627–631. Дои:10.2307/2307285. HDL:10338.dmlcz / 142789. JSTOR  2307285.
  15. ^ Бинг, Курт (1955). «Об упрощении пропозициональных формул». Бюллетень Американского математического общества. 61: 560.
  16. ^ Бинг, Курт (1956). «Об упрощении истинностно-функциональных формул». Журнал символической логики. 21 (3): 253–254. Дои:10.2307/2269097. JSTOR  2269097.