Exercícios de Matemática Discreta

Prévia do material em texto

9	
  
EXERCÍCIOS	
  EXTRA-­‐CLASSE	
  
	
  
	
  
1. Sabendo	
   que	
   os	
   valores	
   de	
   juízo	
   das	
   proposições	
   p	
   e	
   q	
   são,	
   respectivamente,	
   V	
   e	
   F,	
  
determine	
  o	
  valor	
  de	
  juízo	
  de	
  cada	
  uma	
  das	
  seguintes	
  proposições:	
  
	
  
	
  
	
  
2. Construa	
  as	
  tabelas-­‐verdade	
  para	
  cada	
  uma	
  das	
  fórmulas	
  abaixo	
  e	
  identifique	
  as	
  que	
  são	
  
tautologias	
  ou	
  contradições:	
  
	
  
	
  
	
  
	
  
	
  
3. Prove,	
  usando	
  tabelas-­‐verdade,	
  as	
  seguintes	
  equivalências:	
  
	
  
	
  
	
   10	
  
	
  
	
  
	
  
	
  
4. Prove,	
  usando	
  tabelas-­‐verdade,	
  que	
  os	
  seguintes	
  novos	
  conectivos	
  podem	
  ser	
  expressos	
  
usando	
  os	
  conectivos	
  estudados	
  nesta	
  aula:	
  
	
  
	
  
	
  
	
  
	
   7	
  
	
  
	
  
EXERCÍCIOS	
  EXTRA-­‐CLASSE	
  
	
  
1. Considere	
  ℝ	
  o	
  conjunto	
  dos	
  números	
  reais.	
  Quais	
  das	
  sentenças	
  abaixo	
  são	
  predicados	
  
sobre	
  este	
  conjunto	
  ?	
  
	
  
	
  
	
  
2. Negue	
  cada	
  um	
  dos	
  predicados	
  abaixo,	
  obtendo	
  um	
  predicado	
  equivalente:	
  
	
  
	
  
	
  
3. Considere	
  o	
   conjunto	
  A={1,2,3,4,5,6,7,8,9}.	
   Encontre	
  um	
   contra-­‐exemplo	
   em	
  A,	
   isto	
   é,	
  
um	
  elemento	
  em	
  A	
  que	
  torne	
  cada	
  um	
  dos	
  predicados	
  abaixo	
  falso:	
  
	
  
	
  
	
  
	
  
4. Considere	
   o	
   conjunto	
   A={2,3,4,5,6,7,8,9}.	
   Verifique	
   se	
   as	
   sentenças	
   abaixo	
   são	
  
predicados	
  sobre	
  A:	
  
	
  
	
  
	
  
 9 
 
EXERCÍCIOS EXTRA-CLASSE 
 
1. Mostre, utilizando os axiomas estudados em aula, que os programas abaixo possuem 
corretude parcial: 
 
(a) { Y = 2 } X:=2 { Y = X } 
 
(b) { Y = 2  X > 0 } Y:=Y+X { Y > 2 } 
 
(c) { Y = a } 
 IF X > 0 
 THEN Y := Y + X 
 ELSE Y := Y – X 
 FI 
 { Y  a } 
 
(d) {T} 
 R:=X; 
 Q:=0; 
 WHILE YR DO 
 R:=R-Y 
 Q:=Q+1 
 OD 
 { R < Y e X=R+YxQ } 
 
Sugestão: use como invariante do loop while X=R+YxQ. 
 
2. O sistema axiomático de Floyd-Hoare pode ser estendido para conter o comando FOR, 
cujo axioma é mostrado abaixo: 
 
 
 
a. Descreva, informalmente, o que devemos provar para o comando FOR esteja 
correto. 
 
b. Aplique este axioma para mostrar que o programa abaixo está correto 
parcialmente. 
 
 
 
 
 
 
 
 
 
 
 10 
3. O sistema axiomático de Floyd-Hoare pode ser estendido para atribuições com vetores, 
cujo axioma é mostrado abaixo: 
 
 
 
a. Descreva, informalmente, o que devemos provar para a atribuição com vetores esteja 
correta. 
 
b. Aplique este axioma para mostrar que o programa abaixo está correto parcialmente. 
 
 
 
	
   6	
  
§ A	
  prova	
  anterior	
  nos	
  dá	
  um	
  primeiro	
  padrão	
  de	
  prova	
  direta	
  	
  no	
  Isabelle:	
  
	
  
theorem	
  “enunciado	
  do	
  teorema”	
  
	
  	
  	
  proof	
  -­‐	
  
	
  	
  	
  	
  	
  have	
  A:	
  	
  primeiro	
  fato	
  	
  
	
  	
  	
  	
  	
  have	
  B:	
  	
  segundo	
  fato	
  
	
  	
  	
  	
  	
  ...	
  
	
  	
  	
  	
  	
  show	
  "resultado	
  do	
  teorema"	
  by	
  (método	
  de	
  prova)	
  	
  
	
  	
  	
  qed	
  
	
  
§ Se	
  cada	
  passo	
  (A,B,...)	
  da	
  prova	
  estiver	
  correto,	
  então	
  podemos	
  utilizá-­‐los	
  no	
  método	
  de	
  
prova	
  final	
  depois	
  do	
  by.	
  	
  
	
  
	
  
EXERCÍCIOS	
  EXTRA-­‐CLASSE	
  
	
  
1. Prove	
  os	
  seguintes	
  teoremas:	
  
	
  
a. O	
  produto	
  de	
  dois	
  números	
  pares	
  é	
  par.	
  
b. O	
  produto	
  de	
  dois	
  números	
  ímpares	
  é	
  ímpar.	
  
c. Se	
  o	
   sucessor	
  de	
  um	
  número	
  natural	
  n	
  é	
  maior	
  que	
   zero,	
   então	
  o	
   sucessor	
  do	
  
sucessor	
  deste	
  número	
  também	
  é	
  maior	
  que	
  zero.	
  
	
  
d. 𝑝 ∧ 𝑞 ∨ 𝑟 = (𝑝 ∧ 𝑞) ∨ (𝑝 ∧ 𝑟)	
  
e. ¬ 𝑝 ∧ 𝑞 = ¬𝑝 ∨¬𝑞	
  
	
  
	
  
2. Verifique	
  a	
  prova	
  do	
  teorema	
  (c)	
  no	
  Isabelle.	
  	
  
	
  
	
  
	
   6	
  
EXERCÍCIO	
  EXTRA-­‐CLASSE	
  
	
  
1.	
  Os	
   exercícios	
   abaixo	
  misturam	
  as	
   técnicas	
   de	
  prova	
  direta	
   e	
   por	
   contraposição	
   ,	
   de	
   tal	
  
modo	
  que	
  vocês	
  possam	
  verificar	
  qual	
  delas	
  é	
  a	
  mais	
  simples	
  para	
  se	
  obter	
  uma	
  prova:	
  
	
  
a) Para	
  quaisquer	
  números	
  inteiros	
  n,m	
  e	
  p,	
  n+m+p=m+n+p	
  
	
  
b) Para	
  quaisquer	
  números	
  inteiros	
  n,m	
  e	
  p,	
  (n+m)+p=m+(n+p)	
  
	
  
c) Se	
  n	
  e	
  m	
  são	
  números	
  naturais	
  ímpares,	
  se	
  n>m,	
  então	
  n-­‐m	
  é	
  um	
  número	
  par.	
  
	
  
d) Se	
  temos	
  n	
  servidores	
  de	
  impressão	
  e	
  chegam	
  n+1	
  requisições,	
  então	
  teremos	
  pelo	
  
menos	
  um	
  servidor	
  atendendo	
  uma	
  ou	
  mais	
  requisições.	
  
	
  
	
  
2.	
  Verifique	
  as	
  suas	
  provas	
  dos	
  itens	
  a)	
  e	
  b)	
  no	
  software	
  Isabelle.	
  
	
  
	
  
	
   6	
  
	
  
EXERCÍCIO	
  EXTRA-­‐CLASSE	
  
	
  
1. No	
  esquema	
  de	
  prova	
  por	
   redução	
  ao	
  absurdo	
  utilizado	
  no	
   Isabelle,	
  usamos	
  o	
   fato	
  de	
  
que	
  ¬(𝑝 → 𝑞) 	
  é	
   equivalente	
   a	
    𝑝 ∧¬𝑞 .	
   Mostre	
   que	
   isto	
   é	
   verdade	
   construindo	
   as	
  
tabelas-­‐verdade.	
  
	
  
2. No	
  conjunto	
  dos	
  números	
  naturais,	
   podemos	
  definir	
   a	
  noção	
  de	
  divisor.	
  Dizemos	
  que	
  
um	
  número	
  r	
  divide	
  um	
  número	
  n	
  se	
  e	
  somente	
  se	
  existe	
  um	
  número	
  q	
  tal	
  que	
  n=rq.	
  
Mostre	
  que	
  se	
  n	
  for	
  um	
  número	
  primo,	
  então	
  r=1	
  e	
  q=n	
  ou	
  r=n	
  e	
  q=1.	
  	
  
	
  
3. Mostre,	
   utilizando	
   a	
   estratégia	
   por	
   redução	
   ao	
   absurdo,	
   que	
   𝑚𝑑𝑐  (1,𝑛) = 1 	
  é	
  
verdadeiro	
  no	
  conjunto	
  dos	
  números	
  naturais	
  ℕ.	
  
	
  
4. Confirme	
  as	
  provas	
  realizadas	
  nas	
  questões	
  2,3	
  e	
  4	
  com	
  o	
  software	
  Isabelle.	
  	
  
	
  
	
  
 6 
EXERCÍCIOS EXTRA-CLASSE 
 
1. Para cada um dos exercícios feitos em classe, verifique se há uma outra estratégia de 
prova que possa ser aplicada na solução do exercício. 
 
 
	
   11	
  
EXERCÍCIOS	
  EXTRA-­‐CLASSE	
  
	
  
Todos	
  os	
  exercícios	
  propostos	
  a	
  seguir	
  são	
  retirados	
  do	
   livro	
  da	
  referencia	
  básica	
  utilizado	
  
nesta	
  aula:	
  
	
  
	
  
	
  
Utilizando	
   os	
   Diagramas	
   de	
   Venn,	
  mostre	
   graficamente	
   que	
   as	
   duas	
   propriedades	
   abaixo	
  
(chamadas	
  Leis	
  de	
  De	
  Morgan)	
  estão	
  corretas:	
  
	
  
	
  
	
   7	
  
EXERCÍCIOS	
  EXTRA-­‐CLASSE	
  
	
  
1. Para	
  cada	
  uma	
  das	
  provas	
  realizadas	
  na	
  aula	
  de	
  hoje,	
  verifique	
  se	
  há	
  alguma	
  estratégia	
  
diferente	
  (prova	
  direta,	
  por	
  contraposição	
  ou	
  por	
  absurdo)	
  de	
  prova.2. Para	
  cada	
  um	
  dos	
  resultados	
  da	
  Teoria	
  de	
  Conjuntos	
  presentes	
  na	
  tabela	
  abaixo	
  e	
  não	
  
provados	
  em	
  aula,	
  proponha	
  uma	
  estratégia	
  de	
  prova	
  (direta,	
  contraposição	
  ou	
  absurdo)	
  
para	
  eles.	
  
	
  
	
  
	
  	
  	
  	
  	
  
3. Verifique	
  a	
  validade	
  destes	
  resultados	
  no	
  software	
  Isabelle.	
  
 
 
	
   8	
  
EXERCÍCIOS	
  EXTRA-­‐CLASSE	
  
1. Considere	
   o	
   conjunto	
   dos	
   números	
   naturais	
  ℕ.	
   Especifique,	
   na	
   notação	
   de	
   Teoria	
   dos	
  
Conjuntos,	
  as	
  seguintes	
  relações	
  binárias	
  sobre	
  ℕ×ℕ:	
  
(a) um	
  número	
  e	
  seu	
  sucessor	
  
(b) um	
  número	
  e	
  seu	
  antecessor	
  
(c) um	
  número	
  e	
  um	
  dos	
  seus	
  divisores	
  
(d) um	
  número	
  e	
  um	
  dos	
  seus	
  múltiplos	
  
2. Considere	
   o	
   conjunto	
   dos	
   números	
   naturais	
  ℕ.	
   Especifique,	
   na	
   notação	
   de	
   Teoria	
   dos	
  
Conjuntos,	
  as	
  seguintes	
  relações	
  terciárias	
  (3-­‐árias)	
  sobre	
  ℕ×ℕ×ℕ:	
  
(a) dois	
  números	
  e	
  seu	
  mdc	
  
(b) dois	
  números	
  e	
  seu	
  mmc	
  
(c) três	
  números	
  consecutivos	
  
(d) três	
  números	
  pares	
  
(e) três	
  números	
  ímpares	
  
(f) três	
  números	
  primos	
  
3. Na	
  execução	
  da	
  última	
  consulta	
  SQL	
  que	
  fizemos	
  em	
  aula,	
  foi	
  necessária	
  a	
  operação	
  de	
  
junção	
  entre	
  tabelas	
  (relações).	
  Formalize	
  esta	
  operação	
  matematicamente.	
  
	
  
	
  
 
 
	
   9	
  
EXERCÍCIOS	
  EXTRA-­‐CLASSE	
  
1. Sejam	
   A={2,3,4,5}	
   e	
   B={3,4,5,6,10}.	
   Represente	
   cada	
   uma	
   das	
   relações	
   abaixo	
   em	
  
Diagramas	
  de	
  Venn,	
  matrizes	
  e	
  grafos	
  orientados: 
 
2. Classifique	
  as	
  relações	
  abaixo	
  em	
  totais	
  ou	
  parciais.	
  Qual	
  a	
  propriedade	
  deve	
  ser	
  exibida	
  
nos	
  Diagramas	
  de	
  Venn	
  para	
  que	
  a	
  relação	
  seja	
  total	
  ? 
 
3. Verifique	
   se	
   as	
   relações	
   abaixo	
   são	
   injetoras,	
   sobrejetoras,	
   bijetoras	
   ou	
   de	
   nenhum	
  
destes	
   tipos.	
   Qual	
   a	
   propriedade	
   deve	
   ser	
   exibida	
   no	
   diagrama	
   de	
   Venn	
   para	
   que	
   a	
  
relação	
  seja	
  injetora,	
  sobrejetora	
  e	
  bijetora	
  ? 
 
4. Considere	
  novamente	
  o	
  exemplo	
  de	
  composição	
  de	
  relações	
  visto	
  em	
  aula.	
  Represente	
  
cada	
   uma	
   relações	
   como	
  matrizes	
   e	
  mostre	
   que	
   a	
  matriz	
   correspondente	
   à	
   relação	
   C	
  
pode	
  ser	
  obtida	
  pela	
  multiplicação	
  das	
  matrizes	
  correspondentes	
  às	
  relações	
  A	
  e	
  B. 
 
 
	
   10	
  
5. Mostre	
   que	
   a	
   composição	
   da	
   relação	
   identidade	
  𝑖𝑑 ∘ 𝑖𝑑	
  produz	
   a	
   relação	
   identidade.	
  
Verifique	
  a	
  sua	
  prova	
  no	
  software	
  Isabelle. 
6. A	
  operação	
  de	
   composição	
   de	
   relações	
   é	
   uma	
  operação	
   associativa.	
   Para	
   se	
   certificar	
  
disto,	
   prove	
   o	
   seguinte	
   teorema	
   no	
   papel	
   e,	
   sem	
   seguida,	
   verifique	
   o	
   resultado	
   no	
  
Isabelle: 
Teorema:	
  Sejam	
  𝑅 ⊆ 𝐴×𝐵,	
  	
  𝑆 ⊆ 𝐵×𝐶	
  e	
  𝑇 ⊆ 𝐶×𝐷	
  relações	
  binárias.	
  Mostre	
  que: 𝑆 ∘ 𝑅 ∘ 𝑇 =  𝑆 ∘ (𝑅 ∘ 𝑇) 
 
	
   10	
  
EXERCÍCIOS	
  EXTRA-­‐CLASSE	
  
1. Seja	
   A	
   =	
   {1,2,3}	
   .	
   Classifique	
   cada	
   uma	
   das	
   relações	
   abaixo	
   em	
   reflexiva,	
   simétrica	
   ou	
  
transitiva.	
  Algumas	
  delas	
  é	
  uma	
  relação	
  de	
  equivalência	
  ?	
  
	
  
2. Seja	
  A	
  =	
  {a,b,c,d}	
  .	
  Defina	
  endorrelações	
  em	
  A	
  que	
  :	
  
a. R1:	
  só	
  tem	
  a	
  propriedade	
  reflexiva	
  
b. R2:	
  só	
  tem	
  a	
  propriedade	
  simétrica	
  
c. R3:	
  só	
  tem	
  a	
  propriedade	
  transitiva	
  
d. R4:	
  seja	
  reflexiva	
  e	
  transitiva,	
  mas	
  não	
  simétrica	
  
e. R5:	
  seja	
  reflexiva	
  e	
  simétrica,	
  mas	
  não	
  transitiva	
  
	
  
3. Seja	
  A	
  =	
  {1,2,3}	
  .	
  Para	
  cada	
  uma	
  das	
  endorrelações	
  abaixo:	
  
	
  
calcule	
   os	
   fechos	
   simétrico	
   e	
   reflexivo-­‐simétrico	
   e	
   os	
   represente	
   como	
   uma	
  matriz	
   e	
  
como	
  um	
  grafo	
  orientado.	
  	
  
4. Seja	
  A	
  =	
  {a,b,c}	
  .	
  Para	
  cada	
  uma	
  das	
  endorrelações	
  abaixo,	
  verifique	
  quais	
  são	
  e,	
  em	
  caso	
  
afirmativo,	
  mostre	
  as	
  partições	
  definidas	
  pelas	
  classes	
  de	
  equivalência:	
  
	
  
	
   11	
  
EXERCÍCIOS	
  EXTRA-­‐CLASSE	
  
1. Verifique	
  quais	
  das	
  relações	
  abaixo	
  tem	
  a	
  propriedade	
  de	
  ser	
  anti-­‐simétrica.Justifique	
  a	
  
sua	
  resposta.	
  
	
  
2. Verifique	
  quais	
  das	
  relações	
  abaixo	
  são	
  relações	
  de	
  ordem.	
  Justifique	
  a	
  sua	
  resposta.	
  
	
  
3. Suponha	
   que	
   o	
   Diagrama	
   de	
   Hasse	
   abaixo	
   represente	
   um	
   conjunto	
   de	
   tarefas	
   e	
   suas	
  
dependências:	
  
	
  
o quais	
  destas	
  tarefas	
  podem	
  ser	
  executadas	
  de	
  forma	
  independente	
  das	
  outras	
  ?	
  
o quais	
  são	
  as	
  tarefas	
  que	
  dependem	
  de	
  outras	
  para	
  poderem	
  iniciar	
  ?	
  
	
  
	
  
	
  
	
   12	
  
4. Mostre	
  que	
  cada	
  um	
  dos	
  Diagramas	
  de	
  Hasse	
  abaixo	
  são	
  reticulados:	
  
	
  
	
  
5. Construa	
  as	
  relações	
  de	
  ordem	
  definidas	
  por	
  cada	
  um	
  dos	
  reticulados	
  acima.	
  
6. Considere	
  o	
  reticulado	
  abaixo:	
  
	
  
Calcule	
  as	
  seguintes	
  somas	
  e	
  produtos:	
  
o a⊔d	
  
o b⊓f	
  
o c⊔g	
  
o e⊓d