Cap11 - Mat. Complementar - Operações Lógicas sobre Sentenças Abertas

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

LÓGICA PARA COMPUTAÇÃO 	
  
Professora Luciana Conceição Dias Campos	
   1	
  	
  
Capítulo	
  11	
  –	
  Operações	
  Lógicas	
  sobre	
  Sentenças	
  Abertas	
  
	
  
Até	
  o	
  capítulo	
  10,	
  apresentou-­‐se	
  conteúdos	
  do	
  cálculo	
  proposicional.	
  
Agora	
  começaremos	
  um	
  novo	
  conteúdo	
  relacionado	
  ao	
  cálculo	
  de	
  predicados	
  ou	
  lógica	
  de	
  primeira	
  ordem.	
  	
  
	
  
Neste	
   capítulo,	
   vimos	
   o	
   conceito	
   de	
   Sentenças	
   Abertas.	
   Uma	
   sentença	
   aberta	
   é	
   como	
   uma	
  
proposição	
   que	
   contém	
  pelo	
  menos	
   uma	
   variável.	
   Desta	
   forma,	
   não	
   é	
   possível	
   avaliar,	
   por	
   conta	
   desta	
  
variável,	
  se	
  esta	
  sentença	
  é	
  verdadeira	
  ou	
  falsa.	
  Contudo,	
  esta	
  variável	
  pertence	
  a	
  um	
  conjunto	
  universo,	
  
chamado	
  de	
  domínio	
  da	
  variável.	
  Dentro	
  deste	
  domínio,	
  é	
  possível	
  se	
  estabelecer	
  um	
  conjunto	
  verdade,	
  
que	
  corresponde	
  a	
  todos	
  os	
  valores	
  (dentro	
  do	
  domínio)	
  que	
  a	
  variável	
  pode	
  assumir	
  fazendo	
  com	
  que	
  a	
  
sentença	
  seja	
  verdadeira.	
  
Exemplo:	
  Considere	
  ℕ	
  (conjunto	
  dos	
  números	
  naturais)	
  o	
  universo	
  da	
  variável	
  𝑋.	
  Dadas	
  as	
  sentenças	
  
abertas	
  𝑝(𝑋):	
  
1. 𝑋 + 1 > 8.	
  
2. 𝑋 + 7 < 5.	
  
3. 𝑋	
  é	
  divisor	
  de	
  10.	
  
4. 𝑋 + 3 > 1	
  
Temos	
  que	
  o	
  conjunto	
  verdade	
  destas	
  sentenças,	
  expresso	
  por	
  Vp,	
  é	
  dado	
  por:	
  
1. Vp	
  =	
  {9, 10, 11… } ⊂ ℕ	
  
2. Vp	
  =	
  ∅ ⊂ ℕ	
  
3. Vp	
  =	
  {1, 2, 5, 10} ⊂ ℕ	
  
4. Vp	
  =	
   1, 2, 3… = ℕ	
  
	
  
Veja	
  que	
  em	
  uma	
  sentença	
  aberta	
  𝑝(𝑋)	
  em	
  um	
  universo	
  U	
  pode	
  ocorrer	
  3	
  situações:	
  
1. O	
  conjunto	
  verdade	
  coincidir	
  com	
  o	
  universo	
  da	
  variável.	
  Vp	
  =	
  U.	
  Neste	
  caso,	
  diz-­‐se	
  que	
  a	
  sentença	
  
exprime	
  uma	
  condição	
  universal.	
  
2. O	
  conjunto	
  verdade	
  é	
  vazio.	
  Vp	
  =	
  ∅.	
  Ou	
  seja,	
  a	
  sentença	
  não	
  é	
  verdadeira	
  para	
  nenhum	
  elemento	
  
do	
  universo	
  U.	
  Neste	
  caso,	
  diz-­‐se	
  que	
  a	
  sentença	
  exprime	
  uma	
  condição	
  impossível.	
  
3. O	
  conjunto	
  verdade	
  é	
  um	
  subconjunto	
  do	
  universo	
  U.	
  Vp  ⊂	
  U.	
  Ou	
  seja,	
  a	
  sentença	
  é	
  verdadeira	
  para	
  
alguns	
  elementos	
  do	
  universo.	
  Neste	
  caso,	
  diz-­‐se	
  que	
  a	
  sentença	
  exprime	
  uma	
  condição	
  possível.	
  	
  
	
  
Quando	
   a	
   sentença	
   aberta	
   possui	
   mais	
   de	
   uma	
   variável,	
   do	
   tipo	
  𝑝(𝑋,𝑌),	
   temos	
   que	
   o	
   universo	
   desta	
  
sentença	
   é	
   dado	
   pelo	
   produto	
   cartesiano	
   de	
   UX×	
  Uy.	
   Então,	
   uma	
   sentença	
   aberta	
  𝑝(𝑋,𝑌)	
  em	
   UX  ×	
  Uy	
  
torna-­‐se	
  verdadeira	
  (ou	
  falsa)	
  todas	
  as	
  vezes	
  que	
  as	
  variáveis	
  são	
  substituídas	
  pelo	
  par	
  ordenado	
  (𝑎, 𝑏)	
  com	
  (𝑎, 𝑏) ∈	
  UX  ×	
  Uy.	
  
Exemplo:	
  Sejam	
  os	
  conjuntos  𝐴 = {1, 2, 3, 4}	
  e	
  𝐵 = {1, 3, 5}.	
  São	
  sentenças	
  abertas	
  𝑝 𝑋,𝑌 	
  em	
  𝐴  ×  𝐵:	
  
1. 𝑋 < 𝑌.	
  
2. 𝑌 = 2𝑋.	
  
O	
  conjunto	
  verdade	
  destas	
  sentenças	
  são:	
  
1. Vp	
  =	
   𝑋,𝑌    𝑋 ∈ 𝐴   ∧ 𝑌 ∈ 𝐵   ∧ 𝑋 < 𝑌 = { 1,3 , 1,5 , 2,3 , 2,5 , 3,5 , 4,5 } ⊂ 𝐴×𝐵.	
  
2. Vp	
  =	
   𝑋,𝑌    𝑋 ∈ 𝐴   ∧ 𝑌 ∈ 𝐵   ∧ 𝑌 = 2𝑋 = ∅ ⊂ 𝐴×𝐵.	
  
LÓGICA PARA COMPUTAÇÃO 
 
Professora Luciana Conceição Dias Campos	
   2	
  	
  
	
  
A	
  idéia	
  de	
  2	
  variáveis	
  pode	
  ser	
  estendida	
  para	
  N	
  variáveis.	
  
	
  
	
  
As	
  operações	
  com	
  os	
  conectivos	
  lógicos	
  vistos	
  no	
  cálculo	
  proposicional	
  podem	
  ser	
  aplicados	
  às	
  sentenças	
  
abertas:	
  
	
  
1. NEGAÇÃO	
  
Seja	
  a	
  sentença	
  aberta	
  𝑝(𝑋)	
  em	
  um	
  conjunto	
  A.	
  
Tem-­‐se	
  que	
  a	
  negação	
  desta	
  sentença	
  aberta	
  é	
  a	
  sentença	
  dada	
  por	
  ~𝑝(𝑋)	
  em	
  A.	
  
Um	
   elemento	
  𝑎 ∈ 𝐴	
  satisfaz	
   a	
   sentença	
   aberta	
  ~𝑝(𝑋),	
   se	
   e	
   somente	
   se,	
  ~𝑝(𝑎)	
  for	
   verdadeira.	
   E	
  
isto	
  só	
  ocorre	
  se	
  𝑝(𝑎)	
  for	
  falsa,	
  ou	
  seja,	
  se	
  o	
  elemento	
  𝑎 ∈ 𝐴	
  não	
  satisfaz	
  a	
  sentença	
  𝑝(𝑋)	
  em	
  A.	
  
Portanto,	
  o	
  conjunto	
  verdade	
  da	
  sentença	
  𝑝(𝑋),	
  denotado	
  por	
  𝑉~!,	
  é	
  o	
  complemento,	
  em	
  relação	
  a	
  
A,	
  do	
  conjunto	
  verdade	
  𝑉!	
  (𝑉~! =  ∁  𝐴  𝑉!).	
  
	
  
Exemplo:	
  Sejam	
  a	
  sentença	
  𝑝(𝑋)	
  em	
  A	
  (conjunto	
  dos	
  números	
  naturais	
  divisíveis	
  por	
  5):	
  𝐴 = 5𝑌    𝑌 ∈ 𝑁 = {5, 10, 15, 20,… }	
  𝑝 𝑋 =  𝑋	
  termina	
  com	
  o	
  algarismo	
  5.	
  
O	
  conjunto	
  verdade	
  de	
  ~𝑝(𝑋)	
  é	
  dado	
  por:	
  𝑉~! = 𝑋 ∈ 𝐴    𝑋	
  termina	
  com	
  o	
  algarismo	
  0}.	
  
	
  
2. CONJUNÇÃO	
  
Sejam	
  as	
  sentenças	
  abertas	
  𝑝(𝑋)	
  e	
  𝑞(𝑋)	
  em	
  um	
  conjunto	
  A.	
  
Tem-­‐se	
  que	
  a	
  conjunção	
  destas	
  sentenças	
  abertas	
  é	
  a	
  sentença	
  dada	
  por	
  𝑝(𝑋) ∧ 𝑞(𝑋)	
  em	
  A.	
  
Um	
   elemento	
  𝑎 ∈ 𝐴	
  satisfaz	
   a	
   sentença	
   aberta	
  𝑝(𝑋) ∧ 𝑞(𝑋),	
   se	
   e	
   somente	
   se,	
  𝑝(𝑎) ∧ 𝑞(𝑎)	
  for	
  
verdadeira.	
  E	
  isto	
  só	
  ocorre	
  se	
  𝑝(𝑎)	
  e	
  𝑞(𝑎)	
  forem	
  ambas	
  verdadeiras,	
  ou	
  seja,	
  se	
  o	
  elemento	
  𝑎 ∈ 𝐴	
  
satisfaz	
  ao	
  mesmo	
  tempo	
  as	
  sentenças	
  𝑝(𝑋)	
  e	
  𝑞(𝑋)	
  em	
  A.	
  
Portanto,	
   o	
   conjunto	
   verdade	
   da	
   sentença	
  𝑝(𝑋) ∧ 𝑞(𝑋),	
   denotado	
   por	
  𝑉!∧!,	
   é	
   a	
   interseção	
   dos	
  
conjuntos	
  verdades	
  𝑉!	
  e	
  𝑉!	
  (𝑉!∧! =  𝑉! ∩ 𝑉!).	
  
	
  
Exemplo:	
  Sejam	
  as	
  sentenças	
  𝑝(𝑋)	
  e	
  𝑞(𝑋)	
  em	
  ℤ	
  (conjunto	
  dos	
  números	
  inteiros):	
  
	
   𝑝 𝑋 =  𝑋! + 𝑋 − 2 = 0	
  
	
  𝑞 𝑋 =  𝑋! − 4 = 0	
  
O	
  conjunto	
  verdade	
  de	
  𝑝(𝑋) ∧ 𝑞(𝑋)	
  é	
  dado	
  por:	
  𝑉!∧! = −2,1 ∩ −2,2 = {−2} ⊂ ℤ.	
  
	
  
3. DISJUNÇÃO	
  
Sejam	
  as	
  sentenças	
  abertas	
  𝑝(𝑋)	
  e	
  𝑞(𝑋)	
  em	
  um	
  conjunto	
  A.	
  
Tem-­‐se	
  que	
  a	
  disjunção	
  destas	
  sentenças	
  abertas	
  é	
  a	
  sentença	
  dada	
  por	
  𝑝(𝑋) ∨ 𝑞(𝑋)	
  em	
  A.	
  
Um	
   elemento	
  𝑎 ∈ 𝐴	
  satisfaz	
   a	
   sentença	
   aberta	
  𝑝(𝑋) ∨ 𝑞(𝑋),	
   se	
   e	
   somente	
   se,	
  𝑝(𝑎) ∨ 𝑞(𝑎)	
  for	
  
verdadeira.	
   E	
   isto	
   só	
   ocorre	
   se	
  𝑝(𝑎)	
  ou	
  𝑞(𝑎)	
  forem	
   verdadeiras,	
   ou	
   seja,	
   se	
   o	
   elemento	
  𝑎 ∈ 𝐴	
  
satisfaz	
  pelo	
  menos	
  uma	
  das	
  sentenças	
  𝑝(𝑋)	
  ou	
  𝑞(𝑋)	
  em	
  A.	
  
Portanto,	
   o	
   conjunto	
   verdade	
   da	
   sentença	
  𝑝(𝑋) ∨ 𝑞(𝑋) ,	
   denotado	
   por	
  𝑉!∨! ,	
   é	
   a	
   união	
   dos	
  
conjuntos	
  verdades	
  𝑉!	
  e	
  𝑉!	
  (𝑉!∨! =  𝑉! ∪ 𝑉!).	
  
	
  
Exemplo:	
  Sejam	
  as	
  sentenças
𝑝(𝑋)	
  e	
  𝑞(𝑋)	
  em	
  ℤ	
  (conjunto	
  dos	
  números	
  inteiros):	
  𝑝 𝑋 =  𝑋! + 𝑋 − 2 = 0	
  
LÓGICA PARA COMPUTAÇÃO 	
  
Professora Luciana Conceição Dias Campos	
   3	
  	
  
𝑞 𝑋 =  𝑋! − 4 = 0	
  
O	
  conjunto	
  verdade	
  de	
  𝑝(𝑋) ∨ 𝑞(𝑋)	
  é	
  dado	
  por:	
  𝑉!∧! = −2,1 ∪ −2,2 = {−2, 1, 2} ⊂ ℤ.	
  
	
  
4. CONDICIONAL	
  
Sejam	
  as	
  sentenças	
  abertas	
  𝑝(𝑋)	
  e	
  𝑞(𝑋)	
  em	
  um	
  conjunto	
  A.	
  
Tem-­‐se	
  que	
  a	
  condicional	
  destas	
  sentenças	
  abertas	
  é	
  a	
  sentença	
  dada	
  por	
  𝑝(𝑋) → 𝑞(𝑋)	
  em	
  A.	
  
Um	
   elemento	
  𝑎 ∈ 𝐴	
  satisfaz	
   a	
   sentença	
   aberta	
  𝑝(𝑋) → 𝑞(𝑋),	
   se	
   e	
   somente	
   se,	
  𝑝(𝑎) → 𝑞(𝑎)	
  for	
  
verdadeira.	
   Lembrando	
   da	
   regra	
   de	
   equivalência	
   da	
   condicional,	
   temos	
   que	
   a	
   sentença	
  𝑝(𝑋) →𝑞(𝑋)	
  é	
   equivalente	
   à	
   sentença	
  ~𝑝(𝑋) ∨ 𝑞(𝑋).	
   Assim,	
   se	
   a	
   sentença	
  𝑝(𝑎) → 𝑞(𝑎)	
  for	
   verdadeira,	
  
segue	
  que	
   a	
   sentença	
  ~𝑝(𝑎) ∨ 𝑞(𝑎)	
  também	
  é	
   verdadeira.	
   E	
   isto	
   só	
   ocorre	
   se	
   o	
   elemento	
  𝑎 ∈ 𝐴	
  
satisfaz	
  pelo	
  menos	
  uma	
  das	
  sentenças	
  ~𝑝(𝑋)	
  ou	
  𝑞(𝑋)	
  em	
  A.	
  
Portanto,	
   o	
   conjunto	
   verdade	
   da	
   sentença	
  𝑝(𝑋) → 𝑞(𝑋),	
   denotado	
   por	
  𝑉!→! ,	
   é	
   equivalente	
   ao	
  
conjunto	
  verdade	
  𝑉~!∨!,	
  que	
  é	
  a	
  união	
  dos	
  conjuntos	
  verdades	
  𝑉~!	
  e	
  𝑉!	
  (𝑉~!∨! =  𝑉~! ∪ 𝑉!).	
  E	
  como	
  
foi	
  visto,	
  𝑉~!	
  é	
  o	
  complemento,	
  em	
  relação	
  a	
  A,	
  do	
  conjunto	
  verdade	
  𝑉!	
  (𝑉~! =  ∁  𝐴  𝑉!).	
  
	
  
Exemplo:	
  Sejam	
  as	
  sentenças	
  𝑝(𝑋)	
  e	
  𝑞(𝑋)	
  em	
  ℕ	
  (conjunto	
  dos	
  números	
  naturais):	
  𝑝 𝑋 =  12/𝑋	
  (12	
  é	
  divisível	
  por	
  X)	
  𝑞 𝑋 =  45/𝑋(45	
  é	
  divisível	
  por	
  X)	
  
O	
  conjunto	
  verdade	
  de	
  𝑝(𝑋) → 𝑞(𝑋)	
  é	
  dado	
  por:	
  𝑉!→! = 𝑉~!∨! =  𝑉~! ∪ 𝑉! = ∁  ℕ  𝑉! ∪ 𝑉! = ∁  ℕ 1, 2, 3, 4, 6, 12 ∪ 1, 3, 5, 9, 15, 45 =	
  ℕ− {2  , 4, 6, 12}.	
  
	
  
5. BICONDICIONAL	
  
Sejam	
  as	
  sentenças	
  abertas	
  𝑝(𝑋)	
  e	
  𝑞(𝑋)	
  em	
  um	
  conjunto	
  A.	
  
Tem-­‐se	
  que	
  a	
  bicondicional	
  destas	
  sentenças	
  abertas	
  é	
  a	
  sentença	
  dada	
  por	
  𝑝(𝑋) ↔ 𝑞(𝑋)	
  em	
  A.	
  
Um	
   elemento	
  𝑎 ∈ 𝐴	
  satisfaz	
   a	
   sentença	
   aberta	
  𝑝 𝑋 ↔ 𝑞 𝑋 ,	
   se	
   e	
   somente	
   se,	
  𝑝 𝑎 ↔ 𝑞 𝑎 	
  for	
  
verdadeira.	
   Lembrando	
   da	
   regra	
   de	
   equivalência	
   da	
   condicional,	
   temos	
   que	
   a	
   sentença	
  𝑝 𝑋 ↔𝑞 𝑋 	
  é	
  equivalente	
  à	
  sentença	
   𝑝 𝑋 → 𝑞 𝑋 ∧ 𝑞 𝑋 → 𝑝 𝑋 ⇔	
  ~𝑝 𝑋 ∨ 𝑞 𝑋 ∧ ~𝑞 𝑋 ∨ 𝑝 𝑋 ⇔ (~𝑝 𝑋 ∧ ~𝑞 𝑋 ) ∨ (𝑝 𝑋 ∧ 𝑞 𝑋 ).	
  	
  
Assim,	
   se	
   a	
   sentença	
  𝑝(𝑎) ↔ 𝑞(𝑎) 	
  for	
   verdadeira,	
   segue	
   que	
   a	
   sentença	
   (~𝑝 𝑎 ∧ ~𝑞 𝑎 ) ∨(𝑝 𝑎 ∧ 𝑞 𝑎 )	
  também	
  é	
  verdadeira.	
  E	
  isto	
  só	
  ocorre	
  se	
  o	
  elemento	
  𝑎 ∈ 𝐴	
  satisfaz	
  pelo	
  menos	
  uma	
  
das	
  sentenças	
  (~𝑝 𝑋 ∧ ~𝑞 𝑋 )	
  ou	
  (𝑝 𝑋 ∧ 𝑞 𝑋 )	
  em	
  A.	
  
Portanto,	
   o	
   conjunto	
   verdade	
   da	
   sentença	
  𝑝(𝑋) ↔ 𝑞(𝑋),	
   denotado	
   por	
  𝑉!↔! ,	
   é	
   equivalente	
   ao	
  
conjunto	
   verdade	
   𝑉(~!∧~!)∨(!∧!) ,	
   que	
   é	
   a	
   união	
   dos	
   conjuntos	
   verdades	
   𝑉(~!∧~!) 	
  e	
   𝑉(!∧!)	
  
(𝑉(~!∧~!)∨(!∧!) =  𝑉(~!∧~!) ∪ 𝑉(!∧!)).	
  E	
  como	
  foi	
  visto,	
  segue	
  que:	
  
• 𝑉 ~!∧~! = 𝑉~! ∩ 𝑉~!	
  
• 𝑉 !∧! = 𝑉! ∩ 𝑉!	
  
• 𝑉~!	
  é	
  o	
  complemento,	
  em	
  relação	
  a	
  A,	
  do	
  conjunto	
  verdade	
  𝑉!	
  (𝑉~! =  ∁  𝐴  𝑉!).	
  
• 𝑉~!	
  é	
  o	
  complemento,	
  em	
  relação	
  a	
  A,	
  do	
  conjunto	
  verdade	
  𝑉!	
  (𝑉~! =  ∁  𝐴  𝑉!).	
  
	
  
Portanto,	
  𝑉!↔! = ∁  𝐴  𝑉! ∩ ∁  𝐴  𝑉! ∪ {𝑉! ∩ 𝑉!}.	
  
	
  
Exemplo:	
  Sejam	
  as	
  sentenças	
  𝑝(𝑋)	
  e	
  𝑞(𝑋)	
  em	
  ℕ	
  (conjunto	
  dos	
  números	
  naturais):	
  𝑝 𝑋 =  6/𝑋	
  (6	
  é	
  divisível	
  por	
  X)	
  	
  𝑞 𝑋 =  15/𝑋	
  (15	
  é	
  divisível	
  por	
  X)	
  
LÓGICA PARA COMPUTAÇÃO 
 
Professora Luciana Conceição Dias Campos	
   4	
  	
  
O	
  conjunto	
  verdade	
  de	
  𝑝(𝑋) → 𝑞(𝑋)	
  é	
  dado	
  por:	
  𝑉!→! = ∁  ℕ  𝑉! ∩ ∁  ℕ  𝑉! ∪ 𝑉! ∩ 𝑉! = ∁  ℕ 1, 2, 3, 6 ∩ ∁  ℕ 1, 3, 5, 15 ∪ 1, 2, 3, 6 ∩1, 3, 5, 15 = ℕ− 1, 2  , 3, 6 ∩ ℕ− 1, 3, 5, 15 ∪ 1, 3 = ℕ− 1, 2  , 3, 5, 6, 15 ∪ 1, 3 =ℕ− 2  , 5, 6, 15 .	
  
	
  
As	
   propriedades	
   das	
   operações	
   lógicas	
   vistas	
   sobre	
   o	
   cálculo	
   proposicional	
   (álgebra	
   das	
  
proposições)	
  se	
  estendem	
  às	
  operações	
  lógicas	
  sobre	
  sentenças	
  abertas.