Lógica Aplicada a Computação
2o semestre/2011
Professor: Newton José Vieira
Lista do Monteiro/
1. Em uma tabela-verdade existem
dois valores).
existem
n
22
3.
2n
linhas (pois cada uma das
n
variáveis recebe um de
Como para cada linha o valor da fórmula pode ser um de dois valores,
tabelas.
2. Supondo que
(a)
DCC/ICEx/UFMG
Solução do Newton
¬∃xp(x);
p(x)
(b)
signique
¬∀xp(x);
x é perfeito e que a(x) signique x é meu amigo :
(c)
∀x(a(x) → p(x));
(d)
∃x(a(x) ∧ p(x));
(a) Alguém enviou e-email.
(b) Alguém enviou e-email para todos.
(c) Todos enviaram e-email.
(d) Alguém recebeu e-email de todos.
(e) Todos receberam e-email.
(f ) Todos enviaram e-email para todos.
4. Se o número de cartas na mesa não for 64, a seleção é incorreta: virar zero cartas (existem
outras condições que garantem que a seleção é incorreta sem necessidade virar cartas).
Caso contrário:
1: virar as azuis (que estão com face para baixo), enquanto aparecer apenas J, Q e K,
no máximo 12 cartas; se virar número ou ao nal sobrar azul: seleção incorreta;
2: virar as com número (que estão com com face para cima) enquanto não aparecer azul,
no máximo 40 cartas; se aparecer azul ou ao nal sobrar número, seleção incorreta.
Passado esse processo, carão 40 vermelhas com face para baixo e as 24 guras com face
para cima: a seleção é correta.
5. (a) João e Maria não mentem no mesmo dia e (b) só dizem ambos a verdade no domingo,
e neste dia Maria estaria mentido se dissesse que mentiu sábado. De (a) e (b) conclui-se
que um está dizendo a verdade e o outro não. Isto só pode ocorrer na 5a-feira: João diz
a verdade quando diz que mentiu na 4a-feira, e Maria mente quando diz que mentiu na
4a-feira.
6. Se A dissesse a verdade, então, segundo o que diz todos seriam mentirosos, inclusive A.
Logo, A é mentiroso. Se o que B diz é mentira, então, já que A também é mentiroso, os
três estão mentindo; mas isso implica que A diz a verdade. Logo, B só pode estar falando
a verdade e, portanto, além de A, C é mentiroso.
Isso é consistente com o que C diz.
Conclusão: A e C são mentirosos e B fala a verdade.
7. Os divisores de 36 são: 1, 2, 3, 4, 6, 9, 12 e 18 (facilmente obteníveis de
Situações em que o produto das idades é 36, com as respectivas somas:
1 × 2 × 2 × 3 × 3).
Prod = 36
Soma
1
1
36
38
1
2
18
21
1
3
12
16
1
4
9
14
1
6
6
13
2
2
9
13
2
3
6
11
3
3
4
10
Como a soma é insuciente para inferência das idades, então elas só podem ser 1, 6 e 6 ou
2, 2 e 9 (soma 13). Como uma é mais velha que as outras, conclui-se que as idades são 2,
2 e 9.
8. No início, não há como cada um saber se seu boné é branco ou não: ele sabe que os bonés
dos outros dois são brancos, mas o dele pode ser preto ou branco; no entanto, ele sabe
que se o boné dele for preto, um dos outros dois (ou os dois) levanta a mão com certeza
absoluta que seu boné é branco. Assim, dado que após alguns minutos um deles levantou
a mão, só pode ser porque ele, vendo que nenhum dos outros dois levantou a mão, o que
aconteceria se seu boné fosse preto, concluiu então que seu boné era branco.
9. A seguir, a notação
mercadoria;
k+i
k−i
indica que deve-se colocar
indica que deve-se colocar
k
k
no prato dos pesos e
no prato dos pesos e
i
i
no prato da
também. Com os
pesos 1, 3, 9 e 27 pode-se pesar mercadorias com valores de 1 a 40:
•
Com o peso 1: 1;
•
Adicionando-se o peso 3:
2 = 3 − 1,
•
Adicionando-se o peso 9:
5
a
3, e
8 = 9 − i,
4 = 3 + 1,
9, e
10
a
sendo 1 como acima.
13 = 9 + i,
sendo
i
de 1 a 4 como
acima;
•
Adicionando-se o peso 27:
14
a
26 = 27 − i,
27, e
28
a
40 = 27 + i,
sendo
i
de 1 a 13
como acima.
10. Na situação descrita tem-se pelo menos duas
•
inconsistências :
A viu B, B viu F e D viu ambos A e F (é impossível os quatro estarem na biblioteca
ao mesmo tempo sem que também B tivesse visto D ou vice-versa ou que A tivesse
visto F ou vice-versa);
•
A viu E, E viu C e C viu D e D viu A (é impossível os quatro estarem na biblioteca
ao mesmo tempo sem que também A tivesse visto C ou vice-versa ou que D tivesse
visto E ou vice-versa).
Notando que apenas A e D são comuns a ambas, um dos dois deve estar mentindo.
A
única opção para retratação com relação ao dizem A e D que restabelece a consistência é
a de que D viu A. Logo, D mente quando diz que viu A. Portanto, D é o ladrão.