Product Design, Manufacturing & Innovation Resources
집 » 드 모르간의 법칙

드 모르간의 법칙

1850
  • Augustus De Morgan
Digital circuit design workspace showcasing De Morgan's Laws in Boolean algebra.

(설명을 위한 생성된 이미지입니다)

De Morgan’s laws are a pair of transformation rules in 부울 대수 that are fundamental to digital circuit design. The 첫 번째 법칙 첫 번째 명제는 논리곱의 부정은 부정들의 논리합이라는 것을 나타냅니다. [latex]neg(P land Q) iff (neg P) lor (neg Q)[/latex]. 두 번째 명제는 논리합의 부정은 부정들의 논리곱이라는 것을 나타냅니다. [latex]neg(P lor Q) iff (neg P) land (neg Q)[/latex].

In the context of digital electronics, De Morgan’s laws provide a powerful tool for circuit manipulation. They establish a direct equivalence between different types of logic gates. For example, the 첫 번째 법칙, [latex]\neg(A \cdot B) = \neg A + \neg B[/latex] (using dot for AND and plus for OR), shows that a NAND gate is equivalent to an OR gate with inverted inputs. Similarly, the 두 번째 법칙[latex]neg(A + B) = neg A cdot neg B[/latex]는 NOR 게이트가 입력이 반전된 AND 게이트와 동일함을 보여줍니다. 이러한 상호 교환성은 매우 실용적입니다. NAND 게이트와 NOR 게이트는 '범용 게이트', 즉 모든 부울 함수를 NAND 게이트 또는 NOR 게이트만으로 구현할 수 있기 때문에, 드 모르간의 법칙은 AND, OR, NOT 게이트가 혼합된 회로 설계를 단일 게이트 유형을 사용하는 설계로 변환하는 데 필수적입니다. 이는 한 가지 유형의 논리 셀만 완벽하게 개발하고 복제하면 되므로 집적 회로 제조 공정을 단순화합니다. 또한 드 모르간의 법칙은 논리 합성 소프트웨어에서 기본 부울 표현식을 변환하고 단순화하여 속도, 면적 또는 전력 소비를 최적화하는 데 널리 사용됩니다.

UNESCO Nomenclature: 1202
컴퓨터 과학

유형

추상 시스템

분열

상당한

용법

널리 사용됨

전구체

  • 아리스토텔레스 논리학
  • 조지 불의 기호 논리학 공식화
  • 초기 수학자들의 대수학과 논리학에서의 쌍대성 연구

응용 프로그램

  • 회로 설계에서 부울 표현식의 간소화
  • AND/OR 논리와 NAND/NOR 논리 간의 변환
  • 컴파일러 소프트웨어 최적화
  • 데이터베이스 쿼리 최적화
  • 형식적 검증 디지털 시스템

특허:

NA

잠재적 혁신 아이디어

  • automated logic synthesis tools that apply de morgan’s laws for circuit optimization
  • multi-valued logic systems with generalized de morgan’s laws
  • fuzzy logic controllers where de morgan’s laws define fuzzy set operations
  • quantum logic gate synthesis using quantum equivalents of de morgan’s laws
  • formal verification algorithms that use these laws to check circuit equivalence
  • design of fault-tolerant circuits by creating redundant logic paths
  • cryptographic algorithms that use boolean transformations for obfuscation
  • ai-based theorem provers that rediscover or generalize these logical rules
Related to: de morgan’s laws, boolean algebra, logic simplification, nand gate, nor gate, universal gates, digital logic, set theory.

역사적 맥락

드 모르간의 법칙

1822
1827
1829
1850
1854
1854
1895
1822
1822
1828
1848
1850
1854
1884
1896

(날짜를 알 수 없거나 관련이 없는 경우, 예를 들어 "유체역학"의 경우, 주목할 만한 등장 시기를 대략적으로 추정하여 제공합니다.)

10년차 기념일

고화질 이미지 및 다운로드는 등록된 회원에게만 100% 무료로 제공됩니다.

> 로그인 <