Lógica para computação - parte II

arieldll

Continuando o artigo anterior, (se você não o viu, poderá vê-lo em: http://vivaolinux.com.br/artigo/Introducao-a-Logica-para-computacao/ ),
estaremos adentrando em outras propriedades da Lógica direcionada à computação.

[ Hits: 19.879 ]

Por: Ariel Galante Dalla Costa em 27/12/2011 | Blog: http://arielgdc.wordpress.com

0 0

Denuncie Favoritos Indicar Impressora

Álgebra das proposições, regra de Morgam e método dedutivo

Álgebra das proposições

A álgebra das proposições é utilizada para reduzir/modificar expressões compostas, ou seja, também são conhecidas como propriedades.

Como descobrir se a propriedade aplicada está correta? Basta desenvolver a tabela verdade de todas as proposições empregadas na proposição composta, ou seja, todas as proposições devem ser equivalências lógicas.

Sejam as proposições p, q, então, defini-se:

      p^(qvr) <=> (p^q) v (p^r)
      pv(q^r) <=> (pvq) ^ (pvr)
      ~(p^q) <=> ~p v ~q
      ~(pvq) <=> ~p ^ ~q
      p->q <=> ~pvq
      ~(p->q) <=> ~(~pvq) <=> p^~q
      p^(q^r) <=> (p^q)^r
      pv(qvr) <=> (pvq)vr
      p<->q <=> (p<->q)^(q->p)
      ~(p<->q) <=> (p^~q) v (~p^q)
      p<->q <=> (~pvq)^(~qvp)

Exemplo:

   (p->q)^p <=> (~pvq)^p <=> (~p^p) v (q^p)

Outro exemplo:

   (p->(~p->q)<=>p->(~~pvq) <=> ~pv(pvq) <=> (~pvp) v (~pvq)

Mais um exemplo:

   (pvq)->q <=> ~(pvq)vq <=> (~p^~q)vq <=> (qv~q) ^ (qv~p)

Regra de Morgam

A regra nega as proposições invertendo o valor lógico da proposição v (ou) para E e vice-versa.

Exemplo:

~(p^q) <=> ~pv~q

Outro exemplo:

~(pv~q)v~(p^q) <=> (~p^q) v (~pv~q)

Método dedutivo

No método dedutivo, as equivalências relativas desempenham um papel importante nas equivalências lógicas. As simples proposições (simples ou compostas) podem ser substituídas por P,Q,R,T(Tautológica, Contradição).

Exemplo:

       (p->(~p->q)<=>p->(~~pvq) <=> ~pv(pvq) <=> (~pvp) v (~pvq) <=> T v (~pvq) <=> T

A implicação acima representa uma tautologia.

Mas por quê? Porque como pode-se observar, a propriedade distributiva gera (~pvp), ou seja, ela é obrigatoriamente forçada a gerar um valor verdadeiro. Se p:f, então p:v. Se p:v, então p:v. Ao juntar-se com o operador v(OU), ela obriga a proposição formada a gerar um valor verdadeiro na resolução.

Caso a proposição fosse T ^ (~pvq), então, o valor lógico é igual a (~pvq), pois, o valor mesmo que falso, juntado. com (~pvq) será (~pvq).

Exemplo:

      Mostrar equivalências: (p->q) ^ (p->~q)

      Resolução:

      (p->q) ^ (p->~q) <=> (~pvq)^(~pv~q) <=> (~p^~p)v(qv~q) <=> ~pvC <=> ~p

Página anterior

Páginas do artigo

   1. Definições base
   2. Equivalência lógica e Negações Lógicas
   3. Álgebra das proposições, regra de Morgam e método dedutivo

Outros artigos deste autor

Computação em nuvem, uma visão panorâmica

Lógica para computação - parte III

Lógica para computação - parte IV

Ética na Programação

Introdução a Lógica para computação

Leitura recomendada

Iniciação no Linux sem medo usando VMWare

Transformando seu Windows em um quase Linux

openSUSE Evergreen

Pilha de Diretórios (comandos pushd, popd e dirs)

Permissões no Linux

Comentários

[1] Comentário enviado por arieldll em 27/12/2011 - 22:14h

Quem possuir sugestoes ou encontrar algo de errado, fico feliz em compartilhar conosco.
[]'s Ariel

0 0

[2] Comentário enviado por marquinhos1875 em 27/12/2011 - 23:29h

PQP, meu carma no semestre, abre o VOL e mais carma...... (rs)
Mais ta muito bom, parabéns.

0 0

[3] Comentário enviado por arieldll em 28/12/2011 - 07:43h

Obrigado

0 0

[4] Comentário enviado por nicolo em 28/12/2011 - 12:16h

Cruzes, que horror !
Ainda bem que eu já passei desta fase macabra.

Se eu precisasse aprender isso para comer, já teria morrido de fome.

0 0

[5] Comentário enviado por neonx em 28/12/2011 - 17:08h

Olha só... é sempre bom ver alunos com grandes potenciais... Ariel está de parabéns... muito bem escrito e desenvolvido este seu artigo...

abraço...

Ânderson

0 0

[6] Comentário enviado por arieldll em 28/12/2011 - 18:00h

Obrigado e fico feliz por ter gostado.
Abraço
Ariel

0 0

[7] Comentário enviado por lcavalheiro em 29/12/2011 - 14:02h

Ariel, eu tenho uma sugestão com relação às regras de cálculo proposicional de primeira ordem. O método de sistema dedutivo que você apresentou é funcional, mas exigem muita decoreba e nem sempre são de aplicação simples e imediata. Nos estudos contemporâneos de Lógica Matemática esse método está sendo abandonado em prol das regras de inclusão e eliminação de operadores(literalmente, operações com operadores lógicos). Existe um livro muito bom sobre o assunto (infelizmente eu não sei se ele já foi traduzido pro nosso idioma) chamado "Logic and Structure", de Dirk van Dalen. Assim que a carga no meu computador reduzir um pouco (no momento estou compilando o Virtual Box pra testar a distro educacional Pandorga, que nosso governo criou baseada em (argh!) Debian) eu te passo as regras, ok?

0 0

[8] Comentário enviado por arieldll em 29/12/2011 - 14:28h

lcavalheiro, eu agradeço e fico feliz por compartilhar. O conhecimento é o nosso objetivo.
Fico grato desde já.

[]'s Ariel

0 0

[9] Comentário enviado por lestatwa em 30/12/2011 - 19:44h

no seu exemplo 1:
p, q (p^~q)
V V F
V F F
F V F
F F F

temos um erro
o correto seria
p , q, ~q, (p^~q)
V V F F
V F V V
F V F F
F F V F

Lógica Matemática apesar de simples, exige atenção!
Abraço!

0 0

[10] Comentário enviado por arieldll em 30/12/2011 - 21:11h

Obrigado pela sinalização! Sem problemas, podemos corrigir facilmente a expressão.
Para a proposição ser contraválida basta substituir a epxressão por: (p^~q)^q. Onde que o q força uma negação na linha, bem como toda a tabela.
Se possível moderação, favor corrigir.

[]'s Ariel.

0 0

[11] Comentário enviado por lcavalheiro em 31/12/2011 - 11:32h

Ariel, no exemplo 1 em questão o lestatwa está falando de proposições contingentes. A contradição total, se for o caso, pode ser obtida mais facilmente com (p ^ ~p). Duas variáveis com um único operador binário formam, necessariamente, uma expressão contingente, sendo necessário recorrer a um segundo operador binário (aumentando a profundidade da árvore dedutiva da proposição e, em TI, a complexidade computacional do processo) como o amigo Ariel sugeriu. Note que semanticamente falando essa proposição da correção do amigo pode ser escrita como (p ^ q) ^ ~q, ainda que indutivamente você possa dizer que a implicação dessas duas proposições seja o p, mas isso é assunto pra outro lugar...

0 0

[12] Comentário enviado por arieldll em 31/12/2011 - 12:03h

lcalheiro, a ideia é deixar a tabela como contraválida, para, um simples exemplo.
Aproveitando o post, a ideia era ter um exemplo de cada situação com uma proposição composta de mais de uma proposição simples apenas(p), como pode-se observar os outros exemplos, que também são desta forma. A forma mais fácil realmente seria ~p^p.

0 0