Completude funcional

Dado o domínio Booleano B = {0,1}, um conjunto F de funções booleanas ƒi: Bni ? B é funcionalmente completa- se o clone algébrico em B gerado pelas funções básicas ƒi contém todas funções ƒ: Bn ? 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 ƒ: Bn ? 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.

Textos recentes sobre lógica tomam como primitivo algum subconjunto de conectivos : conjução ( ∧ {\displaystyle \land } ); disjunção ( ∨ {\displaystyle \lor } ) ; negação ( ¬ {\displaystyle \neg } ); implicação ( → {\displaystyle \to } ); e bi implicação ( ↔ {\displaystyle \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 : Então { ¬ , ∧ , ∨ } {\displaystyle \{\neg ,\land ,\lor \}} também é funcionamente completo. Mas então, ∨ {\displaystyle \lor } pode ser definido como: ∧ {\displaystyle \land } também pode ser definido em termos de ∨ {\displaystyle \lor } de uma maneira semelhante.

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:

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: Não há conjuntos mínimos funcionalmente completos de mais de três conectivos lógicos binários.

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 {¬, ∪}.