Lista 2: Lógica de Predicados

JavaScript isn't enabled in your browser, so this file can't be opened. Enable and reload.

Nome completo do aluno *

Matrícula *

1 - Julgue as afirmações sobre a lógica de predicados: *

I - A lógica de predicados é uma linguagem mais rica que a lógica proposicional, pois adiciona a esta o conceito de predicados e quantificadores. II - A lógica de predicados tem a limitação de não oferecer todos os conectivos permitidos na lógica proposicional. III - Variáveis, constantes e funções são elementos sintáticos da lógica de predicados que não estão presentes na lógica proposicional. IV - A lógica de predicados, semelhante à proposicional, têm apenas expressões que podem ser avaliadas verdadeiras ou falsas.

a) Somente a I é verdadeira

b) I e III são verdadeiras

c) II e IV são verdadeiras

d) II, III e IV são verdadeiras

2 - Julgue os itens que codificam corretamente o significado da sentença: "Nem todas as classes são superclasses de alguma classe" *

I. ∀x (C(x)→∃ySC(x,y)) II. ∃x(C(x) → ¬∃ySC(x,y)) III. ∃x(C(x) ∧ ¬∃ySC(x,y)) IV. ∀x,y (C(x)→SC(x,y))

a) I e III

b) I e II

c) II e IV

d) Apenas III

3 - Podemos codificar a sentença "Algum filho de meus tios é meu primo e é mais novo que eu", para a lógica de predicados, da seguinte forma: ∀x∃y(T(x,e) ∧ F(y,x) → P(e,y) ∧ N(y,e))? Selecione a alternativa correta: *

a) "x", "y", e "e" são variáveis que denotam pessoas nesta família; "T", "F", "P" e "N" são predicados binários com os seguintes significados: T(x,y) significando x é tio de y, F(x,y) significando x é filho de y, P(x,y) significando x é primo de y e N(x,y) significando x é mais novo que y.

b) "x" e "y" são variáveis, mas "e" é uma constante; "T", "F" e "P" são predicados binários com os seguintes significados: T(x,y) significando x é tio de y, F(x,y) significando x é filho de y, P(x,y) significando x é primo de y. Entretanto, "N" é um símbolo funcional.

c) "x" e "y" são variáveis, mas "e" é uma constante; "T", "F", "P" e "N" são predicados binários com os seguintes significados: T(x,y) significando x é tio de y, F(x,y) significando x é filho de y, P(x,y) significando x é primo de y e N(x,y) significando x é mais novo que y.

d) Não podemos codificar esta sentença da forma proposta usando a lógica de predicados.

4 - Dadas as sentenças "Algum aluno obteve uma nota menor que outro aluno" e "Algum aluno obteve uma nota menor que todos os outros alunos", determine a alternativa correta no que diz respeito ao processo de codificação destas sentenças utilizando a lógica de predicados para as seguintes fórmulas ∃x∃y(N(x, y)) e ∃x∀y(N(x, y)∧¬(x=y)): *

a) Ambas as especificações em lógica de predicados estarão inteiramente corretas sem a necessidade do predicado especial de igualdade, ou seja, a segunda poderia ter sido codificada assim: ∃x∀y(N(x, y)).

b) Enquanto a primeira dispensa o uso do predicado especial de igualdade, a segunda o exige para estar inteiramente correta.

c) "x" e "y" são variáveis e "N" é um símbolo funcional binário.

d) Não podemos codificar estas sentenças da forma proposta.

5 - Sobre f1:¬∃xP(x), e f2: ∀x¬P(x), verifique quais afirmações são corretas *

I. f1 ⊦ f2 II. f2 ⊦ f1 III. f1 ⊨ f2 IV. f2 ⊨ f1

a) I e II

b) I e III

c) II e IV

d) Todas as afirmações

6 - Sobre ∃x (P(x) ∧ Q(x)) ⊦ ∃xP(x) ∧ ∃xQ(x), considere as seguintes regras de dedução, e responda a alternativa que representa a melhor estratégia para deduzir o argumento em questão *

I. Eliminar quantificação universal II. Introduzir quantificação existencial III. Eliminar quantificação existencial IV. Eliminar conjunção V. Introduzir conjunção VI. LEM

I, IV, III, V, IV

II, IV, V, III

III, IV, II, V

VI, IV, III

7 - Sobre ∀x(Q(x) → R(x)), ∃x(P(x) ∧ Q(x)) ⊦ ∃x(P(x) ∧ R(x)) , considere as seguintes regras de dedução, e responda a alternativa que representa a melhor estratégia para deduzir o argumento em questão *

I. Introduzir quantificação universal II. Eliminar quantificação universal III. Introduzir quantificação existencial IV. Eliminar quantificação existencial V. Introduzir conjunção VI. Eliminar conjunção VII. Introduzir implicação VIII. Eliminar implicação

II, depois VI, VIII e VI e depois V, III, IV

IV, depois II,VI,VIII, depois VII,V e III

IV, depois VII, VI e II, depois, V, II, VI

VI, II e IV em qualquer ordem e depois, V, III, IV

8 - Sobre a fórmula ∃x∃y∃z(((¬(x=y) ∧ ¬(x=z) ∧ ¬(y=z) ∧ ∀w (((w = x) ∨ (w = y) ∨ (w = z)))) *

Ela é satisfeita por um modelo cujo conjunto possui exatamente:

nenhum elemento

um elemento

dois elementos

três elementos

9 - Sobre a formula ∀x∀y∃z (R(x,y)→R(y,z)) responda quais dos modelos abaixo satisfazem-na: *

I. A={a} e R={(a,a)} II. A={a,b,c,d} e R={(b,c),(a,b),(c,a)}. III. A={a,b} e R={(a,b),(b,a)}.

II e III

todos

10 - Selecione a prova mais adequada para a vinculação ∀xP(x) ∨ ∀xQ(x) ⊨ ∀x (P(x) ∨ Q(x)) *

Todos os elementos estão em P(x) e Q(x), então a quantificação do lado direito é válida

Seja M qualquer modelo onde M ⊨ ∀xP(x) ∨ ∀xQ(x). Então M ⊨ ∀xP(x) ou M ⊨ ∀xQ(x). Assim, para o caso 1, todos os elementos de A estão em P, o que torna ∀x (P(x) ∨ Q(x)) verdadeiro, pela semântica da disjunção. O mesmo acontece com o caso 2.

A vinculação é impossível de provar.

11 - Sobre as vinculações a seguir ∀xP(x) → ∀xQ(x) ⊨ ∀x (P(x) → Q(x)) e ∀x (P(x) → Q(x)) ⊨ ∀xP(x) → ∀xQ(x), selecione a alternativa correta: *

Ambas podem ser provadas verdadeiras.

Apenas a segunda pode ser provada verdadeira.

Apenas a primeira pode ser provada verdadeira.

Nenhuma das duas pode ser provada verdadeira.

12 - Dada a seguinte fórmula, expressa na lógica de predicados: ∀x∀y(segue(y, x) ∧ segue(x, z) → ¬segue(y, z)), selecione a alternativa INCORRETA: *

OBS: "segue" é um predicado binário e "z" é uma constante.

O modelo M: A(M) = {"a", "b", "c"}; z(M) = "a"; segue(M) = {("a", "a"), ("b", "a"), ("c", "a")} não satisfaz essa fórmula.

O modelo M: A(M) = {"a", "b", "c"}; z(M) = "a"; segue(M) = {"a", "b"} não pode ser utilizado para verificar a veracidade desta fórmula.

O modelo M': A(M') = {"a", "b", "c"}; z(M') = "a"; segue(M') = {("b", "a"), ("c", "b")} satisfaz essa fórmula.

Nenhum modelo é capaz de satisfazer essa fórmula.

1. ∃x(∀y(F(x,y))) Prem

3. F(a,b) ∀x e,2

5. ∃x(F(x,b)) ∃x e, 1, 2-4

13. Na dedução da Lógica de Predicados acima, os espaço representam passos que estão faltando, selecione os passos que estão faltando na prova da fórmula: ∃x ( ∀y F(x,y) ) ⊢ ∀y ( ∃x ( F(x,y) ) ).

Obs: Entre as linhas 2 a 4 e 2 a 5, da dedução acima, existe uma caixa para cada escopo..

6. ∀y ( ∃x ( F( x, y ) ) ) ∀y i, 5

6. ∀y ( ∃x ( F ( x, y ) ) ∀x e, 5

2. ∀y ( F( a, y) ) ∀x e, 2

4. ∃x ( F( x, b ) ) ∃x i, 3

3. ∀y ( F( a, y ) ) ∀x e, 2

2. ∀y ( ∃x ( F( x, y ) ) ) ∀x i, 4

6. ∀y ( ∃x ( F( x, y ) ) ) ∀x i, 4

2. ∀y ( F( a, y ) ∀x e, 4

2. ∀y ( F (a, y) ) hip

14. Na dedução acima, para a formula ∀x ( F(x) → G(x) ) ⊢ ∀x ¬G(x) → ∀x ¬F(x) quais são os passos que estão incorretos e ou incompletos?

Passo 3 e Passo 5

Passo 4, Passo 5 e Passo 6

Passo 5, Passo 6, Passo 7

Passo 6 e Passo 7

Passo 7 e Passo 5

Clear selection

15. Selecione qual a estrategia que se deve utilizar para começar a prova da fórmula ∃x ( F(x) → P ) ⊣⊢ ∀x F(x) → P.

¬ e

¬ i

∀x e

∃x e

∧ i

Clear selection

Submit

Clear form

Never submit passwords through Google Forms.

This content is neither created nor endorsed by Google. - Terms of Service - Privacy Policy

Does this form look suspicious? Report

Forms