Exercícios - Lógica Proposicional

Prévia do material em texto

Matema´tica Ba´sica
Lista de Exerc´ıcios 01
Lo´gica Proposicional
1. Quais dessas sentenc¸as sa˜o proposic¸o˜es? Quais sa˜o os valores-verdade das que sa˜o
proposic¸o˜es?
(a) Curitiba e´ a capital do Parana´.
(b) Joinville e´ a capital de Santa
Catarina.
(c) 2+3=5.
(d) 5+7=10.
(e) x+2=11.
(f) Responda esta questa˜o.
2. Qual e´ a negac¸a˜o de cada proposic¸a˜o a seguir?
(a) Hoje e´ quinta-feira.
(b) Na˜o ha´ poluic¸a˜o em Sa˜o Paulo.
(c) 2 + 1 = 3.
(d) O vera˜o no Rio e´ quente e
ensolarado.
3. Considere que p e q sa˜o as proposic¸o˜es: “Nadar na praia em Recife e´ permitido”e
“Foram descobertos tubaro˜es perto da praia”, respectivamente. Expresse cada uma
dessas proposic¸o˜es compostas como um sentenc¸a em portugueˆs.
(a) ¬q
(b) p ∧ q
(c) ¬p ∨ q
(d) p→ ¬q
(e) ¬q → p
(f) ¬p→ ¬q
(g) p↔ ¬q
(h) ¬p ∧ (p ∨ ¬q)
4. Considere que p e q sa˜o proposic¸o˜es:
p : Esta´ abaixo de zero.
q : Esta´ nevando.
Escreva estas proposic¸o˜es usando p,q e concectivos lo´gicos.
(a) Esta´ abaixo de zero e nevando.
(b) Esta´ abaixo de zero, mas na˜o esta´ nevando.
(c) Na˜o esta´ abaixo de zero e na˜o esta´ nevando.
(d) Esta´ ou nevando ou abaixo de zero (ou os dois).
(e) Se esta´ abaixo de zero, esta´ tambe´m nevando.
(f) Esta´ ou nevando ou abaixo de zero, mais na˜o esta´ nevando se estiver abaixo
de zero.
(g) Para que esteja abaixo de zero e´ necessa´rio, e suficiente, que esteja nevando.
5. Considere que p e q sa˜o proposic¸o˜es:
p : Voceˆ dirige a mais de 100 km/h.
q : Voceˆ recebe uma multa por excesso de velocidade.
Escreva estas proposic¸o˜es usando p, q e conectivos lo´gicos.
(a) Voceˆ na˜o dirige a mais de 100 km/h
(b) Voceˆ dirige a mais de 100 km/h, mas na˜o recebe uma multa por excesso de
velocidade.
(c) Voceˆ recebera´ uma multa por excesso de velocidade, se voceˆ dirige a mais
de 100 km/h.
(d) Se voceˆ na˜o dirigi a mais de 100 km/h, voceˆ na˜o recebera´ uma multa por
excesso de velocidade.
(e) Dirigir a mais de 100 km/h e´ suficiente para receber uma multa por excesso
de velocidade.
(f) Voceˆ recebeu uma multa por excesso de velocidade, mas voceˆ na˜o dirigia a
mais de 100 km/h.
(g) Sempre que receber uma multa por excesso de velocidade, voceˆ estara´
dirigindo a mais de 100 km/h.
6. 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 e r e conectivos lo´gicos.
(a) As bagas esta˜o maduras ao longo da trilha, mas os urso-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-cinzentos 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.
7. Determine se cada uma destas proposic¸o˜es condicionais e´ verdadeira ou falsa.
(a) Se 1+1=2, enta˜o 2+2=5.
(b) Se 1+1=3, enta˜o 2+2=4.
(c) Se 1+1=3, enta˜o 2+2=5.
(d) Se macacos podurem voar, enta˜o
1+1=3.
8. Para cada uma dessas sentenc¸as, determine se o OU e´ inclusivo ou exclusivo.
Explique sua resposta.
(a) Cafe´ ou cha´ vem com jantar.
(b) Uma senha deve ter ou menos treˆs d´ıgitos ou oito caracteres de
comprimento.
(c) O pre´-requisito para o curso e´ um curso em teoria dos nu´meros ou um curso
de criptorafia.
(d) Voceˆ pode jogar usando dolares americanos ou euros.
9. Para cada sentenc¸a indique seu significado caso em que o OU seja inclusivo, e caso
o OU seja exclusivo. Quais dos significados do OU voceˆ acha mais prova´vel?
(a) Para cursar matema´tica discreta, voceˆ deve ter tido ca´lculo ou um curso de
cieˆncia da computac¸a˜o.
(b) Quando voceˆ compra um novo carro na companhia Acme Motor, voceˆ pega
de volta 2000 reais ou um empre´stimo de 2%.
(c) Jantar para dois inclui dois itens da coluna A ou treˆs itens da coluna B.
(d) A escola fechara se cair mais de um metro de neve ou se a sensac¸a˜o te´rmica
estiver abaixo de -10oC.
10. Passe as proposic¸o˜es abaixo para a forma “se p, enta˜o q”(em portugueˆs).
(a) Neva sempre que o vento sopra do nordeste.
(b) As macieiras florescera˜o se continuar quente por uma semana.
(c) O Palmeiras ganhar o campeonato implica derrotar o Sa˜o Paulo.
(d) E´ necessa´rio andar 8 milhas para chegar ao topo do “Pico da Neblina”.
(e) Para conseguir mandato como professor, e´ suficiente ser famoso
mundialmente.
(f) Se voceˆ dirigir por mais de 400 milhas, tera´ de comprar gasolina.
(g) Sua garantia e´ va´lida apenas se voceˆ comprou seu aparelho de som em
menos de 90 dias.
(h) Jan nadara´ a menos que a a´gua esteja muito fria.
11. Passe as proposic¸o˜es abaixo para a forma “p se e somente se q”(em portugueˆs).
(a) Se esta´ calor la´ fora, voceˆ compra um sorvete e se voceˆ comprar um sorvete
e´ porque esta´ calor la´ fora.
(b) Para que voceˆ ganhe na loteria, e´ necessa´rio e suficiente que voceˆ tenha o
u´nico bilhete premiado.
(c) Voceˆ sera´ promovido apenas se voceˆ tiver contatos, e voceˆ so´ tera´ contatos
se for promovido.
(d) Se voceˆ assistir muita TV sua mente se deteriorara´, e vice-versa.
(e) Os trens atrasam exatamente nos dias em que eu os pego.
12. Determine a oposta, a contrapositiva e a inversa de cada uma das proposic¸o˜es
condicionais abaixo.
(a) Se nevar hoje, esquiarei amanha˜.
(b) Eu venho a` aula sempre que ha´ uma prova.
(c) Um inteiro positivo e´ um primo apenas se na˜o tem divisores ale´m de 1 e dele
mesmo.
13. Quantas linhas aparece em uma tabela verdade para cada uma destas proposic¸o˜es
compostas?
(a) p→ ¬p
(b) (p ∨ ¬r) ∧ (q ∨ ¬s)
(c) q ∨ p ∨ ¬s ∨ ¬r ∨ ¬t ∨ u
(d) (p ∧ r ∧ t)↔ (q ∧ t)
14. Construa uma tabela verdade para cada uma destas proposic¸o˜es compostas.
(a) p ∧ ¬p
(b) p ∨ ¬p
(c) (p ∨ ¬q)→ q
(d) (p ∨ q)→ (p ∧ q)
(e) (p→ q)↔ (¬q → ¬p)
(f) (p→ q)→ (q → p)
15. Construa uma tabela verdade para cada uma destas proposic¸o˜es compostas.
(a) (p ∨ q)→ (p⊕ q)
(b) (p⊕ q)→ (p ∧ q)
(c) (p ∨ q)⊕ (p ∧ q)
(d) (p↔ q)⊕ (¬p↔ q)
(e) (p↔ q)⊕ (¬p↔ ¬r)
(f) (p⊕ q)→ (p⊕ ¬q)
16. Construa uam tabela verdade para cada uma destas proposic¸o˜es compostas.
(a) p→ ¬q
(b) ¬p↔ q
(c) (p→ q) ∨ (¬p→ q)
(d) (p→ q) ∧ (¬p→ q)
(e) (p↔ q) ∨ (¬p↔ q)
(f) (¬p↔ ¬q)↔ (p↔ q)
17. Construa uma tabela verdade para cada uma destas proposic¸o˜es compostas.
(a) p→ (¬q ∨ r)
(b) ¬p→ (q → r)
(c) (p→ q) ∨ (¬p→ r)
(d) (p→ q) ∧ (¬p→ r)
(e) (p↔ q) ∨ (¬q ↔ r)
(f) (¬p↔ ¬q)↔ (q ↔ r)
18. Construa uma tabela-verdade para (p↔ q)↔ (r ↔ s).
19. Expresse estas especificac¸o˜es de sistema usando as proposic¸o˜es p “A mensagem e´
verificada contra v´ırus” e q “A mensagem e´ enviada de um sistema desconhecido”,
juntamente com conectivos lo´gicos.
1
(a) “A mensagem e´ verificada contra v´ırus sempre que a mensagem e´ enviada de
um sistema desconhecido.”
(b) “A mensagem foi enviada de um sistema desconhecido, mas na˜o foi
verificada contra v´ırus.”
(c) “E´ necessa´rio verificar a mensagem contra v´ırus sempre que ela for enviada
de um sistema desconhecido”
(d) “Quando a mensagem na˜o e´ enviada de um sistema desconhecido, na˜o e´
verificada contra v´ırus.”
20. Uma cidade possui apenas 2 tipos de pessoas: os que sempre dizem a verdade e os
que sempre mentem. Imagine que voceˆ encontrou 2 pessoas desta cidade, chamadasA e B. O que voceˆ pode concluir de cada situac¸a˜o abaixo?
(a) A diz: “Ao menos um de no´s mente”e B na˜o diz nada.
(b) A diz: “Eu minto ou B diz a verdade”e B na˜o diz nada.
(c) A diz: “No´s dois mentimos”e B na˜o diz nada.
(d) A diz “No´s dois falamos a verdade”, e B diz “A mente”.
(e) Ambos, A e B, dizem “Eu falo a verdade”.
Os exerc´ıcios a seguir sa˜o quebra-cabec¸as que podem ser resolvidos traduzindo
as proposic¸o˜es em expresso˜es lo´gicas, e produzindo argumentos a partir destas
expresso˜es usando a tabela-verdade.
21. Steve quer determinar os sala´rios relativos de treˆs colegas de trabalho usando dois
fatos. Primeiro, ele sabe que se Fred na˜o tem o maior sala´rio dos treˆs, enta˜o Janice
tem. Segundo, ele sabe que se Janice na˜o tem o sala´rio mais baixo, enta˜o Maggie
e´ a mais bem paga. E´ poss´ıvel determinar os sala´rios relativos de Fred, Maggie e
Janice a partir do que Steve sabe? Se sim, quem tem o sala´rio maior e quem tem o
sala´rio menor? Exponha seus argumentos.
22. Um detetive entrevistou quatro testemunhas de um crime. A partir das histo´rias
das testemunhas, o detetive concluiu que, se o mordomo esta´ dizendo a verdade,
enta˜o o cozinheiro tambe´m esta´; o cozinheiro e o jardineiro, ambos, na˜o podem
estar dizendo a verdade; o jardineiro e o zelador, ambos, na˜o esta˜o mentindo; e se
o zelador esta´ dizendo a verdade, enta˜o o cozinheiro esta´ mentindo. Para cada uma
das quatro testemunhas, o detetive pode determinar se a pessoa esta´ mentindo ou
dizendo a verdade? Exponha seus argumentos.
Respostas:
1. (a) sim, V.
(b) sim, F.
(c) sim, V.
(d) sim, F.
(e) na˜o.
(f) na˜o.
2. (a) Hoje na˜o e´ quinta-feira.
(b) Ha´ poluic¸a˜o em Sa˜o Paulo.
(c) 2+1 e´ diferente 3.
(d) O vera˜o no rio na˜o e´ quente e
nem ensolarado.
3. (a) Na˜o foram descobertos tubaro˜es perto da praia.
(b) Nadar na praia em Recife e´ permitido, e foram descobertos tubaro˜es perto
da praia.
(c) Nadar na praia em Recife na˜o e´ permitido, ou foram descobertos tubaro˜es
perto da praia.
(d) Se nadar na praia de Recife e´ permitido, enta˜o na˜o foram descobertos
tubaro˜es perto da praia.
(e) Se tubaro˜es na˜o foram descobertos perto da praia, enta˜o nadar na praia de
Recife e´ permitido.
(f) Se nadar na praia de Recife na˜o e´ permitido, enta˜o foram descobertos
tubaro˜es perto da praia.
(g) Nadar na praia de Recife e´ permitido, se e somente se, na˜o foram descobertos
tubaro˜es perto da praia.
(h) Nadar na praia de Recife na˜o e´ permitido e, ou nadar na praia em Nova
Jersey e´ permitido ou foram descobertos tubaro˜es perto da praia. (Observe
que fomos capazes de incorporar os pareˆnteses pelo uso do primeira ”ou”na
segunda metade da sentenc¸a.)
4. (a) p ∧ q
(b) p ∧ ¬q
(c) ¬p ∧ ¬q
(d) p ∨ q
(e) p→ q
(f) (p ∨ q) ∧ (p→ ¬q)
(g) p↔ p
5. (a) ¬p
(b) p ∧ ¬q
(c) p→ q
(d) ¬p→ ¬q
(e) p→ q
(f) q ∧ ¬p
(g) q → p
6. (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
7. (a) F (b) V (c) V (d) V
8. (a) OU exclusivo: voceˆ recebe apenas uma bebida.
(b) OU inclusivo: senhas longas podem ter qualquer combinac¸a˜o de s´ımbolos.
(c) OU inclusivo: um estudante com ambos os cursos esta´ ainda mais
qualificado.
(d) Ambas as interpretac¸o˜es sa˜o poss´ıveis; um viajante poderia querer pagar
com uma mistura das duas moedas, ou a loja poderia na˜o permitir isso.
9. (a) Ou inclusivo: e´ permitido cursar matema´tica discreta se voceˆ faz ca´lculo
ou cieˆncia da computac¸a˜o ou ambos. Ou exclusivo: e´ permitido cursar
matema´tica discreta se voceˆ faz ca´lculo ou cieˆncia da computac¸a˜o, mas na˜o
se voceˆ faz ambos. E´ mais prova´vel que a intenc¸a˜o tenha sido usar o ou
inclusivo.
(b) Ou inclusivo: voceˆ pode ter um desconto, ou voceˆ pode conseguir uma taxa
de juros baixa, ou voceˆ pode ter tanto o desconto quanto uma taxa de juros
baixa. OU exclusivo: voceˆ pode ter o desconto, ou voceˆ pode conseguir uma
taxa de juros baixa, mas voceˆ na˜o pode ter tanto o desconto quanto uma
taxa de juros baixa. E´ mais prova´vel que a intenc¸a˜o tenha sido usar o ou
exclusivo.
(c) Ou inclusivo: voceˆ pode pedir dois itens da coluna A e nenhuma da coluna B,
ou treˆs itens da coluna B, e nenhuma da coluna A, ou cinco itens, incluindo
dois da coluna A e treˆs da coluna B. Ou exclusivo: voceˆ pode pedir dois itens,
da coluna A ou treˆs itens da coluna B, mas na˜o ambos.e` quase certo que a
intenc¸a˜o tenha sido usar o ou exclusivo.
(d) Ou inclusivo: Mais de um metro de neve ou sensac¸a˜o te´rmica abaixo de -
10oC, ou ambos, fara˜o com que a escola seja fechada. Ou exclusivo: Mais
de um metro de neve ou sensac¸a˜o te´rmica do vento abaixo de -10oC, mas
na˜o ambos, fara˜o com que a escola seja fechada. Com centeza, a intenc¸a˜o
foi usar o ou inclusivo.
10. (a) Se o vento soprar no nordeste, enta˜o nevara´.
(b) Se continuar quente por uma semana, enta˜o as macieiras florescera˜o.
(c) Se o Palmeiras ganhar o campeonato, enta˜o ele ganhou do Sa˜o Paulo.
(d) Se voceˆ chegar ao topo do “Pico da Neblina”, enta˜o voceˆ deve ter andado 8
milhas.
(e) Se voceˆ for famoso mundialmente, enta˜o voceˆ conseguira´ um mandato como
professor.
(f) Se voceˆ dirigi por mais de 400 milhas, enta˜o voceˆ tera´ que comprar gasolina.
(g) Se a sua garantia for va´lida, enta˜o voceˆ deve ter comprado seu aparelho de
som em menos de 90 dias.
(h) Se a a´gua na˜o estiver muito fria, enta˜o Jan nadara´.
11. (a) Voceˆ compra um sorvete se e somente se estiver calor la´ fora.
(b) Voceˆ ganhara´ na loteria se e somente se voceˆ tiver o u´nico bilhete premiado.
(c) Voceˆ sera´ promovido se e somente se voceˆ tiver contatos.
(d) Sua mente se deteriorara´ se e somente se voceˆ assistir muita TV.
(e) O treˆm se atrasara´ se e somente se for um dia que eu pego trem.
12. (a) Rec´ıproca: “Eu esquiarei amanha˜ se neva hoje.”Contrapositiva: “Se eu na˜o
esquiar amanha˜, enta˜o na˜o tera´ nevado hoje.”Inversa: “Se na˜o nervar hoje
enta˜o, eu na˜o esquiarei amanha˜.”
(b) Rec´ıproca: “Se eu vier a` aula, enta˜o havera´ uma prova.”Contrapositiva: “Se
eu na˜o vier a` aula, enta˜o na˜o havera´ uma prova.”Inversa: “Se na˜o houver
uma prova, enta˜o eu na˜o virei a` aula.”
(c) Rec´ıproca: “Um inteiro positivo e´ um primo se ele na˜o tiver divisores ale´m
de 1 e dele mesmo.”Contrapositiva: “Se um inteiro positivo tiver um divisor
ale´m de 1 e dele mesmo, enta˜o ele na˜o e´ primo.”Inversa: “Se um inteiro
positivo na˜o for primo, enta˜o ele tem um divisor alem de 1 e dele mesmo.”
13. (a) 2 (b) 16 (c) 64 (d) 16
14. U´ltima coluna da tabela:
(a) F F
(b) V V
(c) V F V F
(d) V F F V
(e) V V V V
(f) V V F V
15. (a) F V V V
(b) V F F V
(c) F V V F
(d) V V V V
(e) F V V F F V V F
(f) V F F V
16. (a) F V V V
(b) F V V F
(c) V V V V
(d) V F V F
(e) V V V V
(f) V V V V
17. (a) V F V V V V V V
(b) V V V V V F V V
(c) V V V V V V V V
(d) V V F F V F V F
(e) V V V F F V V V
(f) V F V F F V F V
18. V F F V F V V F F V V F V F F V
19. (a) q → p
(b) q ∧ ¬p
(c) q → p
(d) ¬q → ¬p
20. (a) A diz a verdade e B mente.
(b) A diz a verdade e B diz a
verdade.
(c) A mente e B diz a verdade.
(d) A mente e B diz a verdade.
(e) Ou os dois falam a verdade, ou
os dois mentem.
21. Ordem crescente de sala´rio: Janice, Maggie, Fred. Janice na˜o pode ter o maior
sala´rio, pois neste o menor sala´rio na˜o seria de Janice, o que permitiria concluir
que Maggie tambe´m tem o maior sala´rio. Como Janice na˜o tem o maior sala´rio,
conclu´ımos que Fred tem o maior sala´rio. Como Fred tem o maior sala´rio, Maggie
na˜o pode ter o maior sala´rio, e com isso podemos concluir que Janice tem o menor
sala´rio.
22. M : mordomo diz a verdade.
C: cozinheiro diz a verdade.
J: jardineiro diz a verdade.
Z: zelador diz a verdade.
M → C, ¬C ∧ ¬J, J ∨ Z,¬Z ∨ ¬C.
Se o zelador esta´ falando a verdade, conclu´ımos que o cozinheiro esta´ mentindo
(pois ¬Z ∨ ¬C). Se o zelador esta´ mentindo, conclu´ımos que o jardineiro esta´
falando a verdade (pois J∨Z). Portanto, o jardineiro fala a verdade ou o cozinheiro
mente (ou seja, J ∨ ¬C).
Se o jardineiro mente, enta˜o o cozinheiro mente (pois J ∨¬C). Se o jardineiro fala
a verdade, temos que o cozinheiro mente (pois ¬C ∧ ¬J). Isto permite concluir
que o cozinheiro mente.
Como o cozinheiro mente, conclu´ımos que o mordomo tambe´m mente (pois
M → C).
Assim, o detetive pode determinar que o mordomo e o cozinheiro esta˜o mentindo,
mas na˜o pode determinar se o jardineiro esta´ dizendo a verdade ou se o zelador
esta´ dizendo a verdade.
2