parte 03 logica predicados.pdf

Matemática Discreta

•
UFAM

0
leandro castro maciel
22/06/2016
Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original
parte-03-logica-predicados.pdf
EDUARDO 	
   F R E I R E 	
   NAKAMURA 	
  
I n s / t u t o 	
   d e 	
   C o m p u t a ç ã o 	
  
U n i v e r s i d a d e 	
   F e d e r a l 	
   d o 	
   A m a z o n a s 	
  
n a k a m u r a @ i c o m p . u f a m . e d u . b r 	
  
	
  
Lógica	
  de	
  Predicados	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
1	
  
1Este material baseia-se no material da professora Eulanda Miranda dos Santos (emsantos@icomp.ufam.edu.br) e no livro 
 GERSTING, Judith L. Fundamentos Matemáticos para a Ciência da Computação: um Tratamento Moderno de Matemática Discreta, 5a ed. Livros Técnicos e Científicos, 2004. 
Todo	
  ser	
  humano	
  é	
  mortal	
  
Luiz	
  Inácio	
  é	
  humano	
  
∴ Luiz	
  Inácio	
  é	
  mortal	
  
Recapitulando	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
2	
  
Ícone:	
  h>p://www.equiCpz.com/wp-‐content/uploads/2010/06/Warning-‐sign.png	
  
Cálculo	
  Proposicional	
  
Área	
  que	
  trata	
  da	
  análise	
  de	
  proposições	
  compostas,	
  
ligadas	
  por	
  conecCvos	
  (¬,	
  ∧,	
  ∨,	
  →,	
  ↔).	
  	
  
Cálculo	
  de	
  predicados	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
3	
  
Ícone:	
  h>p://online.lbcc.edu/pluginﬁle.php/34778/block_html/content/helpicon.png	
  
Cálculo	
  de	
  predicados	
  
Área	
  que	
  trata	
  da	
  análise	
  simbólica	
  de	
  predicados	
  e	
  de	
  
proposições	
  quanCﬁcadas.	
  	
  
O	
  que	
  é	
  um	
  predicado?	
  
Predicado	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
4	
  
Predicado	
  (dicionário)	
  
1.  Qualidade	
  caracterísCca.	
  	
  
2.  Atributo,	
  prenda,	
  virtude.	
  	
  
3.  Aquilo	
  que	
  se	
  diz	
  do	
  sujeito	
  (gramáCca).	
  
Predicado	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
5	
  
Predicado	
  (lógica)	
  
Um	
  predicado	
  é	
  uma	
  declaração	
  (propriedade)	
  que	
  deve	
  
ser	
  verdadeira	
  ou	
  falsa	
  dependendo	
  do	
  valor	
  de	
  suas	
  
variáveis.	
  
Exemplo	
  
Isaac	
  Newton	
  Silva	
  está	
  matriculado	
  em	
  MatemáCca	
  Discreta.	
  
Predicado	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
6	
  
Sujeito	
  
Predicado	
  
Predicado	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
7	
  
Em	
  lógica	
  de	
  predicados,	
  o	
  predicado	
  
transforma-‐se	
  em	
  uma	
  função,	
  que	
  
retorna	
  verdadeiro	
  ou	
  falso.	
  
Exemplo	
  
Isaac	
  Newton	
  Silva	
  está	
  matriculado	
  em	
  MatemáCca	
  Discreta.	
  
Ícone:	
  h>p://www.equiCpz.com/wp-‐content/uploads/2010/06/Warning-‐sign.png	
  
Predicado	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
8	
  
P(x):	
  “x	
  está	
  matriculado	
  em	
  MatemáCca	
  Discreta”	
  
Exemplo	
  
Isaac	
  Newton	
  Silva	
  está	
  matriculado	
  em	
  MatemáCca	
  Discreta.	
  
Predicado	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
9	
  
P(x):	
  “x	
  está	
  matriculado	
  em	
  MatemáCca	
  Discreta”	
  
x	
  é	
  variável	
  do	
  predicado	
  
Predicado	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
10	
  
P(x,y):	
  “	
  x	
  está	
  matriculado	
  em	
  y	
  ”	
  
Um	
  predicado	
  pode	
  ter	
  múlCplas	
  
variáveis.	
  
Conjunto	
  universo	
  ou	
  domínio	
  de	
  interpretação	
  
Os	
  valores	
  das	
  variáveis	
  de	
  predicados	
  são	
  deﬁnidos	
  por	
  
conjuntos	
  chamados	
  de	
  conjunto	
  universo	
  ou	
  domínio	
  de	
  
interpretação.	
  
Conjunto	
  universo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
11	
  
Conjunto	
  verdade	
  
Se	
  P(x)	
  é	
  um	
  predicado	
  e	
  x	
  tem	
  domínio	
  D,	
  o	
  conjunto	
  verdade	
  
de	
  P(x)	
  é	
  o	
  conjunto	
  de	
  todos	
  elementos	
  de	
  D	
  que	
  tornam	
  P(x)	
  
verdadeiro	
  quando	
  subsCtuído	
  por	
  x.	
  O	
  conjunto	
  verdade	
  de	
  
P(x)	
  é	
  denotado	
  por	
  
{	
  x	
  ∈	
  D	
  |	
  P(x)	
  }	
  
Conjunto	
  verdade	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
12	
  
Conjunto	
  verdade	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
13	
  
Exemplo	
  1	
  
P(x)	
  :	
  x	
  <	
  7	
  e	
  x	
  >	
  3,	
  e	
  o	
  domínio	
  de	
  x	
  é	
  Z+	
  
Conjunto	
  verdade	
  de	
  P(x):	
  	
  {4,5,6}	
  
Exemplo	
  2	
  
P(x)	
  :	
  x	
  divide	
  8,	
  e	
  o	
  domínio	
  de	
  x	
  é	
  Z+	
  
Conjunto	
  verdade	
  de	
  P(x):	
  	
  {1,2,4,8}	
  
QuanCﬁcadores	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
14	
  
Deﬁnição	
  
QuanCﬁcadores	
  são	
  palavras/expressões	
  que	
  referem	
  a	
  
quanCdades	
  tais	
  como	
  “todos”	
  e	
  “alguns”	
  e	
  indicam	
  para	
  
quantos	
  elementos	
  do	
  domínio	
  um	
  dado	
  predicado	
  é	
  
verdadeiro.	
  
QuanCﬁcadores	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
15	
  
  QuanCﬁcador	
  Universal	
  	
  -‐	
  ∀	
  
u  “para	
  todo”,	
  “para	
  cada”	
  e	
  “para	
  qualquer”	
  
u  ∀x	
  ∈	
  S,	
  x	
  é	
  mortal,	
  S	
  é	
  o	
  conjunto	
  de	
  todos	
  seres	
  humanos	
  
  QuanCﬁcador	
  Existencial	
  	
  -‐	
  ∃	
  
u  “existe”,	
  “há	
  pelo	
  menos	
  um”,	
  “existe	
  algum”	
  e	
  “para	
  algum”	
  
u  ∃x	
  ∈	
  S,	
  x	
  é	
  estudande	
  de	
  MD,	
  S	
  é	
  o	
  conjunto	
  de	
  todos	
  seres	
  humanos	
  
	
  
Proposição	
  universal	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
16	
  
Deﬁnição	
  
Seja	
  Q(x)	
  um	
  predicado	
  e	
  D	
  o	
  domínio	
  de	
  x.	
  Uma	
  proposição	
  
universal	
  é	
  uma	
  proposição	
  da	
  forma	
  “(∀x	
  ∈	
  D),	
  Q(x)”	
  
ü  A	
  proposição	
  universal	
  é	
  verdadeira	
  sse	
  Q(x)	
  é	
  verdadeiro	
  
para	
  todo	
  x	
  em	
  D.	
  
ü  A	
   proposição	
   universal	
   é	
   falsa	
   sse	
   Q(x)	
   é	
   falso	
   para	
   pelo	
  
menos	
  um	
  x	
  em	
  D.	
  
ü  O	
  valor	
  de	
  x	
  para	
  o	
  qual	
  Q(x)	
  é	
  falso	
  é	
  chamado	
  de	
  contra-‐
exemplo	
  para	
  a	
  proposição	
  universal.	
  
Proposição	
  universal	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
17	
  
  A	
  proposição	
  ∀x	
  ∈	
  D,	
  x2	
  ≥	
  x,	
  tal	
  que	
  D	
  =	
  {1,2,3}	
  é	
  verdadeira?	
  
u  SIM!	
  
u  12	
  ≥	
  1	
  	
  
u  22	
  ≥	
  2	
  	
  
u  32	
  ≥	
  3	
  	
  
  A	
  proposição	
  ∀x	
  ∈	
  R,	
  x2	
  ≥	
  x,	
  é	
  verdadeira?	
  
u  NÃO	
  
u  0,52	
  =	
  0,25	
  <	
  0,5
Proposição	
  existencial	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
18	
  
Deﬁnição	
  
Seja	
  Q(x)	
  um	
  predicado	
  e	
  D	
  o	
  domínio	
  de	
  x.	
  Uma	
  proposição	
  
existencial	
  é	
  uma	
  proposição	
  da	
  forma	
  “(∃x	
  ∈	
  D),	
  Q(x)”	
  
ü  A	
  proposição	
  existencial	
  é	
  verdadeira	
  sse	
  Q(x)	
  é	
  verdadeiro	
  
para	
  pelo	
  menos	
  um	
  x	
  em	
  D.	
  
ü  A	
  proposição	
  existencialé	
   falsa	
   sse	
  Q(x)	
   é	
   falso	
  para	
   todo	
  x	
  
em	
  D.	
  
Proposição	
  existencial	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
19	
  
  A	
  proposição	
  ∃x	
  ∈	
  Z,	
  x2	
  =	
  x	
  é	
  verdadeira?	
  
u  SIM!	
  
u  12	
  =	
  1	
  	
  
  A	
  proposição	
  ∃x	
  ∈	
  D,	
  x2	
  =	
  x,	
  tal	
  que	
  D	
  =	
  {5,6,7,8}	
  é	
  verdadeira?	
  
u  NÃO	
  
u  52	
  =	
  25	
  ≠	
  5	
  
u  62	
  =	
  36	
  ≠	
  6	
  
u  72	
  =	
  49	
  ≠	
  7	
  
u  82	
  =	
  64	
  ≠	
  8	
  
Proposição	
  condicional	
  universal	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
20	
  
Deﬁnição	
  
Sejam	
  P(x)	
  e	
  Q(x)	
  predicados.	
  Uma	
  proposição	
  condicional	
  
universal	
  tem	
  a	
  forma	
  “∀x,	
  P(x)	
  →	
  Q(x)”.	
  
Para	
  todas	
  combinações	
  de	
  valores	
  verdade	
  das	
  variáveis	
  de	
  
uma	
  sentença	
  
se	
  as	
  premissas	
  são	
  todas	
  verdadeiras	
  
então	
  a	
  conclusão	
  também	
  é	
  verdadeira.	
  
Tradução	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
21	
  
  Todo	
  aluno	
  de	
  Computação	
  faz	
  MD	
  
	
  
  Dado	
  alguém,	
  se	
  ele	
  é	
  aluno	
  de	
  Computação,	
  então	
  ele	
  faz	
  MD	
  
u  P(x):	
  x	
  é	
  um	
  aluno	
  de	
  Computação	
  
u  Q(x):	
  x	
  faz	
  MD	
  
∀x,	
  P(x)	
  →	
  Q(x)	
  
  E	
  se	
  disséssemos	
  ∀x,	
  P(x)	
  ∧	
  Q(x)?	
  O	
  que	
  signiﬁca?	
  
u  Todo	
  mundo	
  é	
  aluno	
  de	
  Computação	
  e	
  faz	
  MD	
  
Tradução	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
22	
  
  Existem	
  algum	
  aluno	
  que	
  faz	
  MD	
  
  Existe	
  alguém	
  que	
  ele	
  é	
  aluno	
  de	
  Computação	
  e	
  faz	
  MD	
  
u  P(x):	
  x	
  é	
  um	
  aluno	
  de	
  Computação	
  
u  Q(x):	
  x	
  faz	
  MD	
  
∃x,	
  P(x)	
  ∧	
  Q(x)	
  
  E	
  se	
  disséssemos	
  ∃x,	
  P(x)	
  →	
  Q(x)?	
  	
  
u  Seria	
  verdadeira	
  se	
  não	
  houvesse	
  aluno	
  de	
  Computação	
  no	
  mundo	
  
(universo	
  de	
  discurso)	
  
Dados	
   Represente	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
  P(x):	
  “x	
  é	
  uma	
  pessoa	
  na	
  
sala”	
  
  I(x):	
  “x	
  fala	
  inglês”	
  
  F(x):	
  “x	
  fala	
  francês”	
  
1.  Todos	
  na	
  sala	
  falam	
  inglês	
  
ou	
  francês	
  
∀x,	
  P(x)	
  →	
  [I(x)	
  ∨	
  F(x)]	
  
	
  
2.  Alguém	
  na	
  sala	
  ou	
  fala	
  
inglês	
  ou	
  francês	
  
∃x,	
  P(x)	
  ∧	
  (I(x)	
  ∨	
  F(x))]	
  
23	
  
Tradução	
  
Dados	
   Represente	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
  A(x):	
  “x	
  é	
  um	
  alunos”	
  
  I(x):	
  “x	
  é	
  inteligente”	
  
  M(x):	
  “x	
  gosta	
  de	
  música”	
  
	
  
1.  Todos	
  alunos	
  são	
  
inteligentes	
  
∀x,	
  A(x)	
  →	
  I(x)	
  
	
  
2.  Existem	
  alunos	
  inteligentes	
  
que	
  gostam	
  de	
  música	
  
∃x,	
  A(x)	
  ∧	
  I(x)	
  ∧	
  M(x)	
  
24	
  
Tradução	
  
Dados	
   Represente	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
  F(x):	
  “x	
  é	
  uma	
  fruta”	
  
  L(y):	
  “y	
  é	
  um	
  legume”	
  
  D(x,y):	
  “x	
  é	
  mais	
  doce	
  do	
  
que	
  y”	
  
1.  Alguns	
  legumes	
  são	
  mais	
  
doces	
  do	
  que	
  todas	
  as	
  
frutas	
  
2.  Todas	
  as	
  frutas	
  são	
  mais	
  
doces	
  do	
  que	
  todos	
  os	
  
legumes	
  
3.  Todas	
  as	
  frutas	
  são	
  mais	
  
doces	
  do	
  que	
  alguns	
  
legumes	
  
25	
  
Tradução	
  
Negando	
  proposições	
  quanCﬁcadas	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
26	
  
Icones	
  obCdos	
  em:	
  
1h>ps://cdn4.iconﬁnder.com/data/icons/free-‐large-‐boss-‐icon-‐set/512/Engineer.png	
  
2h>p://www.avjobs.com/images/v_png_v5/v_collecCon_png/256x256/shadow/scienCst.png	
  
Todo	
  engenheiro	
  usa	
  óculos	
  
Como	
  negar	
  esta	
  
proposição?	
  
Negando	
  proposições	
  quanCﬁcadas	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
27	
  
Icones	
  obCdos	
  em:	
  
1h>ps://cdn4.iconﬁnder.com/data/icons/free-‐large-‐boss-‐icon-‐set/512/Engineer.png	
  
2h>p://www.avjobs.com/images/v_png_v5/v_collecCon_png/256x256/shadow/scienCst.png	
  
Nenhum	
  engenheiro	
  usa	
  óculos	
  
Ícones	
  obCdos	
  em:	
  
1h>p://www.cliparthut.com/clip-‐arts/127/right-‐or-‐wrong-‐127879.jpg	
  
2h>p://www.clipartbest.com/cliparts/9cp/b8g/9cpb8geKi.png	
  
Negando	
  proposições	
  quanCﬁcadas	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
28	
  
Icones	
  obCdos	
  em:	
  
1h>ps://cdn4.iconﬁnder.com/data/icons/free-‐large-‐boss-‐icon-‐set/512/Engineer.png	
  
2h>p://www.avjobs.com/images/v_png_v5/v_collecCon_png/256x256/shadow/scienCst.png	
  
Nenhum	
  engenheiro	
  usa	
  óculos	
  
Icones	
  obCdos	
  em:	
  
1h>ps://openclipart.org/image/2400px/svg_to_png/109/molumen-‐red-‐round-‐error-‐
warning-‐icon.png	
  
Negando	
  proposições	
  quanCﬁcadas	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
29	
  
Icones	
  obCdos	
  em:	
  
1h>ps://cdn4.iconﬁnder.com/data/icons/free-‐large-‐boss-‐icon-‐set/512/Engineer.png	
  
2h>p://www.avjobs.com/images/v_png_v5/v_collecCon_png/256x256/shadow/scienCst.png	
  
Alguns	
  engenheiros	
  não	
  usam	
  óculos	
  
Icones	
  obCdos	
  em:	
  
1h>p://www.cliparthut.com/clip-‐arts/127/right-‐or-‐wrong-‐127879.jpg	
  
2h>p://www.clipartbest.com/cliparts/9cp/b8g/9cpb8geKi.png	
  
Negando	
  proposições	
  quanCﬁcadas	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
30	
  
Icones	
  obCdos	
  em:	
  
1h>ps://cdn4.iconﬁnder.com/data/icons/free-‐large-‐boss-‐icon-‐set/512/Engineer.png	
  
2h>p://www.avjobs.com/images/v_png_v5/v_collecCon_png/256x256/shadow/scienCst.png	
  
Alguns	
  engenheiros	
  não	
  usam	
  óculos	
  
Icones	
  obCdos	
  em:	
  
1h>ps://openclipart.org/image/2400px/svg_to_png/109/molumen-‐red-‐round-‐error-‐
warning-‐icon.png	
  
Negando	
  proposições	
  quanCﬁcadas	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
31	
  
Icones	
  obCdos	
  em:	
  
1h>ps://cdn4.iconﬁnder.com/data/icons/free-‐large-‐boss-‐icon-‐set/512/Engineer.png
2h>p://www.avjobs.com/images/v_png_v5/v_collecCon_png/256x256/shadow/scienCst.png	
  
Existe	
  pelo	
  menos	
  um	
  engenheiro	
  
que	
  não	
  usa	
  óculos	
  
Icones	
  obCdos	
  em:	
  
1h>p://www.eatyourcareer.com/wp-‐content/uploads/2013/06/ok-‐256x256.png	
  
Teorema	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
32	
  
¬(	
  ∀x,	
  P(x)	
  )	
  	
  	
  ≡	
  	
  	
  ∃x,	
  ¬P(x)	
  
¬(	
  ∃x,	
  P(x)	
  )	
  	
  	
  ≡	
  	
  	
  ∀x,	
  ¬P(x)	
  
Validade	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
33	
  
  O	
  valor	
  verdade	
  de	
  {fs	
  em	
  lógica	
  de	
  predicados	
  depende	
  de	
  sua	
  
interpretação,	
  que	
  consiste	
  em	
  
u  Um	
  conjunto	
  universo	
  	
  não	
  vazio;	
  
u  A	
  especiﬁcação	
  de	
  uma	
  propriedade	
  dos	
  objetos	
  do	
  domínio	
  para	
  cada	
  
predicado	
  na	
  expressão;	
  
u  A	
  atribuição	
  de	
  objetos	
  do	
  domínio	
  para	
  cada	
  variável	
  na	
  expressão	
  
Existem	
  inﬁnitas	
  interpretações	
  possíveis	
  
para	
  uma	
  dada	
  {f	
  
Validade	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
34	
  
  Uma	
  {f	
  	
  é	
  dita	
  válida	
  se	
  for	
  verdadeira	
  para	
  todas	
  as	
  
interpretações	
  possíveis	
  
  Não	
  existe	
  um	
  algoritmo	
  para	
  determinar	
  a	
  validade	
  de	
  uma	
  
sentença	
  predicaCva	
  
u  Solução:	
  raciocínio	
  
Se	
  encontrarmos	
  pelo	
  menos	
  uma	
  
interpretação	
  que	
  torne	
  a	
  sentença	
  falsa,	
  
esta	
  não	
  será	
  válida	
  
Fbfs	
  válidas?	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
35	
  
SIM	
  
SIM	
  
NÃO,	
  ex.	
  P(x):	
  x	
  é	
  par	
  
∀x,	
  P(x)	
  →	
  ∃x	
  P(x)	
  
∀x,	
  [P(x)	
  ∧	
  Q(x)]	
  ↔	
  ∀x,	
  P(x)	
  ∧	
  ∀x,	
  Q(x)	
  
∃x,	
  P(x)	
  →	
  	
  ∀y,	
  P(y)	
  
Exercícios	
  “The	
  Flash”	
  	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
36	
  
Qual	
  o	
  valor	
  lógico	
  de	
  cada	
  uma	
  das	
  {fs	
  abaixo?	
  O	
  conjunto	
  
universo	
  é	
  Z	
  
1.  (∀x)	
  (∃y)	
  (x	
  +	
  y	
  =	
  x)	
  
2.  (∃y)	
  (∀x)	
  (x	
  +	
  y	
  =	
  x)	
  
3.  (∀x)	
  (∃y)	
  (x	
  +	
  y	
  =	
  0)	
  
4.  (∃y)	
  (∀x)	
  (x	
  +	
  y	
  =	
  0)	
  
http://cdn.screenrant.com/wp-content/uploads/The-Flash-Premiere-Questions-Answers.jpg 
Regras	
  de	
  dedução	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
37	
  
  As	
  regras	
  de	
  equivalência	
  e	
  de	
  inferência	
  da	
  lógica	
  proposicional	
  
ainda	
  são	
  válidas	
  na	
  lógica	
  de	
  predicados	
  
  Abordagem	
  geral	
  
1.  ReCrar	
  os	
  quanCﬁcadores	
  
2.  Manipular	
  as	
  {fs	
  sem	
  os	
  quanCﬁcadores	
  
3.  Colocar	
  os	
  quanCﬁcadores	
  no	
  lugar	
  
Regras	
  de	
  dedução	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
38	
  
De	
   Podemos	
  deduzir	
   Lei	
  
(∀x)	
  P(x)	
   P(t)	
  onde	
  t	
  é	
  uma	
  variável	
  ou	
  um	
  
símbolo	
  constante	
  
ParCcularização	
  
Universal	
  
(∃x)	
  P(x)	
   P(a),	
  onde	
  a	
  é	
  um	
  símbolo	
  
constante	
  não	
  uClizado	
  até	
  então	
  
ParCcularização	
  
Existencial	
  
P(x)	
   (∀x)	
  P(x)	
   Generalização	
  
Universal	
  
P(x)	
  ou	
  P(a),	
  
a	
  é	
  constante	
  
(∃x)	
  P(x)	
   Generalização	
  
Existencial	
  
Exemplo	
  01	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
39	
  
  (∀x)	
  [	
  P(x)	
  →	
  R(x)	
  ]	
  ∧	
  ¬R(a)	
  →	
  ¬P(a)	
  
	
  
1.  ∀x,	
  P(x)	
  →	
  R(x)	
  
2.  ¬R(a)	
  
3.  	
  P(a)	
  →	
  R(a)	
  
4.  ¬P(a)	
  
	
  
	
  
Hipótese	
  1	
  
Hipótese	
  2	
  
ParCcularização	
  universal	
  	
  
Modus	
  tollens	
  de	
  (2)	
  e	
  (3)	
  
Regras	
  de	
  dedução	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
40	
  
De	
   Podemos	
  deduzir	
   Lei	
  
(∀x)	
  P(x)	
   P(t)	
  onde	
  t	
  é	
  uma	
  variável	
  ou	
  um	
  
símbolo	
  constante	
  
ParCcularização	
  
Universal	
  
(∃x)	
  P(x)	
   P(a),	
  onde	
  a	
  é	
  um	
  símbolo	
  
constante	
  não	
  uClizado	
  até	
  então	
  
ParCcularização	
  
Existencial	
  
P(x)	
   (∀x)	
  P(x)	
   Generalização	
  
Universal	
  
P(x)	
  ou	
  P(a),	
  
a	
  é	
  constante	
  
(∃x)	
  P(x)	
   Generalização	
  
Existencial	
  
Exemplo	
  02	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
41	
  
  ∀x,	
  P(x)	
  →	
  ∃x,	
  P(x)	
  
1.  ∀x,	
  P(x)	
  
2.  	
  P(a)	
  
3.  ∃x,	
  P(x)	
  
Hipótese	
  1	
  
ParCcularização	
  universal	
  
Generalização	
  existencial	
  
Regras	
  de	
  dedução	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
42	
  
De	
   Podemos	
  deduzir	
   Lei	
  
(∀x)	
  P(x)	
   P(t)	
  onde	
  t	
  é	
  uma	
  variável	
  ou	
  um	
  
símbolo	
  constante	
  
ParCcularização	
  
Universal	
  
(∃x)	
  P(x)	
   P(a),	
  onde	
  a	
  é	
  um	
  símbolo	
  
constante	
  não	
  uClizado	
  até	
  então	
  
ParCcularização	
  
Existencial	
  
P(x)	
   (∀x)	
  P(x)	
   Generalização	
  
Universal	
  
P(x)	
  ou	
  P(a),	
  
a	
  é	
  constante	
  
(∃x)	
  P(x)	
   Generalização	
  
Existencial	
  
Exemplo	
  03	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
43	
  
  ∀x,	
  [	
  P(x)	
  ∧	
  Q(x)	
  ]	
  →	
  ∀x,	
  P(x)	
  ∧	
  ∀x,	
  Q(x)	
  
	
  
1.  ∀x,	
  P(x)	
  ∧	
  Q(x)	
  	
  
2.  	
  P(x)	
  ∧	
  Q(x)	
  	
  
3.  	
  P(x)	
  
4.  	
  Q(x)	
  
5.  ∀x,	
  P(x)	
  
6.  ∀x,	
  Q(x)	
  
7.  ∀x,	
  P(x)	
  ∧	
  ∀x,	
  Q(x)	
  
Hipótese	
  1	
  
ParCcularização	
  universal	
  
Conjunção	
  
Generalização	
  Universal	
  de	
  (3)	
  
Generalização	
  Universal	
  de	
  (4)	
  
Conjunção	
  (5)	
  e	
  (6)	
  
	
  
Prove	
  que	
  cada	
  {fs	
  abaixo	
  é	
  um	
  argumento	
  válido	
  
	
  
1.  ∀x,	
  P(x)	
  →	
  ∀x,	
  P(x)	
  ∨	
  Q(x)	
  
2.  ∀x,	
  P(x)	
  ∧	
  ∃x,	
  Q(x)	
  →	
  ∃x,	
  P(x)	
  ∧	
  Q(x)	
  
3.  ∀x,	
  P(x)	
  ∧	
  ∃x,	
  ¬P(x)	
  →	
  ∃x,	
  Q(x)	
  
4.  ∃x,	
  (P(x)	
  →	
  Q(x))	
  ∧	
  ∀y,	
  (Q(y)	
  →	
  R(y))	
  ∧	
  ∀x,	
  P(x)	
  →	
  ∃x,	
  R(x)	
  
Exercícios	
  “The	
  Hulk”	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
44	
  
http://media.ignimgs.com/media/ign/imgs/minisites/topN/comic-book-heroes/9_Hulk.jpg 
Regras	
  de	
  dedução	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
45	
  
De	
   Podemos	
  deduzir	
   Lei	
  
(∀x)
P(x)	
   P(t)	
  onde	
  t	
  é	
  uma	
  variável	
  ou	
  um	
  
símbolo	
  constante	
  
ParCcularização	
  
Universal	
  
(∃x)	
  P(x)	
   P(a),	
  onde	
  a	
  é	
  um	
  símbolo	
  
constante	
  não	
  uClizado	
  até	
  então	
  
ParCcularização	
  
Existencial	
  
P(x)	
   (∀x)	
  P(x)	
   Generalização	
  
Universal	
  
P(x)	
  ou	
  P(a),	
  
a	
  é	
  constante	
  
(∃x)	
  P(x)	
   Generalização	
  
Existencial	
  
__MACOSX/._parte-03-logica-predicados.pdf