Função verdade - Truth function

Na lógica , uma função de verdade é uma função que aceita valores de verdade como entrada e produz um valor de verdade único como saída. Em outras palavras: a entrada e a saída de uma função de verdade são todos valores de verdade; uma função de verdade sempre produzirá exatamente um valor de verdade; e inserir o (s) mesmo (s) valor (is) verdade (s) sempre produzirá o mesmo valor verdade. O exemplo típico está na lógica proposicional , em que uma declaração composta é construída usando declarações individuais conectadas por conectivos lógicos ; se o valor verdade da declaração composta for inteiramente determinado pelo (s) valor (es) verdade (s) da (s) declaração (ões) constituinte (s), a declaração composta é chamada de função verdade e quaisquer conectivos lógicos usados ​​são considerados funcionais de verdade .

A lógica proposicional clássica é uma lógica funcional de verdade, em que cada declaração tem exatamente um valor de verdade que é verdadeiro ou falso, e todo conectivo lógico é funcional de verdade (com uma tabela de verdade correspondente ), portanto, cada declaração composta é uma função de verdade. Por outro lado, a lógica modal não é funcional de verdade.

Visão geral

Um conectivo lógico é funcional de verdade se o valor de verdade de uma sentença composta é uma função do valor de verdade de suas sub sentenças. Uma classe de conectivos é funcional de verdade se cada um de seus membros o for. Por exemplo, o conectivo " e " é funcional de verdade, pois uma frase como " Maçãs são frutas e cenouras são vegetais " é verdadeira se, e somente se cada uma de suas sub-sentenças " maçãs são frutas " e " cenouras são vegetais " é verdadeiro e, caso contrário, é falso. Alguns conectivos de uma linguagem natural, como o inglês, não são funcionais de verdade.

Os conectivos da forma "x acredita que ..." são exemplos típicos de conectivos que não são funcionais de verdade. Se, por exemplo, Mary erroneamente acredita que Al Gore foi presidente dos EUA em 20 de abril de 2000, mas ela não acredita que a lua é feita de queijo verde, então a sentença

" Mary acredita que Al Gore foi presidente dos EUA em 20 de abril de 2000 "

é verdade enquanto

" Maria acredita que a lua é feita de queijo verde "

é falso. Em ambos os casos, cada sentença componente (ou seja, " Al Gore foi presidente dos EUA em 20 de abril de 2000 " e " a lua é feita de queijo verde ") é falsa, mas cada sentença composta formada pelo prefixo " Mary acredita que "difere em valor de verdade. Ou seja, o valor de verdade de uma sentença da forma " Maria acredita que ... " não é determinado apenas pelo valor de verdade de sua sentença componente e, portanto, o conectivo ( unário) (ou simplesmente operador, uma vez que é unário ) não é funcional de verdade.

A classe de conectivos lógicos clássicos (por exemplo , & , → ) usados ​​na construção de fórmulas é funcional de verdade. Seus valores para vários valores de verdade como argumento são geralmente fornecidos por tabelas de verdade . O cálculo proposicional funcional de verdade é um sistema formal cujas fórmulas podem ser interpretadas como verdadeiras ou falsas.

Tabela de funções de verdade binárias

Na lógica de dois valores, há dezesseis possíveis funções de verdade, também chamadas funções Booleanas , de duas entradas P e Q . Qualquer uma dessas funções corresponde a uma tabela verdade de um certo conectivo lógico na lógica clássica, incluindo vários casos degenerados , como uma função que não depende de um ou de ambos os seus argumentos. Verdade e falsidade são denotadas como 1 e 0, respectivamente, nas seguintes tabelas de verdade por questão de brevidade.

Contradição / Falso Notação Fórmulas Equivalentes Mesa da verdade Diagrama de Venn ${\ displaystyle \ bot}$ "inferior" P ∧ ¬ P O pq   Q 0 1 P 0    0   0  1    0   0	Tautologia / Verdadeiro Notação Fórmulas Equivalentes Mesa da verdade Diagrama de Venn ${\ displaystyle \ top}$ "principal" P ∨ ¬ P V pq   Q 0 1 P 0    1   1  1    1   1
Proposição P Notação Fórmulas Equivalentes Mesa da verdade Diagrama de Venn P p I pq   Q 0 1 P 0    0   0  1    1   1	Negação de P Notação Fórmulas Equivalentes Mesa da verdade Diagrama de Venn ¬ P ~ P N p F pq   Q 0 1 P 0    1   1  1    0   0
Proposição Q Notação Fórmulas Equivalentes Mesa da verdade Diagrama de Venn Q q H pq   Q 0 1 P 0    0   1  1    0   1	Negação de Q Notação Fórmulas Equivalentes Mesa da verdade Diagrama de Venn ¬ Q ~ Q N q G pq   Q 0 1 P 0    1   0  1    1   0
Conjunção Notação Fórmulas Equivalentes Mesa da verdade Diagrama de Venn P ∧ Q P & Q P   ·   Q P  E  Q P ↛¬ Q ¬ P ↚ Q ¬ P ↓ ¬ Q K pq   Q 0 1 P 0    0   0  1    0   1	Negação alternativa Notação Fórmulas Equivalentes Mesa da verdade Diagrama de Venn P ↑ Q P | Q P  NAND  Q P → ¬ Q ¬ P ← Q ¬ P ∨ ¬ Q D pq   Q 0 1 P 0    1   1  1    1   0
Disjunção Notação Fórmulas Equivalentes Mesa da verdade Diagrama de Venn P ∨ Q P  OR  Q P ← ¬ Q ¬ P → Q ¬ P ↑ ¬ Q ¬ (¬ P ∧ ¬ Q ) A pq   Q 0 1 P 0    0   1  1    1   1	Negação conjunta Notação Fórmulas Equivalentes Mesa da verdade Diagrama de Venn P ↓ Q P  NOR  Q P ↚ ¬ Q ¬ P ↛ Q ¬ P ∧ ¬ Q X pq   Q 0 1 P 0    1   0  1    0   0
Não Implicação Material Notação Fórmulas Equivalentes Mesa da verdade Diagrama de Venn P ↛ Q P Q P Q${\ displaystyle \ not \ supset}$ ${\ displaystyle>}$ P ∧ ¬ Q ¬ P ↓ Q ¬ P ↚ ¬ Q L pq   Q 0 1 P 0    0   0  1    1   0	Implicação material Notação Fórmulas Equivalentes Mesa da verdade Diagrama de Venn P → Q P ⊃ Q P Q${\ displaystyle \ leq}$ P ↑ ¬ Q ¬ P ∨ Q ¬ P ← ¬ Q C pq   Q 0 1 P 0    1   1  1    0   1
Converse nonimplication Notação Fórmulas Equivalentes Mesa da verdade Diagrama de Venn P ↚ Q P Q P Q${\ displaystyle \ not \ subset}$ ${\ displaystyle <}$ P ↓ ¬ Q ¬ P ∧ Q ¬ P ↛ ¬ Q M pq   Q 0 1 P 0    0   1  1    0   0	Implicação inversa Notação Fórmulas Equivalentes Mesa da verdade Diagrama de Venn P ← Q P ⊂ Q P Q${\ displaystyle \ geq}$ P ∨ ¬ Q ¬ P ↑ Q ¬ P → ¬ Q B pq   Q 0 1 P 0    1   0  1    1   1
Disjunção exclusiva Notação Fórmulas Equivalentes Mesa da verdade Diagrama de Venn P ↮ Q P ≢ Q P ⨁ Q P  XOR  Q P ¬ Q ¬ P Q ¬ P ↮ ¬ Q J pq${\ displaystyle \ leftrightarrow}$ ${\ displaystyle \ leftrightarrow}$   Q 0 1 P 0    0   1  1    1   0	Bicondicional Notação Fórmulas Equivalentes Mesa da verdade Diagrama de Venn P Q P ≡ Q P  XNOR  Q P  IFF  Q${\ displaystyle \ leftrightarrow}$ P ↮ ¬ Q ¬ P ↮ Q ¬ P ¬ Q E pq${\ displaystyle \ leftrightarrow}$   Q 0 1 P 0    1   0  1    0   1

Completude funcional

Como uma função pode ser expressa como uma composição , um cálculo lógico funcional de verdade não precisa ter símbolos dedicados para que todas as funções mencionadas acima sejam funcionalmente completas . Isso é expresso em um cálculo proposicional como equivalência lógica de certas declarações compostas. Por exemplo, a lógica clássica tem ¬ P  ∨  Q equivalente a P  →  Q . O operador condicional "→", portanto, não é necessário para um sistema lógico baseado em clássico se "¬" (não) e "∨" (ou) já estiverem em uso.

Um conjunto mínimo de operadores que podem expressar cada afirmação expressável no cálculo proposicional é chamado de conjunto mínimo funcionalmente completo . Um conjunto minimamente completo de operadores é alcançado apenas por NAND {↑} e apenas por NOR {↓}.

A seguir estão os conjuntos mínimos funcionalmente completos de operadores cujas aridades não excedam 2:

Um elemento

{↑}, {↓}.

Dois elementos

${\ displaystyle \ {\ vee, \ neg \}}$ , , , , , , , , , , , , , , , , , . ${\ displaystyle \ {\ wedge, \ neg \}}$${\ displaystyle \ {\ to, \ neg \}}$${\ displaystyle \ {\ gets, \ neg \}}$${\ displaystyle \ {\ to, \ bot \}}$${\ displaystyle \ {\ gets, \ bot \}}$${\ displaystyle \ {\ to, \ nleftrightarrow \}}$${\ displaystyle \ {\ gets, \ nleftrightarrow \}}$${\ displaystyle \ {\ to, \ nrightarrow \}}$${\ displaystyle \ {\ to, \ nleftarrow \}}$${\ displaystyle \ {\ gets, \ nrightarrow \}}$${\ displaystyle \ {\ gets, \ nleftarrow \}}$${\ displaystyle \ {\ nrightarrow, \ neg \}}$${\ displaystyle \ {\ nleftarrow, \ neg \}}$${\ displaystyle \ {\ nrightarrow, \ top \}}$${\ displaystyle \ {\ nleftarrow, \ top \}}$${\ displaystyle \ {\ nrightarrow, \ leftrightarrow \}}$${\ displaystyle \ {\ nleftarrow, \ leftrightarrow \}}$

Três elementos

${\ displaystyle \ {\ lor, \ leftrightarrow, \ bot \}}$ , , , , , . ${\ displaystyle \ {\ lor, \ leftrightarrow, \ nleftrightarrow \}}$${\ displaystyle \ {\ lor, \ nleftrightarrow, \ top \}}$${\ displaystyle \ {\ land, \ leftrightarrow, \ bot \}}$${\ displaystyle \ {\ land, \ leftrightarrow, \ nleftrightarrow \}}$${\ displaystyle \ {\ land, \ nleftrightarrow, \ top \}}$

Propriedades algébricas

Algumas funções de verdade possuem propriedades que podem ser expressas nos teoremas que contêm o conectivo correspondente. Algumas dessas propriedades que uma função de verdade binária (ou um conectivo lógico correspondente) pode ter são:

• associatividade : dentro de uma expressão contendo dois ou mais dos mesmos conectivos associativos em uma linha, a ordem das operações não importa, desde que a sequência dos operandos não seja alterada.
• comutatividade : os operandos do conectivo podem ser trocados sem afetar o valor de verdade da expressão.
• distributividade : Um conectivo denotado por · distribui sobre outro conectivo denotado por +, se a · ( b + c ) = ( a · b ) + ( a · c ) para todos os operandos a , b , c .
• idempotência : Sempre que os operandos da operação são iguais, o conectivo dá o operando como resultado. Em outras palavras, a operação preserva a verdade e a falsidade (veja abaixo).
• absorção : Um par de conectivos satisfaz a lei de absorção se para todos os operandos a , b . ${\ displaystyle \ land, \ lor}$${\ displaystyle a \ land (a \ lor b) = a}$

Um conjunto de funções de verdade é funcionalmente completo se, e somente se, para cada uma das cinco propriedades a seguir, ele contém pelo menos um membro sem ele:

• monotônico : Se f ( a ₁ , ..., a _n ) ≤ f ( b ₁ , ..., b _n ) para todo a ₁ , ..., a _n , b ₁ , ..., b _n ∈ {0,1} tal que a ₁ ≤ b ₁ , a ₂ ≤ b ₂ , ..., a _n ≤ b _n . Por exemplo, . ${\ displaystyle \ vee, \ wedge, \ top, \ bot}$
• afim : para cada variável, alterar seu valor sempre ou nunca altera o valor de verdade da operação, para todos os valores fixos de todas as outras variáveis. Por exemplo, , . ${\ displaystyle \ neg, \ leftrightarrow}$${\ displaystyle \ not \ leftrightarrow, \ top, \ bot}$
• self dual : Ler as atribuições de valores de verdade para a operação de cima para baixo em sua tabela de verdade é o mesmo que pegar o complemento de lê-las de baixo para cima; em outras palavras, f (¬ a ₁ , ..., ¬ a _n ) = ¬ f ( a ₁ , ..., a _n ). Por exemplo, . ${\ displaystyle \ neg}$
• preservação da verdade : A interpretação sob a qual todas as variáveis ​​são atribuídas a um valor de verdade de 'verdadeiro' produz um valor de verdade de 'verdadeiro' como resultado dessas operações. Por exemplo, . (ver validade ) ${\ displaystyle \ vee, \ wedge, \ top, \ rightarrow, \ leftrightarrow, \ subset}$
• preservação da falsidade : A interpretação sob a qual todas as variáveis ​​recebem um valor verdade de 'falso' produz um valor de verdade de 'falso' como resultado dessas operações. Por exemplo, . (ver validade ) ${\ displaystyle \ vee, \ wedge, \ nleftrightarrow, \ bot, \ not \ subset, \ not \ supset}$

Arity

Uma função concreta também pode ser chamada de operador . Na lógica de dois valores existem 2 operadores nullary (constantes), 4 operadores unárias , 16 operadores binários , 256 operadores ternários , e n operadores -ary. Na lógica de três valores existem 3 operadores nullary (constantes), 27 operadores unárias , 19683 operadores binários , 7625597484987 operadores ternários , e n operadores -ary. Na lógica de k -valor, existem k operadores nulos, operadores unários, operadores binários, operadores ternários e operadores n -ary. Um operador n -ary na lógica com valor k é uma função de . Portanto, o número de tais operadores é , que é como os números acima foram derivados. ${\ displaystyle 2 ^ {2 ^ {n}}}$ ${\ displaystyle 3 ^ {3 ^ {n}}}$ ${\ displaystyle k ^ {k}}$${\ displaystyle k ^ {k ^ {2}}}$${\ displaystyle k ^ {k ^ {3}}}$${\ displaystyle k ^ {k ^ {n}}}$ ${\ displaystyle \ mathbb {Z} _ {k} ^ {n} \ to \ mathbb {Z} _ {k}}$${\ displaystyle | \ mathbb {Z} _ {k} | ^ {| \ mathbb {Z} _ {k} ^ {n} |} = k ^ {k ^ {n}}}$

No entanto, alguns dos operadores de um arity específico são, na verdade, formas degeneradas que executam uma operação de arity inferior em algumas das entradas e ignora o resto das entradas. Dos 256 operadores booleanos ternários citados acima, eles são formas degeneradas de operadores binários ou de aridade inferior, usando o princípio de inclusão-exclusão . O operador ternário é um desses operadores que, na verdade, é um operador unário aplicado a uma entrada e que ignora as outras duas entradas. ${\ displaystyle {\ binom {3} {2}} \ cdot 16 - {\ binom {3} {1}} \ cdot 4 + {\ binom {3} {0}} \ cdot 2}$${\ displaystyle f (x, y, z) = \ lnot x}$

"Não" é um operador unário , leva um único termo (¬ P ). Os demais são operadores binários , usando dois termos para fazer uma declaração composta ( P ∧ Q , P ∨ Q , P → Q , P ↔ Q ).

O conjunto de operadores lógicos Ω pode ser particionado em subconjuntos separados da seguinte forma:

${\ displaystyle \ Omega = \ Omega _ {0} \ cup \ Omega _ {1} \ cup \ ldots \ cup \ Omega _ {j} \ cup \ ldots \ cup \ Omega _ {m} \ ,.}$

Nesta partição, é o conjunto de símbolos de operador de aridade j . ${\ displaystyle \ Omega _ {j}}$

Nos cálculos proposicionais mais familiares, é normalmente dividido da seguinte forma: ${\ displaystyle \ Omega}$

operadores nulos: ${\ displaystyle \ Omega _ {0} = \ {\ bot, \ top \}}$

operadores unários: ${\ displaystyle \ Omega _ {1} = \ {\ lnot \}}$

operadores binários: ${\ displaystyle \ Omega _ {2} \ subseteq \ {\ land, \ lor, \ rightarrow, \ leftrightarrow \}}$

Princípio da composicionalidade

Em vez de usar tabelas de verdade , os símbolos conectivos lógicos podem ser interpretados por meio de uma função de interpretação e um conjunto funcionalmente completo de funções de verdade (Gamut 1991), conforme detalhado pelo princípio da composicionalidade do significado. Seja I uma função de interpretação, seja Φ , Ψ quaisquer duas sentenças e seja a função de verdade f n _e definida como:

• f _ne (T, T) = F; f _nand (T, F) = f _nand (F, T) = f _nand (F, F) = T

Então, por conveniência, f _não , f _ou f _e e assim por diante são definidos por meio de f _NAND :

• f _not ( x ) = f _nand ( x , x )
• f _ou ( x , y ) = f _nand ( f _not ( x ), f _not ( y ))
• f _e ( x , y ) = f _não ( f _nand ( x , y ))

ou, alternativamente, f _não , f _ou f _e e assim por diante são definidos directamente:

• f _não (T) = F; f _não (F) = T;
• f _ou (T, T) = f _ou (T, F) = f _ou (F, T) = T; f _ou (F, F) = F
• f _e (T, T) = T; f _e (T, F) = f _e (F, T) = f _e (F, F) = F

Então

etc.

Assim, se S é uma frase que é uma sequência de símbolos consistindo em símbolos lógicos v ₁ ... v _n representando conectivos lógicos e símbolos não lógicos c ₁ ... c _n , então se e somente se I ( v ₁ ) ... I ( v _n ) foram fornecidos interpretando v ₁ a v _n por meio de f _nand (ou qualquer outro conjunto de funções de verdade completas funcionais), então o valor de verdade de é determinado inteiramente pelos valores de verdade de c ₁ ... c _n , ou seja, de I ( c ₁ ) ... I ( c _n ) . Em outras palavras, conforme esperado e exigido, S é verdadeiro ou falso apenas sob uma interpretação de todos os seus símbolos não lógicos. ${\ displaystyle I (s)}$

Ciência da Computação

Os operadores lógicos são implementados como portas lógicas em circuitos digitais . Praticamente todos os circuitos digitais (a principal exceção é a DRAM ) são construídos a partir de NAND , NOR , NOT e portas de transmissão . As portas NAND e NOR com 3 ou mais entradas em vez das 2 entradas usuais são bastante comuns, embora sejam logicamente equivalentes a uma cascata de portas de 2 entradas. Todos os outros operadores são implementados dividindo-os em uma combinação logicamente equivalente de 2 ou mais das portas lógicas acima.

A "equivalência lógica" de "apenas NAND", "apenas NOR" e "NÃO e E" é semelhante à equivalência de Turing .

O fato de que todas as funções de verdade podem ser expressas apenas com NOR é demonstrado pelo computador de orientação Apollo .

Veja também

Notas

Referências

• Este artigo incorpora material de TruthFunction no PlanetMath , que é licenciado sob a licença Creative Commons Atribuição / Compartilhamento pela mesma Licença .

Leitura adicional

• Józef Maria Bocheński (1959), A Précis of Mathematical Logic , traduzido das versões francesa e alemã por Otto Bird, Dordrecht, South Holland: D. Reidel.
• Alonzo Church (1944), Introdução à Lógica Matemática , Princeton, NJ: Princeton University Press. Consulte a introdução para obter uma história do conceito de função de verdade.