Función booleana

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

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.

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

• Modelo:Cita libro
• Modelo:Springer
• Modelo:Cita revista
• Modelo:Cita libro
• Modelo:Cita libro

Outros artigos

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

Ligazóns externas

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