Lógica de primeira ordem

1. Da proposição ao predicado

A lógica proposicional consegue tratar “todo servidor é agente público” como uma proposição inteira, mas assim perde justamente a estrutura que interessa à questão: quem é servidor, qual propriedade esse objeto possui e quantos objetos precisam satisfazê-la.

A lógica de primeira ordem, também chamada lógica de predicados, abre essa estrutura. Em vez de trabalhar apenas com blocos proposicionais, ela permite representar objetos, propriedades, relações e expressões como:

• todo servidor é agente público;
• algum processo contém informação sigilosa;
• cada auditor analisa algum processo;
• existe um processo analisado por todos os auditores.

Na LPO, os quantificadores percorrem objetos de um domínio. Quantificar propriedades, relações ou conjuntos pertence a lógicas de ordem superior e não integra este recorte.

O foco de prova é reconhecer a linguagem, traduzir enunciados, negar quantificadores, distinguir ordens de quantificação e avaliar inferências simples.

2. Elementos da linguagem

2.1. Domínio

O domínio ou universo do discurso é o conjunto de objetos sobre os quais se fala. Na semântica clássica usual, ele é não vazio:

O mesmo enunciado pode mudar de valor lógico quando o domínio muda. Por isso, antes de avaliar uma fórmula, identifique sobre quais objetos as variáveis estão quantificando.

2.2. Constantes, variáveis, funções e predicados

A aridade é o número de argumentos exigidos. Se $R$ é binário, $R(a,b)$ é bem formada; $R(a)$ e $R(a,b,c)$ não são.

Constantes diferentes não precisam nomear objetos diferentes. Sem premissa como $a\neq b$, é possível que $a$ e $b$ tenham o mesmo referente.

2.3. Termos e fórmulas

Termos designam objetos:

Fórmulas afirmam algo e podem ser verdadeiras ou falsas:

Regra útil: função produz termo; predicado aplicado a termos produz fórmula.

3. Quantificadores

3.1. Universal

Significa: para todo objeto $x$ do domínio, $P(x)$.

3.2. Existencial

Significa: existe ao menos um objeto $x$ do domínio para o qual $P(x)$.

O existencial não significa “exatamente um” nem “algum, mas não todos”. Ele admite um ou vários objetos.

4. Escopo, variáveis livres e sentenças

O escopo de um quantificador é a subfórmula sobre a qual ele atua.

Em

$\forall x$ alcança toda a condicional e $\exists y$ alcança $R(x,y)$.

Uma ocorrência é ligada quando está no escopo de um quantificador para a mesma variável; caso contrário, é livre.

Uma sentença ou fórmula fechada não possui variável livre. Fórmulas abertas dependem também de uma atribuição às variáveis livres.

4.1. Renomear variável ligada e evitar captura

O nome de uma variável ligada é apenas um marcador local. Por isso,

desde que a troca seja feita de forma consistente e não altere ocorrências que estavam livres.

O cuidado aparece na substituição. Considere

em que $x$ está livre. Substituir simplesmente $x$ por $y$ produziria

mas isso muda o sentido: a ocorrência antes livre passa a ficar ligada por $\exists y$. Esse efeito é chamado captura de variável.

Para evitar a captura, primeiro renomeie a variável ligada por uma nova, por exemplo:

Agora a substituição de $x$ por $y$ pode ser feita sem mudar quem está ligado a qual quantificador:

Em prova, portanto, renomear variável ligada é seguro quando preserva o vínculo; substituir é seguro apenas quando não transforma uma ocorrência livre em ligada.

5. Traduções que mais caem

Considere $A(x)$ para “$x$ é $A$” e $B(x)$ para “$x$ é $B$”.

5.1. Universal restrita usa implicação

“Todo servidor é treinado”:

Não use

pois isso diria que todo objeto do domínio é servidor e treinado.

5.2. Existencial restrita usa conjunção

“Algum servidor é treinado”:

Não use

porque um objeto que não seja servidor já tornaria a condicional verdadeira.

6. “Somente”, “nem todo” e “algum”

“Somente servidores acessam o sistema” significa:

A palavra somente aponta a condição necessária: quem acessa deve ser servidor. A frase não afirma que todo servidor acessa.

“Nem todo servidor é treinado” significa:

“Algum” significa ao menos um, sem excluir que todos satisfaçam a propriedade.

7. Ordem dos quantificadores

Predicados relacionais tornam a ordem decisiva.

7.1. Cada auditor analisa algum processo

O processo pode variar conforme o auditor.

7.2. Existe um processo analisado por todos os auditores

Agora há um mesmo processo que funciona para todos.

Em geral:

Quantificadores consecutivos do mesmo tipo podem trocar de ordem:

8. Negação de quantificadores

As equivalências fundamentais são:

Procedimento:

1. troque $\forall$ por $\exists$, ou $\exists$ por $\forall$;
2. negue o escopo;
3. aplique De Morgan e a negação da condicional, se necessário.

Exemplo:

Logo, a negação de “todo $A$ é $B$” é “algum $A$ não é $B$”, e não “nenhum $A$ é $B$”.

Para quantificadores sucessivos:

9. Existência e universais categóricas

Como o domínio global é não vazio:

Mas a universal categórica

não garante que exista algum $A$.

Se $A$ tiver extensão vazia, não haverá contraexemplo $A\land\neg B$, e a universal será verdadeira. Portanto:

Essa distinção é uma pegadinha recorrente: domínio não vazio não significa que toda classe definida por predicado tenha elementos.

10. Distribuições úteis

São válidas:

Não são equivalências em geral:

Na última forma, os dois existenciais do lado direito podem ter testemunhos diferentes.

11. Modelos, validade e contramodelos

Uma interpretação dá significado aos símbolos da linguagem. Uma interpretação que torna verdadeira uma sentença é um modelo dela.

• satisfatível: verdadeira em ao menos uma interpretação;
• válida: verdadeira em todas as interpretações admissíveis;
• insatisfatível: falsa em todas as interpretações admissíveis.

Exemplos:

é satisfatível, mas não válida.

é válida na lógica clássica.

é insatisfatível.

Para mostrar que uma conclusão não decorre das premissas, basta construir um contramodelo: premissas verdadeiras e conclusão falsa.

Exemplo inválido:

Tome

As premissas são verdadeiras, mas nenhum mesmo objeto possui $P$ e $Q$.

12. Inferências elementares

Instanciação universal

Se vale para todo objeto, vale para o objeto nomeado por $a$.

Generalização existencial

Se um objeto possui $P$, então existe objeto com $P$.

Cuidado com testemunhos

De

não se conclui $P(a)$ para uma constante previamente escolhida: o testemunho pode ser outro objeto.

Cuidado com generalização universal

De $P(a)$ para um indivíduo particular não segue $\forall xP(x)$. Para generalizar, o objeto considerado precisa ser arbitrário.

Cadeia válida frequente

implicam

13. Padrão oficial do CEBRASPE

Em item oficial da prova de Escrivão da PCDF, o CEBRASPE julgou errada a afirmação de que a negação de “Todos são iguais perante a lei” seria “Todos são diferentes perante a lei”. A justificativa oficial aponta a forma existencial: nem todos possuem a propriedade, isto é, existe ao menos um contraexemplo.

O padrão é exatamente:

14. Pegadinhas e roteiro de resolução

Pegadinhas

• termo não é fórmula;
• função não é predicado;
• preserve aridade e ordem dos argumentos;
• variável ligada pode ser renomeada consistentemente, mas substituição não pode causar captura;
• universal restrita usa implicação;
• existencial restrita usa conjunção;
• “somente $A$ são $B$” significa $B\to A$;
• “nem todo” não significa “nenhum”;
• negar quantificador troca $\forall$ e $\exists$;
• $\forall\exists$ não equivale a $\exists\forall$;
• universal categórica não garante existência da classe-sujeito;
• testemunhos de duas existenciais podem ser diferentes;
• uma interpretação favorável mostra satisfatibilidade, não validade;
• um contramodelo basta para refutar uma consequência lógica.

Roteiro

1. Identifique o domínio.
2. Defina predicados e relações com suas aridades.
3. Localize “todo”, “algum”, “nenhum”, “somente” e negações.
4. Use implicação na universal restrita e conjunção na existencial restrita.
5. Marque o escopo dos quantificadores e confira se alguma substituição captura variável livre.
6. Confira a ordem de $\forall$ e $\exists$.
7. Para negar, troque o quantificador e negue o escopo.
8. Para testar invalidade, tente um domínio pequeno que torne premissas verdadeiras e conclusão falsa.