Un mapa de Karnaugh é un método para simplificar expresións de álxebra booleana. Maurice Karnaugh introduciu este método en 1953[1][2] coma un refinamento do grafo de Veitch publicado por Edward Veitch en 1952,[3][4] que á súa vez era un redescubrimento do diagrama lóxico de Allan Marquand de 1881[5] tamén coñecido como diagrama Marquand.[4] Os grafos de Veitch tamén se coñecen como diagramas Marquand–Veitch diagrams,[4] e os mapas de Karnaugh como mapas Karnaugh–Veitch. Un mapa de Karnaugh reduce a necesidade de grandes cálculos aproveitando as capacidades humanas de recoñecemento de padróns,[1] e permite a rápida identificación e eliminación de potenciais condicións de carreira.

Exemplo de mapa de Karnaugh. Esta imaxe mostra en realidade dous mapas de Karnaugh: para a función ƒ, utilizando mintermos (rectángulos de cores) e para o seu complemento, utilizando maxtermos (rectángulos grises). Na imaxe, E() significa unha suma de mintermos.

Os resultados booleanos transfírense dende unha táboa de verdade ata unha grella bidimensional na que as celas se ordenan en código Gray,[4][6] e cada posición de cela representa unha combinación de condicións de entrada, mentres que cada valor de cela representa o valor de saída correspondente. Identifícanse grupos óptimos de 1s ou 0s, que representan os termos da forma canónica da lóxica na táboa de verdade orixinal.[7] Estes termos poden empregarse para escribir unha expresión booleana mínima que representa á lóxica requirida.

Os mapas de Karnaugh empréganse para simplificar requirimentos lóxicos no mundo real para que poidan poñerse en funcionamento utilizando un número mínimo de portas lóxicas físicas. Unha expresión de suma de produtos sempre pode poñerse en práctica usando portas AND que alimentan unha porta OR, e un expresión de produto de sumas dá lugar a portas OR alimentando unha porta AND.[8] Os mapas de Karnaugh tamén se poden empregar para simplificar expresións lóxicas en deseño de software. As condicións booleanas empregadas en sentenzas booleanas poden resultar moi complexas, dificultando a lectura e mantemento do código, polo que unha vez minimizadas as expresións poden definirse directamente utilizando operadores lóxicos AND e OR.[9]

Todas as referencias en inglés agás cando se indique o contrario.

  1. 1,0 1,1 Karnaugh, Maurice (1953) [1953-04-23]. "The Map Method for Synthesis of Combinational Logic Circuits" (PDF). Transactions of the American Institute of Electrical Engineers part I 72 (9): 593–599. doi:10.1109/TCE.1953.6371932. Paper 53-217. Arquivado dende o orixinal (PDF) o 16 de abril de 2017. Consultado o 2017-04-16. 
  2. Curtis, H. Allen (1962). A new approach to the design of switching circuits. Bell Laboratories Series. Princeton, New Jersey, USA: D. van Nostrand Company, Inc. 
  3. Veitch, Edward W. (1952-05-03) [1952-05-02]. "A Chart Method for Simplifying Truth Functions". ACM Annual Conference/Annual Meeting: Proceedings of the 1952 ACM Annual Meeting (Pittsburg) (New York, USA: ACM): 127–133. doi:10.1145/609784.609801. 
  4. 4,0 4,1 4,2 4,3 Brown, Frank Markham (2012) [2003, 1990]. Boolean Reasoning - The Logic of Boolean Equations (2nd ed.). Mineola, New York: Dover Publications, Inc. ISBN 978-0-486-42785-0. 
  5. Marquand, Allan (1881). "XXXIII: On Logical Diagrams for n terms". The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science. 5 12 (75): 266–270. doi:10.1080/14786448108627104. Consultado o 2017-05-15. 
  6. Wakerly, John F. (1994). Digital Design: Principles & Practices. New Jersey, USA: Prentice Hall. pp. 222, 48–49. ISBN 0-13-211459-3. 
  7. Belton, David (1998). "Karnaugh Maps – Rules of Simplification". Arquivado dende o orixinal o 18 de abril de 2017. Consultado o 2009-05-30. 
  8. Dodge, Nathan B. (2015). "Simplifying Logic Circuits with Karnaugh Maps" (PDF). The University of Texas at Dallas, Erik Jonsson School of Engineering and Computer Science. Arquivado dende o orixinal (PDF) o 18 de abril de 2017. Consultado o 2017-04-18. 
  9. Cook, Aaron. "Using Karnaugh Maps to Simplify Code". Quantum Rarity. Arquivado dende o orixinal o 18 de abril de 2017. Consultado o 2012-10-07. 

Véxase tamén

editar

Outros artigos

editar

 
 Este artigo sobre matemáticas é, polo de agora, só un bosquexo. Traballa nel para axudar a contribuír a que a Galipedia mellore e medre.
 Existen igualmente outros artigos relacionados con este tema nos que tamén podes contribuír.