Contato

  • Jean Paulo Martins (jeanmartins utfpr edu br)
  • Sala 105, Bloco S (UTFPR - Campus Pato Branco)

Conteúdo

Teoremas

Assim como na lógica proposicional, existem fórmulas na lógica de predicados que podem ser demonstradas sem a necessidade de premissas. Tais fórmulas, chamadas teoremas, são verdades lógicas, ou seja sua verdade é necessária de acordo com as regras da lógica de predicados. Todos os teoremas da lógica proposicional são, também, teoremas na lógica de predicados.

Exemplo 1

O condicional quando aplicado a antecedente e consequente iguais é um teorema na lógica proposicional, $p \to p$, sendo portanto representado em forma de argumento sem premissas

Na lógica de predicados temos a versão generalizada deste teorema, a qual é produzida pela introdução do quantificador universal.

A demonstração deste teorema segue a estratégia utilizada para demonstrarmos qualquer condicional. Assumimos como hipótese o antecedente e derivamos o consequente.

Exemplo 2

Provemos o seguinte teorema:

A estratégia de demonstração é a mesma, basta observarmos que $Fa$ é uma instância da fórmula generalizada $\forall x Fx$. Portanto

Exemplo 3

Neste exemplo, não é evidente qual regra de derivação utilizar. Seguindo a estratégia já mencionada anteriormente, tentaremos a demonstração por redução ao absurdo. Assumindo a negação da conclusão como hipótese

Equivalências

Assim como vimos para as árvores de refutação da lógica proposicional, nem sempre uma fórmula é facilmente demonstrável ou derivavel. Em alguns desses casos, no entanto, a utilização de uma fórmula equivalente facilita consideravelmente o trabalho.

Para ilustrar essa ideia, como demonstraríamos o teorema a seguir?

Não é evidente quais regras aplicar, visto que não temos premissas, a regra de eliminação ou introdução da disjunção não são aplicáveis. Podemos então tentar substituir essa fórmula por uma equivalente, mas qual utilizar? Na lógica proposicional demonstramos a equivalência $p \to q \dashv\vdash \neg p \lor q$, seria essa quivalência válida na lógica de predicados.

Exemplo 1

Demonstre a equivalência

Dada a equivalência acima, demonstrar o teorema $\vdash \forall x Fx \lor \exists x \neg Fx$ é equivalente a demonstrar sua equivalência

Exemplo 2

Demonstre a equivalência

Exemplo 3

Demonstre as equivalências

Intercâmbio de quantificadores

As últimas equivalências, descritas no Exemplo 3, são mais genéricas do que parecem à primeira vista. De fato, elas são válidas para quaiquer subfórmulas, desde que sejam subfórmulas dependentes da mesma variável. No entanto, para formalizarmos essa ideia, precisamos definir antes alguns conceitos.

Variáveis abertas e fechadas

Consideremos como exemplo simples a fórmula $\forall x Fx$. Pela definição das regras de formação da linguagem da lógica de predicados, sabemos que $Fx$ só faz sentido, se houver antes um quantificador discriminando $x$.

  • Uma fórmula é dita fechada em relação a uma variável $x$ qualquer, se existe um quantificador associado a tal variável. Exemplo: $\forall x (Fx \land Gx)$
  • Uma fórmula é dita aberta em relação a uma variável $x$ qualquer, se não existe quantificador que discrimine tal variável. Exemplo: $Fx \land Gx$, $\forall y Fxy$

Essa terminologia permite nos referirmos mais facilmente a fórmulas e subfórmulas com a mesma característica em termos de variáveis. Para melhor exemplificar, consideremos a equivalência $\eqref{eq:4}$ descrita anteriormente.

Nela, podemos nos referir $Fx$ como uma fórmula aberta em $x$ enquanto $\forall x Fx$ é uma fórmula fechada em $x$. Obviamente, existem diversas outras fórmulas abertas em $x$. Por exemplo $Fx\land Gx$ e $Fx\to Gx$ são ambas fórmulas abertas em $x$. Ou seja, todas elas compartilham essa mesma característica com $Fx$. Podemos então, expressar ideias como

“Seja qualquer fórmula $\phi$ que seja aberta em $\beta$”.

Em que $\beta$ represente qualquer variável, e.g. $x, y, z,\dots$. Isso nos permite generalizar as equivalências $\eqref{eq:1}-\eqref{eq:4}$ para além de $Fx$, da seguinte forma:

Exemplo

Vejamos um exemplo da aplicação dessa generalização. Considere a forma de argumento a seguir:

Neste exemplo, $(Fx\to\neg Gx)$ e $(Fx \land Gx)$ são fórmulas abertas em $x$. Se dermos um nome mais simples para cada uma delas, por exemplo, $\phi$ e $\psi$, respectivamente. Então a forma de argumento acima é instância de algo mais genérico

Qual a utilidade?

A principal utilidade desse tipo de generalização é nos permitir utilizar as equivalências em um contexto amplo, sem necessariamente ter que provar cada uma delas, mostrando que todas são instâncias dos mesmos teoremas. Em outras palavras, se:

Então o teorema a seguir também é verdadeiro

pois ambos são instâncias do mesmo teorema genérico.

Este tipo de intercâmbio entre equivalências em muitos casos torna as demonstrações muito mais simples.

Exemplo

Demonstre o seguinte teoremas

Iniciaremos com a tautologia

A subfórmula $\neg \forall x Fx$ pode ser interpretada como

“Nem todo x satisfaz o predicado F”

Que por sua vez é equivalente a dizermos que

“Existe x que não satisfaz F”

A segunda versão pode ser escrita simbolicamente como $\exists x \neg Fx$. Esta equivalência está representada em $\eqref{eq:2}$. Substituindo essa equivalência na tautologia acima, produzimos

O qual finaliza a demonstração do teorema.