페트릭의 방법

부울 대수학에서 페트릭의^[1] 방법(페트릭 함수^[2] 또는 분기 및 바인딩 방법이라고도 함)은 스탠리 R에 의해 기술된 기술이다. 1956년 Petrick(1931–^[3]^[4]2006)은 주요 내연성 차트에서 모든 최소 제품 총합 솔루션을 결정한다^[5]^[6].^[7]페트릭의 방법은 대형 차트에서는 매우 지루하지만, 컴퓨터에서는 구현하기 쉽다.^[7]그 방법은 인슬리 B에 의해 개선되었다. 피네와 에드워드 조셉 맥클러키는 1962년에 결혼했다.^[8]^[9]

알고리즘.

주요 내연성 행과 해당 열을 제거하여 주요 내연성 차트를 줄이십시오.^[7]
축소된 프라이머리 내연성 $P_{1}$ $P_{1}$ 1 ${\$ $P_{2}$ $P_{3}$ ${\$ $P_{3}$ 3 ${\$ $P_{4}$ $P_{4}$ ${\$ 등의 행에 레이블을 붙인다.^[7]
모든 열이 포함되었을 때 참인 $P$ 논리 함수 $P$ $P$ 을(를) 형성하십시오.P consists of a product of sums where each sum term has the form $(P_{i0}+P_{i1}+$ $\cdots$ $+P_{iN})$ , where each $P_{ij}$ represents a row covering column $i$ .^[7]
흡수 [nb 1] 법칙 $X+XY=X$ + $X+XY=X$ $X+XY=X$ = $X+XY=X$ $X+XY=X$ 을(를) 곱하고 적용하여 $P$ ${\displaystyle$ X+XY=X}을 $($ 를) 최소 제품 합으로 $P$ 줄이십시오 $X+XY=X$ ^[7]
결과의 각 용어는 해결책, 즉 표의 모든 작은 단어를 포함하는 행 집합을 나타낸다.최소 해결 방법을 결정하려면 우선 최소 수의 주요 내연성 물질이 포함된 용어를 찾으십시오.^[7]
다음으로, 5단계에서 발견된 각 용어에 대해 각 주요 내연성 물질의 리터 수를 세어 총 리터 수를 찾으십시오.^[7]
최소 총 리터 수로 구성된 항 또는 항을 선택하고 주요 내연제의 합계를 기록하십시오.^[7]

페트릭 방법의 예

다음은 우리가 줄이고자 하는 기능이다.^[10]

f(A,B,C)=\sum m(0,1,2,5,6,7)\,

Quine-McCluskey 알고리즘의 주요 내연성 차트는 다음과 같다.

	⇒	A	B	C
K = m(0,1)	⇒	0	0	—
L = m(0,2)	⇒	0	—	0
M = m(1,5)	⇒	—	0	1
N = m(2,6)	⇒	—	1	0
P = m(5,7)	⇒	1	—	1
Q = m(6,7)	⇒	1	1	—

위 표의 in 마크를 바탕으로 각 행이 추가되고 열이 함께 곱되는 행의 합계 산출물을 작성한다.

(K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q)

그 표현을 제품의 총합으로 바꾸려면 분배법을 사용하라.또한 X + XY = X 및 XX = X 및 X+X=X 식을 단순화하기 위해 다음과 같은 동등성을 사용하십시오.

= (K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q)  = (K+LM)(N+LQ)(P+MQ)  = (KN+KLQ+LMN+LMQ)(P+MQ)  = KNP + KLPQ + LMNP + LMPQ + KMNQ + KLMQ + LMNQ + LMQ

이제 다음 동등성을 다시 사용하여 방정식을 더 줄이십시오: X + XY = X

= KNP + KLPQ + LMNP + LMNQ + KMNQ

용어가 가장 적은 제품을 선택하십시오. 이 예에서는 세 가지 용어가 있는 두 가지 제품이 있다.

KNP LMQ

총 리터 수가 가장 적은 항 또는 항을 선택하십시오.이 예에서 두 제품은 모두 각각 6L로 확장된다.

KNP는 a'b' + bc' + ac LMQ로 확장되며 a'c' + b'c + ab로 확장된다.

그래서 둘 중 하나를 사용할 수 있다.일반적으로 대형 차트에서는 페트릭의 방법 적용이 지루하지만, 컴퓨터에서는 구현이 쉽다.^[7]

메모들

^ 이것은 열 수에 기하급수적인 증가를 야기한다.

참조

^ 린드, 래리 프레드릭, 넬슨, 존 크리스토퍼 Cunliffe(1977-04-01)."2.3.6.필요한 총리 implicants"의 선정.해석 및 설계 시공 단계별 디지털 시스템의.전자 전기 공학(1판).런던&베이싱 스토크, 영국:맥밀란 출판 주식 회사를 대신하여 서명함. 19,77입니다. doi:10.1007/978-1-349-15757-0.아이 에스비엔 0-333-19266-4.그 2020-04-30에 원래에서 Archived..(4+viii+146+6 페이지)2020-04-30 Retrieved
^ Svoboda, Antonín; White, Donnamaie E. (2016) [2012, 1985, 1979-08-01]. "9.9. The Petrick function solution for the minimal ΣΠ-form of y" (PDF). Advanced Logical Circuit Design Techniques (PDF) (retyped electronic reissue ed.). Garland STPM Press (original issue) / WhitePubs Enterprises, Inc. (reissue). pp. 148–150. ISBN 978-0-8240-7014-4. LCCN 78-31384. Archived (PDF) from the original on 2017-04-14. Retrieved 2017-04-15. [1] [2]
^ "Biographical note". Archived from the original on 2017-04-13. Retrieved 2017-04-12. Stanley R. Petrick was born in Cedar Rapids, Iowa on August 16, 1931. He attended the Roosevelt High School and received a B. S. degree in Mathematics from the Iowa State University in 1953. During 1953 to 1955 he attended MIT while on active duty as an Air Force officer and received the S. M. degree from the Department of Electrical Engineering in 1955. He was elected to Sigma Xi in 1955.
Mr. Petrick has been associated with the Applied Mathematics Board of the Data Sciences Laboratory at the Air Force Cambridge Research Laboratories since 1955 and his recent studies at MIT have been partially supported by AFCRL. During 1959–1962 he held the position of Lecturer in Mathematics in the Evening Graduate Division of Northeastern University.
Mr. Petrick is currently a member of the Linguistic Society of America, The Linguistic Circle of New York, The American Mathematical Association, The Association for Computing Machinery, and the Association for Machine Translation and Computational Linguistics.
^ "Obituaries-시더 래피즈-스탠리 R.Petrick".그 Gazette. 2006-08-05. 16페이지의 주.그 2017-04-13에 원래에서 Archived..[...]CEDAR RAPIDS 스탠리 R2017-04-12 Retrieved페트릭 74세의 시더 래피즈 쒓쿋援곗슂, 7월 27일 2006년, Presbyterian/St에서 죽었다.루크의 병원, 덴버 콜로라도 주 Boulder, 백혈병과 13년 전투 이후에.[...]스탠 페트릭 시더 래피즈에서 8월 6일 1931년 캐서린 헌트 페트릭과 프레드 페트릭에 태어난 제사는 8월 14일 미국 장로 교회에서 라라 미에서 개최 Wyo., 그가 몇년을 살았기에. 열릴 예정이다.그는 루즈벨트 고등 학교에서 1949년 아이오와 주립 대학에서 수학 분야 학사 학위를 받았고 졸업했다.스탠 1953년에서 Mary를 Ethel벅스와 결혼했다.그는 학생 장교 MIT, 그는 이런. 학위를 취득한 디지털 계산 연구하는 것 바로 맡겨졌다 미국 공군에 합류했다.그리고 그는 응용 수학 지사 공군 캠브리지 연구소의고 있습니다. 언어학 박사 학위를 받은 할당되었다.그는 20년과 전산 이론적 언어학 그룹은-부서는 IBM의 T.J. 왓슨 연구 센터에서에서 공식적인 언어 이론에서 연구를 수행하고 보냈다.그는 수학 공학부 SIG의 상징성과 대수적 조작은 협회 컴퓨터 학회의 회장은 협회 전산 언어학의 대통령의 조감독으로 재직하고 있다.그는 많은 기술 출판물의 저자이기도 하다.그는 노스 이스턴 대학, 세살 그리고 13년은 프랫 인스티튜트에서 가르쳤다.박사는 페트릭 1987년, 그는 거기서 그 부서에서 박사 과정을 수립, 실시하는데 도움이 되었습니다에서 논문 조언자로서 많은 대학원생들이 근무했던 와이오밍 대학에 입대했다.그는 1995년.[...](주의 은퇴했다.스탠리 R의 사진을 포함한다페트릭.)
^ Petrick, Stanley R. (1956-04-10). A Direct Determination of the Irredundant Forms of a Boolean Function from the Set of Prime Implicants. Bedford, Cambridge, Massachusetts, USA: Air Force Cambridge Research Center. AFCRC Technical Report TR-56-110.
^ Lewin, Douglas (1974) [1968]. Logical Design of Switching Functions (1981 7th reprinted edition of the 2nd ed.). Thomas Nelson and Sons Ltd / Van Nostrand Reinhold Co., Ltd. p. 60. ISBN 0-442-30747-0. ISBN 0-17-771044-6. NCN 420-5805-4.
^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j Roth, Jr., Charles H. (1992). Fundamentals of Logic Design (4 ed.). ISBN 0-31492218-0.
^ Pyne, Insley B.; McCluskey, Jr., Edward Joseph (1962). "The reduction of redundancy in solving prime implicant tables". I.R.E. Transactions on Electronic Computers. EC-11 (4): 473–482.
^ Choudhury, Arun K. (February 1968). "I. B. Pyne and E. J. McCluskey Jr., The reduction of redundancy in solving prime implicant tables. IRE transactions on electronic computers, vol. EC-11 (1962), pp. 473–482". The Journal of Symbolic Logic. Reviews. Association for Symbolic Logic (ASL). 32 (4): 540–541. doi:10.2307/2270229. JSTOR 2270229.
^ Frenzel, James "Jim" F. (2007). "Lecture #10: Petrick's Method". ECE 349 – Background Study in Digital Computer Fundamentals. Moscow, Idaho, USA: Department of Electrical and Computer Engineering, University of Idaho. Archived from the original on 2017-04-12. Retrieved 2019-08-08. [3]

추가 읽기

Krambeck, Donald (2016-02-17). "Prime Implicant Simplification Using Petrick's Method". All About Circuits. EETech Media, LLC. Archived from the original on 2017-04-12. Retrieved 2020-04-03.
Petrick, Stanley R. (1965). A Recognition Procedure for Transformational Grammars (PhD thesis). Massachusetts Institute of Technology.
Bolton, Martin (1990). "4. Minimization". Written at University of Bristol, Bristol, UK. In Dagless, Erik L. (ed.). Digital Systems Design with Programmable Logic. Electronic Systems Engineering Series (1 ed.). Wokingham, UK: Addison-Wesley Publishers Ltd. pp. 100–101, 115. ISBN 0-201-14545-6. LCCN 90000007. ISBN 978-0-201-14545-8 ark:/13960/t2f83p38r. Retrieved 2021-04-17.{{cite book}}: CS1 maint: url-status (link) (xiv+379+1 pages)

외부 링크

Quine-McCluskey 및 Petrick 방법에 대한 자습서
위의 튜토리얼을 기반으로 한 Petrick C++ 구현

[NB_Exponential-10] 이것은 열 수에 기하급수적인 증가를 야기한다.

[Lind_1977-1] 린드, 래리 프레드릭, 넬슨, 존 크리스토퍼 Cunliffe(1977-04-01)."2.3.6.필요한 총리 implicants"의 선정.해석 및 설계 시공 단계별 디지털 시스템의.전자 전기 공학(1판).런던&베이싱 스토크, 영국:맥밀란 출판 주식 회사를 대신하여 서명함. 19,77입니다. doi:10.1007/978-1-349-15757-0.아이 에스비엔 0-333-19266-4.그 2020-04-30에 원래에서 Archived..(4+viii+146+6 페이지)2020-04-30 Retrieved

[Svoboda_1979_Petrick-2] Svoboda, Antonín; White, Donnamaie E. (2016) [2012, 1985, 1979-08-01]. "9.9. The Petrick function solution for the minimal ΣΠ-form of y" (PDF). Advanced Logical Circuit Design Techniques (PDF) (retyped electronic reissue ed.). Garland STPM Press (original issue) / WhitePubs Enterprises, Inc. (reissue). pp. 148–150. ISBN 978-0-8240-7014-4. LCCN 78-31384. Archived (PDF) from the original on 2017-04-14. Retrieved 2017-04-15. [1] [2]

[Petrick_Bio-3] "Biographical note". Archived from the original on 2017-04-13. Retrieved 2017-04-12. Stanley R. Petrick was born in Cedar Rapids, Iowa on August 16, 1931. He attended the Roosevelt High School and received a B. S. degree in Mathematics from the Iowa State University in 1953. During 1953 to 1955 he attended MIT while on active duty as an Air Force officer and received the S. M. degree from the Department of Electrical Engineering in 1955. He was elected to Sigma Xi in 1955.
Mr. Petrick has been associated with the Applied Mathematics Board of the Data Sciences Laboratory at the Air Force Cambridge Research Laboratories since 1955 and his recent studies at MIT have been partially supported by AFCRL. During 1959–1962 he held the position of Lecturer in Mathematics in the Evening Graduate Division of Northeastern University.
Mr. Petrick is currently a member of the Linguistic Society of America, The Linguistic Circle of New York, The American Mathematical Association, The Association for Computing Machinery, and the Association for Machine Translation and Computational Linguistics.

[Petrick_Obit-4] "Obituaries-시더 래피즈-스탠리 R.Petrick".그 Gazette. 2006-08-05. 16페이지의 주.그 2017-04-13에 원래에서 Archived..[...]CEDAR RAPIDS 스탠리 R2017-04-12 Retrieved페트릭 74세의 시더 래피즈 쒓쿋援곗슂, 7월 27일 2006년, Presbyterian/St에서 죽었다.루크의 병원, 덴버 콜로라도 주 Boulder, 백혈병과 13년 전투 이후에.[...]스탠 페트릭 시더 래피즈에서 8월 6일 1931년 캐서린 헌트 페트릭과 프레드 페트릭에 태어난 제사는 8월 14일 미국 장로 교회에서 라라 미에서 개최 Wyo., 그가 몇년을 살았기에. 열릴 예정이다.그는 루즈벨트 고등 학교에서 1949년 아이오와 주립 대학에서 수학 분야 학사 학위를 받았고 졸업했다.스탠 1953년에서 Mary를 Ethel벅스와 결혼했다.그는 학생 장교 MIT, 그는 이런. 학위를 취득한 디지털 계산 연구하는 것 바로 맡겨졌다 미국 공군에 합류했다.그리고 그는 응용 수학 지사 공군 캠브리지 연구소의고 있습니다. 언어학 박사 학위를 받은 할당되었다.그는 20년과 전산 이론적 언어학 그룹은-부서는 IBM의 T.J. 왓슨 연구 센터에서에서 공식적인 언어 이론에서 연구를 수행하고 보냈다.그는 수학 공학부 SIG의 상징성과 대수적 조작은 협회 컴퓨터 학회의 회장은 협회 전산 언어학의 대통령의 조감독으로 재직하고 있다.그는 많은 기술 출판물의 저자이기도 하다.그는 노스 이스턴 대학, 세살 그리고 13년은 프랫 인스티튜트에서 가르쳤다.박사는 페트릭 1987년, 그는 거기서 그 부서에서 박사 과정을 수립, 실시하는데 도움이 되었습니다에서 논문 조언자로서 많은 대학원생들이 근무했던 와이오밍 대학에 입대했다.그는 1995년.[...](주의 은퇴했다.스탠리 R의 사진을 포함한다페트릭.)

[Petrick_1956-5] Petrick, Stanley R. (1956-04-10). A Direct Determination of the Irredundant Forms of a Boolean Function from the Set of Prime Implicants. Bedford, Cambridge, Massachusetts, USA: Air Force Cambridge Research Center. AFCRC Technical Report TR-56-110.

[Lewin_1974-6] Lewin, Douglas (1974) [1968]. Logical Design of Switching Functions (1981 7th reprinted edition of the 2nd ed.). Thomas Nelson and Sons Ltd / Van Nostrand Reinhold Co., Ltd. p. 60. ISBN 0-442-30747-0. ISBN 0-17-771044-6. NCN 420-5805-4.

[Roth_1992-7] ^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j Roth, Jr., Charles H. (1992). Fundamentals of Logic Design (4 ed.). ISBN 0-31492218-0.

[Pyne_1962-8] Pyne, Insley B.; McCluskey, Jr., Edward Joseph (1962). "The reduction of redundancy in solving prime implicant tables". I.R.E. Transactions on Electronic Computers. EC-11 (4): 473–482.

[Choudhury_1968-9] Choudhury, Arun K. (February 1968). "I. B. Pyne and E. J. McCluskey Jr., The reduction of redundancy in solving prime implicant tables. IRE transactions on electronic computers, vol. EC-11 (1962), pp. 473–482". The Journal of Symbolic Logic. Reviews. Association for Symbolic Logic (ASL). 32 (4): 540–541. doi:10.2307/2270229. JSTOR 2270229.

[Frenzel_2007-11] Frenzel, James "Jim" F. (2007). "Lecture #10: Petrick's Method". ECE 349 – Background Study in Digital Computer Fundamentals. Moscow, Idaho, USA: Department of Electrical and Computer Engineering, University of Idaho. Archived from the original on 2017-04-12. Retrieved 2019-08-08. [3]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

Search

페트릭의 방법

네임스페이스

더

목차

알고리즘.

페트릭 방법의 예

메모들

참조

추가 읽기

외부 링크