# Completude funcional

Em lógica, um grupo de conectivos ou operadores Booleanos tem a propriedade da completude funcional se todos outros conectivos possíveis podem ser definidos em função dele.
Do ponto de vista da eletrônica digital, completude funcional significa que cada porta lógica possível pode ser tratada como uma rede de portas dos tipos prescritos pelo conjunto. Em particular, todas as portas lógicas podem ser montadas a partir de apenas NANDs e NOR.

## Definição Formal

Dado o domínio Booleano B = {0,1}, um conjunto F de funções booleanas ƒ$_i$: B$^{ni}$ ? B é funcionalmente completa- se o clone algébrico em B gerado pelas funções básicas ƒ$_i$ contém todas funções ƒ: B$^n$ ? B, para todos inteiros positivos {{{1}}}. Em outras palavras , o conjunto é funcionalmente completo se cada função booleana que leva pelo menos uma variável pode ser expressa em termos das funções ƒ $_i$ . Uma vez que cada função booleana de pelo menos uma variável pode ser expressa em termos de funções booleanas binárias , F é funcionalmente completo se somente se cada função booleana binária pode ser expressa em termos das funções de F.
Uma condição mais natural seria que o clone gerado por F consistem de todas as funções ƒ: B$^n$ ? B, para todos os inteiros {{{1}}}. Porém, os exemplos dados acima não são funcionalmente completos na forma mais forte porque não é possível escrever uma função nulária, ou seja, uma expressão constante, em termos de F se o próprio F não contêm pelo menos uma função nulária.
Outra condição natural seria se o clone algébrico gerado por F juntamente com as duas funções constantes nulárias ser funcionalmente completo ou. O exemplo da função booleana dada por S(x, y, z) = z se x = y e S(x, y, z) = x entretanto mostra que esta condição é estritamente mais fraca do que completude funcional .

## Definição Informal

Textos recentes sobre lógica tomam como primitivo algum subconjunto de conectivos: conjução ($\land$); disjunção ($\lor$) ; negação ($\neg$); implicação ($\to$); e bi implicação ($\leftrightarrow$). Esses conectivos são funcionalmente completos. No entanto , eles não formam um conjunto mínimo funcionalmente completo, já que a implicação e bi implicação podem ser definidas como :
    ${\begin{aligned}A\to B&:=\neg A\lor B\\A\leftrightarrow B&:=(A\to B)\land (B\to A).\end{aligned}}$
Então $\{\neg ,\land ,\lor \}$ também é funcionamente completo. Mas então, $\lor$ pode ser definido como:
    $A\lor B:=\neg (\neg A\land \neg B).$
$\land$ também pode ser definido em termos de $\lor$ de uma maneira semelhante.

## Caracterização da Completude Funcional

Emil Post provou que um conjunto de conectivos lógicos é funcionalmente completo se somente se for um subconjunto de qualquer um dos seguintes conjuntos de conectivos:
* Os conectivos monoatômicos; mudar a valoração verdade de qualquer variável ligada de F para T sem mudar de T para F nunca fará com que esses conectivos mudem seus valores de retorno de T para F. $\vee$, $\wedge$, $\top$, $\bot$.
* Os conectivos afins, de modo que cada variável conectada sempre ou nunca afeta o valor verdade de retorno desses conectivos$\neg$, $\top$, $\bot$, $\leftrightarrow$, $\not \leftrightarrow$.
* Os conectivos de preservação da verdade; eles retornam a valoração verdade de T sob qualquer interpretação que atribui T para todas as variáveis. $\vee$, $\wedge$, $\top$, $\rightarrow$, $\leftrightarrow$.
* Os conectivos de preservação da falsidade; eles retornam a valoração verdade de F sob qualquer interpretação que atribui F para todas as variáveis. $\vee$, $\wedge$, $\bot$, $\not \rightarrow$, $\not \leftrightarrow$.

## Conjunto Mínimo de Operadores Funcionalmente Completos

Quando um único conectivo lógico ou operador booleano é funcionalmente completo por si só, ela é chamada de função de Sheffer. Não há operadores unários com esta propriedade, e as únicas funções de Sheffer binárias - NAND e NOR são duais. Estas foram descobertas, mas não publicadas por Charles Sanders Peirce por volta de 1880, e redescobertas independentemente e publicadas por Henry M. Sheffer em 1913.
A seguir estão os conjuntos mínimos funcionalmente completos de conectivos lógicos com aridade 2:

### Um Elemento

    {NAND}, {NOR}.

### Dois Elementos

    {$\vee$, ¬}, {$\wedge$, ¬}, {?, ¬}, {?, ¬}, {?, $\bot$}, {?, $\bot$}, {?, $\not \leftrightarrow$}, {?, $\not \leftrightarrow$}, {?, $\not \to$}, {?, $\not \leftarrow$}, {?, $\not \to$}, {?, $\not \leftarrow$}, {$\not \to$, ¬}, {$\not \leftarrow$, ¬}, {$\not \to$, $\top$}, {$\not \leftarrow$, $\top$}, {$\not \to$, $\leftrightarrow$}, {$\not \leftarrow$, $\leftrightarrow$}.

### Três Elementos

    {$\lor$, $\leftrightarrow$, $\bot$}, {$\lor$, $\leftrightarrow$, $\not \leftrightarrow$}, {$\lor$, $\not \leftrightarrow$, $\top$}, {$\land$, $\leftrightarrow$, $\bot$}, {$\land$, $\leftrightarrow$, $\not \leftrightarrow$}, {$\land$, $\not \leftrightarrow$, $\top$}.
Não há conjuntos mínimos funcionalmente completos de mais de três conectivos lógicos binários.

## Exemplos

* Exemplo do uso da completude do NAND.
** ¬A = A NAND A
** A ∧ B = ¬(A NAND B) = (A NAND B) NAND (A NAND B)
** A ∨ B = (A NAND A) NAND (B NAND B)
* Exemplo do uso da completude do NOR.
** ¬A = A NOR A
** A ∧ B = (A NOR A) NOR (B NOR B)
** A ∨ B = (A NOR B) NOR (A NOR B)

## Teoria dos Conjuntos

Há um isomorfismo entre a álgebra de conjuntos e a álgebra booleana, ou seja, eles tem a mesma estrutura. Os mais populares "Conjuntos Mínimo de Operadores Funcionalmente Completos" são {¬, ∩} and {¬, ∪}.

## Veja também

* Álgebra de Conjuntos
* Álgebra Booleana