parte 01 logica formal.pdf

Matemática Discreta

•
UFAM

leandro castro maciel
22/06/2016
Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original
parte-01-logica-formal.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	
  Formal	
  
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. 
Linha	
  do	
  tempo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
2	
  
século	
  IV	
  
a.C.	
  
Aristóteles	
  (384	
  a.C.	
  –	
  322	
  a.C.)	
  ﬁlósofo	
  grego.	
  SistemaFzou	
  a	
  lógica,	
  deﬁnindo	
  as	
  formas	
  
de	
  interferência	
  que	
  eram	
  válidas	
  e	
  as	
  que	
  não	
  eram,	
  formando	
  um	
  conjunto	
  de	
  regras	
  
para	
  raciocínio	
  deduFvo	
  que	
  pode	
  ser	
  usado	
  em	
  qualquer	
  área	
  do	
  conhecimento.	
  
hP
p:
//
en
.w
ik
ip
ed
ia
.o
rg
/w
ik
i/A
ris
to
tle
	
  
Linha	
  do	
  tempo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
3	
  
século	
  IV	
  
a.C.	
  
GoVried	
  Wilhelm	
  von	
  Leibniz	
  (1646	
  –	
  1716)	
  ﬁlósofo	
  e	
  matemáFco	
  alemão,	
  conhecido	
  por	
  
ter	
  criado	
  o	
  cálculo	
  integral	
  e	
  diferencial	
  independentemente	
  de	
  Isaac	
  Newton.	
  	
  
.	
  	
  
Uso	
  de	
  símbolos	
  para	
  mecanizar	
  o	
  processo	
  de	
  raciocínio	
  deduFvo.	
  	
  
século	
  XVI	
  
d.C.	
  
hP
p:
//
en
.w
ik
ip
ed
ia
.o
rg
/w
ik
i/G
oV
rie
d_
W
ilh
el
m
_L
ei
bn
iz	
  
hP
p:
//
en
.w
ik
ip
ed
ia
.o
rg
/w
ik
i/A
ris
to
tle
	
  
Linha	
  do	
  tempo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
4	
  
século	
  IV	
  
a.C.	
  
George	
  Boole	
  (1815	
  –	
  1864)	
  ﬁlósofo	
  e	
  matemáFco	
  inglês	
  e	
  Augustus	
  De	
  Morgan	
  (1806	
  –	
  
1871)	
  matemáFco	
  inglês.	
  	
  Bases	
  da	
  lógica	
  simbólica	
  moderna	
  usando	
  as	
  ideias	
  de	
  Leibniz.	
  	
  	
  
século	
  XVI	
  
d.C.	
  
século	
  XIX	
  
d.C.	
  
século	
  XIX	
  
d.C.	
  
hP
p:
//
en
.w
ik
ip
ed
ia
.o
rg
/w
ik
i/G
eo
rg
e_
Bo
ol
e	
  
hP
p:
//
en
.w
ik
ip
ed
ia
.o
rg
/w
ik
i/A
ug
us
tu
s_
De
_M
or
ga
n	
  
hP
p:
//
en
.w
ik
ip
ed
ia
.o
rg
/w
ik
i/G
oV
rie
d_
W
ilh
el
m
_L
ei
bn
iz	
  
hP
p:
//
en
.w
ik
ip
ed
ia
.o
rg
/w
ik
i/A
ris
to
tle
	
  
Lógica	
  Formal	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
5	
  
  Fornece	
  bases	
  para	
  o	
  método	
  de	
  pensar	
  organizado;	
  
  Expressa	
  métodos	
  de	
  raciocínio	
  sob	
  a	
  forma	
  de	
  argumentos.	
  
  Tem	
  duas	
  aplicações	
  diretas	
  em	
  Ciência	
  da	
  Computação	
  
1.  Programação	
  Lógica	
  
2.  Prova	
  se	
  programas	
  	
  estão	
  corretos	
  ou	
  não	
  
  É	
  análoga	
  à	
  lógica	
  de	
  circuitos	
  de	
  um	
  computador	
  
Lógica	
  Formal	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
6	
  
  Exemplos	
  de	
  uFlização	
  em	
  computação:	
  
u  Inteligência	
  ArFﬁcial;	
  
u Circuitos	
  Lógicos;	
  
u Banco	
  de	
  Dados;	
  
u Sistemas	
  Computacionais	
  (hardware	
  e	
  somware)	
  
u Sistemas	
  Distribuídos;	
  
u Teoria	
  de	
  autômatos	
  e	
  computabilidade;	
  
u Teoria	
  de	
  linguagens;	
  
Proposições	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
7	
  
  Uma	
  proposição	
  é	
  uma	
  sentença	
  declaraFva,	
  ou	
  uma	
  aﬁrmação,	
  que	
  
admite	
  apenas	
  um	
  dos	
  dois	
  valores	
  lógicos	
  verdadeiro	
  ou	
  falso,	
  nunca	
  
ambos	
  
  Proposições?????	
  
u  Manaus	
  é	
  a	
  capital	
  do	
  Amazonas	
  
u  1	
  +	
  1	
  =	
  2	
  
u  Como	
  você	
  está?	
  
u  9	
  <	
  6	
  
u  Estudem	
  regularmente	
  
u  Londres	
  é	
  na	
  Dinamarca	
  
u  MatemáFca	
  Discreta	
  é	
  fácil	
  
Proposições	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
8	
  
  PROPOSIÇÕES	
  ATÔMICAS	
  não	
  podem	
  ser	
  sub-‐divididas	
  em	
  
proposições	
  mais	
  simples	
  
u  Ex:	
  O	
  servidor	
  de	
  arquivos	
  está	
  desligado	
  
	
  
  PROPOSIÇÕES	
  COMPOSTAS	
  são	
  combinações	
  de	
  proposições	
  
atômicas	
  via	
  conecFvos	
  lógicos	
  
u  Ex:	
  A	
  rede	
  local	
  está	
  mal	
  conﬁgurada	
  ou	
  o	
  servidor	
  de	
  arquivos	
  está	
  
desligado	
  
u  O	
  valor	
  verdade	
  é	
  completamente	
  determinado	
  pelos	
  valores-‐verdade	
  das	
  
subproposições	
  junto	
  com	
  a	
  forma	
  que	
  estão	
  conectadas	
  
Proposições	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
9	
  
  PROPOSIÇÕES	
  ATÔMICAS	
  são	
  representadas	
  por	
  meio	
  de	
  
variáveis	
  proposicionais	
  
u  Variáveis	
  proposicionais:	
  	
  (P,	
  Q,	
  R,	
  S,	
  .	
  .	
  .)	
  
u  Constantes	
  proposicionais:	
  (V,	
  F)	
  →	
  (T,	
  F)	
  
	
  
  Nas	
  PROPOSIÇÕES	
  COMPOSTAS,	
  as	
  variáveis	
  proposicionais	
  são	
  
combinadas	
  através	
  de	
  pelo	
  menos	
  um	
  operador	
  ou	
  conecFvo	
  
lógico	
  
u  Operadores	
  lógicos	
  são	
  uFlizados	
  para	
  combinar	
  proposições	
  e	
  formar	
  
novas	
  proposições	
  
ConecFvos	
  lógicos	
  básicos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
10	
  
  Terminologia	
  	
  
u  Negação:	
  ¬	
  
u  Conjunção:	
  ∧	
  
u  Disjunção:	
  ∨	
  
u  Condicional:	
  	
  →	
  
u  Bicondicional:	
  	
  ↔	
  
Proposições	
  atômicas	
  
P:	
  	
  MD	
  é	
  fácil	
  
Q:	
  Cálculo	
  é	
  fácil	
  
¬Q:	
  (não	
  Q)	
  
Cálculo	
  não	
  é	
  fácil	
  
Cálculo	
  é	
  diLcil	
  
ConecFvos	
  lógicos	
  básicos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
11	
  
  Terminologia	
  	
  
u  Negação:	
  ¬	
  
u  Conjunção:	
  ∧	
  
u  Disjunção:	
  ∨	
  
u  Condicional:	
  	
  →	
  
u  Bicondicional:	
  	
  ↔	
  
P∧Q:	
  (P	
  e	
  Q)	
  
MD	
  é	
  fácil	
  e	
  Cálculo	
  também	
  
	
  
P∧¬Q:	
  (P	
  e	
  não	
  Q)	
  
MD	
  é	
  fácil,	
  mas	
  Cálculo	
  não	
  é	
  
Proposições	
  atômicas	
  
P:	
  	
  MD	
  é	
  fácil	
  
Q:	
  Cálculo	
  é	
  fácil	
  
ConecFvos
lógicos	
  básicos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
12	
  
  Terminologia	
  	
  
u  Negação:	
  ¬	
  
u  Conjunção:	
  ∧	
  
u  Disjunção:	
  ∨	
  
u  Condicional:	
  	
  →	
  
u  Bicondicional:	
  	
  ↔	
  
P∨Q:	
  (P	
  ou	
  Q)	
  
MD	
  é	
  fácil	
  ou	
  Cálculo	
  é	
  fácil	
  
	
  
P∨¬Q:	
  (P	
  ou	
  não	
  Q)	
  
MD	
  é	
  fácil	
  ou	
  Cálculo	
  não	
  é	
  fácil	
  
Proposições	
  atômicas	
  
P:	
  	
  MD	
  é	
  fácil	
  
Q:	
  Cálculo	
  é	
  fácil	
  
Exercícios	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
13	
  
1.  Escreva	
  as	
  seguintes	
  sentenças	
  como	
  proposições	
  em	
  lógica:	
  
a)  Agesilau	
  vai	
  sair	
  mais	
  cedo	
  e	
  não	
  vai	
  voltar.	
  
b)  Hermosina	
  é	
  aluna	
  de	
  MD	
  e	
  Agesilau	
  também.	
  
c)  Hermosina	
  está	
  no	
  laboratório	
  e	
  Agesilau	
  não,	
  ou	
  ele	
  está	
  e	
  ela	
  não.	
  
2.  Considere	
  as	
  seguintes	
  proposições:	
  
P:	
  “Ariosto	
  é	
  rico”	
  	
  	
  	
  	
  	
  	
  	
  	
  Q:	
  “Ariosto	
  é	
  educado”	
  	
  
	
  
Escreva	
  as	
  proposições	
  abaixo	
  em	
  Lógica	
  Formal:	
  
a)  Ariosto	
  não	
  é	
  nem	
  rico	
  e	
  nem	
  educado.	
  
b)  Ariosto	
  é	
  rico,	
  ou	
  é	
  pobre	
  e	
  educado.	
  
c)  É	
  falso	
  que	
  Ariosto	
  seja	
  rico	
  e	
  educado.	
  
d)  Não	
  é	
  falso	
  que	
  Ariosto	
  é	
  mal	
  educado	
  ou	
  ele	
  é	
  pobre.	
  
Tabela	
  verdade	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
14	
  
  Ferramenta	
  usada	
  para	
  
determinar	
  os	
  valores	
  de	
  
uma	
  expressão	
  lógica	
  	
  
u  Go:lob	
  Frege	
  e	
  Charles	
  Peirce,	
  
em	
  1880	
  
u  Emil	
  Post	
  e	
  Ludwig	
  
Wi:genstein,	
  em	
  1922	
  forma	
  
atual	
  
hP
p:
//
pt
.w
ik
ip
ed
ia
.o
rg
/w
ik
i/L
ud
w
ig
_W
iP
ge
ns
te
in
	
  
hP
p:
//
pt
.w
ik
ip
ed
ia
.o
rg
/w
ik
i/E
m
il_
Po
st
	
  
hP
p:
//
pt
.w
ik
ip
ed
ia
.o
rg
/w
ik
i/C
ha
rle
s_
Sa
nd
er
s_
Pe
irc
e	
  
hP
p:
//
pt
.w
ik
ip
ed
ia
.o
rg
/w
ik
i/G
oP
lo
b_
Fr
eg
e	
  
Tabela	
  verdade	
  e	
  conecFvos	
  lógicos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
15	
  
  Tabela	
  da	
  Verdade	
  
  Negação	
  
Negação	
  
P	
   ¬P	
  
V	
   F	
  
F	
   V	
  
Se	
  P	
  é	
  verdade,	
  então	
  ¬P	
  é	
  falso;	
  e	
  
se	
  P	
  é	
  falso	
  ¬P	
  é	
  verdade	
  
Tabela	
  verdade	
  e	
  conecFvos	
  lógicos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
16	
  
  Tabela	
  da	
  Verdade	
  
  Conjunção	
  
Conjunção	
  
P	
   Q	
   P∧Q	
  
V	
   V	
   V	
  
V	
   F	
   F	
  
F	
   V	
   F	
  
F	
   F	
   F	
  Se	
  P	
  e	
  Q	
  são	
  verdade,	
  então	
  P∧Q	
  é	
  
verdade;	
  caso	
  contrário	
  P∧Q	
  é	
  falso	
  
Tabela	
  verdade	
  e	
  conecFvos	
  lógicos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
17	
  
  Tabela	
  da	
  Verdade	
  
  Disjunção	
  
Disjunção	
  
P	
   Q	
   P∨Q	
  
V	
   V	
   V	
  
V	
   F	
   V	
  
F	
   V	
   V	
  
F	
   F	
   F	
  Se	
  P	
  e	
  Q	
  são	
  falsos,	
  então	
  P∨Q	
  é	
  
falso;	
  caso	
  contrário	
  P∨Q	
  é	
  
verdade.	
  
Tabela	
  verdade:	
  proposição	
  composta	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
18	
  
  Qual	
  a	
  tabela	
  verdade	
  da	
  proposição	
  ¬(P∧¬Q)	
  ?	
  
¬(P∧¬Q)	
  	
  
P	
   Q	
  
V	
   V	
  
V	
   F	
  
F	
   V	
  
F	
   F	
  
Tabela	
  verdade:	
  proposição	
  composta	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
19	
  
  Qual	
  a	
  tabela	
  verdade	
  da	
  proposição	
  ¬(P∧¬Q)	
  ?	
  
¬(P∧¬Q)	
  	
  
P	
   Q	
   ¬Q	
  
V	
   V	
  
V	
   F	
  
F	
   V	
  
F	
   F	
  
Tabela	
  verdade:	
  proposição	
  composta	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
20	
  
  Qual	
  a	
  tabela	
  verdade	
  da	
  proposição	
  ¬(P∧¬Q)	
  ?	
  
¬(P∧¬Q)	
  	
  
P	
   Q	
   ¬Q	
  
V	
   V	
   F	
  
V	
   F	
  
F	
   V	
  
F	
   F	
  
Tabela	
  verdade:	
  proposição	
  composta	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
21	
  
  Qual	
  a	
  tabela	
  verdade	
  da	
  proposição	
  ¬(P∧¬Q)	
  ?	
  
¬(P∧¬Q)	
  	
  
P	
   Q	
   ¬Q	
  
V	
   V	
   F	
  
V	
   F	
   V	
  
F	
   V	
  
F	
   F	
  
Tabela	
  verdade:	
  proposição	
  composta	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
22	
  
  Qual	
  a	
  tabela	
  verdade	
  da	
  proposição	
  ¬(P∧¬Q)	
  ?	
  
¬(P∧¬Q)	
  	
  
P	
   Q	
   ¬Q	
  
V	
   V	
   F	
  
V	
   F	
   V	
  
F	
   V	
   F	
  
F	
   F	
  
Tabela	
  verdade:	
  proposição	
  composta	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
23	
  
  Qual	
  a	
  tabela	
  verdade	
  da	
  proposição	
  ¬(P∧¬Q)	
  ?	
  
¬(P∧¬Q)	
  	
  
P	
   Q	
   ¬Q	
  
V	
   V	
   F	
  
V	
   F	
   V	
  
F	
   V	
   F	
  
F	
   F	
   V	
  
Tabela	
  verdade:	
  proposição	
  composta	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
24	
  
  Qual	
  a	
  tabela	
  verdade	
  da	
  proposição	
  ¬(P∧¬Q)	
  ?	
  
¬(P∧¬Q)	
  	
  
P	
   Q	
   ¬Q	
  
V	
   V	
   F	
  
V	
   F	
   V	
  
F	
   V	
   F	
  
F	
   F	
   V	
  
Tabela	
  verdade:	
  proposição	
  composta	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
25	
  
  Qual	
  a	
  tabela	
  verdade	
  da	
  proposição	
  ¬(P∧¬Q)	
  ?	
  
¬(P∧¬Q)	
  	
  
P	
   Q	
   ¬Q	
   P∧¬Q	
  
V	
   V	
   F	
   F	
  
V	
   F	
   V	
  
F	
   V	
   F	
  
F	
   F	
   V	
  
Tabela	
  verdade:	
  proposição	
  composta	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
26	
  
  Qual	
  a	
  tabela	
  verdade	
  da	
  proposição	
  ¬(P∧¬Q)	
  ?	
  
¬(P∧¬Q)	
  	
  
P	
   Q	
   ¬Q	
   P∧¬Q	
  
V	
   V	
   F	
   F	
  
V	
   F	
   V	
   V	
  
F	
   V	
   F	
  
F	
   F	
   V	
  
Tabela	
  verdade:	
  proposição	
  composta	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
27	
  
  Qual	
  a	
  tabela	
  verdade	
  da	
  proposição	
  ¬(P∧¬Q)	
  ?	
  
¬(P∧¬Q)	
  	
  
P	
   Q	
   ¬Q	
   P∧¬Q	
  
V	
   V	
   F	
   F
V	
   F	
   V	
   V	
  
F	
   V	
   F	
   F	
  
F	
   F	
   V	
  
Tabela	
  verdade:	
  proposição	
  composta	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
28	
  
  Qual	
  a	
  tabela	
  verdade	
  da	
  proposição	
  ¬(P∧¬Q)	
  ?	
  
¬(P∧¬Q)	
  	
  
P	
   Q	
   ¬Q	
   P∧¬Q	
  
V	
   V	
   F	
   F	
  
V	
   F	
   V	
   V	
  
F	
   V	
   F	
   F	
  
F	
   F	
   V	
   F	
  
Tabela	
  verdade:	
  proposição	
  composta	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
29	
  
  Qual	
  a	
  tabela	
  verdade	
  da	
  proposição	
  ¬(P∧¬Q)	
  ?	
  
¬(P∧¬Q)	
  	
  
P	
   Q	
   ¬Q	
   P∧¬Q	
  
V	
   V	
   F	
   F	
  
V	
   F	
   V	
   V	
  
F	
   V	
   F	
   F	
  
F	
   F	
   V	
   F	
  
Tabela	
  verdade:	
  proposição	
  composta	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
30	
  
  Qual	
  a	
  tabela	
  verdade	
  da	
  proposição	
  ¬(P∧¬Q)	
  ?	
  
¬(P∧¬Q)	
  	
  
P	
   Q	
   ¬Q	
   P∧¬Q	
   ¬(P∧¬Q)	
  
V	
   V	
   F	
   F	
   V	
  
V	
   F	
   V	
   V	
  
F	
   V	
   F	
   F	
  
F	
   F	
   V	
   F	
  
Tabela	
  verdade:	
  proposição	
  composta	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
31	
  
  Qual	
  a	
  tabela	
  verdade	
  da	
  proposição	
  ¬(P∧¬Q)	
  ?	
  
¬(P∧¬Q)	
  	
  
P	
   Q	
   ¬Q	
   P∧¬Q	
   ¬(P∧¬Q)	
  
V	
   V	
   F	
   F	
   V	
  
V	
   F	
   V	
   V	
   F	
  
F	
   V	
   F	
   F	
  
F	
   F	
   V	
   F	
  
Tabela	
  verdade:	
  proposição	
  composta	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
32	
  
  Qual	
  a	
  tabela	
  verdade	
  da	
  proposição	
  ¬(P∧¬Q)	
  ?	
  
¬(P∧¬Q)	
  	
  
P	
   Q	
   ¬Q	
   P∧¬Q	
   ¬(P∧¬Q)	
  
V	
   V	
   F	
   F	
   V	
  
V	
   F	
   V	
   V	
   F	
  
F	
   V	
   F	
   F	
   V	
  
F	
   F	
   V	
   F	
  
Tabela	
  verdade:	
  proposição	
  composta	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
33	
  
  Qual	
  a	
  tabela	
  verdade	
  da	
  proposição	
  ¬(P∧¬Q)	
  ?	
  
¬(P∧¬Q)	
  	
  
P	
   Q	
   ¬Q	
   P∧¬Q	
   ¬(P∧¬Q)	
  
V	
   V	
   F	
   F	
   V	
  
V	
   F	
   V	
   V	
   F	
  
F	
   V	
   F	
   F	
   V	
  
F	
   F	
   V	
   F	
   V	
  
Tabela	
  verdade:	
  proposição	
  composta	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
34	
  
  Qual	
  a	
  tabela	
  verdade	
  da	
  proposição	
  ¬(P∧¬Q)	
  ?	
  
¬(P∧¬Q)	
  	
  
P	
   Q	
   ¬Q	
   P∧¬Q	
   ¬(P∧¬Q)	
  
V	
   V	
   F	
   F	
   V	
  
V	
   F	
   V	
   V	
   F	
  
F	
   V	
   F	
   F	
   V	
  
F	
   F	
   V	
   F	
   V	
  
Assinalar	
  “valores-‐verdade”	
  para	
  proposições	
  compostas	
  permite	
  o	
  uso	
  da	
  lógica	
  para	
  
decidir	
  a	
  verdade	
  de	
  uma	
  proposição	
  usando	
  somente	
  o	
  conhecimento	
  das	
  partes	
  
Exercícios	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
35	
  
1.  Escreva	
  as	
  seguintes	
  sentenças	
  como	
  proposições	
  em	
  lógica:	
  
a)  Milcíades	
  lê	
  O	
  Mascate	
  ou	
  Folha	
  de	
  São	
  Paulo,	
  mas	
  não	
  lê	
  o	
  Valor	
  
Econômico.	
  
b)  Leonêsa	
  é	
  pobre,	
  ou	
  é	
  rica	
  e	
  infeliz.	
  
c)  Vai	
  chover	
  ou	
  vai	
  nevar,	
  mas	
  não	
  ambos.	
  
2.  Construa	
  a	
  tabela-‐verdade	
  das	
  seguintes	
  proposições:	
  
a)  (P∧Q)∧¬(P∨Q)	
  	
  
b)  ¬(¬P∨Q)	
  
c)  (P∨Q)∧¬Q	
  
ConecFvos	
  lógicos	
  condicional	
  e	
  bicondicional	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
36	
  
  Terminologia	
  	
  
u  Negação:	
  ¬	
  
u  Conjunção:	
  ∧	
  
u  Disjunção:	
  ∨	
  
u  Condicional:	
  	
  →	
  
u  Bicondicional:	
  	
  ↔	
  
P→Q:	
  (se	
  P,	
  então	
  Q)	
  
-  se	
  MD	
  é	
  fácil	
  então	
  serei	
  aprovado	
  
-  MD	
  ser	
  fácil	
  implica	
  que	
  serei	
  
aprovado	
  
-  MD	
  ser	
  fácil	
  é	
  condição	
  suﬁciente	
  
para	
  eu	
  ser	
  aprovado	
  
-  Serei	
  aprofado	
  caso	
  MD	
  seja	
  fácil	
  
	
  
Proposições	
  atômicas	
  
P:	
  	
  MD	
  é	
  fácil	
  
Q:	
  Serei	
  aprovado	
  
ConecFvos	
  lógicos	
  condicional	
  e	
  bicondicional	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
37	
  
  Terminologia	
  	
  
u  Negação:	
  ¬	
  
u  Conjunção:	
  ∧	
  
u  Disjunção:	
  ∨	
  
u  Condicional:	
  	
  →	
  
u  Bicondicional:	
  	
  ↔	
  
P↔Q:	
  (P	
  se,	
  e	
  somente	
  se,	
  Q)	
  
-  x	
  é	
  par	
  se,	
  e	
  somente	
  se,	
  x+1	
  é	
  ímpar	
  
-  x	
  é	
  par	
  é	
  condição	
  necessária	
  e	
  
suﬁciente	
  para,	
  x+1	
  ser	
  ímpar	
  
-  se	
  x	
  é	
  par,	
  então	
  x+1	
  é	
  ímpar,	
  e	
  vice-‐
versa	
  
Proposições	
  atômicas	
  
P:	
  x	
  é	
  par	
  
Q:	
  x+1	
  é	
  ímpar	
  
Tabela	
  verdade	
  e	
  conecFvos	
  lógicos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
38	
  
  Tabela	
  da	
  Verdade	
  
  Condicional	
  
Condicional	
  
P	
   Q	
   P→Q	
  
V	
   V	
   V	
  
V	
   F	
   F	
  
F	
   V	
   V	
  
F	
   F	
   V	
  Se	
  P	
  é	
  verdade	
  e	
  Q	
  é	
  falso,	
  então	
  
P→Q	
  é	
  falso;	
  caso	
  contrário	
  é	
  
verdadeiro	
  
Tabela	
  verdade	
  e	
  conecFvos	
  lógicos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
39	
  
  Tabela	
  da	
  Verdade	
  
  Condicional	
  
Condicional	
  
P	
   Q	
   P→Q	
  
V	
   V	
   V	
  
V	
   F	
   F	
  
F	
   V	
   V	
  
F	
   F	
   V	
  Caso	
  interessante:	
  se	
  P	
  é	
  falso	
  e	
  Q	
  é	
  
verdadeiro,	
  então	
  P→Q	
  é	
  
verdadeiro	
  
Se	
  Ozzy	
  Osbourne	
  cantou	
  no	
  Restart,	
  
então	
  todos	
  passarão	
  em	
  MD	
  
	
  
Quando	
  nevou	
  em	
  Manaus,	
  choveu	
  
piranhas	
  em	
  Paris	
  
Verdadeiro	
  ou	
  falso?	
  
Tabela	
  verdade	
  e	
  conecFvos	
  lógicos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
40	
  
  Tabela	
  da	
  Verdade	
  
  Condicional	
  
Condicional	
  
P	
   Q	
   P→Q	
  
V	
   V	
   V	
  
V	
   F	
   F	
  
F	
   V	
   V	
  
F	
   F	
   V	
  
Bruna	
  Marquezine	
  lhe	
  fez	
  a	
  seguinte	
  
promessa	
  para	
  ErnesFno:	
  
	
  
Se	
  você	
  ganhar	
  na	
  megasena,	
  então	
  eu	
  
caso	
  com	
  você	
  
Em	
  que	
  situação	
  Bruna	
  estaria	
  menFdo?	
  
E	
  se	
  ErnesFno	
  não	
  ganhar	
  na	
  megasena?	
  
Tabela	
  verdade	
  e	
  conecFvos	
  lógicos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br)
Matemática Discreta 
41	
  
  Tabela	
  da	
  Verdade	
  
  Bicondicional	
  
Bicondicional	
  
P	
   Q	
   P↔Q	
  
V	
   V	
   V	
  
V	
   F	
   F	
  
F	
   V	
   F	
  
F	
   F	
   V	
  Se	
  P	
  e	
  Q	
  são	
  iguais,	
  então	
  P↔Q	
  é	
  
verdadeiro;	
  caso	
  contrário	
  é	
  falso	
  
Galvão	
  é	
  pai	
  de	
  Cacá	
  se,	
  e	
  somente	
  se,	
  
Cacá	
  é	
  ﬁlho	
  de	
  Galvão	
  
Exercícios	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
42	
  
1.  Escreva	
  as	
  seguintes	
  proposições	
  compostas	
  em	
  notação	
  simbólica	
  
a)  Os	
  abacates	
  estão	
  maduros	
  quando	
  estão	
  macios	
  
b)  Uma	
  boa	
  dieta	
  é	
  uma	
  condição	
  necessária	
  para	
  você	
  ser	
  saudável	
  
c)  Se	
  os	
  preços	
  subirem,	
  então	
  haverá	
  muitas	
  casas	
  para	
  vender	
  e	
  elas	
  serão	
  
caras;	
  mas	
  se	
  as	
  casas	
  não	
  forem	
  caras,	
  então	
  ainda	
  assim	
  haverá	
  muitas	
  
casas	
  para	
  vender.	
  
d)  Tanto	
  ir	
  para	
  cama	
  como	
  nadar	
  é	
  condição	
  suﬁciente	
  para	
  trocar	
  de	
  roupa;	
  
no	
  entanto,	
  trocar	
  de	
  roupa	
  não	
  signiﬁca	
  que	
  se	
  vai	
  nadar.	
  
2.  Escreva	
  as	
  tabelas-‐verdade	
  das	
  seguintes	
  proposições	
  
a)  (P	
  ∧	
  Q)	
  ↔	
  ¬P	
  ∨	
  ¬Q	
  
b)  [P	
  ∧	
  (¬Q	
  →	
  ¬P)]	
  →	
  Q	
  
c)  (¬P	
  →	
  ¬Q)	
  ∧	
  [	
  (P	
  →	
  Q)	
  →	
  P	
  ]	
  
Linguagem	
  proposicional	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
43	
  
  Uma	
  linguagem	
  proposicional	
  L	
  é	
  composta	
  por	
  
u  Um	
  Alfabeto	
  (letras	
  maiúsculas,	
  o	
  conjunto	
  {V,F}	
  e	
  os	
  conecFvos	
  lógicos)	
  	
  
u  Símbolos	
  para	
  variáveis	
  e	
  constantes	
  e	
  proposições	
  compostas	
  ou	
  fórmulas	
  
  A	
  GramáFca	
  de	
  uma	
  linguagem	
  proposicional	
  deﬁne	
  a	
  sintaxe	
  
das	
  expressões	
  
u  Permite	
  a	
  formação	
  e	
  o	
  reconhecimento	
  de	
  fórmulas	
  bem	
  formadas	
  (f)	
  
u  Exemplo:	
  	
  P¬vQ	
  	
  (fórmula	
  incorreta,	
  mal	
  formada)	
  
GramáFca	
  de	
  uma	
  linguagem	
  proposicional	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
44	
  
1.  Letras	
  proposicionais	
  do	
  vocabulário	
  são	
  fórmulas	
  em	
  L	
  
2.  Se	
  α	
  e	
  β	
  são	
  fórmulas	
  em	
  L,	
  então	
  também	
  são	
  fórmulas	
  as	
  
seguintes	
  expressões:	
  
u  ¬α	
  
u  α	
  ∧	
  β	
  	
  
u  α	
  ∨	
  β	
  	
  
u  α	
  →	
  β	
  
u  α	
  ↔	
  β	
  
  Somente	
  o	
  que	
  pode	
  ser	
  gerado	
  através	
  dos	
  itens	
  1	
  e	
  2	
  em	
  um	
  
número	
  ﬁnito	
  de	
  passos	
  é	
  uma	
  fórmula	
  em	
  L	
  
Ambiguidade	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
45	
  
1.  P	
  ∨	
  Q	
  ∧	
  R	
  =	
  (P	
  ∨	
  Q)	
  ∧	
  R	
  	
  ?	
  
2.  P	
  ∨	
  Q	
  ∧	
  R	
  =	
  	
  P	
  ∨	
  (Q	
  ∧	
  R)	
  ?	
  
u  O	
  PSDB	
  ganhou	
  a	
  eleição	
  ou	
  o	
  PT	
  ganhou	
  a	
  eleição,	
  e	
  o	
  Brasil	
  começou	
  a	
  
mudar?	
  
u  O	
  PSDB	
  ganhou	
  a	
  eleição,	
  ou	
  o	
  PT	
  ganhou	
  a	
  eleição	
  e	
  o	
  Brasil	
  começou	
  a	
  
mudar?	
  
Ambiguidade	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
46	
  
1.  P	
  ∨	
  Q	
  ∧	
  R	
  =	
  (P	
  ∨	
  Q)	
  ∧	
  R	
  	
  ?	
  
2.  P	
  ∨	
  Q	
  ∧	
  R	
  =	
  	
  P	
  ∨	
  (Q	
  ∧	
  R)	
  ?	
  
	
  
P	
   Q	
   R	
   P	
  ∨	
  Q	
   Q	
  ∧	
  R	
   (P	
  ∨	
  Q)	
  ∧	
  R	
   P	
  ∨	
  (Q	
  ∧	
  R)	
  
V	
   V	
   F	
  
V	
   V	
   V	
  
V	
   F	
   F	
  
V	
   F	
   V	
  
F	
   V	
   F	
  
F	
   V	
   V	
  
F	
   F	
   F	
  
F	
   F	
   V	
  
Ambiguidade	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
47	
  
1.  P	
  ∨	
  Q	
  ∧	
  R	
  =	
  (P	
  ∨	
  Q)	
  ∧	
  R	
  	
  ?	
  
2.  P	
  ∨	
  Q	
  ∧	
  R	
  =	
  	
  P	
  ∨	
  (Q	
  ∧	
  R)	
  ?	
  
	
  
P	
   Q	
   R	
   P	
  ∨	
  Q	
   Q	
  ∧	
  R	
   (P	
  ∨	
  Q)	
  ∧	
  R	
   P	
  ∨	
  (Q	
  ∧	
  R)	
  
V	
   V	
   F	
   V	
  
V	
   V	
   V	
   V	
  
V	
   F	
   F	
   V	
  
V	
   F	
   V	
   V	
  
F	
   V	
   F	
   V	
  
F	
   V	
   V	
   V	
  
F	
   F	
   F	
   F	
  
F	
   F	
   V	
   F	
  
Ambiguidade	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
48	
  
1.  P	
  ∨	
  Q	
  ∧	
  R	
  =	
  (P	
  ∨	
  Q)	
  ∧	
  R	
  	
  ?	
  
2.  P	
  ∨	
  Q	
  ∧	
  R	
  =	
  	
  P	
  ∨	
  (Q	
  ∧	
  R)	
  ?	
  
	
  
P	
   Q	
   R	
   P	
  ∨	
  Q	
   Q	
  ∧	
  R	
   (P	
  ∨	
  Q)	
  ∧	
  R	
   P	
  ∨	
  (Q	
  ∧	
  R)	
  
V	
   V	
   F	
   V	
   F	
  
V	
   V	
   V	
   V	
   V	
  
V	
   F	
   F	
   V	
   F	
  
V	
   F	
   V	
   V	
   V	
  
F	
   V	
   F	
   V	
   F	
  
F	
   V	
   V	
   V	
   V	
  
F	
   F	
   F	
   F	
   F	
  
F	
   F	
   V	
   F	
   F	
  
Ambiguidade	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
49	
  
1.  P	
  ∨	
  Q	
  ∧	
  R	
  =	
  (P	
  ∨	
  Q)	
  ∧	
  R	
  	
  ?	
  
2.  P	
  ∨	
  Q	
  ∧	
  R	
  =	
  	
  P	
  ∨	
  (Q	
  ∧	
  R)	
  ?	
  
	
  
P	
   Q	
   R	
   P	
  ∨	
  Q	
   Q	
  ∧	
  R	
   (P	
  ∨	
  Q)	
  ∧	
  R	
   P	
  ∨	
  (Q	
  ∧	
  R)	
  
V	
   V	
   F	
   V	
   F	
   F	
  
V	
   V	
   V	
   V	
   V	
   V	
  
V	
   F	
   F	
   V	
   F	
   F	
  
V	
   F	
   V	
   V	
   F	
   V	
  
F	
   V	
   F	
   V	
   F	
   F	
  
F	
   V	
   V	
   V	
   V	
   V	
  
F	
   F	
   F	
   F	
   F	
   F	
  
F	
   F	
   V	
   F	
   F	
   F	
  
Ambiguidade	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
50	
  
1.  P	
  ∨	
  Q	
  ∧	
  R	
  =	
  (P	
  ∨	
  Q)	
  ∧	
  R	
  	
  ?	
  
2.  P	
  ∨	
  Q	
  ∧	
  R	
  =	
  	
  P	
  ∨	
  (Q	
  ∧	
  R)	
  ?	
  
	
  
P	
   Q	
   R	
   P	
  ∨	
  Q	
   Q	
  ∧	
  R	
   (P	
  ∨	
  Q)	
  ∧	
  R	
   P	
  ∨	
  (Q	
  ∧	
  R)	
  
V	
   V	
   F	
   V	
   F	
   F	
   V	
  
V	
   V	
   V	
   V	
   V	
   V	
   V	
  
V	
   F	
   F	
   V	
   F	
   F	
   V	
  
V	
   F	
   V	
   V	
   F	
   V	
   V	
  
F	
   V	
   F	
   V	
   F	
   F	
   F	
  
F	
   V	
   V	
   V	
   V	
   V	
   V	
  
F	
   F	
   F	
   F	
   F	
   F	
   F	
  
F	
   F	
   V	
   F	
   F	
   F	
   F	
  
Ambiguidade	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
51	
  
1.  P	
  ∨	
  Q	
  ∧	
  R	
  =	
  (P	
  ∨	
  Q)	
  ∧	
  R	
  	
  ?	
  
2.  P	
  ∨	
  Q	
  ∧	
  R	
  =	
  	
  P	
  ∨	
  (Q	
  ∧	
  R)	
  ?	
  
	
  
P	
   Q	
   R	
   P	
  ∨	
  Q	
   Q	
  ∧	
  R	
   (P
∨	
  Q)	
  ∧	
  R	
   P	
  ∨	
  (Q	
  ∧	
  R)	
  
V	
   V	
   F	
   V	
   F	
   F	
   V	
  
V	
   V	
   V	
   V	
   V	
   V	
   V	
  
V	
   F	
   F	
   V	
   F	
   F	
   V	
  
V	
   F	
   V	
   V	
   F	
   V	
   V	
  
F	
   V	
   F	
   V	
   F	
   F	
   F	
  
F	
   V	
   V	
   V	
   V	
   V	
   V	
  
F	
   F	
   F	
   F	
   F	
   F	
   F	
  
F	
   F	
   V	
   F	
   F	
   F	
   F	
  
Ambiguidade	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
52	
  
  Solução:	
  ordem	
  de	
  precedência	
  
1.  Parênteses	
  mais	
  internos	
  
2.  Negação:	
  ¬	
  
3.  Conjunção:	
  ∧	
  
4.  Disjunção:	
  ∨	
  
5.  Condicional:	
  	
  →	
  
6.  Bicondicional:	
  	
  ↔	
  
Tautologia	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
53	
  
  Sempre	
  verdade	
  independente	
  dos	
  valores	
  verdade	
  das	
  variáveis	
  
  Também	
  denominada	
  proposição	
  tautológica	
  ou	
  logicamente	
  
verdadeira	
  
  Exemplo	
  
u  P	
  ∨	
  ¬P	
  	
  
u  “Amanhã	
  vai	
  chover	
  ou	
  amanhã	
  não	
  vai	
  chover”	
  	
  
Contradição	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
54	
  
  Sempre	
  falso	
  independente	
  dos	
  valores	
  verdade	
  das	
  variáveis	
  
  Exemplo	
  	
  
u  P	
  ∧	
  ¬P	
  
u  Hoje	
  choveu	
  e	
  hoje	
  não	
  choveu	
  
  Observação	
  
u  A	
  negação	
  de	
  uma	
  tautologia	
  é	
  uma	
  contradição	
  
u  A	
  negação	
  de	
  uma	
  contradição	
  é	
  uma	
  tautologia	
  
ConFngência	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
55	
  
  Fórmula	
  bem	
  formada	
  que	
  não	
  é	
  tautologia	
  e	
  nem	
  é	
  contradição	
  
  Seu	
  valor	
  verdade	
  dependente	
  dos	
  valores	
  verdade	
  das	
  variáveis	
  
  Exemplo	
  	
  
u  P	
  ∧	
  Q	
  
u  Hoje	
  choveu	
  e	
  ontem	
  nevou	
  
Exercício	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
56	
  
Veriﬁque	
  se	
  as	
  proposições	
  abaixo	
  são	
  tautologia,	
  contradição	
  ou	
  
conFngência	
  
1.  (P	
  ∧	
  Q)	
  →	
  (P	
  ↔	
  Q)	
  
2.  (P	
  ∧	
  Q)	
  ∧	
  ¬(P	
  ∨	
  Q)	
  
3.  P	
  ∧	
  Q	
  ↔	
  ¬Q	
  ∨	
  ¬P	
  
4.  [	
  (P	
  →	
  Q)	
  →	
  (P	
  ∨	
  R)]	
  →	
  (Q	
  ∨	
  R)	
  
Equivalência	
  lógica	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
57	
  
  Duas	
  proposições	
  α	
  e	
  β	
  são	
  logicamente	
  equivalentes	
  (α	
  ⇔	
  β),	
  
se	
  ambas	
  possuem	
  tabelas-‐verdade	
  idênFcas	
  
  Exemplo	
  
u  O	
  São	
  Raimundo	
  é	
  o	
  melhor	
  Fme	
  do	
  Amazonas	
  e	
  vence	
  sempre	
  	
  	
  	
  
u  O	
  São	
  Raimundo	
  vence	
  sempre	
  e	
  é	
  o	
  melhor	
  Fme	
  do	
  Amazonas	
  
u  (P	
  ∧	
  Q)	
  ⇔	
  (Q	
  ∧	
  P)	
  
Equivalência	
  lógica	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
58	
  
  Duas	
  proposições	
  α	
  e	
  β	
  são	
  logicamente	
  equivalentes	
  (α	
  ⇔	
  β),	
  
se	
  ambas	
  possuem	
  tabelas-‐verdade	
  idênFcas	
  
  Exemplo	
  
u  Jurandir	
  é	
  GaranFdo	
  ou	
  é	
  Caprichoso	
  
u  Jurandir	
  é	
  Caprichoso	
  ou	
  é	
  GaranFdo	
  
u  (P	
  ∨	
  Q)	
  ⇔	
  (Q	
  ∨	
  P)	
  
Equivalência	
  lógica	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
59	
  
  Duas	
  proposições	
  α	
  e	
  β	
  são	
  logicamente	
  equivalentes	
  (α	
  ⇔	
  β),	
  
se	
  ambas	
  possuem	
  tabelas-‐verdade	
  idênFcas	
  
  Exemplo	
  
u  Se	
  Nancy	
  está	
  dormindo,	
  então	
  Freddy	
  Krueger	
  aparece	
  
u  Se	
  Freddy	
  Krueger	
  não	
  aparece,	
  então	
  Nancy	
  não	
  está	
  dormindo	
  
u  (P	
  →	
  Q)	
  ⇔	
  (¬Q	
  →	
  ¬P)	
  
Teorema	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
60	
  
α	
  ⇔	
  β	
  se,	
  e	
  somente	
  se,	
  α	
  ↔	
  β	
  é	
  tautologia.	
  
  Exemplos	
  
u  (P	
  →	
  Q)	
  ↔	
  (¬P	
  ∨	
  Q)	
  é	
  tautologia	
  
u  Logo,	
  (P	
  →	
  Q)	
  ⇔	
  (¬P	
  ∨	
  Q)	
  
u  [	
  P	
  →	
  (Q	
  →	
  R)	
  ]	
  ↔	
  [(P	
  ∧	
  Q)	
  →	
  R	
  ]	
  é	
  tautologia	
  
u  Logo,	
  [	
  P	
  →	
  (Q	
  →	
  R)	
  ]	
  ⇔	
  [(P	
  ∧	
  Q)	
  →	
  R	
  ]	
  
Exercício	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
61	
  
Veriﬁque	
  se	
  as	
  proposições	
  abaixo	
  são	
  equivalências	
  lógicas	
  
1.  ¬(P	
  ∧	
  Q)	
  →	
  (P	
  ↔	
  Q)	
  	
  	
  e	
  	
  	
  (¬P	
  ∨	
  ¬Q)	
  
2.  P	
  ∨	
  (Q	
  ∧	
  R)	
  	
  	
  e	
  	
  	
  [	
  (P	
  ∨	
  Q)	
  ∧	
  R)	
  ]	
  	
  
3.  ¬(¬P	
  ∨	
  Q)	
  	
  	
  e	
  	
  	
  ¬P	
  →	
  ¬Q	
  
Regras	
  de	
  equivalência	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
62	
  
  Duas	
  proposições	
  α	
  e	
  β	
  são	
  logicamente	
  equivalentes	
  (α	
  ⇔	
  β),	
  
se	
  ambas	
  possuem	
  tabelas-‐verdade	
  idênFcas	
  
u Deﬁnem	
  que	
  determinados	
  pares	
  de	
  FBFs	
  são	
  equivalentes	
  
u Portanto,	
  se	
  α	
  ⇔	
  β,	
  então	
  α	
  pode	
  ser	
  subsFtuída	
  por	
  β	
  em	
  
qualquer	
  	
  FBFs	
  sem	
  mudança	
  em	
  seu	
  valor	
  lógico	
  
Regras	
  de	
  equivalência	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Fundamentos de Teoria da Computação 
63	
  
Fórmula	
   Lei	
  
P∨P	
  ≡	
  P	
  
P∧P	
  ≡	
  P	
   Idempotência	
  
(P∨Q)∨R	
  ≡	
  P∨(Q∨R)	
  
(P∧Q)∧R	
  ≡	
  P∧(Q∧R)	
   AssociaFva	
  
P∨Q	
  ≡	
  Q∨P	
  
P∧Q	
  ≡	
  Q∧P	
   ComutaFva	
  
(P∧Q)∨R	
  ≡	
  (P∨R)∧(Q∨R)	
  
(P∨Q)∧R	
  ≡	
  (P∧R)∨(Q∧R)	
   DistribuFva	
  
P∨F	
  ≡	
  P	
  
P∨V	
  ≡	
  V	
  
P∧V	
  ≡	
  P	
  
P∧F	
  ≡	
  F	
   IdenFdade	
  
Regras	
  de	
  equivalência	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Fundamentos de Teoria da Computação 
64	
  
Fórmula	
   Lei	
  
P∨¬P	
  ≡	
  V	
  
¬V	
  ≡	
  F	
  
P∧¬P	
  ≡	
  F	
  
¬F	
  ≡	
  V	
   Complemento	
  
¬¬P	
  ≡	
  P	
   Involução	
  
¬(P∧Q)	
  ≡	
  ¬P∨¬Q	
  
¬(P∨Q)	
  ≡	
  ¬P∧¬Q	
   DeMorgan	
  
P→Q	
  ≡	
  ¬P∨Q	
   Condicional	
  
Regras	
  de	
  equivalência	
  (resumo)	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Fundamentos de Teoria da Computação 
65	
  
Fórmula	
   Lei	
  
P∨P	
  ≡	
  P	
  
P∧P	
  ≡	
  P	
   Idempotência	
  
(P∨Q)∨R	
  ≡	
  P∨(Q∨R)	
  
(P∧Q)∧R	
  ≡	
  P∧(Q∧R)	
   AssociaFva	
  
P∨Q	
  ≡	
  Q∨P	
  
P∧Q	
  ≡	
  Q∧P	
   ComutaFva	
  
(P∧Q)∨R	
  ≡	
  (P∨R)∧(Q∨R)	
  
(P∨Q)∧R	
  ≡	
  (P∧R)∨(Q∧R)	
   DistribuFva	
  
P∨F	
  ≡	
  P	
  
P∨V	
  ≡	
  V	
  
P∧V	
  ≡	
  P	
  
P∧F	
  ≡	
  F	
   IdenFdade	
  
P∨¬P	
  ≡	
  V	
  
¬V	
  ≡	
  F	
  
P∧¬P	
  ≡
F	
  
¬F	
  ≡	
  V	
   Complemento	
  
¬¬P	
  ≡	
  P	
   Involução	
  
¬(P∧Q)	
  ≡	
  ¬P∨¬Q	
  
¬(P∨Q)	
  ≡	
  ¬P∧¬Q	
   DeMorgan	
  
P→Q	
  ≡	
  ¬P∨Q	
   Condicional	
  
__MACOSX/._parte-01-logica-formal.pdf