Product Design, Manufacturing & Innovation Resources
Lar » Leis de De Morgan

Leis de De Morgan

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

(Imagem gerada apenas para fins ilustrativos)

De Morgan’s laws are a pair of transformation rules in Álgebra booleana that are fundamental to digital circuit design. The primeira lei A primeira afirma que a negação de uma conjunção é a disjunção das negações: [latex]neg(P land Q) iff (neg P) land (neg Q)[/latex]. A segunda afirma que a negação de uma disjunção é a conjunção das negações: [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 primeira lei, [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 segunda leiA figura [latex]neg(A + B) = neg A cdot neg B[/latex] mostra que uma porta NOR é equivalente a uma porta AND com entradas invertidas. Essa intercambialidade é extremamente prática. Como as portas NAND e NOR são "portas universais" — o que significa que qualquer função booleana pode ser implementada usando apenas portas NAND ou apenas portas NOR — as leis de De Morgan são essenciais para converter um projeto de circuito de uma combinação de portas AND, OR e NOT em um projeto usando um único tipo de porta. Isso simplifica o processo de fabricação de circuitos integrados, pois apenas um tipo de célula lógica precisa ser aperfeiçoado e replicado. As leis também são amplamente utilizadas em softwares de síntese lógica para otimizar circuitos em termos de velocidade, área ou consumo de energia, transformando e simplificando as expressões booleanas subjacentes.

UNESCO Nomenclature: 1202
Ciência da Computação

Tipo

Sistema abstrato

Interrupção

Substancial

Uso

Uso generalizado

Precursores

  • lógica aristotélica
  • A formulação da lógica simbólica por George Boole
  • Trabalhos sobre dualidade em álgebra e lógica realizados por matemáticos anteriores.

Aplicações

  • Simplificação de expressões booleanas no projeto de circuitos
  • Conversão entre lógica AND-OR e lógica NAND/NOR.
  • compilador otimização em software
  • otimização de consultas de banco de dados
  • verificação formal de sistemas digitais

Patentes:

NA

Ideias de Inovação Potencial

  • 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, álgebra booleana, logic simplification, nand gate, nor gate, universal gates, digital logic, set theory.

Contexto histórico

Leis de De Morgan

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

(Caso a data seja desconhecida ou irrelevante, por exemplo, "mecânica dos fluidos", é fornecida uma estimativa aproximada de seu surgimento notável)

10º ano aniversário

Imagens em tamanho real e downloads estão disponíveis apenas, 100% gratuitos, para membros registrados.