블레이크 표준형

Blake canonical form
AB + BC + AC의 Karnaugh 지도는 모든 주요 내연성 물질(각각 다른 색으로 렌더링됨)의 합이다.AC를 삭제하면 최소 합이 된다.
ABD + ABC + ABB + ABC
ACD + BCD + ACD + BCD
서로 다른 두 개의 최소 형식을 가진 부울 함수.블레이크 표준형식은 둘의 합이다.

부울 논리에서는 부울함수 f의 공식은 블레이크 표준형식(BCF)으로,[1] f의 모든 주요 함수를 분리할 때 주요 함수의 전체 합,[2] 전체 합,[3] 또는 분리 원시 형태라고도 한다.[4][1]

다른 형태와의 관계

블레이크 표준형식은 분리 정규형식의 특별한 경우다.

블레이크 표준형식이 반드시 최소형(상단 도표)은 아니지만, 최소 합계의 모든 용어가 블레이크 표준형식에 포함되어 있다.[3]반면에 블레이크 표준형식은 표준형식으로, 즉 재주문까지 고유하지만, 여러 개의 최소형식(하단도)이 있을 수 있다.블레이크 표준 형식에서 최소 합계를 선택하는 것은 일반적으로 세트 커버 문제를 해결하는 데 드는 양이며,[5] NP-hard도 마찬가지다.[6][7]

역사

아치 블레이크는 1932년 미국수학협회 모임에서,[8] 그리고 1937년 논문에서 자신의 표준형식을 발표했다.그는 그것을 "간단한 표준형식"이라고 불렀고,[9][10][11] 1986–90년에 프랭크 마크햄 브라운과 세르주 루드파누[d]에 의해 "Blake 표준형식"으로 명명되었다.[12][1]

계산방법

블레이크는 세 가지 표준 형식 계산 방법을 논의했는데, 즉 내연제의 소진, 반복적인 합의, 그리고 곱셈이었다.반복된 합의 방식은 에드워드 샘슨과 버튼 E에 의해 재발견되었다[1].밀스,[13] 윌러드 킨,[14] 커트 빙.[15][16]

참고 항목

참조

  1. ^ a b c d Brown, Frank Markham (2012) [2003, 1990]. "Chapter 3: The Blake Canonical Form". Boolean Reasoning - The Logic of Boolean Equations (reissue of 2nd ed.). Mineola, New York: Dover Publications, Inc. pp. 4, 77ff, 81. ISBN 978-0-486-42785-0. [1]
  2. ^ Sasao, Tsutomu (1996). "Ternary Decision Diagrams and their Applications". In Sasao, Tsutomu; Fujita, Masahira (eds.). Representations of Discrete Functions. p. 278. doi:10.1007/978-1-4613-1385-4_12. ISBN 978-0792397205.
  3. ^ a b Kandel, Abraham (1998). Foundations of Digital Logic Design. p. 177. ISBN 978-9-81023110-1.
  4. ^ Knuth, Donald Ervin (2011). Combinatorial Algorithms, Part 1. The Art of Computer Programming. Vol. 4A. p. 54.
  5. ^ Feldman, Vitaly (2009). "Hardness of Approximate Two-Level Logic Minimization and PAC Learning with Membership Queries". Journal of Computer and System Sciences. 75: 13–25 [13–14]. doi:10.1016/j.jcss.2008.07.007.
  6. ^ Gimpel, James F. (1965). "A Method for Producing a Boolean Function Having an Arbitrary Prescribed Prime Implicant Table". IEEE Transactions on Computers. 14: 485–488.
  7. ^ Paul, Wolfgang Jakob (1974). "Boolesche Minimalpolynome und Überdeckungsprobleme". Acta Informatica (in German). 4 (4): 321–336. doi:10.1007/BF00289615. S2CID 35973949.
  8. ^ Blake, Archie (November 1932). "Canonical expressions in Boolean algebra". Bulletin of the American Mathematical Society. Abstracts of Papers: 805.
  9. ^ Blake, Archie (1937). Canonical expressions in Boolean algebra (Dissertation). Department of Mathematics, University of Chicago: University of Chicago Libraries.
  10. ^ Blake, Archie (September 1938). "Corrections to Canonical Expressions in Boolean Algebra". The Journal of Symbolic Logic. 3 (3): 112–113. doi:10.2307/2267595. JSTOR 2267595.
  11. ^ McKinsey, John Charles Chenoweth, ed. (June 1938). "Blake, Archie. Canonical expressions in Boolean algebra, Department of Mathematics, University of Chicago, 1937". The Journal of Symbolic Logic (Review). 3 (2:93): 93. doi:10.2307/2267634. JSTOR 2267634.
  12. ^ Brown, Frank Markham; Rudeanu, Sergiu (1986), A Functional Approach to the Theory of Prime Implicants, Publication de l'institut mathématique, Nouvelle série, vol. 40, pp. 23–32
  13. ^ Samson, Edward Walter; Mills, Burton E. (April 1954). Circuit Minimization: Algebra and Algorithms for New Boolean Canonical Expressions (Technical Report). Bedford, Massachusetts, USA: Air Force Cambridge Research Center. AFCRC TR 54-21.
  14. ^ Quine, Willard Van Orman (November 1955). "A Way to Simplify Truth Functions". The American Mathematical Monthly. 62 (9): 627–631. doi:10.2307/2307285. hdl:10338.dmlcz/142789. JSTOR 2307285.
  15. ^ Bing, Kurt (1955). "On simplifying propositional formulas". Bulletin of the American Mathematical Society. 61: 560.
  16. ^ Bing, Kurt (1956). "On simplifying truth-functional formulas". The Journal of Symbolic Logic. 21 (3): 253–254. doi:10.2307/2269097. JSTOR 2269097.