[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [obm-l] Lógica+Conjuntos



Em 29 Jan 2004, obm-l@mat.puc-rio.br escreveu: 

>Olá a todos, 
> Gostaria de saber se é correta a igualdade: 
> [A C B e B C C => A C C] = [(A => B ^ B => C) => (A => C)] 
> 
> obs: ^ = e 

  Apesar de saber um pouco das duas coisas e ter estudado 
eng. de computação, gostaria que humildemente alguém me 
corrigisse se eu disser alguma besteira.  Logo farei 
aqui uma *tentativa* de demonstração: 
---------------------------------------------- 

  Pelo que entendo, do ponto de vista lógico, as operações com 
conjuntos e a álgebra booleana são homomorfas:  O operador 
interseção pode ser identificado com o operador "e" lógico 
e o operador união pode ser identificado com o operador "ou" 
lógico.    O valor lógico falso é identificado com 
o conjunto vazio e o valor true é identificado com 
o conjunto universo. 
   Assim, dá pra provar que as operações são equivalentes 
procedendo da seguinte forma: 
  Primeiro provamos que a implicação lógica é equivalente 
à inclusão de conjuntos: 
(como sou "computeiro", para mim 0==F e 1==T): 
  A tabela verdade de p => q é: 

  p  q  p=>q    booleanamente p  q p=>q 
    T  T  T       falando       1  1  1 
    T  F  F                     1  0  0 
    F  T  T                     0  1  1 
    F  F  T                     0  0  1 
   Na álgebra booleana, isto pode ser 
  escrito como:  p=>q == p.q + p'.q + p'.q' , note que estou 
trabalhando com mintermos, logo escolhendo os valores em 
que o resultado dá 1 e montando a expressão com + (ou 
lógico)). Minimizando a expressão acima (há duas formas, 
mas escolhi somente uma), temos: 
   p=>q == p.q + p'q + p'q' 
        == p.q + p'(q+q') 
        == p.q + p' 
   Sejam agora, P e Q conjuntos. Queremos saber se a operação 
de conjuntos "está contido" pode ser identificada com 
a operação lógica "implica". Para isso devemos ter uma 
"tautologia", isto é (P inter Q) uniao P' deve 
ser o conjunto universo se e somente se 
P cont Q. 

(==>) Se P está contido em Q então: 
    (P inter Q) uniao compl(P) = 
        P uniao compl (P) = 
          universo. 
(<==) Por outro lado, se 
    (P inter Q) uniao compl(P) = universo então 
    para qualquer x: 
     (i)  x está em (P inter Q) ou 
     (ii)  x está em compl (P) 

    Se (i) for verdadeiro então x pert P e x pert Q, logo 
  x npert compl(P). Logo não existe nenhum x pert a comp(P) 
  que esteja em P e P está inteiramente 
   em Q.   Se, por outro lado,  (ii) é verdadeiro então (i) é 
falso, pois  x não pode estar em P. Se x está em Q mas 
não está em P a única possibilidade é 
x pert compl(P) inter (Q) ou seja P está inteiramente em Q. 
    Logo a afirmação está contido em conjuntos é equivalente 
à implicação lógica em álgebra booleana. 
---------------------------------------------- 
   Se a demonstração acima estiver certa, então fica fácil 
ver que as operações são equivalentes. 




> 
> e também: 
> (A = B) = (A <=> B) 
> 
> Desde já, agradeço. 
> 
>---------- 

_________________________________________________________
Voce quer um iGMail protegido contra vírus e spams?
Clique aqui: http://www.igmailseguro.ig.com.br
Ofertas imperdíveis! Link: http://www.americanas.com.br/ig/

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================