Completude funcional

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página ou secção não cita nenhuma fonte ou referência, o que compromete sua credibilidade (desde Outubro de 2012).
Por favor, melhore este artigo providenciando fontes fiáveis e independentes, inserindo-as no corpo do texto por meio de notas de rodapé. Encontre fontes: Googlenotícias, livros, acadêmicoScirusBing. Veja como referenciar e citar as fontes.

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

Na lógica, um grupo de conectivos tem a propriedade da completude funcional se todos outros conectivos possíveis podem ser definidos em função dele.

A maioria das lógicas encontradas nos livros modernos tomam como conectivos primitivos: a conjunção (\land), disjunção (\lor), negação(\lnot), implicação(\to) e a bi-implicação (\leftrightarrow). Esse conjunto de conectivos goza da propriedade de completude funcional. Porém, esse não é um conjunto mínimo, já que a implicação e bi-implicação podem ser definidos como:

A \to B := \neg A \lor B
A \leftrightarrow B := (A \to B) \land (B \to A)

Já a disjunção, por sua vez, pode ser definida utilizando a conjunção:

A \lor B := \neg(\neg A \land \neg B)

A conjunção pode ser expressa em termos da disjunção de modo semelhante:

A \land B:= \neg(\neg A \lor \neg B)

Já os conectivos binários NOR e NAND sozinhos, possuem a propriedade da completude funcional, e são chamados Anfeque.

Conjuntos mínimos funcionalmente completos[editar | editar código-fonte]

Todos os conjuntos abaixo possuem a propriedade completude funcional:

{  }, {  }, { \rightarrow\neg }, { \rightarrow\not\equiv }, { \neg }, { \rightarrow }, { \vee\neg }, { \rightarrow }, { \neg }, { \not\equiv }, { \neg }, {  }, { \wedge\neg }, {  }, { \bot\rightarrow }, { \equiv }, { \equiv }

Demonstração da completude funcional em um conjunto[editar | editar código-fonte]

Utilizando apenas a negação (\lnot) e a implicação (\rightarrow) podemos gerar todas as outras operações.

Disjunção:

A \lor B \equiv \lnot A \rightarrow B

Conjunção:

A \land B \equiv \lnot (A \rightarrow \lnot B)

Bi-implicação:

A \leftrightarrow B \equiv \lnot ((A \rightarrow B) \rightarrow \lnot (B \rightarrow A))

Conjunto funcionalmente incompleto[editar | editar código-fonte]

Seja um conjunto que engloba a conjunção, disjunção, implicação e a bi-implicação. Tentemos fazer a negação:

A \land A \equiv A

A \lor A \equiv A

A \rightarrow A \equiv T

A \leftrightarrow A \equiv A

Com isso não conseguimos a partir de um valor lógico "1" gerar um "0", e com isso a negação não teria como ser implementada utilizando essas portas lógicas. Conclui-se que esse conjunto seria funcionalmente incompleto.

Ver também[editar | editar código-fonte]