lei de Peirce

Da Wikipédia, a enciclopédia livre
Ir para a navegação Saltar para pesquisar

Na lógica , a lei de Peirce é nomeada em homenagem ao filósofo e lógico Charles Sanders Peirce . Foi tomado como axioma em sua primeira axiomatização da lógica proposicional . Ela pode ser pensada como a lei do terceiro excluído escrita de uma forma que envolve apenas um tipo de conectivo, a saber, a implicação.

No cálculo proposicional , a lei de Peirce diz que (( PQ )→ P )→ P . Escrito, isso significa que P deve ser verdadeiro se houver uma proposição Q tal que a verdade de P decorre da verdade de "se P , então Q ". Em particular, quando Q é considerado uma fórmula falsa, a lei diz que se P deve ser verdadeiro sempre que implica falsidade, então P é verdadeiro. Desta forma, a lei de Peirce implica a lei do terceiro excluído .

A lei de Peirce não se sustenta na lógica intuicionista ou na lógica intermediária e não pode ser deduzida apenas do teorema da dedução .

Sob o isomorfismo de Curry-Howard , a lei de Peirce é o tipo de operadores de continuação , por exemplo call/cc em Scheme . [1]

História

Aqui está a própria declaração da lei de Peirce:

Um quinto ícone é necessário para o princípio do meio excluído e outras proposições relacionadas a ele. Uma das fórmulas mais simples desse tipo é:
{( xy ) → x } → x .
Isso dificilmente é axiomático. Que é verdade aparece como se segue. Ela só pode ser falsa se o consequente final x for falso enquanto seu antecedente ( xy ) → x for verdadeiro. Se isso for verdadeiro, ou seu consequente, x , é verdadeiro, quando toda a fórmula seria verdadeira, ou seu antecedente xy é falso. Mas no último caso o antecedente de xy , que é x , deve ser verdadeiro. (Peirce, os Collected Papers 3.384).

Peirce prossegue apontando uma aplicação imediata da lei:

Da fórmula que acabamos de dar, obtemos imediatamente:
{( xy ) → a } → x ,
onde o a é usado de tal forma que ( xy ) → a significa que de ( xy ) toda proposição segue. Com esse entendimento, a fórmula enuncia o princípio do terceiro excluído, que da falsidade da negação de x segue a verdade de x . (Peirce, os Collected Papers 3.384).

Atenção : (( xy )→ a )→ x não é uma tautologia . No entanto, [ ax ]→[(( xy )→ a )→ x ] é uma tautologia.

Outras provas

Aqui está uma prova simples da lei de Peirce assumindo dupla negaçãoe derivando a disjunção padrão de uma implicação:

Usando a lei de Peirce com o teorema da dedução

A lei de Peirce permite aprimorar a técnica de usar o teorema da dedução para provar teoremas. Suponha que alguém receba um conjunto de premissas Γ e queira deduzir uma proposição Z a partir delas. Com a lei de Peirce, pode-se adicionar (sem custo) premissas adicionais da forma ZP a Γ. Por exemplo, suponha que recebemos PZ e ( PQ )→ Z e desejamos deduzir Z para que possamos usar o teorema da dedução para concluir que ( PZ )→((( PQ )→ Z )→ Z) é um teorema. Então podemos adicionar outra premissa ZQ . A partir disso e PZ , obtemos PQ . Então aplicamos modus ponens com ( PQ )→ Z como premissa maior para obter Z. Aplicando o teorema da dedução, obtemos que ( ZQ )→ Z segue das premissas originais. Então usamos a lei de Peirce na forma (( ZQ )→ Z )→ Z e modus ponens para derivar Zdas instalações originais. Então podemos terminar provando o teorema como originalmente pretendíamos.

  • PZ
1. hipótese
    • ( PQ ) → Z
2. hipótese
      • ZQ
3. hipótese
        • P
4. hipótese
        • Z
5. modus ponens usando as etapas 4 e 1
        • Q
6. modus ponens usando as etapas 5 e 3
      • PQ
7. dedução de 4 a 6
      • Z
8. modus ponens usando as etapas 7 e 2
    • ( ZQ ) → Z
9. dedução de 3 a 8
    • (( ZQ )→ Z )→ Z
10. Lei de Peirce
    • Z
11. modus ponens usando as etapas 9 e 10
  • (( PQ )→ Z )→ Z
12. dedução de 2 a 11

( PZ )→((( PQ )→ Z )→ Z )

13. dedução de 1 a 12 QED

Completude do cálculo proposicional implicacional

Uma razão pela qual a lei de Peirce é importante é que ela pode substituir a lei do terceiro excluído na lógica que usa apenas implicação. As sentenças que podem ser deduzidas dos esquemas de axiomas:

  • P →( QP )
  • ( P →( QR ))→(( PQ )→( PR ))
  • (( PQ )→ P )→ P
  • de P e PQ inferir Q

(onde P , Q , R contêm apenas "→" como conectivo) são todas as tautologias que usam apenas "→" como conectivo.


Falha em modelos não clássicos de lógica intuicionista

Como a lei de Pierce implica a lei do terceiro excluído, ela sempre deve falhar em lógicas intuicionistas não clássicas. Um contra-exemplo explícito simples é o de Gödel muitas lógicas de valor , que são uma lógica difusa onde os valores de verdade são números reais entre 0 e 1, com implicação material definida por:

e onde a lei de Pierce como uma fórmula pode ser simplificada para:

onde ser sempre verdadeiro seria equivalente à afirmação de que u > v implica u = 1, o que é verdadeiro somente se 0 e 1 forem os únicos valores permitidos. Ao mesmo tempo, no entanto, a expressão nunca pode ser igual ao valor de verdade inferior da lógica e sua dupla negação é sempre verdadeira.

Veja também

Notas

  1. Timothy G. Griffin, A Formulae-as-Types Notion of Control, 1990 - Griffin define K na página 3 como um equivalente ao call/cc de Scheme e então discute seu tipo sendo o equivalente da lei de Peirce no final da seção 5 sobre página 9.

Leitura adicional

  • Peirce, CS, "Sobre a Álgebra da Lógica: Uma Contribuição para a Filosofia da Notação", American Journal of Mathematics 7, 180–202 (1885). Reimpresso, os Documentos Coletados de Charles Sanders Peirce 3.359–403 e os Escritos de Charles S. Peirce: Uma Edição Cronológica 5, 162–190.
  • Peirce, CS, Collected Papers of Charles Sanders Peirce , Vols. 1–6, Charles Hartshorne e Paul Weiss (eds.), Vols. 7–8, Arthur W. Burks (ed.), Harvard University Press, Cambridge, MA, 1931–1935, 1958.