Completude funcional

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em lógica, um grupo de conectivos ou operadores Booleanos [1] 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. [2] [3] [4] [5]

Definição Formal[editar | editar código-fonte]

Dado o domínio Booleano B = {0,1}, um conjunto F de funções booleanas ƒiBni ? 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 compleo 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.

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(xyz) = z se x = y e S(xyz) = x entretanto mostra que esta condição é estritamente mais fraca do que completude funcional .


Definição Informal[editar | editar código-fonte]

Textos recentes sobre lógica tomam como primitivo algum subconjunto de conectivos [6] : 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{align}
  A \to B &:= \neg A \lor B\\
  A \leftrightarrow B &:= (A \to B) \land (B \to A).
\end{align}

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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: [7]


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[editar | editar código-fonte]

  • Exemplo do uso da completude do NAND. [8]
    • ¬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. [9]
    • ¬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[editar | editar código-fonte]

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[editar | editar código-fonte]

Referências[editar | editar código-fonte]

  1. Nolt, John; Rohatyn, Dennis; Varzi, Achille (1998), Schaum's outline of theory and problems of logic (2nd ed.), New York: McGraw–Hill, ISBN 978-0-07-046649-4 . ("[F]unctional completeness of [a] set of logical operators").
  2. Smith, Peter (2003), An introduction to formal logic, Cambridge University Press, ISBN 978-0-521-00804-4 . (Defines "expressively adequate", shortened to "adequate set of connectives" in a section heading.)
  3. Wesselkamper, T.C. (1975), "A sole sufficient operator", Notre Dame Journal of Formal Logic 16: 86–88, doi:10.1305/ndjfl/1093891614, http://projecteuclid.org/euclid.ndjfl/1093891614 
  4. Massey, G.J. (1975), "Concerning an alleged Sheffer function", Notre Dame Journal of Formal Logic 16 (4): 549–550, doi:10.1305/ndjfl/1093891898, http://projecteuclid.org/euclid.ndjfl/1093891898 
  5. Wesselkamper, T.C. (1975), "A Correction To My Paper" A. Sole Sufficient Operator", Notre Dame Journal of Formal Logic 16 (4): 551, doi:10.1305/ndjfl/1093891899, http://projecteuclid.org/euclid.ndjfl/1093891899 
  6. The term was originally restricted to binary operations, but since the end of the 20th century it is used more generally. Martin, N.M. (1989), Systems of logic, Cambridge University Press, p. 54, ISBN 978-0-521-36770-7 .
  7. Wernick, William (1942) "Complete Sets of Logical Functions," Transactions of the American Mathematical Society 51: 117–32. In his list on the last page of the article, Wernick does not distinguish between ← and →, or between \not\leftarrow and \not\rightarrow.
  8. "NAND Gate Operations" at http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html
  9. "NOR Gate Operations" at http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nor.html