Aula 6 - Relação Semântica entre Conectivos

Prévia do material em texto

Prof. Ricardo Mesquita 
Relações Semânticas entre os 
Conectivos da Lógica Proposicional 
Conjuntos de Conectivos Completos 
 Um conjunto de conectivos proposicionais  é completo 
quando é possível expressar, equivalentemente, os conectivos 
, , ,  e  utilizando apenas os conectivos de . 
 
 
 Exemplo: Vamos mostrar que o conjunto {, } é completo. 
 
 
02/15 
Conjuntos de Conectivos Completos 
 Proposição 1: Equivalência entre ,  e  
 Em outras palavras, vamos definir “” usando “ e ”. 
 
 Demonstração: 
 
Se (P  Q)  (P  Q) é uma tautologia, 
Então, (P  Q) é equivalente a (P  Q) (vide aula passada!) 
Portanto, (P  Q) pode ser expressa por uma fórmula que 
utiliza apenas os conectivos  e  e os símbolos 
proposicionais P e Q. 
Logo, do ponto de vista semântico, o conectivo  pode ser 
expresso pelos conectivos  e . 
03/15 
Conjuntos de Conectivos Completos 
 Proposição 2: Equivalência entre ,  e  
 Em outras palavras, vamos definir “” usando “ e ”. 
 
 Demonstração: 
Na aula anterior enunciamos as Leis de De Morgan e vimos que 
(P  Q)  (P  Q) é uma tautologia. 
Se negarmos ambos os lados da bi-implicação, mantemos o valor 
lógico da sentença (pela semântica do conectivo ). 
Ou seja, ((P  Q))  (P  Q) é uma tautologia. 
Pela regra da dupla negação, temos que ((P  Q)) é equivalente 
a (P  Q), assim, substituindo, temos que 
(P  Q)  (P  Q) é uma tautologia. 
Então, (P  Q) é equivalente a (P  Q). 
Logo, do ponto de vista semântico, o conectivo  pode ser expresso 
pelos conectivos  e . 
 
04/15 
Conjuntos de Conectivos Completos 
 Proposição 3: Equivalência entre ,  e  
 Em outras palavras, vamos definir “” usando “ e ”. 
Demonstração: 
(P  Q)  ((P  Q)  (Q  P)) é uma tautologia (lei de equivalência) 
Então, (P  Q) é equivalente a ((P  Q)  (Q  P)) 
((P  Q)  (Q  P)) é equivalente a (( P  Q)  ( Q  P)) (Prop. 1) 
(( P  Q)  ( Q  P)) é equivalente a (( P  Q)  ( Q  P)) 
 (Prop. 2) 
Como a equivalência entre fórmulas é transitiva, 
(P  Q) é equivalente a (( P  Q)  ( Q  P)) 
Logo, do ponto de vista semântico, o conectivo  pode ser expresso pelos 
conectivos  e . 
 
05/15 
Conjuntos de Conectivos Completos 
 Proposição 4: O conjunto {, } é completo. 
 
 A demonstração é imediata, a partir das proposições 1, 2 e 3, e 
da definição de conjunto de fórmulas completo. 
 Isso significa que, dada uma fórmula H, do tipo P1, P1  P2, 
P1  P2, P1  P2, ou P1  P2, então é possível determinar outra 
fórmula G, equivalente a H, em que G possui apenas conectivos 
 e , e os símbolos proposicionais P1 e P2 que ocorrem em H. 
 
 
06/15 
Conjuntos de Conectivos Completos 
 Definição: Conectivo nand 
O conectivo nand é definido pela correspondência 
 
(P nand Q) = (P  Q) 
 
 Definição: Conectivo nor 
O conectivo nor é definido pela correspondência 
 
(P nor Q) = (P  Q) 
 
Exercício: 
Mostrar que os conjuntos {nand} e {nor} são completos. 
 
07/15 
Resolução 
 {nand} é completo. 
1. Negação: 
P nand P = (P  P), pela definição de nand 
P  P é equivalente a P, pela propriedade da idempotência 
Então, P nand P = (P  P) = P 
Logo, do ponto de vista semântico, o conectivo  pode ser 
expresso pelo conectivo nand. 
 
08/15 
Resolução 
 {nand} é completo. 
2. Disjunção (): 
 (P  Q)  P  Q, Lei de De Morgan 
 (P  Q)  (P  Q), negando ambos os lados da relação 
 P  Q  (P  Q), Dupla negação 
  ((P nand P)  (Q nand Q)), relação de  com nand 
  (P nand P) nand (Q nand Q), pela definição de nand 
Logo, do ponto de vista semântico, o conectivo  pode ser 
expresso pelo conectivo nand. 
09/15 
Resolução 
 {nand} é completo. 
Sabemos que o conjunto {, } é completo e conhecemos as 
relações. Podemos usá-las para escrever representações com 
nand: 
3. Implicação (): 
Temos que 
 P  Q  P  Q, lei de equivalência 
  (P nand P)  Q, relação de  com nand 
  ((P nand P) nand (P nand P)) nand (Q nand Q), 
 pela relação de  com nand 
Logo, do ponto de vista semântico, o conectivo  pode ser expresso 
pelo conectivo nand. 
 
10/15 
Resolução 
 {nand} é completo. 
4. Conjunção (): 
(P  Q)  P nand Q, definição de nand 
(P  Q)  (P nand Q), negando ambos os lados 
P  Q  (P nand Q), dupla negação 
  (P nand Q) nand (P nand Q), relação de  com nand 
Logo, do ponto de vista semântico, o conectivo  pode ser expresso 
pelo conectivo nand. 
 
11/15 
Resolução 
 {nand} é completo. 
5. Bi-implicação (): 
Temos: 
(P  Q)  (P  Q)  (P  Q), Lei de equivalência 
 (P  Q)  (P  Q), Equivalência da implicação 
 (P  Q)  (P  Q), Lei de De Morgan 
 ((P nand P)  (Q nand Q))  (P  Q),   nand 
 (((P nand P) nand (Q nand Q)) nand ((P nand P) nand (Q nand Q)))  ((P 
nand Q) nand (P nand Q)),   nand 
 ((((P nand P) nand (Q nand Q)) nand ((P nand P) nand (Q nand Q))) nand 
(((P nand P) nand (Q nand Q)) nand ((P nand P) nand (Q nand Q))) nand 
(((P nand Q) nand (P nand Q)) nand ((P nand Q) nand (P nand Q))), 
  nand 
Logo, do ponto de vista semântico, o conectivo  pode ser expresso pelo 
conectivo nand. 
 
12/15 
Resolução 
 Demonstramos que podemos escrever os conectivos , , , 
,  podem ser representados apenas usando o conectivo 
nand. 
 Logo {nand} é um conjunto completo! 
13/15 
Resolução 
 Use um procedimento equivalente para demonstrar que o 
conjunto {nor} é também completo. 
 
 Observação: {nand} e {nor} são os únicos conjuntos 
unitários completos 
14/15 
Exercícios 
 Verifique se os conjuntos a seguir são ou não completos: 
a. {, } 
b. {, } 
c. {, } 
d. {, } 
e. {, } 
f. { , } 
g. { , } 
 
 
15/15