Каноническая форма Блейка
В булевой логике формула , для булевой функции f находится в канонической форме Блейка ( BCF ) [1] также называется полной суммой простых импликант , [2] полная сумма , [3] или дизъюнктивная простая форма , [4] это дизъюнкция всех простых импликант f . когда [1]
Связь с другими формами [ править ]
Каноническая форма Блейка является частным случаем дизъюнктивной нормальной формы .
Каноническая форма Блейка не обязательно минимальна (верхняя диаграмма), однако все члены минимальной суммы содержатся в канонической форме Блейка. [3] С другой стороны, каноническая форма Блейка является канонической формой , то есть она уникальна с точностью до переупорядочения, тогда как минимальных форм может быть несколько (нижняя диаграмма). Выбор минимальной суммы из канонической формы Блейка, в общем, сводится к решению проблемы покрытия множества : [5] так и NP-трудно . [6] [7]
История [ править ]
Арчи Блейк представил свою каноническую форму на собрании Американского математического общества в 1932 году. [8] и в своей диссертации 1937 года. Он назвал это «упрощенной канонической формой»; [9] [10] [11] [12] в 1986–1990 годах назвали ее «канонической формой Блейка» Фрэнк Маркхэм Браун и Серджиу Рудяну . [13] [1] Совместно с Платона Порецкого творчеством [14] его также называют «законами Блейка – Порецкого». [15] [ нужны разъяснения ]
Методы расчета [ править ]
Блейк обсудил три метода вычисления канонической формы: исчерпание импликантов, повторный консенсус и умножение. Метод итерированного консенсуса был открыт заново [1] Эдвард В. Самсон и Бертон Э. Миллс, [16] Уиллард Куайн , [17] и Курт Бинг. [18] [19] В 2022 году Милан Моссе, Гарри Ша и Ли-Янг Тан обнаружили почти оптимальный алгоритм вычисления канонической формы Блейка формулы в конъюнктивной нормальной форме . [20]
См. также [ править ]
Ссылки [ править ]
- ↑ Перейти обратно: Перейти обратно: а б с д Браун, Фрэнк Маркхэм [в Викиданных] (2012) [2003, 1990]. «Глава 3: Каноническая форма Блейка». Булево рассуждение - Логика булевых уравнений (переиздание 2-го изд.). Минеола, Нью-Йорк: Dover Publications, Inc., стр. 4, 77 и далее, 81. ISBN. 978-0-486-42785-0 . [1]
- ^ Сасао, Цутому (1996). «Тройные диаграммы решений и их приложения». В Сасао — Цутому; Фудзита, Масахира (ред.). Представления дискретных функций . п. 278. дои : 10.1007/978-1-4613-1385-4_12 . ISBN 978-0792397205 .
- ↑ Перейти обратно: Перейти обратно: а б Кандель, Авраам (1998). Основы проектирования цифровой логики . п. 177. ИСБН 978-9-81023110-1 .
- ^ Кнут, Дональд Эрвин (2011). Комбинаторные алгоритмы, часть 1 . Искусство компьютерного программирования . Том. 4А. п. 54.
- ^ Фельдман, Виталий [в Викиданных] (2009). «Трудность приближенной двухуровневой логической минимизации и обучения PAC с помощью запросов на членство» . Журнал компьютерных и системных наук . 75 : 13–25 [13–14]. дои : 10.1016/j.jcss.2008.07.007 .
- ^ Гимпель, Джеймс Ф. (1965). «Метод создания логической функции, имеющей произвольную предписанную таблицу простых импликантов». Транзакции IEEE на компьютерах . 14 : 485–488.
- ^ Пауль, Вольфганг Якоб [на немецком языке] (1974). «Булевы минимальные многочлены и проблемы покрытия». Acta Informatica (на немецком языке). 4 (4): 321–336. дои : 10.1007/BF00289615 . S2CID 35973949 .
- ^ Блейк, Арчи (ноябрь 1932 г.). «Канонические выражения в булевой алгебре». Бюллетень Американского математического общества . Тезисы докладов: 805.
- ^ Блейк, Арчи (1937). Канонические выражения в булевой алгебре (Диссертация). Департамент математики Чикагского университета : Библиотеки Чикагского университета .
- ^ Блейк, Арчи (1938). «Канонические выражения в булевой алгебре». Журнал символической логики . 3 (2).
- ^ Блейк, Арчи (сентябрь 1938 г.). «Исправления канонических выражений в булевой алгебре ». Журнал символической логики . 3 (3): 112–113. дои : 10.2307/2267595 . JSTOR 2267595 . S2CID 5810863 .
- ^ McKinsey, Джон Чарльз Ченовет , изд. (июнь 1938 г.). «Блейк, Арчи. Канонические выражения в булевой алгебре, математический факультет Чикагского университета, 1937» . Журнал символической логики (обзор). 3 (2:93): 93. дои : 10.2307/2267634 . JSTOR 2267634 . S2CID 122640691 .
- ^ Браун, Фрэнк Маркхэм [в Викиданных] ; Рудяну, Серджиу [в Викиданных] (1986), Функциональный подход к теории простых импликантов , Публикация Института математики, Новая серия, том. 40, с. 23–32
- ^ Poretsky, Platon Sergeevich (1884). "O sposobach reschenija lopgischeskich rawenstw i ob obrathom spocobe matematischeskoi logiki" О способах решения логических равенств и об обратном способе [О методах решения логических равенств и обратном методе математической логики. Очерк построения полной и доступной теории дедукции на качественных формах. Сборник отчетов заседаний секции физико-математических наук Общества естествоиспытателей Казанского университета (на русском языке) (2). (Примечание. Эта публикация также называется «О методах решения логических равенств и об обратном методе математической логики».)
- ^ Васюкевич, Вадим О. (2011). «1.10 Венъюнктивные свойства (основные формулы)». Написано в Риге, Латвия. Асинхронные операторы последовательной логики: венъюнкция и секвенция — анализ и проектирование цифровых схем . Конспекты лекций по электротехнике (LNEE). Том. 101 (1-е изд.). Берлин / Гейдельберг, Германия: Springer-Verlag . п. 20. дои : 10.1007/978-3-642-21611-4 . ISBN 978-3-642-21610-7 . ISSN 1876-1100 . LCCN 2011929655 . (xiii+1+123+7 страниц) (Примечание. На задней обложке этой книги ошибочно указан том 4, хотя на самом деле это том 101.)
- ^ Самсон, Эдвард Уолтер; Миллс, Бертон Э. (апрель 1954 г.). Минимизация схемы: алгебра и алгоритмы для новых логических канонических выражений (технический отчет). Бедфорд, Массачусетс, США: Кембриджский исследовательский центр ВВС . ТР 54-21 АФКРК.
- ^ Куайн, Уиллард Ван Орман (ноябрь 1955 г.). «Способ упростить функции истинности». Американский математический ежемесячник . 62 (9): 627–631. дои : 10.2307/2307285 . hdl : 10338.dmlcz/142789 . JSTOR 2307285 .
- ^ Бинг, Курт (1955). «Об упрощении формул высказываний». Бюллетень Американского математического общества . 61 : 560.
- ^ Бинг, Курт (1956). «Об упрощении формул истинностного функционала». Журнал символической логики . 21 (3): 253–254. дои : 10.2307/2269097 . JSTOR 2269097 . S2CID 37877557 .
- ^ Моссе, Милан; Ша, Гарри; Тан, Ли-Янг (2022). «Обобщение леммы о выполнимости кодирования и ее приложения» . DROPS-IDN/v2/document/10.4230/LIPIcs.SAT.2022.9 . Замок Дагштуль – Центр информатики Лейбница. дои : 10.4230/LIPIcs.SAT.2022.9 .
