ブレイク標準形

A B + BC + ACのカルノー図。すべての主項の和（それぞれ異なる色で表示）。ACを削除すると和は最小になる。
ABD + A BC + ABD + A BC
ACD + BCD + ACD + BCD​​​​
2つの異なる極小形式を持つブール関数。ブレイク標準形はこれら2つの関数の和である。

ブール論理では、ブール関数 fの式はブレイク標準形( BCF ) [ 1 ]であり、これは素因数の完全和[ 2 ]完全和[ 3 ]またはfのすべての素因数の選言であるときは選言素形[ 4 ]とも呼ばれる。[ 1 ]

他のフォームとの関係

ブレイク標準形は、選言標準形の特殊なケースです。

ブレイク標準形は必ずしも最小和ではない（上図）が、最小和のすべての項はブレイク標準形に含まれる。[ 3 ]一方、ブレイク標準形は標準形であり、つまり並べ替えを除いて一意であるが、最小和は複数存在する可能性がある（下図）。ブレイク標準形から最小和を選択することは、一般に集合被覆問題を解くことと等しく、[ 5 ] NP困難である。[ 6 ] [ 7 ]

歴史

アーチー・ブレイクは、 1932年のアメリカ数学会で自身の標準形を発表し[ 8 ]、1937年の博士論文でも発表した。彼はこれを「簡略化された標準形」と呼んだ[ 9 ] [ 10 ] [ 11 ] [ 12 ]。これは1986年から1990年にかけて、フランク・マーカム・ブラウンとセルジュ・ルデアヌによって「ブレイク標準形」と名付けられた[ 13 ] [ 1 ] 。プラトン・ポレツキーの研究[ 14 ]と合わせて「ブレイク＝ポレツキーの法則」とも呼ばれる[ 15 ] 。

計算方法

ブレイクは、正準形を計算するための3つの手法、すなわち含意の枯渇、反復コンセンサス、そして乗算について論じた。反復コンセンサス法は、エドワード・W・サムソンとバートン・E・ミルズ[ 16 ] 、ウィラード・クワイン[ 17 ]、そしてカート・ビング[ 18 ]によって再発見された。[ 19 ] 2022年には、ミラン・モセ、ハリー・シャ、リー・ヤン・タンが、連言正規形における式のブレイク正準形を計算するためのほぼ最適なアルゴリズムを発見した。[ 20 ]

参照

参考文献

  1. ^ a b c dブラウン、フランク・マーカム[Wikidataにて] (2012) [2003, 1990]. 「第3章 ブレイク標準形」.ブール推論 - ブール方程式の論理（第2版の再発行）. ミネオラ、ニューヨーク：ドーバー出版. pp. 4, 77ff, 81. ISBN 978-0-486-42785-0。[1]
  2. ^笹尾、勉 (1996). 「三者決定図とその応用」。笹尾では勉。藤田正平（編）離散関数の表現。 p. 278.土井: 10.1007/978-1-4613-1385-4_12。ISBN 978-0792397205。
  3. ^ a bカンデル、アブラハム（1998年）『デジタルロジック設計の基礎』ワールドサイエンティフィック、p. 177、ISBN 978-9-81023110-1。
  4. ^ Knuth, Donald Ervin (2011).組み合わせアルゴリズム 第1部. 『コンピュータプログラミングの芸術』 第4A巻. p. 54.
  5. ^ Feldman, Vitaly [Wikidataにて] (2009). 「近似2レベルロジック最小化の困難性とメンバーシップクエリによるPAC学習」 . Journal of Computer and System Sciences . 75 : 13–25 [13–14]. doi : 10.1016/j.jcss.2008.07.007 .
  6. ^ギンペル、ジェームズ・F. (1965). 「任意の規定された主項表を持つブール関数を生成する方法」. IEEE Transactions on Computers . 14 : 485–488 .
  7. ^ポール、ヴォルフガング・ヤコブ[ドイツ語] (1974). 「ブールの極小多項式と超巨大な問題」。Acta Informatica (ドイツ語)。4 (4): 321–336。土井: 10.1007/BF00289615。S2CID 35973949。 
  8. ^ブレイク、アーチー（1932年11月）「ブール代数における標準表現」アメリカ数学会報、論文抄録：805。
  9. ^ Blake, Archie (1937).ブール代数の標準表現（学位論文）.シカゴ大学数学科：シカゴ大学図書館.
  10. ^ブレイク、アーチー(1938). 「ブール代数における標準表現」.記号論理学ジャーナル. 3 (2).
  11. ^ Blake, Archie (1938年9月). 「ブール代数における標準表現の修正」. The Journal of Symbolic Logic . 3 (3): 112– 113. doi : 10.2307/2267595 . JSTOR 2267595. S2CID 5810863 .  
  12. ^マッキンゼー、ジョン・チャールズ・チェノウェス編（1938年6月）。「アーチー・ブレイク『ブール代数の標準表現』シカゴ大学数学科、1937年」。『記号論理学ジャーナル』（レビュー）。3 ( 2:93): 93. doi : 10.2307/2267634。JSTOR 2267634 。S2CID 122640691。  
  13. ^ブラウン、フランク・マーカム[ウィキデータにて] ; Rudeanu, Sergiu [ウィキデータにて] (1986)、「プライム・インプリカントの理論への関数的アプローチ」、Publication de l'institut mathématique、Nouvelle série、vol. 40、23–32ページ 
  14. ^ポレツキー、プラトン・セルゲイヴィッチ(1884)。 「O sposobach reschenija lopgischeskich rawenstw i ob obrathom spocobe matematischeskoi logiki」О способах резения логических равенств и об обратном способе[論理等式の解法と数理論理学の逆法について。質的形式に関する完全かつアクセスしやすい演繹理論の構築に関する試論]カザン大学自然科学協会物理・数学部会会議録集（ロシア語）(2)。(注: この出版物は、「論理等式の解法と数理論理学の逆方法について」とも呼ばれています。)
  15. ^ Vasyukevich, Vadim O. (2011). 「1.10 ヴェンジャンクション特性（基本公式）」. ラトビア、リガにて執筆.非同期式順序論理演算子：ヴェンジャンクションとシーケンション — デジタル回路の解析と設計. 電気工学講義ノート (LNEE). 第101巻 (第1版). ベルリン/ハイデルベルク, ドイツ: Springer-Verlag . p. 20. doi : 10.1007/978-3-642-21611-4 . ISBN 978-3-642-21610-7. ISSN  1876-1100 . LCCN  2011929655 .(xiii+1+123+7 ページ) (注: この本の裏表紙には第 4 巻と誤って記載されていますが、実際は第 101 巻です。)
  16. ^サムソン、エドワード・ウォルター、ミルズ、バートン・E.（1954年4月）。『回路の最小化：新しいブール標準式のための代数とアルゴリズム（技術報告書）』マサチューセッツ州ベッドフォード、米国：空軍ケンブリッジ研究センター。AFCRC TR 54-21。
  17. ^クワイン、ウィラード・ヴァン・オーマン（1955年11月）「真理関数の簡略化の方法」アメリカ数学月刊誌. 62 (9): 627– 631. doi : 10.2307/2307285 . hdl : 10338.dmlcz/142789 . JSTOR 2307285 . 
  18. ^ビング、カート (1955). 「命題式の簡略化について」アメリカ数学会報61 :560 .
  19. ^ビング、カート (1956). 「真理関数式の簡略化について」.記号論理学ジャーナル. 21 (3): 253– 254. doi : 10.2307/2269097 . JSTOR 2269097. S2CID 37877557 .  
  20. ^ Mossé, Milan; Sha, Harry; Tan, Li-Yang (2022). 「充足可能性符号化補題の一般化とその応用」 . DROPS-IDN/V2/Document/10.4230/LIPIcs.SAT.2022.9 . Leibniz International Proceedings in Informatics (LIPIcs). 236. Schloss Dagstuhl – Leibniz-Zentrum für Informatik: 9:1–9:18. doi : 10.4230/LIPIcs.SAT.2022.9 . ISBN 978-3-95977-242-6。
「 https://en.wikipedia.org/w/index.php?title=Blake_canonical_form&oldid=1329367112」より取得