parte 02 logica proposicional.pdf

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

parte-02-logica-proposicional.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	
  Proposicional	
  
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. 
Lógica	
  proposicional	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
2	
  
—  Sistema	
  que	
  usa	
  ferramentas	
  da	
  Lógica	
  Formal	
  para	
  chegar	
  a	
  
conclusões	
  a	
  par<r	
  das	
  proposições	
  dadas	
  
—  Outros	
  nomes	
  
u  LÓGICA	
  DECLARATIVA	
  	
  
u  CÁLCULO	
  PROPOCIONAL	
  
Lógica	
  proposicional	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
3	
  
—  O	
  que	
  é	
  um	
  argumento?	
  
—  O	
  que	
  é	
  um	
  argumento	
  válido?	
  
hQp://www.clipartbest.com/cliparts/xig/Kok/xigKokxjT.jpeg	
  
Argumento	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
4	
  
—  Do	
  ponto	
  de	
  vista	
  da	
  matemá<ca	
  e	
  da	
  lógica	
  
u  Um	
  argumento	
  não	
  é	
  uma	
  disputa	
  
u  Um	
  argumento	
  é	
  uma	
  sequência	
  de	
  comandos/afirmações	
  que	
  termina	
  
numa	
  conclusão	
  
—  Um	
  argumento	
  ser	
  válido	
  significa	
  que	
  a	
  conclusão	
  pode	
  ser	
  
ob<da	
  necessariamente	
  das	
  afirmações	
  que	
  precedem	
  
Argumento	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
5	
  
	
  
	
  	
  	
  P1,	
  P2,	
  P3,	
  ...,	
  Pn	
  ∴	
  Q	
  
Um	
  argumento	
  é	
  uma	
  	
  
sequência	
  de	
  afirmações	
  
Argumento	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
6	
  
	
  
	
  	
  	
  P1,	
  P2,	
  P3,	
  ...,	
  Pn	
  ∴	
  Q	
  
Todas	
  as	
  afirmações,	
  exceto	
  a	
  úl<ma,	
  
são	
  chamadas	
  de	
  
	
  premissas	
  ou	
  suposições	
  ou	
  hipóteses	
  
Argumento	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
7	
  
	
  
	
  	
  	
  P1,	
  P2,	
  P3,	
  ...,	
  Pn	
  ∴	
  Q	
  
A	
  úl<ma	
  afirmação	
  é	
  chamada	
  de	
  
conclusão	
  
Argumento	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
8	
  
	
  
	
  	
  	
  P1,	
  P2,	
  P3,	
  ...,	
  Pn	
  ∴	
  Q	
  
•  símbolo	
  ∴	
  
•  “de	
  onde	
  se	
  conclui”	
  
•  colocado	
  antes	
  da	
  conclusão	
  
Argumento	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
9	
  
	
  
	
  	
  	
  P1,	
  P2,	
  P3,	
  ...,	
  Pn	
  ∴	
  Q	
  
—  Asser<va	
  
u  Um	
  conjunto	
  de	
  proposições	
  (premissas)	
  P1,	
  P2,	
  ...,	
  Pn,	
  que	
  
u  Resulta,	
  como	
  uma	
  consequência,	
  outra	
  proposição	
  Q	
  (conclusão	
  ou	
  tese)	
  
Exemplo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
10	
  
Exemplo	
  01	
  
Se	
  Riva	
  é	
  humano,	
  então	
  Riva	
  é	
  mortal	
  
Riva	
  é	
  humano	
  
∴	
  
Exemplo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
11	
  
Exemplo	
  01	
  
Se	
  Riva	
  é	
  humano,	
  então	
  Riva	
  é	
  mortal	
  
Riva	
  é	
  humano	
  
∴	
   Riva	
  é	
  mortal	
  
Forma	
  simbólica	
  
P→Q	
  
P	
  
∴	
   Q	
  
Exemplo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
12	
  
Exemplo	
  02	
  
Homem	
  solteiro	
  é	
  infeliz	
  
Homem	
  infeliz	
  morre	
  cedo	
  
∴	
  
Exemplo	
  01	
  
Se	
  Riva	
  é	
  humano,	
  então	
  Riva	
  é	
  mortal	
  
Riva	
  é	
  humano	
  
∴	
   Riva	
  é	
  mortal	
  
Forma	
  simbólica	
  
P→Q	
  
P	
  
∴	
   P→R	
  
Argumentos	
  válidos????	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
13	
  
Exemplo	
  02	
  
Homem	
  solteiro	
  é	
  infeliz	
  
Homem	
  infeliz	
  morre	
  cedo	
  
∴	
   Homem	
  solteiro	
  morre	
  cedo	
  
Exemplo	
  01	
  
Se	
  Riva	
  é	
  humano,	
  então	
  Riva	
  é	
  mortal	
  
Riva	
  é	
  humano	
  
∴	
   Riva	
  é	
  mortal	
  
Forma	
  simbólica	
  
P→Q	
  
Q→R	
  
∴	
   P→R	
  
Forma	
  simbólica	
  
P→Q	
  
P	
  
∴	
   Q	
  
Argumento	
  válido	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
14	
  
—  Um	
  argumento	
  é	
  válido	
  se,	
  e	
  somente	
  se,	
  para	
  todas	
  as	
  
combinações	
  de	
  argumentos	
  que	
  levam	
  a	
  premissas	
  verdadeiras,	
  
então	
  a	
  conclusão	
  também	
  é	
  verdadeira	
  
—  A	
  verdade	
  da	
  conclusão	
  é	
  ob<da	
  analisando	
  os	
  valores-­‐verdade	
  
da	
  forma	
  lógica	
  em	
  si	
  
Argumento	
  válido	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
15	
  
—  Linhas	
  crí<cas	
  
u  Linhas	
  onde	
  todas	
  as	
  premissas	
  são	
  verdadeiras.	
  
u  O	
  argumento	
  é	
  válido	
  se	
  a	
  conclusão	
  for	
  verdadeira	
  para	
  todas	
  as	
  linhas	
  
crí<cas	
  
—  Falácia:	
  argumento	
  que	
  não	
  é	
  válido	
  
Como	
  avaliar	
  a	
  validade	
  de	
  um	
  argumento	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
16	
  
1.  Iden<fique	
  as	
  premissas	
  e	
  conclusão	
  do	
  argumento	
  
2.  Construa	
  a	
  tabela	
  da	
  verdade	
  iden<ficando	
  as	
  colunas	
  das	
  
premissas	
  e	
  da	
  conclusão	
  
3.  Iden<fique	
  as	
  linhas	
  onde	
  todas	
  as	
  premissas	
  são	
  verdadeiras	
  
(linhas	
  crí<cas)	
  
4.  Para	
  cada	
  linha	
  crí<ca	
  verifique	
  se	
  a	
  conclusão	
  do	
  argumento	
  é	
  
verdadeira	
  
a)  Se	
  for	
  para	
  todas	
  as	
  linhas	
  crí<cas	
  então	
  a	
  forma	
  do	
  argumento	
  é	
  válida.	
  
b)  Se	
  exis<r	
  pelo	
  menos	
  uma	
  linha	
  crí<ca	
  com	
  conclusão	
  falsa	
  então	
  a	
  forma	
  
do	
  argumento	
  é	
  inválida.	
  
Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
17	
  
Exemplo	
  01	
  
Se	
  Riva	
  é	
  humano,	
  então	
  Riva	
  é	
  mortal	
  
Riva	
  é	
  humano	
  
∴	
   Riva	
  é	
  mortal	
  
Forma	
  simbólica	
  
P→Q	
  
P	
  
∴	
   Q	
  
Premissas	
   Conclusão	
  
P	
   Q	
  
V	
   V	
  
V	
   F	
  
F	
   V	
  
F	
   F
Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
18	
  
Exemplo	
  01	
  
Se	
  Riva	
  é	
  humano,	
  então	
  Riva	
  é	
  mortal	
  
Riva	
  é	
  humano	
  
∴	
   Riva	
  é	
  mortal	
  
Forma	
  simbólica	
  
P→Q	
  
P	
  
∴	
   Q	
  
Premissas	
   Conclusão	
  
P	
   Q	
   P→Q	
   P	
  
V	
   V	
  
V	
   F	
  
F	
   V	
  
F	
   F	
  
Premissas	
  
Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
19	
  
Exemplo	
  01	
  
Se	
  Riva	
  é	
  humano,	
  então	
  Riva	
  é	
  mortal	
  
Riva	
  é	
  humano	
  
∴	
   Riva	
  é	
  mortal	
  
Forma	
  simbólica	
  
P→Q	
  
P	
  
∴	
   Q	
  
Premissas	
   Conclusão	
  
P	
   Q	
   P→Q	
   P	
   Q	
  
V	
   V	
  
V	
   F	
  
F	
   V	
  
F	
   F	
   Conclusão	
  
Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
20	
  
Exemplo	
  01	
  
Se	
  Riva	
  é	
  humano,	
  então	
  Riva	
  é	
  mortal	
  
Riva	
  é	
  humano	
  
∴	
   Riva	
  é	
  mortal	
  
Forma	
  simbólica	
  
P→Q	
  
P	
  
∴	
   Q	
  
Premissas	
   Conclusão	
  
P	
   Q	
   P→Q	
   P	
   Q	
  
V	
   V	
   V	
  
V	
   F	
  
F	
   V	
  
F	
   F	
  
Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
21	
  
Exemplo	
  01	
  
Se	
  Riva	
  é	
  humano,	
  então	
  Riva	
  é	
  mortal	
  
Riva	
  é	
  humano	
  
∴	
   Riva	
  é	
  mortal	
  
Forma	
  simbólica	
  
P→Q	
  
P	
  
∴	
   Q	
  
Premissas	
   Conclusão	
  
P	
   Q	
   P→Q	
   P	
   Q	
  
V	
   V	
   V	
  
V	
   F	
   F	
  
F	
   V	
  
F	
   F	
  
Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
22	
  
Exemplo	
  01	
  
Se	
  Riva	
  é	
  humano,	
  então	
  Riva	
  é	
  mortal	
  
Riva	
  é	
  humano	
  
∴	
   Riva	
  é	
  mortal	
  
Forma	
  simbólica	
  
P→Q	
  
P	
  
∴	
   Q	
  
Premissas	
   Conclusão	
  
P	
   Q	
   P→Q	
   P	
   Q	
  
V	
   V	
   V	
  
V	
   F	
   F	
  
F	
   V	
   V	
  
F	
   F	
  
Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
23	
  
Exemplo	
  01	
  
Se	
  Riva	
  é	
  humano,	
  então	
  Riva	
  é	
  mortal	
  
Riva	
  é	
  humano	
  
∴	
   Riva	
  é	
  mortal	
  
Forma	
  simbólica	
  
P→Q	
  
P	
  
∴	
   Q	
  
Premissas	
   Conclusão	
  
P	
   Q	
   P→Q	
   P	
   Q	
  
V	
   V	
   V	
  
V	
   F	
   F	
  
F	
   V	
   V	
  
F	
   F	
   V	
  
Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
24	
  
Exemplo	
  01	
  
Se	
  Riva	
  é	
  humano,	
  então	
  Riva	
  é	
  mortal	
  
Riva	
  é	
  humano	
  
∴	
   Riva	
  é	
  mortal	
  
Forma	
  simbólica	
  
P→Q	
  
P	
  
∴	
   Q	
  
Premissas	
   Conclusão	
  
P	
   Q	
   P→Q	
   P	
   Q	
  
V	
   V	
   V	
   V	
  
V	
   F	
   F	
   V	
  
F	
   V	
   V	
   F	
  
F	
   F	
   V	
   F	
  
Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
25	
  
Exemplo	
  01	
  
Se	
  Riva	
  é	
  humano,	
  então	
  Riva	
  é	
  mortal	
  
Riva	
  é	
  humano	
  
∴	
   Riva	
  é	
  mortal	
  
Forma	
  simbólica	
  
P→Q	
  
P	
  
∴	
   Q	
  
Premissas	
   Conclusão	
  
P	
   Q	
   P→Q	
   P	
   Q	
  
V	
   V	
   V	
   V	
   V	
  
V	
   F	
   F	
   V	
   F	
  
F	
   V	
   V	
   F	
   V	
  
F	
   F	
   V	
   F	
   F	
  
Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
26	
  
Exemplo	
  01	
  
Se	
  Riva	
  é	
  humano,	
  então	
  Riva	
  é	
  mortal	
  
Riva	
  é	
  humano	
  
∴	
   Riva	
  é	
  mortal	
  
Forma	
  simbólica	
  
P→Q	
  
P	
  
∴	
   Q	
  
Premissas	
   Conclusão	
  
P	
   Q	
   P→Q	
   P	
   Q	
  
V	
   V	
   V	
   V	
   V	
  
V	
   F	
   F	
   V	
   F	
  
F	
   V	
   V	
   F	
   V	
  
F	
   F	
   V	
   F	
   F	
  
Iden<ficar	
  linhas	
  crí<cas:	
  
Premissas	
  são	
  verdadeiras	
  
Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
27	
  
Exemplo	
  01	
  
Se	
  Riva	
  é	
  humano,	
  então	
  Riva	
  é	
  mortal	
  
Riva	
  é	
  humano	
  
∴	
   Riva	
  é	
  mortal	
  
Forma	
  simbólica	
  
P→Q	
  
P	
  
∴	
   Q	
  
Premissas	
   Conclusão	
  
P	
   Q	
   P→Q	
   P	
   Q	
  
V	
   V	
   V	
   V	
   V	
  
V	
   F	
   F	
   V	
   F	
  
F	
   V	
   V	
   F	
   V	
  
F	
   F	
   V	
   F	
   F	
  
Iden<ficar	
  linhas	
  crí<cas:	
  
Premissas	
  são	
  verdadeiras	
  
Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
28	
  
Exemplo	
  01	
  
Se	
  Riva	
  é	
  humano,	
  então	
  Riva	
  é	
  mortal	
  
Riva	
  é	
  humano	
  
∴	
   Riva	
  é	
  mortal	
  
Forma	
  simbólica	
  
P→Q	
  
P	
  
∴	
   Q	
  
Premissas	
   Conclusão	
  
P	
   Q	
   P→Q	
   P	
   Q	
  
V	
   V	
   V	
   V	
   V	
  
V	
   F	
   F	
   V	
   F	
  
F	
   V	
   V	
   F	
   V	
  
F	
   F	
   V	
   F	
   F	
  
Premissas	
  são	
  verdadeiras:	
  
Conclusão	
  verdadeira	
  
Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
29	
  
Exemplo	
  01	
  
Se	
  Riva	
  é	
  humano,	
  então	
  Riva	
  é	
  mortal	
  
Riva	
  é	
  humano	
  
∴	
   Riva	
  é	
  mortal	
  
Forma	
  simbólica	
  
P→Q	
  
P	
  
∴	
   Q	
  
Premissas	
   Conclusão	
  
P	
   Q	
   P→Q	
   P	
   Q	
  
V	
   V	
   V	
   V	
   V	
  
V	
   F	
   F	
   V	
   F	
  
F	
   V	
   V	
   F	
   V	
  
F	
   F	
   V	
   F	
   F	
  
Argumento	
  Válido	
  
Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
30	
  
Exemplo	
  01	
  
Se	
  Riva	
  é	
  humano,	
  então	
  Riva	
  é	
  mortal	
  
Riva	
  é	
  humano	
  
∴	
   Riva	
  é	
  mortal	
  
Forma	
  simbólica	
  
P→Q	
  
P	
  
∴	
   Q	
  
Premissas	
   Conclusão	
  
P	
   Q	
   P→Q	
   P	
   Q	
  
V	
   V	
   V	
   V	
   V	
  
V	
   F	
   F	
   V	
   F	
  
F	
   V	
   V	
   F	
   V	
  
F	
   F	
   V	
   F	
   F	
  
Demais	
  linhas	
  são	
  
irrelevantes	
  
Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
31	
  
Premissas	
   Conclusão	
  
P	
   Q	
   R	
   P→Q	
   Q→R	
   P→R	
  
V	
   V	
   V	
  
V	
   V	
   F	
  
V	
   F	
   V	
  
V	
   F
F	
  
F	
   V	
   V	
  
F	
   V	
   F	
  
F	
   F	
   V	
  
F	
   F	
   F	
  
Exemplo	
  02	
  
Homem	
  solteiro	
  é	
  infeliz	
  
Homem	
  infeliz	
  morre	
  cedo	
  
∴	
   Homem	
  solteiro	
  morre	
  cedo	
  
Forma	
  simbólica	
  
P→Q	
  
Q→R	
  
∴	
   P→R	
  
Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
32	
  
Premissas	
   Conclusão	
  
P	
   Q	
   R	
   P→Q	
   Q→R	
   P→R	
  
V	
   V	
   V	
  
V	
   V	
   F	
  
V	
   F	
   V	
  
V	
   F	
   F	
  
F	
   V	
   V	
  
F	
   V	
   F	
  
F	
   F	
   V	
  
F	
   F	
   F	
  
Exemplo	
  02	
  
Homem	
  solteiro	
  é	
  infeliz	
  
Homem	
  infeliz	
  morre	
  cedo	
  
∴	
   Homem	
  solteiro	
  morre	
  cedo	
  
Forma	
  simbólica	
  
P→Q	
  
Q→R	
  
∴	
   P→R	
  
Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
33	
  
Premissas	
   Conclusão	
  
P	
   Q	
   R	
   P→Q	
   Q→R	
   P→R	
  
V	
   V	
   V	
  
V	
   V	
   F	
  
V	
   F	
   V	
  
V	
   F	
   F	
  
F	
   V	
   V	
  
F	
   V	
   F	
  
F	
   F	
   V	
  
F	
   F	
   F	
  
Exemplo	
  02	
  
Homem	
  solteiro	
  é	
  infeliz	
  
Homem	
  infeliz	
  morre	
  cedo	
  
∴	
   Homem	
  solteiro	
  morre	
  cedo	
  
Forma	
  simbólica	
  
P→Q	
  
Q→R	
  
∴	
   P→R	
  
Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
34	
  
Premissas	
   Conclusão	
  
P	
   Q	
   R	
   P→Q	
   Q→R	
   P→R	
  
V	
   V	
   V	
   V	
  
V	
   V	
   F	
   V	
  
V	
   F	
   V	
   F	
  
V	
   F	
   F	
   F	
  
F	
   V	
   V	
   V	
  
F	
   V	
   F	
   V	
  
F	
   F	
   V	
   V	
  
F	
   F	
   F	
   V	
  
Exemplo	
  02	
  
Homem	
  solteiro	
  é	
  infeliz	
  
Homem	
  infeliz	
  morre	
  cedo	
  
∴	
   Homem	
  solteiro	
  morre	
  cedo	
  
Forma	
  simbólica	
  
P→Q	
  
Q→R	
  
∴	
   P→R	
  
Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
35	
  
Premissas	
   Conclusão	
  
P	
   Q	
   R	
   P→Q	
   Q→R	
   P→R	
  
V	
   V	
   V	
   V	
   V	
  
V	
   V	
   F	
   V	
   F	
  
V	
   F	
   V	
   F	
   V	
  
V	
   F	
   F	
   F	
   V	
  
F	
   V	
   V	
   V	
   V	
  
F	
   V	
   F	
   V	
   F	
  
F	
   F	
   V	
   V	
   V	
  
F	
   F	
   F	
   V	
   V	
  
Exemplo	
  02	
  
Homem	
  solteiro	
  é	
  infeliz	
  
Homem	
  infeliz	
  morre	
  cedo	
  
∴	
   Homem	
  solteiro	
  morre	
  cedo	
  
Forma	
  simbólica	
  
P→Q	
  
Q→R	
  
∴	
   P→R	
  
Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
36	
  
Premissas	
   Conclusão	
  
P	
   Q	
   R	
   P→Q	
   Q→R	
   P→R	
  
V	
   V	
   V	
   V	
   V	
   V	
  
V	
   V	
   F	
   V	
   F	
   F	
  
V	
   F	
   V	
   F	
   V	
   V	
  
V	
   F	
   F	
   F	
   V	
   F	
  
F	
   V	
   V	
   V	
   V	
   V	
  
F	
   V	
   F	
   V	
   F	
   V	
  
F	
   F	
   V	
   V	
   V	
   V	
  
F	
   F	
   F	
   V	
   V	
   V	
  
Exemplo	
  02	
  
Homem	
  solteiro	
  é	
  infeliz	
  
Homem	
  infeliz	
  morre	
  cedo	
  
∴	
   Homem	
  solteiro	
  morre	
  cedo	
  
Forma	
  simbólica	
  
P→Q	
  
Q→R	
  
∴	
   P→R	
  
Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
37	
  
Premissas	
   Conclusão	
  
P	
   Q	
   R	
   P→Q	
   Q→R	
   P→R	
  
V	
   V	
   V	
   V	
   V	
   V	
  
V	
   V	
   F	
   V	
   F	
   F	
  
V	
   F	
   V	
   F	
   V	
   V	
  
V	
   F	
   F	
   F	
   V	
   F	
  
F	
   V	
   V	
   V	
   V	
   V	
  
F	
   V	
   F	
   V	
   F	
   V	
  
F	
   F	
   V	
   V	
   V	
   V	
  
F	
   F	
   F	
   V	
   V	
   V	
  
Exemplo	
  02	
  
Homem	
  solteiro	
  é	
  infeliz	
  
Homem	
  infeliz	
  morre	
  cedo	
  
∴	
   Homem	
  solteiro	
  morre	
  cedo	
  
Forma	
  simbólica	
  
P→Q	
  
Q→R	
  
∴	
   P→R	
  
Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
38	
  
Premissas	
   Conclusão	
  
P	
   Q	
   R	
   P→Q	
   Q→R	
   P→R	
  
V	
   V	
   V	
   V	
   V	
   V	
  
V	
   V	
   F	
   V	
   F	
   F	
  
V	
   F	
   V	
   F	
   V	
   V	
  
V	
   F	
   F	
   F	
   V	
   F	
  
F	
   V	
   V	
   V	
   V	
   V	
  
F	
   V	
   F	
   V	
   F	
   V	
  
F	
   F	
   V	
   V	
   V	
   V	
  
F	
   F	
   F	
   V	
   V	
   V	
  
Exemplo	
  02	
  
Homem	
  solteiro	
  é	
  infeliz	
  
Homem	
  infeliz	
  morre	
  cedo	
  
∴	
   Homem	
  solteiro	
  morre	
  cedo	
  
Forma	
  simbólica	
  
P→Q	
  
Q→R	
  
∴	
   P→R	
  
Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
39	
  
Premissas	
   Conclusão	
  
P	
   Q	
   R	
   P→Q	
   Q→R	
   P→R	
  
V	
   V	
   V	
   V	
   V	
   V	
  
V	
   V	
   F	
   V	
   F	
   F	
  
V	
   F	
   V	
   F	
   V	
   V	
  
V	
   F	
   F	
   F	
   V	
   F	
  
F	
   V	
   V	
   V	
   V	
   V	
  
F	
   V	
   F	
   V	
   F	
   V	
  
F	
   F	
   V	
   V	
   V	
   V	
  
F	
   F	
   F	
   V	
   V	
   V	
  
Exemplo	
  02	
  
Homem	
  solteiro	
  é	
  infeliz	
  
Homem	
  infeliz	
  morre	
  cedo	
  
∴	
   Homem	
  solteiro	
  morre	
  cedo	
  
Forma	
  simbólica	
  
P→Q	
  
Q→R	
  
∴	
   P→R	
  
Argumento	
  Válido	
  
Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
40	
  
Exemplo	
  03	
  
Se	
  Riva	
  é	
  humano,	
  então	
  Riva	
  é	
  mortal	
  
Riva	
  é	
  mortal	
  
∴	
   Riva	
  é	
  humano	
  
Forma	
  simbólica	
  
P→Q	
  
Q	
  
∴	
   P	
  
Premissas	
   Conclusão	
  
P	
   Q	
  
V	
   V	
  
V	
   F	
  
F	
   V	
  
F	
   F	
  
Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
41	
  
Exemplo	
  03	
  
Se	
  Riva	
  é	
  humano,	
  então	
  Riva	
  é	
  mortal	
  
Riva	
  é	
  mortal	
  
∴	
   Riva	
  é	
  humano	
  
Forma	
  simbólica	
  
P→Q	
  
Q	
  
∴	
   P	
  
Premissas	
   Conclusão	
  
P	
   Q	
   P→Q	
   Q	
   P	
  
V	
   V	
  
V	
   F	
  
F	
   V	
  
F	
   F	
  
Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
42	
  
Exemplo	
  03	
  
Se	
  Riva	
  é	
  humano,	
  então	
  Riva	
  é	
  mortal	
  
Riva	
  é	
  mortal	
  
∴	
   Riva	
  é	
  humano	
  
Forma	
  simbólica	
  
P→Q	
  
Q	
  
∴	
   P	
  
Premissas	
   Conclusão	
  
P	
   Q	
   P→Q	
   Q
P	
  
V	
   V	
   V	
  
V	
   F	
   F	
  
F	
   V	
   V	
  
F	
   F	
   V	
  
Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
43	
  
Exemplo	
  03	
  
Se	
  Riva	
  é	
  humano,	
  então	
  Riva	
  é	
  mortal	
  
Riva	
  é	
  mortal	
  
∴	
   Riva	
  é	
  humano	
  
Forma	
  simbólica	
  
P→Q	
  
Q	
  
∴	
   P	
  
Premissas	
   Conclusão	
  
P	
   Q	
   P→Q	
   Q	
   P	
  
V	
   V	
   V	
   V	
  
V	
   F	
   F	
   F	
  
F	
   V	
   V	
   V	
  
F	
   F	
   V	
   F	
  
Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
44	
  
Exemplo	
  03	
  
Se	
  Riva	
  é	
  humano,	
  então	
  Riva	
  é	
  mortal	
  
Riva	
  é	
  mortal	
  
∴	
   Riva	
  é	
  humano	
  
Forma	
  simbólica	
  
P→Q	
  
Q	
  
∴	
   P	
  
Premissas	
   Conclusão	
  
P	
   Q	
   P→Q	
   Q	
   P	
  
V	
   V	
   V	
   V	
   V	
  
V	
   F	
   F	
   F	
   V	
  
F	
   V	
   V	
   V	
   F	
  
F	
   F	
   V	
   F	
   F	
  
Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
45	
  
Exemplo	
  03	
  
Se	
  Riva	
  é	
  humano,	
  então	
  Riva	
  é	
  mortal	
  
Riva	
  é	
  mortal	
  
∴	
   Riva	
  é	
  humano	
  
Forma	
  simbólica	
  
P→Q	
  
Q	
  
∴	
   P	
  
Premissas	
   Conclusão	
  
P	
   Q	
   P→Q	
   Q	
   P	
  
V	
   V	
   V	
   V	
   V	
  
V	
   F	
   F	
   F	
   V	
  
F	
   V	
   V	
   V	
   F	
  
F	
   F	
   V	
   F	
   F	
  
Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
46	
  
Exemplo	
  03	
  
Se	
  Riva	
  é	
  humano,	
  então	
  Riva	
  é	
  mortal	
  
Riva	
  é	
  mortal	
  
∴	
   Riva	
  é	
  humano	
  
Forma	
  simbólica	
  
P→Q	
  
Q	
  
∴	
   P	
  
Premissas	
   Conclusão	
  
P	
   Q	
   P→Q	
   Q	
   P	
  
V	
   V	
   V	
   V	
   V	
  
V	
   F	
   F	
   F	
   V	
  
F	
   V	
   V	
   V	
   F	
  
F	
   F	
   V	
   F	
   F	
  
Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
47	
  
Exemplo	
  03	
  
Se	
  Riva	
  é	
  humano,	
  então	
  Riva	
  é	
  mortal	
  
Riva	
  é	
  mortal	
  
∴	
   Riva	
  é	
  humano	
  
Forma	
  simbólica	
  
P→Q	
  
Q	
  
∴	
   P	
  
Premissas	
   Conclusão	
  
P	
   Q	
   P→Q	
   Q	
   P	
  
V	
   V	
   V	
   V	
   V	
  
V	
   F	
   F	
   F	
   V	
  
F	
   V	
   V	
   V	
   F	
  
F	
   F	
   V	
   F	
   F	
  
Argumento	
  Inválido	
  
Argumentos	
  válidos:	
  regras	
  de	
  inferência	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Fundamentos de Teoria da Computação 
48	
  
Modus	
  ponens	
  
P	
  
P→Q	
  
Q	
  
MD	
  é	
  fácil	
  
SE	
  MD	
  é	
  fácil,	
  ENTÃO	
  serei	
  aprovado	
  
serei	
  aprovado	
  
Argumentos	
  válidos:	
  regras	
  de	
  inferência	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Fundamentos de Teoria da Computação 
49	
  
Modus	
  ponens	
  
P	
  
P→Q	
  
Q	
  
Modus	
  tollens	
  
¬Q	
  
P→Q	
  
¬P	
  
NÃO	
  fui	
  aprovado	
  
SE	
  estudei,	
  ENTÃO	
  fui	
  aprovado	
  
NÃO	
  estudei	
  
Argumentos	
  válidos:	
  regras	
  de	
  inferência	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Fundamentos de Teoria da Computação 
50	
  
Modus	
  ponens	
  
P	
  
P→Q	
  
Q	
  
Modus	
  tollens	
  
¬Q	
  
P→Q	
  
¬P	
  
Conjunção	
  
P	
  
Q	
  
P∧Q	
  
estudei	
  
fui	
  aprovado	
  
estudei	
  E	
  fui	
  aprovado	
  
Argumentos	
  válidos:	
  regras	
  de	
  inferência	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Fundamentos de Teoria da Computação 
51	
  
Modus	
  ponens	
  
P	
  
P→Q	
  
Q	
  
Modus	
  tollens	
  
¬Q	
  
P→Q	
  
¬P	
  
Conjunção	
  
P	
  
Q	
  
P∧Q	
  
Adição	
  
P	
  
P∨Q	
  
estudei	
  
estudei	
  OU	
  dormi	
  
Argumentos	
  válidos:	
  regras	
  de	
  inferência	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Fundamentos de Teoria da Computação 
52	
  
Modus	
  ponens	
  
P	
  
P→Q	
  
Q	
  
Modus	
  tollens	
  
¬Q	
  
P→Q	
  
¬P	
  
Conjunção	
  
P	
  
Q	
  
P∧Q	
  
Adição	
  
P	
  
P∨Q	
  
Silogismo	
  hipoté<co	
  
P→Q	
  
Q→R	
  
P→R	
  
SE	
  estudar,	
  ENTÃO	
  MD	
  é	
  fácil	
  
SE	
  MD	
  é	
  fácil,	
  ENTÃO	
  serei	
  aprovado	
  
SE	
  estudar,	
  ENTÃO	
  serei	
  aprovado	
  
Argumentos	
  válidos:	
  regras	
  de	
  inferência	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Fundamentos de Teoria da Computação 
53	
  
Modus	
  ponens	
  
P	
  
P→Q	
  
Q	
  
Modus	
  tollens	
  
¬Q	
  
P→Q	
  
¬P	
  
Conjunção	
  
P	
  
Q	
  
P∧Q	
  
Adição	
  
P	
  
P∨Q	
  
Silogismo	
  hipoté<co	
  
P↔Q	
  
Q↔R	
  
P↔R	
  
Silogismo	
  hipoté<co	
  
P→Q	
  
Q→R	
  
P→R	
  
estudo	
  SE,	
  E	
  SOMENTE	
  SE,	
  quero	
  passar	
  
quero	
  passar	
  SE,	
  E	
  SOMENTE	
  SE,	
  aprendo	
  
estudo	
  SE,	
  E	
  SOMENTE	
  SE,	
  aprendo	
  	
  
Argumentos	
  válidos:	
  regras	
  de	
  inferência	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Fundamentos de Teoria da Computação 
54	
  
Modus	
  ponens	
  
P	
  
P→Q	
  
Q	
  
Modus	
  tollens	
  
¬Q	
  
P→Q	
  
¬P	
  
Conjunção	
  
P	
  
Q	
  
P∧Q	
  
Adição	
  
P	
  
P∨Q	
  
Silogismo	
  disjun<vo	
  
P∨Q	
  
¬Q	
  
P	
  
Silogismo	
  hipoté<co	
  
P↔Q	
  
Q↔R	
  
P↔R	
  
Silogismo	
  hipoté<co	
  
P→Q	
  
Q→R	
  
P→R	
  
estudei	
  OU	
  dormi	
  
NÃO	
  dormi	
  
estudei	
  
Argumentos	
  válidos:	
  regras	
  de	
  inferência	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Fundamentos de Teoria da Computação 
55	
  
Modus	
  ponens	
  
P	
  
P→Q	
  
Q	
  
Modus	
  tollens	
  
¬Q	
  
P→Q	
  
¬P	
  
Conjunção	
  
P	
  
Q	
  
P∧Q	
  
Adição	
  
P	
  
P∨Q	
  
Silogismo	
  disjun<vo	
  
P∨Q	
  
¬Q	
  
P	
  
Silogismo	
  hipoté<co	
  
P↔Q	
  
Q↔R	
  
P↔R	
  
Silogismo	
  hipoté<co	
  
P→Q	
  
Q→R	
  
P→R	
  
Argumentos	
  válidos:	
  regras	
  de	
  inferência	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Fundamentos de Teoria da Computação 
56	
  
Modus	
  ponens	
  
P	
  
P→Q	
  
Q	
  
Modus	
  tollens	
  
¬Q	
  
P→Q	
  
¬P	
  
Conjunção	
  
P	
  
Q
P∧Q	
  
Adição	
  
P	
  
P∨Q	
  
Silogismo	
  disjun<vo	
  
P∨Q	
  
¬Q	
  
P	
  
Silogismo	
  hipoté<co	
  
P↔Q	
  
Q↔R	
  
P↔R	
  
Silogismo	
  hipoté<co	
  
P→Q	
  
Q→R	
  
P→R	
  
U<lizando	
  a	
  tabela-­‐verdade	
  demonstre	
  que	
  estes	
  argumentos	
  são	
  válidos.	
  
Agumentos	
  válidos:	
  exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
57	
  
—  Argumento	
  
(A→B)∧	
  (¬C∨A)	
  ∧	
  C	
  →	
  B	
  
—  Premissas	
  
a)  A→B	
  
b)  ¬C∨A	
  	
  
c)  C	
  
—  Conclusão	
  
u  B	
  
—  Sequência	
  de	
  demonstração	
  
Ponto	
  de	
  Par<da	
  
Onde	
  se	
  quer	
  
chegar	
  
Agumentos	
  válidos:	
  exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
58	
  
—  Argumento	
  
(A→B)∧	
  (¬C∨A)	
  ∧	
  C	
  →	
  B	
  
—  Premissas	
  
a)  A→B	
  
b)  ¬C∨A	
  	
  
c)  C	
  
—  Conclusão	
  
u  B	
  
—  Sequência	
  de	
  demonstração	
  
1.  C→A	
  
(¬C∨A)	
  ≡	
  (C→A)	
  
Agumentos	
  válidos:	
  exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
59	
  
—  Argumento	
  
(A→B)∧	
  (¬C∨A)	
  ∧	
  C	
  →	
  B	
  
—  Premissas	
  
a)  A→B	
  
b)  ¬C∨A	
  	
  
c)  C	
  
—  Conclusão	
  
u  B	
  
—  Sequência	
  de	
  demonstração	
  
1.  C→A	
  
2.  A	
   C→A	
  
C	
  
∴	
  A	
  
(modus	
  ponens)	
  
Agumentos	
  válidos:	
  exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
60	
  
—  Argumento	
  
(A→B)∧	
  (¬C∨A)	
  ∧	
  C	
  →	
  B	
  
—  Premissas	
  
a)  A→B	
  
b)  ¬C∨A	
  	
  
c)  C	
  
—  Conclusão	
  
u  B	
  
—  Sequência	
  de	
  demonstração	
  
1.  C→A	
  
2.  A	
   C→A	
  
C	
  
∴	
  A	
  
(modus	
  ponens)	
  
Agumentos	
  válidos:	
  exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
61	
  
—  Argumento	
  
(A→B)∧	
  (¬C∨A)	
  ∧	
  C	
  →	
  B	
  
—  Premissas	
  
a)  A→B	
  
b)  ¬C∨A	
  	
  
c)  C	
  
—  Conclusão	
  
u  B	
  
—  Sequência	
  de	
  demonstração	
  
1.  C→A	
  
2.  A	
  
3.  B	
   A→B	
  
A	
  
∴	
  B	
  
(modus	
  ponens)	
  
Agumentos	
  válidos:	
  exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
62	
  
—  Argumento	
  
(A→B)∧	
  (¬C∨A)	
  ∧	
  C	
  →	
  B	
  
—  Premissas	
  
a)  A→B	
  
b)  ¬C∨A	
  	
  
c)  C	
  
—  Conclusão	
  
u  B	
  
—  Sequência	
  de	
  demonstração	
  
1.  C→A	
  
2.  A	
  
3.  B	
   A→B	
  
A	
  
∴	
  B	
  
(modus	
  ponens)	
  
Agumentos	
  válidos:	
  exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
63	
  
—  Argumento	
  
(A→B)∧	
  (¬C∨A)	
  ∧	
  C	
  →	
  B	
  
—  Premissas	
  
a)  A→B	
  
b)  ¬C∨A	
  	
  
c)  C	
  
—  Conclusão	
  
u  B	
  
—  Sequência	
  de	
  demonstração	
  
1.  C→A	
  
2.  A	
  
3.  B	
  
Agumentos	
  válidos:	
  exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
64	
  
—  Argumento	
  
(A→B)∧	
  (¬C∨A)	
  ∧	
  C	
  →	
  B	
  
—  Premissas	
  
a)  A→B	
  
b)  ¬C∨A	
  	
  
c)  C	
  
—  Conclusão	
  
u  B	
  
—  Sequência	
  de	
  demonstração	
  
1.  C→A	
  (equivalência	
  condicional	
  de	
  (b))	
  
2.  A	
  (modus	
  ponens	
  de	
  (1)	
  e	
  (c))	
  
3.  B	
  (modus	
  ponens	
  de	
  (a)	
  e	
  	
  (2))	
  
Agumentos	
  válidos:	
  exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
65	
  
—  Argumento	
  
(¬A∨B)	
  ∧	
  (B→C)	
  →	
  (A→C)	
  
—  Premissas	
  
a)  ¬A∨B	
  
b)  B→C	
  
—  Conclusão	
  
u  A→C	
  
—  Sequência	
  de	
  demonstração	
  
Agumentos	
  válidos:	
  exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
66	
  
—  Argumento	
  
(¬A∨B)	
  ∧	
  (B→C)	
  →	
  (A→C)	
  
—  Premissas	
  
a)  ¬A∨B	
  
b)  B→C	
  
—  Conclusão	
  
u  A→C	
  
—  Sequência	
  de	
  demonstração	
  
1.  A→B	
  
(¬A∨B)	
  ≡	
  (A→B)	
  
Agumentos	
  válidos:	
  exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
67	
  
—  Argumento	
  
(¬A∨B)	
  ∧	
  (B→C)	
  →	
  (A→C)	
  
—  Premissas	
  
a)  ¬A∨B	
  
b)  B→C	
  
—  Conclusão	
  
u  A→C	
  
—  Sequência	
  de	
  demonstração	
  
1.  A→B	
  
2.  A→C	
   A→B	
  B→C	
  
∴	
  A→C	
  
(silogismo	
  
hipoté<co)	
  
	
  
Agumentos	
  válidos:	
  exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
68	
  
—  Argumento	
  
(¬A∨B)	
  ∧	
  (B→C)	
  →	
  (A→C)	
  
—  Premissas	
  
a)  ¬A∨B	
  
b)  B→C	
  
—  Conclusão	
  
u  A→C	
  
—  Sequência	
  de	
  demonstração	
  
1.  A→B	
  
2.  A→C	
  
Agumentos	
  válidos:	
  exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
69	
  
—  Argumento	
  
(¬A∨B)	
  ∧	
  (B→C)	
  →	
  (A→C)	
  
—  Premissas	
  
a)  ¬A∨B	
  
b)  B→C	
  
—  Conclusão	
  
u  A→C	
  
—  Sequência	
  de	
  demonstração	
  
1.  A→B	
  (equivalência	
  condicional	
  de	
  (a))	
  
2.  A→C	
  (silog.	
  hipoté<co	
  em	
  (1)	
  e	
  (b))	
  
Um	
  exemplo	
  mais	
  complexo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Fundamentos de Teoria da Computação 
70	
  
—  Você	
  está	
  saindo	
  para	
  a	
  UFAM	
  de	
  manhã	
  e	
  percebe	
  que	
  não	
  está	
  
usando	
  os	
  óculos.	
  Ao	
  tentar	
  descobrir	
  onde	
  estão	
  os	
  óculos	
  você	
  
começa	
  a	
  pensar	
  sobre	
  os	
  seguintes	
  fatos	
  que	
  são	
  verdadeiros	
  
1.  Se	
  os	
  meus	
  óculos	
  estão	
  na	
  mesa	
  da	
  cozinha	
  então	
  eu	
  os	
  vi	
  no	
  café	
  da	
  
manhã;	
  
2.  Eu	
  estava	
  lendo	
  o	
  jornal	
  na	
  sala	
  de	
  estar	
  ou	
  eu	
  estava	
  lendo	
  o	
  jornal	
  na	
  
cozinha;	
  
3.  Se	
  eu	
  estava	
  lendo	
  o	
  jornal	
  na	
  sala	
  de	
  estar	
  então	
  meus	
  óculos	
  estão	
  na	
  mesa	
  
do	
  café;	
  
4.  Eu	
  não	
  vi	
  meus	
  óculos	
  no	
  café	
  da	
  manhã;	
  
5.  Se	
  eu	
  estava	
  lendo	
  um	
  livro	
  na	
  cama	
  então	
  meus	
  óculos	
  estão	
  no	
  criado-­‐
mudo;	
  
6.  Se	
  eu	
  estava	
  lendo	
  o	
  jornal	
  na	
  cozinha	
  então	
  meus	
  óculos	
  estão	
  na	
  mesa	
  da	
  
cozinha;	
  
Um	
  exemplo	
  mais	
  complexo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Fundamentos de Teoria da Computação 
71	
  
—  Você	
  está	
  saindo	
  para	
  a	
  UFAM	
  de	
  manhã	
  e	
  percebe	
  que	
  não	
  está	
  
usando	
  os	
  óculos.	
  Ao	
  tentar	
  descobrir	
  onde	
  estão	
  os	
  óculos	
  você
começa	
  a	
  pensar	
  sobre	
  os	
  seguintes	
  fatos	
  que	
  são	
  verdadeiros	
  
1.   Se	
  os	
  meus	
  óculos	
  estão	
  na	
  mesa	
  da	
  cozinha	
  então	
  eu	
  os	
  vi	
  no	
  café	
  da	
  
manhã;	
  	
  	
  	
  	
  P→Q	
  
2.  Eu	
  estava	
  lendo	
  o	
  jornal	
  na	
  sala	
  de	
  estar	
  ou	
  eu	
  estava	
  lendo	
  o	
  jornal	
  na	
  
cozinha;	
  
3.  Se	
  eu	
  estava	
  lendo	
  o	
  jornal	
  na	
  sala	
  de	
  estar	
  então	
  meus	
  óculos	
  estão	
  na	
  mesa	
  
do	
  café;	
  
4.  Eu	
  não	
  vi	
  meus	
  óculos	
  no	
  café	
  da	
  manhã;	
  
5.  Se	
  eu	
  estava	
  lendo	
  um	
  livro	
  na	
  cama	
  então	
  meus	
  óculos	
  estão	
  no	
  criado-­‐
mudo;	
  
6.  Se	
  eu	
  estava	
  lendo	
  o	
  jornal	
  na	
  cozinha	
  então	
  meus	
  óculos	
  estão	
  na	
  mesa	
  da	
  
cozinha;	
  
Um	
  exemplo	
  mais	
  complexo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Fundamentos de Teoria da Computação 
72	
  
—  Você	
  está	
  saindo	
  para	
  a	
  UFAM	
  de	
  manhã	
  e	
  percebe	
  que	
  não	
  está	
  
usando	
  os	
  óculos.	
  Ao	
  tentar	
  descobrir	
  onde	
  estão	
  os	
  óculos	
  você	
  
começa	
  a	
  pensar	
  sobre	
  os	
  seguintes	
  fatos	
  que	
  são	
  verdadeiros	
  
1.   Se	
  os	
  meus	
  óculos	
  estão	
  na	
  mesa	
  da	
  cozinha	
  então	
  eu	
  os	
  vi	
  no	
  café	
  da	
  
manhã;	
  	
  	
  	
  	
  P→Q	
  
2.  Eu	
  estava	
  lendo	
  o	
  jornal	
  na	
  sala	
  de	
  estar	
  ou	
  eu	
  estava	
  lendo	
  o	
  jornal	
  na	
  
cozinha;	
  	
  	
  	
  R∨S	
  
3.  Se	
  eu	
  estava	
  lendo	
  o	
  jornal	
  na	
  sala	
  de	
  estar	
  então	
  meus	
  óculos	
  estão	
  na	
  mesa	
  
do	
  café;	
  	
  	
  	
  	
  	
  
4.  Eu	
  não	
  vi	
  meus	
  óculos	
  no	
  café	
  da	
  manhã;	
  
5.  Se	
  eu	
  estava	
  lendo	
  um	
  livro	
  na	
  cama	
  então	
  meus	
  óculos	
  estão	
  no	
  criado-­‐
mudo;	
  
6.  Se	
  eu	
  estava	
  lendo	
  o	
  jornal	
  na	
  cozinha	
  então	
  meus	
  óculos	
  estão	
  na	
  mesa	
  da	
  
cozinha;	
  
Um	
  exemplo	
  mais	
  complexo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Fundamentos de Teoria da Computação 
73	
  
—  Você	
  está	
  saindo	
  para	
  a	
  UFAM	
  de	
  manhã	
  e	
  percebe	
  que	
  não	
  está	
  
usando	
  os	
  óculos.	
  Ao	
  tentar	
  descobrir	
  onde	
  estão	
  os	
  óculos	
  você	
  
começa	
  a	
  pensar	
  sobre	
  os	
  seguintes	
  fatos	
  que	
  são	
  verdadeiros	
  
1.   Se	
  os	
  meus	
  óculos	
  estão	
  na	
  mesa	
  da	
  cozinha	
  então	
  eu	
  os	
  vi	
  no	
  café	
  da	
  
manhã;	
  	
  	
  	
  	
  P→Q	
  
2.  Eu	
  estava	
  lendo	
  o	
  jornal	
  na	
  sala	
  de	
  estar	
  ou	
  eu	
  estava	
  lendo	
  o	
  jornal	
  na	
  
cozinha;	
  	
  	
  	
  R∨S	
  
3.   Se	
  eu	
  estava	
  lendo	
  o	
  jornal	
  na	
  sala	
  de	
  estar	
  então	
  meus	
  óculos	
  estão	
  na	
  mesa	
  
do	
  café;	
  	
  	
  	
  	
  R→T	
  
4.  Eu	
  não	
  vi	
  meus	
  óculos	
  no	
  café	
  da	
  manhã;	
  	
  
5.  Se	
  eu	
  estava	
  lendo	
  um	
  livro	
  na	
  cama	
  então	
  meus	
  óculos	
  estão	
  no	
  criado-­‐
mudo;	
  
6.  Se	
  eu	
  estava	
  lendo	
  o	
  jornal	
  na	
  cozinha	
  então	
  meus	
  óculos	
  estão	
  na	
  mesa	
  da	
  
cozinha;	
  
Um	
  exemplo	
  mais	
  complexo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Fundamentos de Teoria da Computação 
74	
  
—  Você	
  está	
  saindo	
  para	
  a	
  UFAM	
  de	
  manhã	
  e	
  percebe	
  que	
  não	
  está	
  
usando	
  os	
  óculos.	
  Ao	
  tentar	
  descobrir	
  onde	
  estão	
  os	
  óculos	
  você	
  
começa	
  a	
  pensar	
  sobre	
  os	
  seguintes	
  fatos	
  que	
  são	
  verdadeiros	
  
1.   Se	
  os	
  meus	
  óculos	
  estão	
  na	
  mesa	
  da	
  cozinha	
  então	
  eu	
  os	
  vi	
  no	
  café	
  da	
  
manhã;	
  	
  	
  	
  	
  P→Q	
  
2.  Eu	
  estava	
  lendo	
  o	
  jornal	
  na	
  sala	
  de	
  estar	
  ou	
  eu	
  estava	
  lendo	
  o	
  jornal	
  na	
  
cozinha;	
  	
  	
  	
  R∨S	
  
3.   Se	
  eu	
  estava	
  lendo	
  o	
  jornal	
  na	
  sala	
  de	
  estar	
  então	
  meus	
  óculos	
  estão	
  na	
  mesa	
  
do	
  café;	
  	
  	
  	
  	
  R→T	
  
4.  Eu	
  não	
  vi	
  meus	
  óculos	
  no	
  café	
  da	
  manhã;	
  	
  	
  	
  	
  ¬Q	
  
5.  Se	
  eu	
  estava	
  lendo	
  um	
  livro	
  na	
  cama	
  então	
  meus	
  óculos	
  estão	
  no	
  criado-­‐
mudo;	
  
6.  Se	
  eu	
  estava	
  lendo	
  o	
  jornal	
  na	
  cozinha	
  então	
  meus	
  óculos	
  estão	
  na	
  mesa	
  da	
  
cozinha;	
  
Um	
  exemplo	
  mais	
  complexo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Fundamentos de Teoria da Computação 
75	
  
—  Você	
  está	
  saindo	
  para	
  a	
  UFAM	
  de	
  manhã	
  e	
  percebe	
  que	
  não	
  está	
  
usando	
  os	
  óculos.	
  Ao	
  tentar	
  descobrir	
  onde	
  estão	
  os	
  óculos	
  você	
  
começa	
  a	
  pensar	
  sobre	
  os	
  seguintes	
  fatos	
  que	
  são	
  verdadeiros	
  
1.   Se	
  os	
  meus	
  óculos	
  estão	
  na	
  mesa	
  da	
  cozinha	
  então	
  eu	
  os	
  vi	
  no	
  café	
  da	
  
manhã;	
  	
  	
  	
  	
  P→Q	
  
2.  Eu	
  estava	
  lendo	
  o	
  jornal	
  na	
  sala	
  de	
  estar	
  ou	
  eu	
  estava	
  lendo	
  o	
  jornal	
  na	
  
cozinha;	
  	
  	
  	
  R∨S	
  
3.   Se	
  eu	
  estava	
  lendo	
  o	
  jornal	
  na	
  sala	
  de	
  estar	
  então	
  meus	
  óculos	
  estão	
  na	
  mesa	
  
do	
  café;	
  	
  	
  	
  	
  R→T	
  
4.  Eu	
  não	
  vi	
  meus	
  óculos	
  no	
  café	
  da	
  manhã;	
  	
  	
  	
  	
  ¬Q	
  
5.   Se	
  eu	
  estava	
  lendo	
  um	
  livro	
  na	
  cama	
  então	
  meus	
  óculos	
  estão	
  no	
  criado-­‐
mudo;	
  	
  	
  	
  	
  	
  	
  	
  U→X	
  
6.  Se	
  eu	
  estava	
  lendo	
  o	
  jornal	
  na	
  cozinha	
  então	
  meus	
  óculos	
  estão	
  na	
  mesa	
  da	
  
cozinha;	
  
Um	
  exemplo	
  mais	
  complexo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Fundamentos de Teoria da Computação 
76	
  
—  Você	
  está	
  saindo	
  para	
  a	
  UFAM	
  de	
  manhã	
  e	
  percebe	
  que	
  não	
  está	
  
usando	
  os	
  óculos.	
  Ao	
  tentar	
  descobrir	
  onde	
  estão	
  os	
  óculos	
  você	
  
começa	
  a	
  pensar	
  sobre	
  os	
  seguintes	
  fatos	
  que	
  são	
  verdadeiros	
  
1.   Se	
  os	
  meus	
  óculos	
  estão	
  na	
  mesa	
  da	
  cozinha	
  então	
  eu	
  os	
  vi	
  no	
  café	
  da	
  
manhã;	
  	
  	
  	
  	
  P→Q	
  
2.  Eu	
  estava	
  lendo	
  o	
  jornal	
  na	
  sala	
  de	
  estar	
  ou	
  eu	
  estava	
  lendo	
  o	
  jornal	
  na	
  
cozinha;	
  	
  	
  	
  R∨S	
  
3.   Se	
  eu	
  estava	
  lendo	
  o	
  jornal	
  na	
  sala	
  de	
  estar	
  então	
  meus	
  óculos	
  estão	
  na	
  mesa	
  
do	
  café;	
  	
  	
  	
  	
  R→T	
  
4.  Eu	
  não	
  vi	
  meus	
  óculos
no	
  café	
  da	
  manhã;	
  	
  	
  	
  	
  ¬Q	
  
5.   Se	
  eu	
  estava	
  lendo	
  um	
  livro	
  na	
  cama	
  então	
  meus	
  óculos	
  estão	
  no	
  criado-­‐
mudo;	
  	
  	
  	
  	
  	
  	
  	
  U→X	
  
6.   Se	
  eu	
  estava	
  lendo	
  o	
  jornal	
  na	
  cozinha	
  então	
  meus	
  óculos	
  estão	
  na	
  mesa	
  da	
  
cozinha;	
  	
  	
  	
  	
  S→P	
  
Um	
  exemplo	
  mais	
  complexo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Fundamentos de Teoria da Computação 
77	
  
Fatos	
  transformados	
  em	
  proposições	
  
1.	
   P→Q	
   2.	
   R∨S	
   3.	
   R→T	
  
4.	
   ¬Q	
   5.	
   U→X	
   6.	
   S→P	
  
Variável	
   Argumento	
  
P	
   meus	
  óculos	
  estão	
  na	
  mesa	
  da	
  cozinha	
  
Q	
   eu	
  os	
  vi	
  no	
  café	
  da	
  manhã	
  
R	
   estava	
  lendo	
  o	
  jornal	
  na	
  sala	
  de	
  estar	
  
S	
   eu	
  estava	
  lendo	
  o	
  jornal	
  na	
  cozinha	
  
T	
   meus	
  óculos	
  estão	
  na	
  mesa	
  do	
  café	
  
U	
   eu	
  estava	
  lendo	
  um	
  livro	
  na	
  cama	
  
X	
   meus	
  óculos	
  estão	
  no	
  criado-­‐mudo	
  
Um	
  exemplo	
  mais	
  complexo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Fundamentos de Teoria da Computação 
78	
  
Fatos	
  transformados	
  em	
  proposições	
  
1.	
   P→Q	
   2.	
   R∨S	
   3.	
   R→T	
  
4.	
   ¬Q	
   5.	
   U→X	
   6.	
   S→P	
  
1.	
   P→Q	
  
4.	
   ¬Q	
  
Um	
  exemplo	
  mais	
  complexo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Fundamentos de Teoria da Computação 
79	
  
Fatos	
  transformados	
  em	
  proposições	
  
1.	
   P→Q	
   2.	
   R∨S	
   3.	
   R→T	
  
4.	
   ¬Q	
   5.	
   U→X	
   6.	
   S→P	
  
1.	
   P→Q	
  
4.	
   ¬Q	
  
7.	
   ¬P	
   Modus	
  tollens	
  
Um	
  exemplo	
  mais	
  complexo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Fundamentos de Teoria da Computação 
80	
  
Fatos	
  transformados	
  em	
  proposições	
  
1.	
   P→Q	
   2.	
   R∨S	
   3.	
   R→T	
  
4.	
   ¬Q	
   5.	
   U→X	
   6.	
   S→P	
  
1.	
   P→Q	
  
4.	
   ¬Q	
  
7.	
   ¬P	
   Modus	
  tollens	
  
6.	
   S→P	
  
7.	
   ¬P	
  
Um	
  exemplo	
  mais	
  complexo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Fundamentos de Teoria da Computação 
81	
  
Fatos	
  transformados	
  em	
  proposições	
  
1.	
   P→Q	
   2.	
   R∨S	
   3.	
   R→T	
  
4.	
   ¬Q	
   5.	
   U→X	
   6.	
   S→P	
  
1.	
   P→Q	
  
4.	
   ¬Q	
  
7.	
   ¬P	
   Modus	
  tollens	
  
6.	
   S→P	
  
7.	
   ¬P	
  
8.	
   ¬S	
   Modus	
  tollens	
  
Um	
  exemplo	
  mais	
  complexo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Fundamentos de Teoria da Computação 
82	
  
Fatos	
  transformados	
  em	
  proposições	
  
1.	
   P→Q	
   2.	
   R∨S	
   3.	
   R→T	
  
4.	
   ¬Q	
   5.	
   U→X	
   6.	
   S→P	
  
1.	
   P→Q	
  
4.	
   ¬Q	
  
7.	
   ¬P	
   Modus	
  tollens	
  
6.	
   S→P	
  
7.	
   ¬P	
  
8.	
   ¬S	
   Modus	
  tollens	
  
2.	
   R∨S	
  
8.	
   ¬S	
  
Um	
  exemplo	
  mais	
  complexo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Fundamentos de Teoria da Computação 
83	
  
Fatos	
  transformados	
  em	
  proposições	
  
1.	
   P→Q	
   2.	
   R∨S	
   3.	
   R→T	
  
4.	
   ¬Q	
   5.	
   U→X	
   6.	
   S→P	
  
1.	
   P→Q	
  
4.	
   ¬Q	
  
7.	
   ¬P	
   Modus	
  tollens	
  
6.	
   S→P	
  
7.	
   ¬P	
  
8.	
   ¬S	
   Modus	
  tollens	
  
2.	
   R∨S	
  
8.	
   ¬S	
  
9.	
   R	
   Silogismo	
  disjun@vo	
  
9.	
   R→T	
  
8.	
   R	
  
Um	
  exemplo	
  mais	
  complexo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Fundamentos de Teoria da Computação 
84	
  
Fatos	
  transformados	
  em	
  proposições	
  
1.	
   P→Q	
   2.	
   R∨S	
   3.	
   R→T	
  
4.	
   ¬Q	
   5.	
   U→X	
   6.	
   S→P	
  
1.	
   P→Q	
  
4.	
   ¬Q	
  
7.	
   ¬P	
   Modus	
  tollens	
  
6.	
   S→P	
  
7.	
   ¬P	
  
8.	
   ¬S	
   Modus	
  tollens	
  
2.	
   R∨S	
  
8.	
   ¬S	
  
9.	
   R	
   Silogismo	
  disjun@vo	
  
9.	
   R→T	
  
8.	
   R	
  
10.	
   T	
   Modus	
  Ponens	
  
Um	
  exemplo	
  mais	
  complexo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Fundamentos de Teoria da Computação 
85	
  
Fatos	
  transformados	
  em	
  proposições	
  
1.	
   P→Q	
   2.	
   R∨S	
   3.	
   R→T	
  
4.	
   ¬Q	
   5.	
   U→X	
   6.	
   S→P	
  
1.	
   P→Q	
  
4.	
   ¬Q	
  
7.	
   ¬P	
   Modus	
  tollens	
  
6.	
   S→P	
  
7.	
   ¬P	
  
8.	
   ¬S	
   Modus	
  tollens	
  
2.	
   R∨S	
  
8.	
   ¬S	
  
9.	
   R	
   Silogismo	
  disjun@vo	
  
9.	
   R→T	
  
8.	
   R	
  
10.	
   T	
   Modus	
  Ponens	
  
Um	
  exemplo	
  mais	
  complexo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Fundamentos de Teoria da Computação 
86	
  
Fatos	
  transformados	
  em	
  proposições	
  
1.	
   P→Q	
   2.	
   R∨S	
   3.	
   R→T	
  
4.	
   ¬Q	
   5.	
   U→X	
   6.	
   S→P	
  
Variável	
   Argumento	
  
P	
   meus	
  óculos	
  estão	
  na	
  mesa	
  da	
  cozinha	
  
Q	
   eu	
  os	
  vi	
  no	
  café	
  da	
  manhã	
  
R	
   estava	
  lendo	
  o	
  jornal	
  na	
  sala	
  de	
  estar	
  
S	
   eu	
  estava	
  lendo	
  o	
  jornal	
  na	
  cozinha	
  
T	
   meus	
  óculos	
  estão	
  na	
  mesa	
  do	
  café	
  
U	
   eu	
  estava	
  lendo	
  um	
  livro	
  na	
  cama	
  
X	
   meus	
  óculos	
  estão	
  no	
  criado-­‐mudo	
  
Validade	
  vs.	
  Verdade	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
87	
  
http://www.pop.com.br/arquivos/M/Met/Metallicamusica15102012/732801_MetallicaINjpg.jpg 
ht
tp
:/
/i
m
g2
.ti
m
ei
nc
.n
et
/p
eo
pl
e/
i/
20
14
/d
at
ab
as
e/
14
08
31
/j
us
tin
-b
ie
be
r-
30
0.
jp
g 
Validade	
  vs.	
  Verdade	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
88	
  
Argumento	
  
1.	
   Se	
  Metallica	
  é	
  uma	
  banda,	
  então	
  Jus<n	
  Bieber	
  é	
  seu	
  vocalista	
  
2.	
   Metallica	
  é	
  uma	
  banda	
  
∴ Jus<n	
  Bieber	
  é	
  vocalista	
  do	
  Metallica	
  
Forma	
  simbólica	
  
1.	
   P→Q	
  
2.	
   P	
  
∴	
   Q	
  
Premissas	
   Conclusão	
  
P	
   Q	
   P→Q	
   P	
   Q	
  
V	
   V	
   V	
   V	
   V	
  
V	
   F	
   F	
   V	
   F	
  
F	
   V	
   V	
   F	
   V	
  
F	
   F	
   V	
   F	
   F	
  
Argumento	
  válido	
  	
  
(modus	
  ponens)	
  
Validade	
  vs.	
  Verdade	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
89	
  
Argumento	
  
1.	
   Se	
  Metallica	
  é	
  uma	
  banda,	
  então	
  Jus<n	
  Bieber	
  é	
  seu	
  vocalista	
  
2.	
   Metallica	
  é	
  uma	
  banda	
  
∴ Jus<n
Bieber	
  é	
  vocalista	
  do	
  Metallica	
  
Forma	
  simbólica	
  
1.	
   P→Q	
  
2.	
   P	
  
∴	
   Q	
  
Premissas	
   Conclusão	
  
P	
   Q	
   P→Q	
   P	
   Q	
  
V	
   V	
   V	
   V	
   V	
  
V	
   F	
   F	
   V	
   F	
  
F	
   V	
   V	
   F	
   V	
  
F	
   F	
   V	
   F	
   F	
  
Conclusão	
  falsa	
  
Primeira	
  premissa	
  é	
  falsa	
  
Validade	
  vs.	
  Verdade	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
90	
  
Argumento	
  
1.	
   Se	
  NY	
  é	
  uma	
  metrópole,	
  então	
  NY	
  possui	
  arranha-­‐céus	
  
2.	
   NY	
  possui	
  arranha-­‐céus	
  
∴ NY	
  é	
  uma	
  metrópole	
  
Forma	
  simbólica	
  
1.	
   P→Q	
  
2.	
   Q	
  
∴	
   P	
  
Premissas	
   Conclusão	
  
P	
   Q	
   P→Q	
   Q	
   P	
  
V	
   V	
   V	
   V	
   V	
  
V	
   F	
   F	
   F	
   V	
  
F	
   V	
   V	
   V	
   F	
  
F	
   F	
   V	
   F	
   F	
   Argumento	
  Inválido	
  
Conclusão	
  Verdadeira	
  
Honesto	
  vs.	
  desonesto	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
91	
  
—  Em	
  uma	
  ilha	
  deserta	
  há	
  dois	
  
náufragos	
  Michael	
  e	
  Sawyer	
  
a)  Michael	
  diz:	
  Sawyer	
  é	
  honesto	
  
b)  Sawyer	
  diz:	
  Michael	
  e	
  eu	
  somos	
  
opostos	
  
—  Quem	
  é	
  honesto?	
  
1.  Suponha	
  que	
  Michael	
  é	
  honesto	
  
2.  De	
  acordo	
  com	
  (a),	
  Sawyer	
  é	
  honesto	
  
3.  De	
  acordo	
  com	
  (b),	
  Michael	
  é	
  
desonesto	
  
4.  Michael	
  é	
  honesto	
  e	
  desonesto,	
  uma	
  
contradição!	
  
http://images3.wikia.nocookie.net/lostpedia/images/c/c6/2x02_michael_sawyer.JPG 
Honesto	
  vs.	
  desonesto	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
92	
  
—  Em	
  uma	
  ilha	
  deserta	
  há	
  dois	
  
náufragos	
  Michael	
  e	
  Sawyer	
  
a)  Michael	
  diz:	
  Sawyer	
  é	
  honesto	
  
b)  Sawyer	
  diz:	
  Michael	
  e	
  eu	
  somos	
  
opostos	
  
—  Quem	
  é	
  honesto?	
  
1.  Suponha	
  que	
  Michael	
  é	
  desonesto	
  
2.  Então	
  (a)	
  é	
  falso,	
  e	
  Sawyer	
  é	
  desonesto	
  
3.  Então	
  (b)	
  é	
  falso	
  e	
  Sawyer	
  e	
  Michael	
  
são	
  iguais	
  
4.  Sawyer	
  e	
  Michael	
  são	
  desonestos	
  
http://images3.wikia.nocookie.net/lostpedia/images/c/c6/2x02_michael_sawyer.JPG 
Onde	
  está	
  o	
  carro?	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
93	
  
Fatos	
  verdadeiros	
  
1.  Existe	
  um	
  carro	
  em	
  uma	
  dessas	
  caixas	
  
2.  Cada	
  caixa	
  possui	
  uma	
  proposição	
  
3.  Apenas	
  uma	
  proposição	
  é	
  verdadeira	
  
1	
  
2	
  
3	
  
Qual	
  é	
  a	
  proposição	
  
verdadeira?	
  
Onde	
  está	
  o	
  carro?	
  
O	
  carro	
  não	
  	
  
está	
  nesta	
  caixa	
  
O	
  carro	
  está	
  	
  
nesta	
  caixa	
  
O	
  carro	
  não	
  	
  
está	
  na	
  caixa	
  1	
  
O	
  carro	
  não	
  	
  
está	
  nesta	
  caixa	
  
Onde	
  está	
  o	
  carro?	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
94	
  
Fatos	
  verdadeiros	
  
1.  Existe	
  um	
  carro	
  em	
  uma	
  dessas	
  caixas	
  
2.  Cada	
  caixa	
  possui	
  uma	
  proposição	
  
3.  Apenas	
  uma	
  proposição	
  é	
  verdadeira	
  
O	
  carro	
  está	
  	
  
nesta	
  caixa	
  
O	
  carro	
  não	
  	
  
está	
  na	
  caixa	
  1	
  
1	
  
3	
  
Qual	
  é	
  a	
  proposição	
  
verdadeira?	
  
Onde	
  está	
  o	
  carro?	
  
Exercício	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
95	
  
Demonstre	
  a	
  validade	
  dos	
  seguintes	
  argumentos	
  
1.  (P	
  →	
  ¬Q)∧Q	
  →	
  ¬P	
  
2.  (P	
  →	
  ¬Q)∧(R	
  →	
  Q)	
  ∧	
  R	
  →	
  ¬P	
  
3.  P∧(P	
  →	
  Q)∧[P	
  →	
  (Q	
  →	
  R)]	
  →	
  R	
  
4.  (¬P	
  →	
  ¬Q)	
  ∧	
  Q	
  ∧	
  (P	
  →	
  Q)	
  →	
  Q	
  
5.  (¬P	
  →	
  ¬Q)	
  ∧	
  (P	
  →	
  R)	
  ∧	
  Q	
  →	
  R	
  
6.  [P	
  ∨(Q	
  ∧	
  R)]	
  ∧	
  (¬R	
  ∨	
  S)	
  ∧	
  (S	
  →	
  ¬T)	
  →	
  (T	
  →	
  P)	
  
	
  
__MACOSX/._parte-02-logica-proposicional.pdf