Lógica de primeira ordem — quantificadores e predicados

Variável, predicado e universo

O predicado é a propriedade ou relação: P(x) lê-se "x tem a propriedade P". A variável x percorre o universo de discurso, o conjunto dos elementos de que se fala. P(x) sozinho é sentença aberta: não tem valor lógico até a variável receber um valor ou ser quantificada. O conjunto-verdade reúne os elementos do universo que tornam P(x) verdadeira.

Ex.: universo {1, 2, …, 10} e P(x): "x² < 20".

1. P(4): 16 < 20, verdadeira. P(5): 25 < 20, falsa.
2. Conjunto-verdade: {1, 2, 3, 4}.

Quantificador universal

∀x P(x) lê-se "para todo x, P(x)", "qualquer que seja x". É verdadeira quando todos os elementos do universo satisfazem P. Para mostrar que é falsa, basta um contraexemplo.

Ex.: no universo {1, 2, …, 10}, "∀x (x > 2)" é falsa: x = 1 é contraexemplo.

Quantificador existencial

∃x P(x) lê-se "existe x tal que P(x)", "algum", "pelo menos um". É verdadeira quando ao menos um elemento satisfaz P. Para mostrar que é verdadeira, basta um exemplo; para mostrar que é falsa, é preciso que nenhum elemento sirva.

Ex.: no universo {1, 2, …, 10}, "∃x (x² = 9)" é verdadeira: x = 3. Já "∃x (x² = 2)" é falsa, pois nenhum inteiro serve. O valor depende do universo: nos números reais, a segunda seria verdadeira.

Negação de sentenças quantificadas

• ¬∀x P(x) ≡ ∃x ¬P(x): "nem todo" é "algum não".
• ¬∃x P(x) ≡ ∀x ¬P(x): "não existe" é "todo não", isto é, "nenhum".

Troca-se o quantificador e nega-se o predicado. Ao negar desigualdades, o sinal de igual muda de lado: a negação de x > 2 é x ≤ 2.

Ex.: negar ∀x (x > 2).

1. Troca do quantificador: ∃x.
2. Negação do predicado: ¬(x > 2) é x ≤ 2.
3. Resultado: ∃x (x ≤ 2). Escrever x < 2 deixaria de fora o caso x = 2.

Como ler fórmulas com negação

A posição da negação muda o sentido:

• ∃x ¬P(x): existe ao menos um que não é P.
• ∀x ¬P(x): nenhum é P.
• ¬∃x ¬P(x): não existe quem não seja P, isto é, todos são P.

Ex.: P(x): "x é servidor efetivo", no universo dos funcionários do órgão. ∃x ¬P(x): "existe ao menos um funcionário que não é servidor efetivo". ∀x ¬P(x): "nenhum funcionário é servidor efetivo".

Traduzir "todo A é B"

∀x (A(x) → B(x)): "para todo x, se x é A, então x é B". O universal pede a condicional. Com conjunção, ∀x (A(x) ∧ B(x)), a frase passaria a dizer que tudo no universo é A e é B.

Ex.: A(x): "x é agente"; H(x): "x é habilitado". "Todo agente é habilitado" é ∀x (A(x) → H(x)). A fórmula ∀x (H(x) → A(x)) diria o inverso: "todo habilitado é agente".

Traduzir "algum A é B" e "algum A não é B"

∃x (A(x) ∧ B(x)): "existe x que é A e é B". O existencial pede a conjunção. Com condicional, ∃x (A(x) → B(x)), a frase seria verdadeira bastando existir alguém que não é A. "Algum A não é B" é ∃x (A(x) ∧ ¬B(x)).

Ex.: C(x): "x é concursado"; E(x): "x é estável". "Algum servidor concursado não é estável" é ∃x (C(x) ∧ ¬E(x)).

Negar "todo A é B" e "algum A é B"

As regras de negação, aplicadas às traduções, dão as negações da linguagem comum:

• ¬∀x (A(x) → B(x)) ≡ ∃x (A(x) ∧ ¬B(x)): "algum A não é B".
• ¬∃x (A(x) ∧ B(x)) ≡ ∀x (A(x) → ¬B(x)): "nenhum A é B".

Ex.: negar "Todos os servidores do setor são concursados".

1. Forma: ∀x (S(x) → C(x)).
2. Troca do quantificador e negação da condicional (mantém o antecedente e nega o consequente): ∃x (S(x) ∧ ¬C(x)).
3. Leitura: "Pelo menos um servidor do setor não é concursado".