Concursos
Online

Lógica de primeira ordem

Linguagem, quantificadores, tradução, negação, ordem dos quantificadores, modelos e inferências elementares da lógica de primeira ordem.

Lógica de primeira ordem

Mapa básico

ElementoRegra de prova
domínio U≠∅U\neq\varnothingobjetos percorridos pelas variáveis
constante aanomeia objeto
variável xxrepresenta objeto
função f(x)f(x)recebe objeto(s) e devolve objeto
predicado P(x)P(x)produz afirmação
relação R(x,y)R(x,y)predicado com mais de um argumento
aridadequantidade fixa de argumentos
igualdade a=ba=bidentidade entre objetos designados

Termo ≠ fórmula: f(a)f(a) é termo; P(f(a))P(f(a)) é fórmula.

Traduções obrigatórias

PortuguêsFórmula
Todo AA é BB∀x(A→B)\forall x(A\to B)
Nenhum AA é BB∀x(A→¬B)\forall x(A\to\neg B)
Algum AA é BB∃x(A∧B)\exists x(A\land B)
Algum AA não é BB∃x(A∧¬B)\exists x(A\land\neg B)

Universal restrita → implicação. Existencial restrita → conjunção.

Palavras que invertem ou restringem

FraseLeitura
Somente AA são BBtodo BB é AA: B→AB\to A
Nem todo AA é BBexiste AA que não é BB
Algum AA é BBao menos um; pode ser todos

“Somente servidores acessam”:

Acessa(x)→Servidor(x).Acessa(x)\to Servidor(x).

Não conclua Servidor(x)→Acessa(x)Servidor(x)\to Acessa(x).

Negação sem erro

¬∀xφ≡∃x¬φ\neg\forall x\varphi\equiv\exists x\neg\varphi ¬∃xφ≡∀x¬φ\neg\exists x\varphi\equiv\forall x\neg\varphi
OriginalNegação
todo AA é BBalgum AA não é BB
nenhum AA é BBalgum AA é BB
algum AA é BBnenhum AA é BB
algum AA não é BBtodo AA é BB

CEBRASPE: negar “todos” não produz “nenhum”; produz contraexemplo existencial.

Ordem dos quantificadores

∀x∃yR(x,y)\forall x\exists yR(x,y)

→ para cada xx, pode haver um yy diferente.

∃y∀xR(x,y)\exists y\forall xR(x,y)

→ um mesmo yy funciona para todo xx.

Em geral:

∀x∃yR(x,y)≢∃y∀xR(x,y).\forall x\exists yR(x,y)\not\equiv\exists y\forall xR(x,y).

Trocas seguras:

∀x∀yR≡∀y∀xR\forall x\forall yR\equiv\forall y\forall xR ∃x∃yR≡∃y∃xR.\exists x\exists yR\equiv\exists y\exists xR.

Escopo e variáveis

FórmulaSituação
P(x)P(x)xx livre
∀xP(x)\forall xP(x)xx ligada
∀xR(x,y)\forall xR(x,y)xx ligada; yy livre
P(x)∧∃xQ(x)P(x)\land\exists xQ(x)xx livre em PP e ligada em QQ

Sentença: fórmula sem variável livre.

Existência: pegadinha central

Domínio clássico não vazio:

∀xP(x)⊨∃xP(x).\forall xP(x)\models\exists xP(x).

Mas:

∀x(A(x)→B(x))⊭∃xA(x).\forall x(A(x)\to B(x))\not\models\exists xA(x).

A classe AA pode ser vazia. Universal categórica não cria existência.

Distribuições

Válidas:

∀x(P∧Q)≡(∀xP)∧(∀xQ)\forall x(P\land Q)\equiv(\forall xP)\land(\forall xQ) ∃x(P∨Q)≡(∃xP)∨(∃xQ)\exists x(P\lor Q)\equiv(\exists xP)\lor(\exists xQ)

Não válidas em geral:

∀x(P∨Q)≢(∀xP)∨(∀xQ)\forall x(P\lor Q)\not\equiv(\forall xP)\lor(\forall xQ) ∃x(P∧Q)≢(∃xP)∧(∃xQ)\exists x(P\land Q)\not\equiv(\exists xP)\land(\exists xQ)

Na última, os testemunhos podem ser diferentes.

Validade e contramodelo

ConceitoAtalho
satisfatívelverdadeira em alguma interpretação
válidaverdadeira em todas
insatisfatívelverdadeira em nenhuma
contramodelopremissas verdadeiras + conclusão falsa

Uma interpretação favorável prova satisfatibilidade, não validade.

Um único contramodelo refuta a consequência lógica.

Inferências rápidas

Válida:

∀x(P→Q), ∃xP⊨∃xQ.\forall x(P\to Q),\ \exists xP\models\exists xQ.

Inválidas:

∀x(P→Q)⊭∀x(Q→P)\forall x(P\to Q)\not\models\forall x(Q\to P) ∀x(P→Q)⊭∃xP\forall x(P\to Q)\not\models\exists xP ∃xP, ∃xQ⊭∃x(P∧Q)\exists xP,\ \exists xQ\not\models\exists x(P\land Q) ∀x∃yR⊭∃y∀xR.\forall x\exists yR\not\models\exists y\forall xR.

Checklist de questão

  1. Qual é o domínio?
  2. Predicados e relações têm qual aridade?
  3. Há “todo”, “algum”, “nenhum”, “somente” ou “nem todo”?
  4. Universal restrita usa →\to; existencial restrita usa ∧\land.
  5. Qual é o escopo de cada quantificador?
  6. ∀∃\forall\exists ou ∃∀\exists\forall?
  7. Negou? Troque ∀↔∃\forall\leftrightarrow\exists e negue o escopo.
  8. A conclusão inventou existência ou unificou testemunhos diferentes?
  9. Suspeita de invalidade? Monte domínio com 1 ou 2 objetos.

Pegadinhas finais

  • Função não é predicado.
  • Termo não recebe valor lógico isoladamente.
  • Preserve aridade e ordem dos argumentos.
  • Constantes diferentes podem nomear o mesmo objeto.
  • “Somente” aponta condição necessária.
  • “Nem todo” ≠ “nenhum”.
  • Negação de universal é existencial.
  • Quantificadores mistos não comutam em geral.
  • Universal categórica não garante existência da classe-sujeito.
  • Duas existenciais podem usar testemunhos distintos.
Voltar para o concursoVoltar ao topo

Selecione o que incluir. Referências não saem no impresso.

Seções

Na janela do sistema, escolha “Salvar como PDF” como destino se quiser um PDF.