Lógica de predicados - Regras de dedução I
Contato
- Jean Paulo Martins (jeanmartins utfpr edu br)
- Sala 105, Bloco S (UTFPR - Campus Pato Branco)
Conteúdo
Regras de inferência
O cálculo de predicados usa as mesmas dez regras do cálculo proposicional. Adicionalmente, temos as regras de introdução e de eliminação dos quantificadores. Relembremos um exemplo do cálculo proposicional
Este exemplo pode ser demonstrado utilizando a abordagem de prova de condicionais: assumir o antecedente como hipótese e derivar o consequente. Vejamos como ficaria
Um exemplo similar na lógica de predicados, poderia ser provado utilizando-se das mesmas regras de derivação. Consideremos, por exemplo, a forma de argumento.
Se substituirmos as subfórmulas análogamente ao exemplo anterior, temos a demonstração a seguir:
Neste exemplo da lógica de predicados não precisamos utilizar regras de inferência para os quantificadores, deste modo a demonstração se restringiu à utilização das regras já definidas para a lógica proposicional. Como esse não é sempre o caso, precisamos especificar o funcionamento das regras de derivação para os quantificadores: universal ($\forall$) e existencial ($\exists$).
Quantificador universal
Regra de eliminação
Iremos iniciar pela definição da regra de eliminação do quantificador universal ($\forall$e). Intuitivamente a regra de eliminação do quantificador universal é bem simples e segue a seguinte ideia:
- Se algo é valido para todos objetos, também é válido para um objeto em específico.
Portanto, uma fórmula geral do tipo $\forall x P(x)$, pode ser substituída durante uma demonstração por um caso específico $P(a)$, onde $a$ é um termo qualquer. Vejamos o seguinte exemplo.
“Todos os homens são mortais”
“Sócrates é homem”
“Sócrates é mortal”
Se definirmos os predicados:
- $H(x):$ $x$ é homem
- $M(x):$ $x$ é mortal
- $s:$ Sócrates
Temos o seguinte argumento formalizado:
O caso genérico indicado pela premissa $\forall x(H(x)\to M(x))$ pode ser especializado em termos de $s$ (Sócrates), levando à fórmula $H(s)\to M(s)$. Ou seja, se o fato de ser homem implica ser mortal, essa regra se aplica a qualquer homem $x$, inclusive Sócrates $s$. Pode-se dizer que $H(s)\to M(s)$ é uma instanciação da regra universal.
Exemplo 1
Prove a validade da seguinte forma de argumento
Exemplo 2
Prove a validade da seguinte forma de argumento
Exemplo 3
Regra de introdução
Em princípio, para introduzirmos uma fórmula do tipo $\forall x F(x)$, teríamos que demonstrar que para qualquer que seja $x$ então o predicado $P(x)$ é verdadeiro. Obviamente, sendo $x$ parte de um domínio possivelmente infinito esse tipo de abordagem não é possível. Como então introduzirmos o quantificador universal?
A ideia também é simples, apesar de um pouco confusa no início. Se eu consigo demonstrar que para um caso específico $a$, $P(a)$ é verdadeiro, então, se nenhuma consideração/restrição foi feita em termos de $a$, essa demonstração poderia ser utilizada para demonstrar que para qualquer $x$, $P(x)$ também é verdadeiro. Consideremos um exemplo:
“Todos os peixes são ciprinídeos”
“Todos ciprinídeos são vistosos”
“Todos os peixes são vistosos”
Que formalizada por meio dos predicados:
- $P(x)$: $x$ é peixe
- $C(x)$: $x$ é ciprinídeo
- $V(x)$: $x$ é vistoso
Apesar de $a$ neste exemplo ser utilizado para referenciar um caso específico de $x$, nenhuma suposição foi feita acerca de $a$, portanto ele poderia ser utilizado para substituir qualquer $x$. Portanto é possível generalizar a conclusão de $a$ para $\forall x$.
- Para que a aplicação dessa regra seja válida, não pode haver suposições sobre o símbolo $a$, ou seja, ele não pode aparecer nas premissas nem e nenhuma hipótese vigente.
- Pois nesses casos haveria suposições sobre $a$, consequentemente ele não poderia representar um $x$ arbitrário.