lista1 key

Prévia do material em texto

Answer Key for Exam A
Questo˜es de Sistema de Numerac¸a˜o
1. Fazendo as converso˜es em binario, decimal, octal, hexadecimal, complete a seguinte tabela:
Bina´rio Decimal Octal Hexadecimal
11010
255
23
1A
100
Acesse: http://www.calculadoraonline.com.br/conversao-bases para calcular e ver as
respostas.
2. Efetue a conversa˜o dos seguintes valores em binario para octal e hexadecimal:
• a) 100101010111101101
• b) 100110011001100110011001
• c) 101101101101101101101101
• d) 101010110101001
Acesse: http://www.calculadoraonline.com.br/conversao-bases para calcular e
ver as respostas.
Questo˜es de Lo´gica Proposicional
3. Considere as proposic¸o˜es p:”A casa e´ verde” e q:”A casa e´ nova”. Dado as seguintes frases,
expresse-as utilizando a lo´gica proposicional.
a) A casa e´ verde e nova : p ∧ q
b) Se a casa for nova, enta˜o ela e´ verde : q → p
c) A casa e´ verde ou velha (mas na˜o pode ser verde e velha ao mesmo tempo) : (p∨¬q)∧
¬(p ∧ ¬q)
d) A casa e´ verde ou, se a casa na˜o for verde, enta˜o a casa e´ velha : p ∨ (¬p→ ¬q)
1
4. Dado as proposic¸o˜es:
• p: gatos sabem voar
• q: unico´rnios existem
• r: 1+1 = 2
• s: 4+3 = 7
Seja as seguintes expresso˜es:
1) p→ r ∧ q
2) p ∨ q ↔ r
3) r → ¬r ∧ s
4) p ∧ q ∨ r
Quais delas retornara˜o verdadeiro?
(a) 1 e 2
(b) 2 e 3
(c) 3 e 4
(d) 1 e 4
(e) 4, apenas Resposta: d
2
5. Considere que p, q e r sa˜o proposic¸o˜es:
• p: Ursos-cinzentos sa˜o vistos na a´rea
• q: Fazer caminhada na trilha e´ seguro
• r: As bagas esta˜o maduras ao longo da trilha.
Escreva estas proposic¸o˜es usando p, q, r e conectivos lo´gicos.
a) As bagas esta˜o maduras ao longo da trilha, mas os ursos-cinzentos na˜o sa˜o vistos na
a´rea.
b) Ursos-cinzentos na˜o sa˜o vistos na a´rea e fazer caminhada na trilha e´ seguro, mas as
bagas esta˜o maduras ao longo da trilha.
c) Se as bagas esta˜o maduras ao longo da trilha, fazer caminhada e´ seguro se e somente se
os ursos-cinzentos na˜o forem vistos na a´rea.
d) Na˜o e´ seguro fazer caminhada na trilha, mas os ursos-cinzentos na˜o sa˜o vistos na a´rea
e as bagas ao longo da trilha esta˜o maduras.
e) Para a caminhada ser segura, e´ necessa´rio, mas na˜o suficiente, que as bagas na˜o estejam
maduras ao longo da trilha e que os ursos-cienzentos na˜o sejam vistos na a´rea.
f) Caminhada na˜o e´ segura ao longo da trilha sempre que os ursos-cinzentos sa˜o vistos na
a´rea e as bagas esta˜o maduras ao longo da trilha.
Respostas:
a) r ∧ ¬p
b) ¬p ∧ q ∧ r
c) r → (q ↔ ¬p)
d) ¬q ∧ ¬p ∧ r
e) (q → (¬r ∧ ¬p)) ∧ ¬((¬r ∧ ¬p)→ q
f) (p ∧ r)→ ¬q
6. Negue as seguintes frases:
a) Alice e´ esperta e inteligente :Alice na˜o e´ esperta ou na˜o e´ inteligente
b) Alice e´ esperta ou inteligente : Alice na˜o e´ esperta e na˜o e´ inteligente
c) Todos sa˜o espertos e inteligentes : Nem todos sa˜o espertos ou inteligentes. Outra
resposta: Existem pessoas que na˜o sa˜o espertas ou na˜o sa˜o inteligentes.
d) Algumas pessoas sa˜o espertas e inteligentes: Nenhuma pessoa e´ esperta e in-
teligente. Outra resposta: na˜o existe pessoa esperta e inteligente. Outra
resposta: todas as pessoas na˜o sa˜o espertas ou na˜o sa˜o inteligentes.
Questo˜es de Equivaleˆncias Lo´gicas
3
7. Mostre, por tabela verdade, que as seguintes proposic¸o˜es sa˜o tautologias:
a) (p→ q) ∧ (q → r)→ (p→ r) Fazendo a tabela-verdade, temos:
p q r (p→ q) (q → r) (p → q) ∧
(q → r)
(p→ r) (p → q) ∧
(q → r) →
(p→ r)
V V V V V V V V
V V F V F F F V
V F V F V F V V
V F F F V F F V
F V V V V V V V
F V F V F F V V
F F V V V V V V
F F F V V V V V
b) (p ∨ q) ∧ (¬p ∨ r)→ (q ∨ r) Fazendo a tabela-verdade, temos:
p q r (p ∨ q) (¬p ∨ r) (p ∨ q) ∧
(¬p ∨ r)
(q ∨ r) (p ∨ q) ∧
(¬p ∨ r) →
(q ∨ r)
V V V V V V V V
V V F V F F V V
V F V V V V V V
V F F V F F F V
F V V V V V V V
F V F V V V V V
F F V F V F V V
F F F F V F F V
c) [(p ∨ q) ∧ (p→ r) ∧ (q → r)]→ r Fazendo a tabela-verdade, temos:
p q r (p ∨ q) (p→ r) (p ∨ q) ∧
(p→ r)
[(p ∨ q) ∧
(p → r) ∧
(q → r)]
[(p ∨ q) ∧
(p → r) ∧
(q → r)] →
r
V V V V V V V V
V V F V F F F V
V F V V V V V V
V F F V F F F V
F V V V V V V V
F V F V V V F V
F F V F V F F V
F F F F V F F V
d) p ∧ q → r ↔ p→ (q → r) Fazendo a tabela-verdade, temos:
4
p q r (p ∧ q) (p ∧ q)→ r (p ∧ q)↔ p [(q → r) p∧q → r ↔
p → (q →
r)
V V V V V V V V
V V F V F F F V
V F V F V V V V
V F F F V V V V
F V V F V F V V
F V F F V F F V
F F V F V F V V
F F F F V F V V
e) [(p→ q) ∧ (q → r)]→ (p→ r) Fazendo a tabela-verdade, temos:
p q r (p→ q) (q → r) (p → q) ∧
(q → r)
[(p→ r) [(p → q) ∧
(q → r)] →
(p→ r)
V V V V V V V V
V V F V F F F V
V F V F V F V V
V F F F V F F V
F V V V V V V V
F V F V F F V V
F F V V V V V V
F F F V V V V V
8. Mostre, por tabela verdade, se as seguintes proposic¸o˜es sa˜o logicamente equivalentes:
a) A = (p→ q) ∧ (p→ r)
B = p→ (q ∧ r)
Respostas:
Fazendo a tabela-verdade, temos:
p q r (p→ q) (p→ r) (p → q) ∧
(p→ r)
V V V V V V
V V F V F F
V F V F V F
V F F F F F
F V V V V V
F V F V V V
F F V V V V
F F F V V V
5
p q r (q ∧ r) p→ (q ∧ r)
V V V V V
V V F F F
V F V F F
V F F F F
F V V V V
F V F F V
F F V F V
F F F F V
Logo, as proposic¸o˜es sa˜o logicamente equivalentes.
b) A = (p→ q) ∨ (p→ r)
B = p→ (q ∨ r)
Respostas:
Fazendo a tabela-verdade, temos:
p q r (p→ q) (p→ r) (p → q) ∨
(p→ r)
V V V V V V
V V F V F V
V F V F V V
V F F F F F
F V V V V V
F V F V V V
F F V V V V
F F F V V V
p q r (q ∨ r) p→ (q ∨ r)
V V V V V
V V F V V
V F V V V
V F F F F
F V V V V
F V F V V
F F V V V
F F F F V
Logo, as proposic¸o˜es sa˜o logicamente equivalentes.
c) A = (p→ q)→ r
B = (p→ r) ∧ (q → r)
Respostas:
Fazendo a tabela-verdade, temos:
6
p q r (p→ q) (p → q) →
r
(p→ r) (q → r) (p → r) ∧
(q → r)
V V V V V V V V
V V F V F F F F
V F V F V V V V
V F F F V F V F
F V V V V V V V
F V F V F V F F
F F V V V V V V
F F F V F V V V
Logo, as proposic¸o˜es na˜o sa˜o logicamente equivalentes.
d) A = (p→ q)→ (r → s)
B = (p→ r)→ (q → s)
Respostas:
Fazendo a tabela-verdade, temos:
p q r s (p→ q) (r → s) A (p→ r) (q → s)) B
V V V V V V V V V V
V V V F V F F V F F
V V F V V V V F V V
V V F F V V V F F V
V F V V F V V V V V
V F V F F F V V V V
V F F V F V V F V V
V F F F F V V F V V
F V V V V V V V V V
F V V F V F F V F F
F V F V V V V V V V
F V F F V V V V F F
F F V V V V V V V V
F F V F V F F V V V
F F F V V V V V V V
F F F F V V V V V V
Logo, as proposic¸o˜es na˜o sa˜o logicamente equivalentes.
9. Mostre, utilizando tabela verdade e equivalencias lo´gicas que cada uma das proposic¸o˜es a
seguir sa˜o tautologia.
a) [¬p→ (p ∧ q)] ∨ ¬p
≡ [p ∨ (p ∧ q)] ∨ ¬p ≡ (Condicional)
≡ [(p ∨ p) ∧ (p ∨ q)] ∨ ¬p ≡ (Distributiva)
≡ [p ∧ (p ∨ q)] ∨ ¬p ≡ (Idempotentes)
≡ p ∨ ¬p ≡ (Absorc¸a˜o)
7
≡ V (Negac¸a˜o)
b) [(¬p→ p) ∧ (¬p→ q)] ∨ ¬p
≡ (p ∨ p) ∧ (p ∨ q)] ∨ ¬p ≡ (Condicional)
≡ [p ∧ (p ∨ q)] ∨ ¬p ≡ (Idempotentes)
≡ p ∨ ¬p ≡ (Absorc¸a˜o)
≡ V (Negac¸a˜o)
c) (¬p ∧ q)→ q
≡ ¬(¬p ∧ q) ∨ q ≡ (Condicional)
≡ (p ∨ ¬q) ∨ q ≡ (Lei de De Morgan)
≡ p ∨ (¬q ∨ q) ≡ (Associativa)
≡ p ∨ V ≡ (Negac¸a˜o)
≡ V ≡ (Dominac¸a˜o)
d) [¬p ∧ (p ∨ q)]→ q
≡ ¬[¬p ∧ (p ∨ q)] ∨ q ≡(Condicional)
≡ [p ∨ ¬(p ∨ q)] ∨ q ≡(Lei de Morgan)
≡ [p ∨ (¬p ∧ ¬q)] ∨ q ≡(Lei de De Morgan)
≡ [(p ∨ ¬p) ∧ (p ∨ ¬q)] ∨ q ≡(Distributiva)
≡ [V ∧ (p ∨ ¬q)] ∨ q ≡(Negac¸a˜o)
≡ (p ∨ ¬q) ∨ q ≡ (Elementos Neutros)
≡ p ∨ (¬q ∨ q) ≡ (Associativa)
≡ p ∨ V ≡ (Negac¸a˜o)
≡ V ≡ (Dominac¸a˜o)
10. Verifique as equivaleˆncias abaixo sem utilizar a tabela verdade:
a) p→ (q ∧ r) ≡ (p→ q) ∧ (p→ r)
p→ (q ∧ r) ≡
≡ ¬p ∨ (q ∧ r) ≡ (Condicional)
≡ (¬p ∨ q) ∧ (¬p ∨ r) ≡ (Distributiva)
≡ (p→ q) ∧ (p→ r)(Condicional)
b) {p ∧ [¬(¬p ∨ ¬q)]} ∨ (p ∧ q) ≡ p ∧ q
{p ∧ [¬(¬p ∨ ¬q)]} ∨ (p ∧ q) ≡
≡ [p ∧ (p ∧ q)] ∨ (p ∧ q) ≡ (Lei de De Morgan)
≡ [(p ∧ p) ∧ q] ∨ (p ∧ q) ≡ (Associativa)
≡ (p ∧ q) ∨ (p ∧ q) ≡ (Associativa)
≡ p ∧ q (Idempotente)
c) (p→ r) ∧ (q → r) ≡ (p ∨ q)→ r
(p→ r) ∧ (q → r) ≡
≡ (¬p ∨ r) ∧ (¬q ∨ r) ≡ (Condicional)
≡ r ∨ (¬p ∧ ¬q) ≡ (Distributiva)
≡ (¬p ∧ ¬q) ∨ r ≡ (Comutativa)
≡ ¬(¬p ∧ ¬q)→ r ≡ (Condicional)
≡ (p ∨ q)→ r (Lei de De Morgan)
8
d) ¬[∀x(P (x)→ F (x))] ≡ ∃x(P (x) ∧ ¬F (x))
¬[∀x(P (x)→ F (x))] ≡
≡ ∃x¬(P (x)→ F (x)) ≡ (Lei de Morgan)
≡ ∃x¬(¬P (x) ∨ F (x)) ≡ (Condicional)
≡ ∃x(P (x) ∨ ¬F (x)) (Lei de De Morgan)
Questo˜es de Quantificadores
Para as questoes 11 ate´ 14 considere os predicados B(x) : x e´ brasileiro, F (x): x e´ feliz, G(x): x
torce pelo atle´tico. O domı´nio sa˜o pessoas no mundo.
Assinale, para cada questa˜o, a expressa˜o utilizando predicados e quantificadores que corre-
ponde a` frase em portugueˆs apresentada no enunciado. Logo apo´s, traduza em portugueˆs todas as
alternativas incorretas.
11. Todo brasileiro que torce pelo atletico e´ feliz
(a) ∀x(B(x) ∧ F (x) ∧G(x))
(b) ∀x((B(x) ∧G(x))→ F (x))
(c) ∀x(F (x)→ (B(x) ∧G(x)))
(d) ∃x(F (x)→ (B(x) ∧G(x)))
(e) ∃x(B(x) ∧ F (x) ∧G(x))
Resposta correta: b
a) Todas as pessoas sa˜o brasileiras, torcem pelo atle´tico e sa˜o felizes
c) Todas as pessoas felizes sa˜o brasileiras e torcem pelo atle´tico
d) Existe pelo menos uma pessoa que, se ela for feliz, enta˜o ela e´ brasileira e torce
pelo atle´tico
e) Existe brasileiros felizes que torcem pelo atletico
12. Existem brasileiros que torcem pelo atletico e sa˜o felizes
(a) ∀x(B(x) ∧ F (x) ∧G(x))
(b) ∃x((B(x) ∧G(x))→ F (x))
(c) ∀x(F (x)→ (B(x) ∧G(x)))
(d) ∃x(F (x)→ (B(x) ∧G(x)))
(e) ∃x(B(x) ∧ F (x) ∧G(x))
Resposta: e
a) Igual a` letra (a) do exerc´ıcio anterior
b) Existem pessoas que, se ela for brasileira e torcer pelo atle´tico, enta˜o ela e´ feliz
c) Igual a` letra (c) do exerc´ıcio anterior
d) Igual a` letra (d) do exerc´ıcio anterior
9
13. Existem pessoas que, se elas forem brasileiras e torcerem pelo atletico enta˜o elas sa˜o felizes
(a) ∀x(B(x) ∧ F (x) ∧G(x))
(b) ∃x((B(x) ∧G(x))→ F (x))
(c) ∀x(F (x)→ (B(x) ∧G(x)))
(d) ∃x(F (x)→ (B(x) ∧G(x)))
(e) ∃x(B(x) ∧ F (x) ∧G(x))
Resposta: b
As alternativas (a), (c), (d) e (e) sa˜o iguais ao do exerc´ıcio anterior
14. Existem brasileiros que, se eles na˜o torcem pelo atletico enta˜o eles sa˜o felizes
(a) ∃x(B(x) ∧ (¬G(x)→ F (x)))
(b) ∃x((B(x) ∧G(x))→ F (x))
(c) ∃x((B(x) ∧ ¬G(x))→ F (x))
(d) ∃x(B(x) ∧ (F (x)→ ¬G(x)))
(e) ∃x(B(x) ∧ (F (x)→ G(x)))
Resposta: c (a letra (a) tambe´m pode ser considerada correta).
b) Igual letra (b) do exerc´ıcio anterior
d) Existem brasileiros que, se eles forem felizes, enta˜o na˜o sa˜o atleticanos
e) Existem brasileiros que, se eles forem felizes, enta˜o sa˜o atleticanos
Para as questoes 15 ate´ 17 considere o predicados A(x, y) : x ama y onde x e y sa˜o pessoas.
Assinale, para cada questa˜o, a frase em portugueˆs que correponde a` expressa˜o usando predicados
e quantificadores apresentada no enunciado. Logo apo´s, expresse em predicados e quantificadores
todas as alternativas incorretas.
15. ∀x(A(x,Alice))
(a) Todos amam Alice
(b) Alice ama todos
(c) Algumas pessoas amam Alice
(d) Alice ama algumas pessoas
(e) Nem todos amam Alice
Resposta: a
b) ∀x(A(Alice, x))
c) ∃x(A(x,Alice))
d) ∃x(A(Alice, x))
e) ¬∀x(A(x,Alice)) ou ∃x(¬A(x,Alice))
10
16. ∃x∀y(A(x, y))
(a) Todos amam algue´m
(b) Ha´ algue´m que e´ amado por todos
(c) Existem pessoas que amam algue´m
(d) Todos amam todos
(e) Existe algue´m que ama todos
Resposta: e
a) ∀x∃y(A(x, y))
b) ∃y∀x(A(x, y))
c) ∃x∃y(A(x, y))
d) ∀x∀y(A(x, y))
17. ∀x(A(Alice, x)→ A(x, x))
(a) Todos que Alice ama tambe´m amam algue´m
(b) Alice ama algue´m que possui amor pro´prio (ama a si mesmo)
(c) Alice ama todos que possuem amor pro´prio (amam a si mesmos)
(d) Todas as pessoas que possuem amor pro´prio (amam a si mesmos) tambe´m amam Alice
(e) Alice e´ amada por algue´m que possui amor pro´prio (ama a si mesmo)
Resposta: c
a) ∀x∃y(A(Alice, x)→ A(x, y))
b) ∃x(A(Alice, x) ∧A(x, x))
c) ∀x(A(x, x)→ A(x,Alice))
e) ∃x(A(x,Alice) ∧A(x, x))
11
18. Considere P (x): x fala portugueˆs, I(x) x fala ingleˆs e A(x, y): x e´ amiga de y. Verifique se
as seguintes expresso˜es sa˜o verdadeiras ou falsas. Considere como domı´nio (tanto x quanto
y): Alice, Bob e Carol. As tabelas abaixo apresentam as caracter´ısticas de cada um (por
exemplo, Alice fala portugueˆs e e´ amiga apenas de Bob).
x y A(x, y)
Alice Alice F
Alice Bob V
Alice Carol F
Bob Alice F
Bob Bob V
Bob Carol F
Carol Alice F
Carol Bob V
Carol Carol V
x P (x) I(x)
Alice V V
Bob F V
Carol F F
a) ∀x(P (x) ∧ I(x)) : Falso
b) ∃x(P (x) ∧ I(x)) : Verdadeiro
c) ∃x(P (x)→ I(x)) : Verdadeiro
d) ∀x∀y(P (x) ∧A(x, y)) : Falso
e) ∀x∃y(P (x) ∧ I(y) ∧ A(x, y)) : Falso.
Seria verdadeiro se todas as pes-
soas falassem portugueˆs e possuis-
sem um amigo que falasse ingleˆs.
f) ∃x∀y(P (x)∧I(y)∧A(x, y)): Falso. Se-
ria verdadeiro se todas as pessoas
falassem ingleˆs e existisse uma pes-
soa que falasse portugueˆs que fosse
amigo de todas essas pessoas.
12
Questo˜es de Regras de Infereˆncia
19. Transforme os seguintes argumentos em proposic¸o˜es. Logo apo´s, demonstre se o argumento
e´ va´lido ou na˜o utilizando as regras de infereˆncia.
a) Se Martins e´ o autor, enta˜o o livro e´ de ficc¸a˜o. Mas o livro na˜o e´ de ficc¸a˜o. Logo, Martins
na˜o e´ autor. p: Martins e´ autor q: O livro e´ de ficc¸a˜o
Num. Afirmac¸a˜o Justificativa
(1) p→ q premissa (tambe´m chamado de hipo´tese)
(2) ¬q premissa
∴ ¬p Modus Tolens de (1) e (2)
b) Se fizer frio, enta˜o ira´ chover. Se chover, o alunos ira˜o chegar atrasado. Os alunos na˜o
chegaram atrasado. Logo, na˜o fez frio.
p: Ira´ fazer frio
q: Ira´ chover
r: Alunos chegara˜o atrasados
Num. Afirmac¸a˜o Justificativa
(1) p→ q premissa
(2) q → r premissa
(3) ¬r premissa
(4) ¬q Modus Tolens usando (2) e (3)
∴ ¬p Modus Tolens usando (1) e (4)
c) Alice passou em todas as disciplinas em que se matriculou. Alice se matriculou em
Ca´lculo. Logo, algue´m passou em Ca´lculo.
M(x, y): O aluno x se matriculou em y
P (x, y): O aluno x passou na disciplina y
Num. Afirmac¸a˜o Justificativa
(1) ∀y(M(Alice, y)→ P (Alice, y)) premissa
(2) M(Alice, Calculo) premissa
(3) M(Alice, Calculo)→ P (Alice, Calculo) Instanciac¸a˜o Universal usando (1) e (2)
(4) P (Alice, Calculo) Modus Ponens usando (2) e (3)
∴ ∃x(P (x,Calculo)) Generalizac¸a˜o Existencial de (4)
d) Se a firma falir, todos os seus ativos teˆm que ser confiscados. A firma faliu. Segue que
todos os ativos foram confiscados.
p: A firma ira´ falir
q: Todos os seus ativos teˆm que ser confiscados
Num. Afirmac¸a˜o Justificativa
(1) p→ q premissa
(2) p premissa
∴ q Modus Ponens usando (1) e (2)
e) Se Paulo e´ um bom nadador, enta˜o ele e´ um bom corredor. Se Paulo e´ um bom corredor,
enta˜o ele e´ um bom ciclista. Paulo na˜o e´ um bom ciclista. Logo, Paulo na˜o e´ um bom
nadador.
p: Paulo e´ um bom nadador
q: Paulo e´ um bom corredor
13
r: Paulo e´ um bom ciclista
Num. Afirmac¸a˜o Justificativa
(1) p→ q premissa
(2) q → r premissa
(3) ¬r premissa
(4) ¬q Modus Tolens usando (2) e (3)
∴ ¬p Modus Tolens usando (1) e (4)
f) Se Jane e´ a mais popular, ela sera´ eleita. Se Jane e´ a mais popular, enta˜o Carlos vai
renunciar. Portanto, se Jane e´ a mais popular, ela sera´ eleita e Carlos renunciara´.
p: Jane e´ a mais popular
q: Jane sera´ eleita
r: Carlos vai renunciar
Num. Afirmac¸a˜o Justificativa
(1) p→ q premissa
(2) p→ r premissa
(3) (p→ q) ∧ (p→ r) Conjunc¸a˜o de (1) e (2)
∴ p→ (q ∧ r) Pois (p → q) ∧ (p → r) ≡ p → (q ∧ r)
(conforme prova a seguir)
Prova da equivaleˆncia (p→ q) ∧ (p→ r) ≡ p→ (q ∧ r):
(p→ q) ∧ (p→r) ≡
≡ (¬p ∨ q) ∧ (¬p ∨ r) ≡ (condicional)
≡ ¬p ∨ (q ∧ r) ≡ (prop. distributiva)
≡ p→ (q ∧ r) (condicional)
f) [alterada] Se Jane e´ a mais popular, ela sera´ eleita. Se Jane e´ a mais popular, enta˜o
Carlos vai renunciar. Jane e´ a mais popular. Portanto, Jane sera´ eleita e Carlos renun-
ciara´.
p: Jane e´ a mais popular
q: Jane sera´ eleita
r: Carlos vai renunciar
Num. Afirmac¸a˜o Justificativa
(1) p→ q premissa
(2) p→ r premissa
(3) p premissa
(4) q Modus Ponens usando (1) e (3)
(5) r Modus Ponens usando (2) e (3)
∴ (q ∧ r) Conjunc¸a˜o de (4) e (5)
g) Bob chega atrasado quando chove. Bob esta´ matriculado em Calculo. Logo, algue´m que
esta´ matriculado em Ca´lculo chega atrasado quando chove.
A(x): O aluno x chega atrasado
q: Esta´ chovendo
M(x, y): O aluno x esta´ matriculado na disciplina y
14
Num. Afirmac¸a˜o Justificativa
(1) ∀y((M(Bob, y) ∧ q)→ A(Bob)) premissa
(2) M(Bob, Calculo) premissa
(3) M(Bob, Calculo) ∧ q → A(Bob) Instanciac¸a˜o Universal usando (1) e (2)
∴ ∃x((M(x,Calculo) ∧ q)→ A(x)) Generalizac¸a˜o Existencial de (3)
h) Considere o domı´nio de uma sequeˆncia de 10 pec¸as de domino´. A primeira pec¸a ira´ cair.
Para toda pec¸a k deste domı´nio, se esta pec¸a k cair, a pro´xima pec¸a (pec¸a k+1) tambe´m
ira´ cair. Logo, todas as pec¸as ira˜o cair.
C(i): A pec¸a nu´mero i (i-e´sima pec¸a) ira´ cair
Num. Afirmac¸a˜o Justificativa
(1) C(1) premissa
(2) ∀k(C(k)→ C(k + 1)) premissa
(3) C(1)→ C(1 + 1) Instanciac¸a˜o Universal usando (2) e (1)
(4) C(2) Modus Ponens de (1) e (3)
(5) C(2)→ C(2 + 1) Instanciac¸a˜o Universal usando (2) e (4)
(6) C(3) Modus Ponens de (4) e (5)
(7) C(3)→ C(3 + 1) Instanciac¸a˜o Universal usando (2) e (6)
(8) C(4) Modus Ponens de (6) e (7)
(9) C(4)→ C(4 + 1) Instanciac¸a˜o Universal usando (2) e (8)
(10) C(5) Modus Ponens de (8) e (9)
(11) C(5)→ C(5 + 1) Instanciac¸a˜o Universal usando (2) e (10)
(12) C(6) Modus Ponens de (10) e (11)
(13) C(6)→ C(6 + 1) Instanciac¸a˜o Universal usando (2) e (12)
(14) C(7) Modus Ponens de (12) e (13)
(15) C(7)→ C(7 + 1) Instanciac¸a˜o Universal usando (2) e (14)
(16) C(8) Modus Ponens de (14) e (15)
(17) C(8)→ C(8 + 1) Instanciac¸a˜o Universal usando (2) e (16)
(18) C(9) Modus Ponens de (16) e (17)
(19) C(9)→ C(9 + 1) Instanciac¸a˜o Universal usando (2) e (18)
(20) C(10) Modus Ponens de (18) e (19)
∴ ∀n(P (n)) Generalizac¸a˜o Universal usando (4), (6),
(8),..., (20)
20. Demonstre, utilizando tabela verdade, se os argumentos abaixo sa˜o va´lidos ou na˜o.
a) Alice e´ me´dica. Se Alice for advogada, enta˜o Alice e´ me´dica. Logo, Alice e´ me´dica e
advogada.
p: Alice e´ me´dica
q: Alice e´ advogada
Proposic¸o˜es Premissas Conclusa˜o
p q p q → p p ∧ q
V V V V V
V F V V F
F V F F F
F F F V F
Argumento inva´lido (fala´cia). Podemos ver na segunda linha da tabela acima, onde
15
mesmo as premissas p e q → p sendo verdadeiras, quando q for falso e p verdadeiro, a
conclusa˜o sera´ falsa. Ou seja, com essas premissas, na˜o conseguimos concluir que Alice
e´ me´dica e advogada.
b) Bob gosta de futebol ou volei. Se Bob gosta de futebol, enta˜o ele gosta de basquete.
Bob na˜o gosta de futebol. Logo, ele na˜o gosta de basquete.
f : Bob gosta de futebol
v: Bob gosta de volei
b: Bob gosta de basquete
Proposic¸o˜es Premissas Conclusa˜o
f v b f ∨ v f → b ¬f ¬b
V V V V V F F
V V F V F F V
V F V V V F F
V F F V F F V
F V V V V V F
F V F V V V V
F F V F V V F
F F F F V V V
Argumento inva´lido (fala´cia). Podemos ver na quinta linha da tabela, em que a conclusa˜o
e´ falsa mesmo todas as premissas sendo verdadeiras.
c) Carol fala portugueˆs ou ingleˆs. Se Carol fala ingleˆs, enta˜o ela na˜o fala japoneˆs. Carol
fala japoneˆs. Logo, Carol fala portugueˆs.
p: Carol fala portugueˆs
i: Carol fala ingleˆs
j: Carol fala japoneˆs
Proposic¸o˜es Premissas Conclusa˜o
p i j p ∨ i i→ ¬j j p
V V V V F V V
V V F V V F V
V F V V V V V
V F F V V F V
F V V V F V F
F V F V V F F
F F V F V V F
F F F F V F F
Argumento va´lido. Na u´nica linha onde as premissas sa˜o verdadeiras a conclusa˜o tambe´m
e´ verdadeira.
21. O famoso detetive Percule Hoirot foi chamado para resolver um assassinato misterioso. Ele
determinou os seguintes fatos:
(1) Lord Charles, o homem assassinado, foi morto com uma pancada na cabec¸a com um
castic¸al
(2) Lady Camila ou a empregada Sara estavam na sala de jantar no momento do assassinato.
(3) Se o cozinheiro estava na cozinha no momento do assassinato, enta˜o o ac¸ougueiro matou
Lord Charles com uma dose fatal de arseˆnico.
16
(4) Se Lady Camila estava na sala de jantar no momento do assassinato, enta˜o o motorista
matou Lord Charles.
(5) Se o cozinheiro na˜o estava na cozinha no momento do assassinato, enta˜o Lady Camila
na˜o estava na sala de jantar quando o assassinato ocorreu.
(6) Se Sara estava na sala de jantar no momento do assassinato, enta˜o o ajudante pessoal
de Lord Charles o matou.
E´ poss´ıvel deduzir quem foi o assassino? Se sim, quem foi o assassino? Justifique transfor-
mando os argumentos em proposic¸o˜es e usando regras de infereˆncia.
Sim. O ajudante pessoal de Lord Charles o matou, conforme demonstrac¸a˜o abaixo.
p: Lord Charles foi morto uma pancada na cabec¸a com um castic¸al
q: Lady Camila estava na sala de jantar no momento do assassinato
r: Sara estava na sala de jantar no momento do assassinato
s: O cozinheiro estava na cozinha no momento do assassinato
t: O motorista matou Lord Charles
u: O ajudante pessoal de Lord Charles o matou
Num. Afirmac¸a˜o Justificativa
(1) p Premissa
(2) s→ ¬p Premissa
(3) ¬s Modus Tolens usando (1) e (2)
(4) ¬s→ ¬q Premissa
(5) ¬q Modus Ponens usando (3) e (4)
(6) q ⊕ r Premissa
(7) r Silogismo disjuntivo usando (6) em (5)
(8) r → u Premissa
∴ u Modus Ponens usando (7) e (8)
Questo˜es de Demonstrac¸o˜es
22. Prove:
a) Se a e b sa˜o valores inteiros pares, enta˜o sua soma tambe´m sera´ par
Prova direta:
Considere a frase do exerc´ıcio no formato da proposic¸a˜o p→ q, assumimos p verdadeiro:
Assumimos a e b pares: a = 2k e b = 2l
Desejamos provar que a soma (a+ b) tambe´m e´ par
a+ b =
2k + 2l = (pois assumimos que a = 2k e b = 2l)
= 2(k + l)
Como k + l e´ um valor inteiro e que um nu´mero multiplicado por 2 sempre sera´ par,
conseguimos provar que, para a e b pares, a sua soma tambe´m sera´ par.
b) Se a e b sa˜o valores inteiros impares, enta˜o sua soma sera´ par
Prova direta:
Considere a frase do exerc´ıcio no formato da proposic¸a˜o p→ q, assumimos p verdadeiro:
Assumimos a e b impares: a = 2k + 1 e b = 2l + 1
Desejamos provar que a soma (a+ b) sera´ par
17
a+ b =
2k + 1 + 2l + 1 = (pois assumimos que a = 2k + 1 e b = 2l + 1)
= 2k + 2l + 2 =
= 2(k + l + 1)
Como k+ l+1 e´ um valor inteiro e que um nu´mero multiplicado por 2 sempre sera´ par,
conseguimos provar que, para a e b impares, a sua soma tambe´m sera´ par.
c) Se n e´ impar enta˜o 3n+5 e´ par
Prova direta:
Considere a frase do exerc´ıcio no formato da proposic¸a˜o p→ q, assumimos p verdadeiro:
Assumimos n impar: n = 2k + 1
Desejamos provar que a soma (3n+ 5) sera´ par
3n+ 5 =
3(2k + 1) + 5 = (pois assumimos que n = 2k + 1)
= 6k + 3 + 5 =
= 6k + 8 =
= 2(3k + 4)
Como 3k + 4 e´ um valor inteiro e que um nu´mero multiplicado por 2 sempre sera´ par,
conseguimos provar que, quando n for impar, o resultado de 3n+ 5 sera´ par.
d) 3n+ 4 e´ par se somente se n e´ par
Considere a frase do exerc´ıcio no formato da proposic¸a˜o p↔ q. Temos que provar p→ q
e q → p.
Prova p→ q: Se 3n+ 4 e´ par enta˜o n e´ par
Prova por contraposic¸a˜o: para provar p→ q podemos provar ¬q → ¬p.
Assumimos ¬q: n e´ impar (ou seja, n = 2k + 1
Temos que provar ¬p: 3n+ 4 e´ impar
3n+ 4 =
3(2k + 1) + 4 = (pois assumimos que n = 2k + 1)
= 6k + 3 + 4 =
= 6k + 6 + 1 =
= 2(3k + 3) + 1
Como 3k + 3 e´ um valor inteiro e um nu´mero multiplicado por2 sempre sera´ par. Se
somamos um a este nu´mero, ele sera´ impar, enta˜o 2(3k + 3) + 1 e´ impar. Assim, con-
seguimos provar que quando n for impar, o resultado de 3n + 4 sera´ impar, ou seja,
¬q → ¬p. Consequentemente, provamos que p→ q, pois p→ q ≡ ¬q → ¬p.
Prova q → p: Se n e´ par enta˜o 3n+ 4 e´ par
Prova direta:
Assumimos p: n e´ par (ou seja, n = 2k)
Temos que provar que 3n+ 4 e´ par
3n+ 4 =
3(2k) + 4 = (pois assumimos que n = 2k)
= 6k + 4 =
= 2(3k + 2)
Como 3k + 2 e´ um valor inteiro e um nu´mero multiplicado por 2 sempre sera´ par, con-
seguimos provar q → p, ou seja, quando n for par, o resultado de 3n+ 5 sera´ par.
e) Todo nu´mero inteiro ı´mpar e´ a diferenc¸a de dois quadrados.
Prova direta:
18
Como n e´ ı´mpar, podemos escrever n = 2k + 1 para algum inteiro k.
Enta˜o, (k + 1)2 − k2 = k2 + 2k + 1− k2 = n.
Questo˜es de Conjuntos e Func¸o˜es
23. Para cada um dos conjuntos abaixo, determine se 4 pertence ao conjunto
a) {4, {4}}: Pertence
b) {4, {{4}}}: Pertence
c) {{{4}}}: Na˜o pertence
d) {{4}, {{4}}}: Na˜o pertence
24. Qual e´ a cardinalidade de cada um dos conjuntos abaixo?
a) {2,{2}}: 2
b) {2, {{2}} }: 2
c) {{{2}}}: 1
d) {{2},{{2}}}: 2
25. Considere A, B e C conjuntos. Mostre, utilizando equivaleˆncias lo´gicas, que
a) (A− C) ∩ (C −B) = ∅
{x|(x ∈ A ∧ x /∈ C) ∧ (x ∈ C ∧ x /∈ B)} =
= {x|x ∈ A ∧ (x /∈ C ∧ x ∈ C) ∧ x /∈ B} = (Prop. Associativa)
= A ∩ (C ∩ C) ∩B =
= A ∩ ∅ ∩B = (Complementares)
= ∅ (Prop. Dominac¸a˜o)
b) (B −A) ∪ (C −A) = (B ∪ C)−A
{x|(x ∈ B ∧ x /∈ A) ∨ (x ∈ C ∨ x /∈ A)} =
{x|x /∈ A ∧ (x ∈ B ∨ x ∈ C)} = (Prop. distributiva)
{x|(x ∈ B ∨ x ∈ C) ∧ x /∈ A} = (Prop. comutativa)
= (B ∪ C)−A
c) (A ∩B) ∪ (A ∩B) = A
{x|(x ∈ A ∧ x ∈ B) ∨ (x ∈ A ∧ x /∈ B)} =
= {x|x ∈ A ∨ (x ∈ B ∧ x /∈ B)} = (Prop. distributiva)
= A ∪ (B ∩B) =
= A ∪ ∅ =(Complementares)
= A (Elementos neutros)
d) (Rosen, 2009) A ∩B = A ∪B
{x|x /∈ (A ∩B)} =
= {x|¬[x ∈ (A ∩B)]} =
= {x|¬(x ∈ A ∧ x ∈ B)} =
= {x|(x /∈ A ∨ x /∈ B)} =(Lei de Morgan)
= {x|(x ∈ A ∨ x ∈ B)} = A ∪B
19
e) (Rosen, 2009) A ∪ (B ∩ C) = (C ∪B) ∩A
{x|¬(x ∈ A ∨ (x ∈ B ∧ x ∈ C))} =
= {x|x /∈ A ∧ ¬(x ∈ B ∧ x ∈ C)} = (Lei de Morgan)
= {x|x /∈ A ∧ (x /∈ B ∨ x /∈ C)} = (Lei de Morgan)
= {x|(x /∈ B ∨ x /∈ C) ∧ x /∈ A} = (Comutativa)
= (B ∪ C) ∩A
26. Seja A = {1} B={u,v} e C={m,n}:
a) Liste todos os elementos de (C ×B)×A.
C ×B = {(m,u), (m, v), (n, u), (n, v)}
(C ×B)×A = {((m,u), 1), ((m, v), 1), ((n, u), 1), ((n, v), 1)}
b) Liste todos os elementos do conjunto poteˆncia de A×B (ou seja, P (A×B))
A×B = {(1, u), (1, v)}
P (A×B) = {∅, {(1, u)}, {(1, v)}{(1, u), (1, v)}}
27. Seja X = {a, b, c}, Y = {1,2,3}. Considere as func¸o˜es X → Y abaixo, classifique-as (se
poss´ıvel) como: injetora, sobrejetora, na˜o e´ uma func¸a˜o.
a) f(a) = 1, f(b) = 2, f(c) = 2: E´ uma func¸a˜o, mas na˜o e´ injetora nem sobrejetora
b) g(a) = 1, g(b) = 2, g(c) = 3: E´ uma func¸a˜o injetora e sobrejetora
c) h(a) = 1, h(b) = 2, h(b) = 3: Na˜o e´ uma func¸a˜o
d) i(a) = 1, i(b) = 2, i(c) = 2: Na˜o e´ nem injetora nem sobrejetora
e) j(a) = 1, j(b) = 1, j(c) = 2: Na˜o e´ nem injetora nem sobrejetora
20