MatematicaDiscreta Lista 1

Prévia do material em texto

1
 
Universidade Federal Rural de Pernambuco 
Disciplina: Matemática Discreta I 
Professor: Pablo Azevedo Sampaio 
Semestre: 2017.1 
 
Primeira Lista de Exercícios 
 
Parte A: Operadores lógicos, Tradução de/para Linguagem Natural 
 
1) Considerando que p e q são proposições verdadeiras, e que r e s são proposições 
falsas, determine o valor-verdade de cada proposição composta abaixo: 
 
a) q → (p  r) 
b) (r  s) → p 
c) r  (s → q) 
d) p ↔ r 
e) q ↔  s 
f) ( r   s) → (p ↔ q) 
g)  s → (p  r) 
 
2) Considere as proposições p , q e r abaixo: 
p : “Você está com gripe”. 
q : “Você perde a última prova”. 
r : “Você é aprovado no curso”. 
 
Com base nessas definições de p, q e r, expresse cada uma das proposições compos-
tas dadas abaixo como uma frase em português: 
 
Exemplo:  p 
Resposta: “Você não está com gripe”. 
 
a) p → q 
b)  q ↔ r 
c) q →  r 
d) p  q  r 
e) (p →  r)  (q →  r) 
f) (p  q)  ( q  r) 
 
3) Cada uma das frases abaixo pode ser representada por uma implicação x → y. Diga 
quais são a condição (ou antecedente) x e o resultado (ou consequente) y de cada 
frase abaixo: 
 
Exemplo: “Se a função é derivável, então ela é contínua”. 
Resposta: x: “A função é derivável”, 
 y: “A função é contínua”. 
 
a) Leo é pego sempre que ele trapaceia. 
 2
*) Você pode acessar o site se você pagar uma taxa de assinatura. (fiz em sala) 
b) Você pode acessar o site somente se você pagar uma taxa de assinatura. 
c) Você escolhe a companhia certa, se conhecer as pessoas certas. 
d) Jan nadará, a menos que a água esteja muito fria. 
e) É necessário lavar o carro do chefe para ser promovido. 
f) Uma condição suficiente para a garantia ser válida é que a compra tenha acon-
tecido há menos de um ano. 
 
4) Considere que p, q e r são as seguintes proposições: 
 
p : “Existem ursos na área”. 
q : “Caminhar na trilha é seguro”. 
r : “Os frutos estão maduros (ao longo da trilha)”. 
 
Escreva as afirmações abaixo usando p, q e r e conectivos lógicos: 
 
a) Há ursos na área, mas caminhar na trilha é seguro. 
b) Não há ursos na área e caminhar na trilha é seguro, mas os frutos estão madu-
ros ao longo da trilha. 
c) Se existem ursos na área e os frutos estão maduros, não é seguro caminhar na 
trilha. 
d) Para haver ursos na área, é necessário que os frutos estejam maduros. 
e) Se os frutos estão maduros, fazer caminhada na trilha é seguro se e somente se 
não há ursos na área. 
f) Não é seguro caminhar na trilha, mas não há ursos na área e os frutos estão 
maduros ao longo da trilha. 
g) Caminhar na trilha não é seguro sempre que os frutos estão maduros e há ursos 
na área. 
h) *Para a caminhada ser segura, é necessário (mas não se sabe se é suficiente), 
que os frutos não estejam maduros e que não haja ursos na área. 
 
**) Divida cada afirmação abaixo nas proposições mais básicas possíveis, represente-as 
com variáveis proposicionais e, depois, crie uma fórmula para representar o sentido 
completo de cada frase: 
 
a) 2 é par e primo. 
b) Um número é primo maior que 10, somente se for diferente de 2. 
c) Um inteiro x é par se e somente se x não é ímpar. 
d) Uma condição suficiente para x2 ser par é x ser par. 
e) Uma condição necessária para x ser divisível por 4 é x ser par. 
 
 
Parte B: Equivalências e Inferência Lógica 
 
5) Prove ou disprove a validade de cada equivalência lógica abaixo construindo as 
tabelas-verdades das proposições envolvidas. 
 
a)  (a → b) ≡ (a → b) 
b)  (a → b) ≡ (a  b) 
c) (a  b) ≡  (a  b) 
 3
d)  (a ↔ b) ≡ (a ↔ b) 
 
6) Reescreva cada uma das duas afirmações abaixo de uma ou duas formas diferentes, 
usando equivalências lógicas como base para essa reescrita. 
 
a) Se o filho almoçou, a mãe o levou ao cinema. 
b) Se n é par e maior que 2, então n não é primo. 
c) Não é verdade que n é par ou primo. 
d) G é um grafo Euleriano sse G é conectado e não tem vértice de grau ímpar. 
e) G não é Hamiltoniano e G não é Euleriano. 
 
7) Em cada um dos raciocínios abaixo verifique se a última afirmação é ou não uma 
conclusão válida, tomando as afirmações anteriores como premissas. Se a conclusão 
for válida, indique o nome da regra de inferência. 
 
a) Se o animal é um leopardo, então ele tem manchas. O animal tem manchas. 
Logo, ele é um leopardo. 
b) Se um inseto é da família dos cupins, então ele é atraído pelo fogo. Este inseto 
não é atraído pelo fogo. 
Logo, este inseto não é cupim. 
c) Os alunos dormem, se a aula é monótona. A aula não é monótona. 
Logo, os alunos não dormem. 
d) Hoje está quente e úmido. 
Logo, hoje está úmido. 
e) Quando chove, alaga. Sempre que alaga, tem congestionamento. Então, quan-
do chove tem congestionamento. 
f) Alguém contou um segredo que só as pessoas Bê e Cê sabiam. A pessoa Bê 
não contou. Então, foi Cê quem contou. 
g) Hagar foi à feira. Logo, Hagar foi à feira ou ao zoológico. 
 
8) Para cada argumento da questão acima, faça: 
 
a) Dê uma representação formal do argumento, usando fórmulas proposicionais. 
Trate-os como (supostas) regras de inferência, identificando premissas e con-
clusão. 
b) Usando tabelas-verdade, prove a sua resposta da questão anterior. Ou seja, 
construa tabelas-verdade para mostrar, para cada “suposta regra”, se ela é ou 
não uma regra de inferência. 
 
9) Crie um argumento lógico (de inferência lógica) aplicando as regras de inferência 
do material complementar sucessivamente, até concluir a proposição o. Essas são as 
premissas. 
1. b 
2. b  (i  j) 
3.  g  o 
4. ( g)   (n  m) 
5. i  n 
 
 4
10) Você está projetando a base de conhecimento de um robô que raciocina por meio de 
inferências lógicas. Considere que cada variável proposicional se refere a alguma 
ação do robô, e ela é verdadeira se o robô pode realizar (ou já realizou) aquela ação. 
Use inferência lógica para indicar a seqüência de ações que o robô precisa seguir até 
realizar a ação g. 
 
1. a 3. (d  e)  f 5. (a  b)  d 
2. b 4. d   e 6.  g   f 
 
 
11) Em uma investigação de um crime em uma mansão, a polícia analisou os depoimen-
tos dos funcionários da mansão e, então, chegou às seguintes conclusões: 
C1 – O jardineiro ou o zelador (ou ambos) diz a verdade. 
C2 – Se o mordomo diz a verdade, então o zelador está mentindo. 
C3 – O jardineiro mente. 
C4 – Se o mordomo ou o porteiro está mentindo, então o cozinheiro diz a verda-
de. 
C5 – Se o zelador e o cozinheiro (ambos) dizem a verdade, então o porteiro 
também diz a verdade. 
Assumindo que essas informações são verdadeiras, diga se cada um dos funcioná-
rios – o zelador, o porteiro, o mordomo e o cozinheiro – estão dizendo a verdade ou 
não. 
Para isso, represente cada afirmação acima como uma fórmula lógica. Depois, tra-
tando as fórmulas como premissas, use regras de inferência para chegar às respostas. 
 
12) Crie um conjunto de fórmulas lógicas para servirem de premissas em um raciocínio 
lógico e preencha-as na tabela abaixo. As premissas devem satisfazer estas condi-
ções: 
 Deve haver, pelo menos, cinco premissas distintas, dadas como fórmulas pro-
posicionais. 
 As premissas (no total) devem usar, pelo menos, quatro variáveis proposicio-
nais, chamadas assim: a, b, c, d, e, ... 
 As premissas devem servir para criar um argumento lógico que chegue à conclu-
são c (a negação de c). 
 
13) Mostre como uma tabela o argumento lógico que, partindo das suas premissas esco-
lhidas na seção anterior, conclua c. Condições: 
 Este argumento tem que usar, pelo menos, três regras de inferência distintas. 
 Não pode existir um argumento que, usando menos regras, chegue à conclusão 
desejada. 
 
14) (Extra) Os bandidos Gavião e Falcão assaltaram um banco na cidade Xis. Após o 
assalto, o delegado da cidadeXis apurou os seguintes fatos: 
F1 – Se Gavião e Falcão saíram da cidade, então o dinheiro não ficou com Ga-
vião. 
F2 – Se havia um caixa eletrônico em frente ao banco, então o dinheiro ficou 
com Gavião. 
F3 – Gavião e Falcão saíram da cidade. 
F4 – Havia um caixa eletrônico em frente ao banco ou o dinheiro foi entregue à 
mulher de Gavião. 
 5
Assumindo que essas informações são comprovadamente verdadeiras, responda: 
 
a) A proposição F2 é logicamente equivalente à proposição “Se o dinheiro não fi-
cou com Gavião, então não havia um caixa eletrônico em frente ao banco”. Se 
não for, indique uma proposição equivalente em português. 
b) A negação da proposição F4 é logicamente equivalente a “Não havia um caixa 
eletrônico em frente ao banco ou o dinheiro não foi entregue à mulher de Gavi-
ão”. Se não for, indique, em português, uma proposição que seria equivalente à 
negação de F4. 
c) É possível concluir que “o dinheiro foi entregue à mulher de Gavião”? Explique 
sua resposta. 
 
15) (Extra) No estudo dos circuitos digitais (usados, por exemplo, para projetar os pro-
cessadores), as portas lógicas são pequenos circuitos que calculam o resultado de 
operações lógicas básicas. Nesses tipos de circuitos, o equivalente das variáveis 
proposicionais são os fios “abertos” desenhados à esquerda e que representam sinais 
de entrada para portas. Seguem as principais portas lógicas: 
 
Nome Desenho 
AND 
 
OR 
 
NOT 
 
 
Usando as portas lógicas dadas acima, desenhe os circuitos que calculam os resulta-
dos das seguintes fórmulas. 
 
a) ( p)  q 
b)  (p  q) 
c) (p)  (q) 
d) p  (q  r) 
 
 
Observação: questões * e ** foram adicionadas depois da primeira divulgação da lista. 
 
 
 
 
 
 
 
“Para o tolo, o cometer desordem é divertimento; 
mas para o homem entendido [divertimento] é o ter sabedoria.” 
(Provérbios cap. 10, verso 23)