lista-poscomp

Prévia do material em texto

Questo˜es do Poscomp
SIN015 – Lo´gica para Computac¸a˜o
Davi Romero de Vasconcelos
1. (2002 - Q10) Assinale o argumento va´lido, onde S1, S2 indicam premissas e S a conclusa˜o:
(a) S1: Se o cavalo estiver cansado enta˜o ele perdera´ a corrida
S2: O cavalo estava descansado
S: O cavalo ganhou a corrida
(b) S1: Se o cavalo estiver cansado enta˜o ele perdera´ a corrida
S2: O cavalo ganhou a corrida
S: O cavalo estava descansado
(c) S1: Se o cavalo estiver cansado enta˜o ele perdera´ a corrida
S2: O cavalo perdeu a corrida
S: O cavalo estava cansado
(d) S1: Se o cavalo estiver cansado enta˜o ele perdera´ a corrida
S2: O cavalo estava descansado
S: O cavalo perdeu a corrida
(e) nenhuma das anteriores
2. (2003 - Q17) Assinale o argumento va´lido, onde S1 e S2 indicam premissas e C a conclusa˜o.
(a) S1: Se a comida e´ boa, enta˜o o servic¸o e´ bom.
S2: A comida na˜o e´ boa.
C: O servic¸o na˜o e´ bom.
(b) S1: Se a comida e´ boa, enta˜o o servic¸o e´ bom.
S2: O servic¸o na˜o e´ bom.
C: A comida e´ boa.
(c) S1: Se a comida e´ boa, enta˜o o servic¸o e´ bom.
S2: O servic¸o na˜o e´ bom.
C: A comida na˜o e´ boa.
(d) S1: Se a comida e´ boa, enta˜o o servic¸o e´ bom.
S2: A comida e´ boa.
C: O servic¸o na˜o e´ bom.
(e) S1: Se a comida e´ boa, enta˜o o servic¸o e´ bom.
S2: A comida na˜o e´ boa.
C: O servic¸o e´ bom.
3. (2003 - Q16) Assinale a forma correta da negac¸a˜o da seguinte frase:
“Algumas pessoas gostam de matema´tica.´´
(a) Algumas pessoas na˜o gostam de matema´tica.
(b) Todas as pessoas na˜o gostam de matema´tica.
(c) Existe uma pessoa que gosta de matema´tica.
(d) Existe uma pessoa que na˜o gosta de matema´tica.
(e) Todas as pessoas gostam de matema´tica.
4. (2005 - Q20) Considere a fo´rmula e o domı´nio de interpretac¸a˜o a seguir:
[∀x[Fx⇒ [Ex ∧ Txa]]]∧
[∃x[[Ex ∧ Txa] ∧ Fx]]∧
1
[∃x[[Ex ∧ Txa] ∧ ¬Fx]]
Domı´nio: Universo
a: Alberto
Ex: x e´ estudante
Fx: x formou-se
Txy: x trabalhou mais que y
Qual sentenc¸a e´ logicamente consistente com a fo´rmula usando o domı´nio de interpretac¸a˜o apresentado?
(a) Todos os estudantes que trabalharam mais que Alberto formaram-se.
(b) Somente estudantes que trabalharam mais que Alberto formaram-se.
(c) Alberto trabalhou mais que qualquer estudante que na˜o se formou.
(d) Somente estudantes que se formaram trabalharam mais que Alberto.
(e) Todos os estudantes que na˜o se formaram trabalharam menos que Alberto.
5. (2004 - Q29) Considerando A e B duas varia´veis lo´gicas, a expressa˜o (not(A) and B) or (A and not(B))
assume o valor verdadeiro:
(a) para todos os valores de A e de B
(b) sempre que A e´ igual a B
(c) sempre que A e´ diferente de B
(d) sempre que A e´ falso
(e) sempre que B e´ falso
6. (2005 - Q12) Determine qual das seguintes proposic¸o˜es na˜o pode ser provada a partir da premissa:
((a ∧ b) ∨ c) ∧ (c→ d)
(a) (a ∨ d) ∧ (b ∨ d)
(b) (¬a ∨ ¬b)→ (c ∧ d)
(c) (a ∧ b)→ ¬d
(d) ¬a→ d
(e) ¬d→ b
7. (2005 - Q13) Dadas as quatro premissas:
• Se o universo e´ finito, enta˜o a vida e´ curta.
• Se a vida vale a pena, enta˜o a vida e´ complexa.
• Se a vida e´ curta ou complexa, enta˜o a vida tem sentido.
• A vida na˜o tem sentido.
e as assertivas lo´gicas:
(I) se o universo e´ finito e a vida vale a pena, enta˜o a vida tem sentido;
(II) a vida na˜o e´ curta;
(III) a vida tem sentido ou o universo e´ finito;
quais assertivas pode-se dizer que se seguem logicamente das premissas dadas?
(a) Somente (I) e (III)
(b) Somente (II) e (III)
(c) Somente (I) e (II)
(d) (I), (II) e (III)
(e) Somente a assertiva (I).
2
8. (2005 - Q14) Considere a seguinte proposic¸a˜o:
P : ∀x[Bx→ [Lx ∧ Cx]]
Assinale a alternativa que conte´m uma proposic¸a˜o equivalente a ¬P .
(a) ∀x¬[Bx→ [Lx ∧ Cx]].
(b) ∃x[Bx ∧ [¬Lx ∨ ¬Cx]].
(c) ∀x[Bx→ ¬[Lx ∧ Cx]].
(d) ∃x[¬Bx ∧ [¬Lx ∨ ¬Cx]].
(e) ∃x[¬Bx ∨ [Lx ∧ Cx]].
9. (2005 - Q24) Considere as seguintes expresso˜es booleanas:
(A) (a · b) + (c · d · e)
(B) (a · b) · (c · d · e)
(C) (a+ b) · (c+ d+ e)
(D) (a+ b) + (c+ d+ e)
Considere ainda as seguintes afirmac¸o˜es:
(I) A e´ equivalente a B.
(II) C e´ equivalente a D.
(III) A e´ equivalente a D.
(IV) B e´ equivalente a C.
Quais das alternativas acima sa˜o verdadeiras?
(a) Somente as afirmac¸o˜es (I) e (II) sa˜o verdadeiras.
(b) Somente as afirmac¸o˜es (I) e (III) sa˜o verdadeiras.
(c) Somente as afirmac¸o˜es (II) e (IV) sa˜o verdadeiras.
(d) Todas as afirmac¸o˜es sa˜o verdadeiras.
(e) Todas as afirmac¸o˜es sa˜o falsas.
10. (2006 - Q09) Assinale a proposic¸a˜o logicamente equivalente a ¬(p ∨ q) ∨ (¬p ∧ q)
(a) ¬p ∧ (q ∨ ¬q)
(b) ¬p
(c) (p ∨ q) ∧ (p ∨ ¬q)
(d) (p ∨ q) ∨ (p ∧ ¬q)
(e) p
11. (2006 - Q10) Considere as seguintes proposic¸o˜es
(I) ¬p ∨ q
(II) ¬(p ∧ ¬q)
(III) p→ q
(IV) (V → q) ∨ (p→ F )
Quais das proposic¸o˜es acima sa˜o logicamente equivalentes ?
(a) Somente (I) ≡ (III)
(b) Somente (I) ≡ (II)
(c) Somente (I) ≡ (II) ≡ (III)
(d) (I) ≡ (III) e (II) ≡ (III) mas (III) 6≡ (IV )
(e) (I), (II), (III) e (IV ) sa˜o equivalentes.
12. (2006 - Q23) De acordo com o teorena de De Morgan, o complemento de X + Y · Z e´:
(a) X + Y · Z
3
(b) X · Y + Z
(c) X · (Y + Z)
(d) X · Y · Z
(e) X · Y + Z
13. (2007 - Q10) Dados os conceitos de coereˆncia e completeza de um sistema dedutivo, analise as seguintes
afirmativas.
I. Existe pelo menos um sistema de deduc¸a˜o coerente e completo para a Lo´gica Proposicional.
II. Todo sistema de deduc¸a˜o para a Lo´gica de Predicados de Primeira Ordem que e´ completo tambe´m e´
coerente.
III. Existe pelo menos um sistema de deduc¸a˜o coerente e completo para a Lo´gica de Predicados de Primeira
Ordem.
A partir da ana´lise, pode-se concluir que e´(sa˜o) VERDADEIRA(S)
(a) nenhuma das afirmativas.
(b) somente as afirmativas I e II.
(c) somente as afirmativas I e III.
(d) somente as afirmativas II e III.
(e) todas as afirmativas.
14. (2007 - Q11) Considere a seguinte linguagem de primeira ordem:
• constantes: a, b
• varia´veis: x, y
• predicados una´rios: P
• predicados bina´rios: R
Considere a seguinte func¸a˜o de interpretac¸a˜o I para essa linguagem, com valores no conjunto N dos nu´meros
naturais:
• I(a) = I(b) = 0
• I(P ) = {n|n < 4}
• I(R) = {(x, y)|x < y}
Dadas as seguintes fo´rmulas:
I. P (a)
II. ∀x, y : R(x, y)→ R(y, x)
III. ∃x : R(x, a)
Em relac¸a˜o a` func¸a˜o de interpretac¸a˜o I definida acima, pode-se afirmar que e´(sa˜o) VERDADEIRA(AS)
(a) somente a fo´rmula I.
(b) somente as fo´rmulas I e II.
(c) somente a fo´rmula III.
(d) nenhuma das fo´rmulas.
(e) todas as fo´rmulas.
15. (2007 - Q12) Seja ∗ um conectivo terna´rio definido por: ∗(α, β, γ) e´ verdadeiro se, e somente se, ou nenhuma
ou apenas uma das fo´rmulas α, β, γ e´ verdadeira.
Assinale a alternativa que apresenta a fo´rmula equivalente a ∗(α, β, γ).
(a) (α ∨ β ∨ γ) ∧ (α ∨ (¬β) ∨ (¬γ)) ∧ ((¬α) ∨ β ∨ (¬γ)) ∧ ((¬α) ∨ (¬β) ∨ γ)
(b) ((¬α) ∧ (¬β) ∧ (¬γ)) ∨ (α ∧ (¬β) ∧ (¬γ)) ∨ ((¬α) ∧ β ∧ (¬γ)) ∨ ((¬α) ∧ (¬(¬β)) ∧ γ)
(c) (α ∨ (¬β) ∨ (¬γ)) ∧ ((¬α) ∨ β ∨ (¬γ)) ∧ ((¬α) ∨ (¬β) ∨ γ)
(d) ((¬α) ∧ (¬β) ∧ (¬γ)) ∨ (α ∧ (¬β) ∧ (¬γ)) ∨ ((¬α) ∧ β ∧ (¬γ)) ∨ ((¬α) ∧ (¬β) ∧ γ)
4
(e) Nenhuma destas respostas e´ correta.
16. (2007 - Q13) Um conjunto C, subconjunto de um conjunto A, e´ decid´ıvel se existe um programa que recebe
uma entrada x ∈ A, e sempre pa´ra indicando se x ∈ C ou se x 6∈ C.
Entre os conjuntos relacionados abaixo, assinale o que NA˜O e´ decid´ıvel.
(a) O conjunto das fo´rmulas satisfat´ıveis da lo´gica cla´ssica proposicional.
(b) O conjunto dos teoremas da lo´gica cla´ssica proposicional.
(c) O conjunto dos teoremas da lo´gica cla´ssica de primeira ordem.
(d) O conjunto das fo´rmulas da lo´gica cla´ssica de primeira ordem.
(e) O conjunto das tautologias da lo´gica cla´ssica proposicional.
17. (2008 - Q65) Defina os conectivos NIMP, NEQ, NAND, negac¸a˜o da implicac¸a˜o, equivaleˆncia e conjunc¸a˜o,
respectivamente, como:
(NIMP ) ≡ ¬(α→ β)
(NEQ) ≡ ¬(α↔ β)
(NAND) ≡ ¬(α ∧ β)
Assinale alternativa que representa um conjunto de conectivos completo.
(a) {NIMP}
(b) {NEQ}
(c) {NAND}
(d) {NIMP,NEQ}
(e) Nenhum e´ completo.
18. (2009 - Q13) A sentenca logicaA ∧ (B ∨ ¬C) e equivalente a
(a) A ∧ (¬B ∧ C)
(b) ¬A ∨ ¬(B ∨ ¬C)
(c) ¬A ∨ (¬B ∧ C)
(d) Todas as respostas anteriores.
(e) Nenhuma das respostas anteriores.
19. (2009 - Q14) Se e´ verdade que as treˆs sentenc¸as a seguir sa˜o verdade
p→ q
r → s
p ∧ t↔ r
enta˜o e´ verdade que:
(a) ¬s→ (t ∨ p)
(b) ¬r → ¬s
(c) ¬q → ¬r
(d) Todas as respostas anteriores.
(e) Nenhuma das respostas anteriores.
20. (2009 - Q15) Existem treˆs suspeitos de invadir uma rede de computadores: Andre´, Bruna e Carlos. Sabe-
se que a invasa˜o foi efetivamente cometida por um ou por mais de um deles, ja´ que podem ter agido
individualmente ou na˜o. Sabe-se, ainda, que:
I. Se Andre´ e´ inocente, enta˜o Bruna e´ culpada.
II. Ou Carlos e´ culpado ou Bruna e´ culpada, mas na˜o os dois.
III. Carlos na˜o e´ inocente.
Com base nestas considerac¸o˜es, conclui-se que:
5
(a) Somente Andre´ e´ inocente.
(b) Somente Bruna e´ culpada.
(c) Somente Carlos e´ culpado.
(d) Sa˜o culpados apenas Bruna e Carlos.
(e) Sa˜o culpados apenas Andre´ e Carlos.
21. (2010 - Q16) Os conectores lo´gicos ∨,→ sa˜o lidos como “ou” e “implica”. O operador “na˜o” e´ representado
por ¬. Considerando esta notac¸a˜o, a tabela verdade da proposic¸a˜o (P → Q)→ (¬Q ∨ P ), assumindo que
a sequeˆncia de valores de P e´ {V, V, F, F} e a de Q e´ {V, F, V, F}, tem os valores:
(a) {F, F, F, F}
(b) {V, V, V, V }
(c) {V, V, F, V }
(d) {F, F, V, V }
(e) {V, F, V, F}
22. (2011 - Q14) Considere as proposic¸o˜es p e q, cujas respectivas negac¸o˜es sao p e q. Enta˜o e correto afirmar
que a rec´ıproca de p→ q e´:
(a) q → p
(b) q → p
(c) p→ q
(d) p e q
(e) p e q
6