Esta sequência lógica de predicado é válida?

Oct 13 2020

Este é talvez um conjunto bobo de questões relacionadas e o seguinte é o problema que o gerou.

Sou solicitado a provar este sequente lógico de predicado:

$\exists x[R(x) \vee S(x)] \;\;\;\;\; |- \;\;\;\;\exists x R(x) \vee \exists x S(x) $

Tenho vergonha de dizer que não posso provar. Tentei a abordagem direta e também uma abordagem de prova por contradição, sem sorte. E então me ocorreu que talvez a pergunta esteja errada. Talvez não haja provas. Claro, não ser capaz de provar uma sequência não implica que ela seja inválida e, portanto, nem mesmo sei se a pergunta foi formulada incorretamente. Se essa fosse uma questão de lógica proposicional, e a quantidade de átomos proposicionais fosse suficientemente pequena, eu poderia construir uma tabela de verdade e verificar a vinculação semântica. Um sequente proposicional é válido se for semanticamente vinculado e, portanto, uma tabela verdade poderia invalidá-lo. No entanto, com o predicado Logic e seu conjunto de quantificadores, não tenho nenhuma experiência em verificar tabelas de verdade neste caso e, portanto, não posso nem saber se o sequente é inválido.

Usando um argumento inglês, posso invalidá-lo, permitindo $R(x)$ significar $x$ é um objeto áspero e $S(x)$ significado $x$ é um objeto liso:

"Premissa: existe um objeto áspero como um grão de areia. Conclusão: existe um objeto liso como um rolamento de esferas".

Proposicionalmente, a frase é válida porque a premissa e a conclusão são verdadeiras. Mas logicamente, é inválido. A existência de um objeto áspero não implica na existência de um objeto liso. (Observação: o que é mais confuso agora é que deixei o domínio da lógica proposicional central e entrei no que parece ser um domínio mais "subjetivo" e é frustrante)

Mas não há "rigor" no argumento lógico articulado em inglês.

Questões:

A sequência acima é válida?
Se você sabe que é válido porque o provou usando regras de dedução, pare aqui
Se não houver provas, como você pode provar que é inválido? Você usa tabelas de verdade?

Respostas

2 lemontree Oct 13 2020 at 19:23

A inferência é válida e derivável.

Em geral, um contra-exemplo a uma inferência inválida consiste em uma estrutura em que todas as premissas são verdadeiras, mas a conclusão é falsa.

Seu argumento está incorreto porque não mostra precisamente (por meio de fornecer um modelo de contador concreto) que esta interpretação dos predicados invalida o sequente, e seu exemplo em inglês não é uma deformalização apropriada da afirmação: Você não pode simplesmente abandonar um dos disjuntos em cada uma das frases. E se$R(x)$ é representar um objeto áspero e $S(x)$ liso, então o argumento é "Se existe um objeto áspero ou liso, então existe um objeto áspero ou liso".

Normalmente, é aconselhável iniciar uma prova de dedução natural de baixo para cima, executando regras de introdução reversas no operador principal até que você não consiga mais, em seguida, alternando para o topo e descendo das instalações por sucessivas aplicações de eliminação regras até que você esperançosamente se encontre no meio.
Nesse caso, a conclusão é uma disjunção, mas tentar a introdução da disjunção como última etapa não levará ao sucesso, pois isso exigiria a prova de uma das disjunções, o que obviamente não é possível, porque você não pode inferir nenhuma das os dois lados com certeza, apenas a disjunção deles. Portanto, vá imediatamente ao topo e comece a desmontar as instalações.

A única premissa que você recebe é uma declaração existencial, então a primeira coisa a fazer é uma eliminação existencial. Eliminação existencial significa que você assume a declaração quantificada para algum objeto arbitrário (digamos$a$), tire alguma conclusão dessa suposição; então, como você sabe que pelo menos um desses objetos existe, pode inferir a conclusão com certeza. A conclusão a que você quer chegar é$\exists x R(x) \lor \exists x S(x)$, então tente derivar isso sob a suposição $R(a) \lor S(a)$:

| exists x(R(x) v S(x))
| | R(a) v S(a)
| | -----------
| | ...
| | exists x R(x) v exists x S(x)
| exists x R(x) v exists x S(x)

A próxima coisa do topo é a disjunção $R(a) \lor S(a)$. Portanto, você elimina a disjunção, o que significa que você assume cada uma das disjunções, obtém a mesma conclusão de ambas e, em seguida, conclui que, uma vez que pelo menos um dos dois lados é válido, a conclusão segue com certeza. A conclusão a inferir no final, e nas duas subprovações, é novamente$\exists x R(x) \lor \exists x S(x)$: