Función booleana

En matemáticas, unha función booleana é unha función cuxos argumentos e resultado asumen valores dun conxunto de dous elementos (normalmente {verdadeiro, falso}, {V, F}, {V,T], {0,1} ou {-1,1}). Os nomes alternativos son función de verdade (ou función lóxica), usado na lóxica. As funcións booleanas son obxecto da álxebra de Boole, usada na informática e nas portas lóxicas.

Un diagrama de decisión binario e unha táboa de verdade dunha función booleana ternaria

Unha función booleana toma a forma $f:\{0,1\}^{k}\to \{0,1\}$, onde $\{0,1\}$ coñécese como dominio booleano e $k$ é un enteiro non negativo chamado aridade da función. No caso de $k=0$, a función é un elemento constante de $\{0,1\}$. Unha función booleana con múltiples saídas, $f:\{0,1\}^{k}\to \{0,1\}^{m}$ con $m>1$ é unha función booleana vectorial.

Cada función booleana de dimensión $k$ pode expresarse como unha fórmula proposicional en $k$ variábeis $x_{1},...,x_{k}$, e dúas fórmulas proposicionais son loxicamente equivalentes se e só se expresan a mesma función booleana.

Exemplos

As funcións booleanas simétricas rudimentarias (conectivas lóxicas ou portas lóxicas) son:

• NOT, negación ou complemento: recibe unha entrada e devolve verdadeiro cando esa entrada é falsa ("non").
• AND ou conxunción: verdadeiro cando todas as entradas son verdadeiras ("ambas").
• OU ou disxunción: verdadeiro cando calquera entrada é verdadeira ("algunha delas ou ambas as dúas")
• XOR ou disxunción exclusiva: verdadeiro cando unha das súas entradas é verdadeira e a outra é falsa ("só algunha delas")
• Barra de Sheffer ou NAND: verdadeiro cando non é o caso de que todas as entradas sexan verdadeiras ("non ambas as dúas")
• NOR ou non ou lóxico : verdadeiro cando ningunha das entradas é verdadeira ("ningunha das dúas")
• XNOR ou igualdade lóxica: verdadeiro cando as dúas entradas son iguais ("iguais")

Representación

Unha función booleana representada como un circuíto booleano

Unha función booleana pódese especificar de varias maneiras:

• Táboa de verdade: lista explícitamente o seu valor para todos os posíbeis valores dos argumentos
  • Diagrama de Marquand: valores da táboa de verdade dispostos nunha cuadrícula bidimensional (usado nun mapa de Karnaugh)
  • Diagrama de decisión binario, que enumera os valores da táboa de verdade na parte inferior dunha árbore binaria
  • Diagrama de Venn, que representa os valores da táboa de verdade como unha cor das rexións do plano

Alxebricamente, como fórmula proposicional usando funcións booleanas rudimentarias:

• Forma normal de negación, unha mestura arbitraria de AND e OR dos argumentos e dos seus complementos
• Forma normal disxuntiva, como OU de ANDs dos argumentos e dos seus complementos
• Forma normal conxuntiva, como AND de ORs dos argumentos e os seus complementos
• Forma normal canónica, unha fórmula estandarizada que identifica de forma única a función:
  • Forma normal alxébrica ou polinomio de Zhegalkin, como XOR de ANDs dos argumentos (non se admiten complementos)
  • Forma normal disxuntiva completa (canónica), un OU de ANDs que contén cada argumento ou complemento (mintermos)
  • Forma normal conxuntiva completa (canónica), un AND de ORs que contén cada argumento ou complemento (maxtermos)
  • Forma canónica de Blake, o OR de todos os implicantes primos da función

As fórmulas booleanas tamén se poden mostrar como un Grafo.

Véxase tamén

Bibliografía

• Crama, Yves; Hammer, Peter L. (2011). Boolean Functions: Theory, Algorithms, and Applications. Cambridge University Press. ISBN 9780511852008. doi:10.1017/CBO9780511852008. 
• "Boolean function". Encyclopedia of Mathematics. EMS Press. 2001 [1994]. 
• Janković, Dragan; Stanković, Radomir S.; Moraga, Claudio (November 2003). "Arithmetic expressions optimisation using dual polarity property". Serbian Journal of Electrical Engineering 1 (71-80, number 1): 71–80. doi:10.2298/SJEE0301071J. 
• Arnold, Bradford Henry (1 January 2011). Logic and Boolean Algebra. Courier Corporation. ISBN 978-0-486-48385-6. 
• Mano, M. M.; Ciletti, M. D. (2013). Digital Design. Pearson. 

Outros artigos

• Táboa de verdad.
• Porta lóxica

Ligazóns externas

• forall x: Calgary An Introduction to Formal Logic. .

---

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.

---