Lógica de primeira ordem — quantificadores e predicados

Flashcards de Lógica de primeira ordem — quantificadores e predicados

Tente lembrar antes de virar o card.

• Negação de ∀x P(x)

  Revelar resposta

  ∃x ¬P(x) (algum não).

• Como provar que um universal é falso?

  Revelar resposta

  Com um contraexemplo.

• Negação de ∀x P(x) e de ∃x P(x)

  Revelar resposta

  ¬∀x P(x) ≡ ∃x ¬P(x) · ¬∃x P(x) ≡ ∀x ¬P(x).

• Como se representa “Todo A é B”?

  Revelar resposta

  ∀x (A(x) → B(x)), com condicional, e não com conjunção.

• Como se representa “Algum A é B”?

  Revelar resposta

  ∃x (A(x) ∧ B(x)), com conjunção.

• Quantificador universal (∀)

  Revelar resposta

  "Para todo"; ∀x P(x) é V se todos satisfazem P.

• Quantificador existencial (∃)

  Revelar resposta

  "Existe", "algum"; ∃x P(x) é V se pelo menos um satisfaz P.

• Negação de ∀x P(x)

  Revelar resposta

  ∃x ¬P(x) ("nem todo" = "algum não").

• Negação de ∃x P(x)

  Revelar resposta

  ∀x ¬P(x) ("não existe" = "nenhum").

• Contraexemplo

  Revelar resposta

  Basta um contraexemplo para mostrar que ∀x P(x) é falsa.

• Negação de quantificadores

  Revelar resposta

  ¬(∀x P) ≡ ∃x ¬P; ¬(∃x P) ≡ ∀x ¬P. 'Nenhum A é B' ≡ ∀x (A → ¬B).

• Quantificadores — valor lógico

  Revelar resposta

  ∀ é V se todos satisfazem (um contraexemplo o falseia); ∃ é V se ao menos um satisfaz. Predicados expressam propriedades ou relações.

Questões de Lógica de primeira ordem — quantificadores e predicados

1. Questão 1 · Agente Administrativo PRF · Múltipla escolha

   Considere o predicado P(x): “x é servidor efetivo”, no universo dos funcionários de um órgão. A sentença ∃x ¬P(x) significa:

   1. A)

      Existe ao menos um funcionário que não é servidor efetivo.

   2. B)

      Nenhum funcionário é servidor efetivo.

   3. C)

      Todos os funcionários são servidores efetivos.

   4. D)

      Existe ao menos um funcionário que é servidor efetivo.

   5. E)

      Não existe funcionário que não seja servidor efetivo.

   Revelar gabarito

   Gabarito: letra A

   ∃x lê-se “existe ao menos um x”, e ¬P(x) é “x não é servidor efetivo”. “Nenhum funcionário é efetivo” (B) seria ∀x ¬P(x). (C) é ∀x P(x), e (D) é ∃x P(x). (E) é ¬∃x ¬P(x), equivalente a ∀x P(x): é justamente a negação da sentença dada.

2. Questão 2 · Agente Administrativo PRF · Múltipla escolha

   No conjunto dos números naturais, a negação da sentença ∀x (x > 2) é:

   1. A)

      ∀x (x < 2)

   2. B)

      ∃x (x ≤ 2)

   3. C)

      ∃x (x > 2)

   4. D)

      ∀x (x ≤ 2)

   5. E)

      ∃x (x < 2)

   Revelar gabarito

   Gabarito: letra B

   Para negar “todo x satisfaz a condição”, basta que exista um x que não a satisfaça: ¬∀x P(x) ≡ ∃x ¬P(x). A negação de “x > 2” é “x ≤ 2”, que inclui o próprio 2. Por isso (E), com “x < 2”, deixa de fora o caso x = 2. Trocar o quantificador por “todo” (A, D) não nega a sentença, e (C) mantém a condição original.

3. Questão 3 · Agente Administrativo PRF · Múltipla escolha

   Sejam os predicados A(x): “x é agente” e H(x): “x é habilitado”. A sentença “Todo agente é habilitado” é corretamente representada por:

   1. A)

      ∀x (A(x) ∧ H(x))

   2. B)

      ∃x (A(x) ∧ H(x))

   3. C)

      ∀x (A(x) → H(x))

   4. D)

      ∀x (H(x) → A(x))

   5. E)

      ∃x (A(x) → H(x))

   Revelar gabarito

   Gabarito: letra C

   “Todo A é H” significa “para todo x, se x é agente, então x é habilitado”: ∀x (A(x) → H(x)). A conjunção com “todo” (A) diria que todos são agentes e habilitados. (B) traduz “algum agente é habilitado”. (D) inverte a relação (“todo habilitado é agente”). O quantificador existencial (E) não expressa “todo”.

4. Questão 4 · Agente Administrativo PRF · Múltipla escolha

   A negação da proposição “Algum agente é motorista” é:

   1. A)

      Nenhum agente é motorista.

   2. B)

      Algum agente não é motorista.

   3. C)

      Todo agente é motorista.

   4. D)

      Todo motorista é agente.

   5. E)

      Algum motorista não é agente.

   Revelar gabarito

   Gabarito: letra A

   ¬∃x (A(x) ∧ M(x)) ≡ ∀x (A(x) → ¬M(x)): “nenhum agente é motorista”, que equivale a “todo agente não é motorista”. “Algum agente não é motorista” (B) é a negação de “todo agente é motorista” (C) e pode ser verdadeira junto com a proposição original.

5. Questão 5 · Agente Administrativo PRF · Múltipla escolha

   A negação da proposição “Todos os servidores do setor são concursados” é:

   1. A)

      Nenhum servidor do setor é concursado.

   2. B)

      Todos os servidores do setor não são concursados.

   3. C)

      Alguns servidores concursados não são do setor.

   4. D)

      Todo concursado é servidor do setor.

   5. E)

      Pelo menos um servidor do setor não é concursado.

   Revelar gabarito

   Gabarito: letra E

   ¬∀x P(x) ≡ ∃x ¬P(x): basta que exista um servidor do setor não concursado. “Nenhum” (A) e “todos não” (B) são afirmações mais fortes, contrárias à original, e não contraditórias a ela.