Lógica para computação - parte II

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.838 ]

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


Definições base



Algumas definições base:

- Tautologia:

Toda a proposição composta, cuja última coluna de resolução de sua tabela verdade é expressa totalmente pelo valor lógico verdadeiro (1).

- Contradição:

Toda a proposição composta, cuja última coluna de resolução de sua tabela verdade é expressa totalmente pelo valor lógico falso (0), ou seja, dizer que a tautologia é o antônimo de uma contradição é verdadeiro, e ainda, dizer que tautologia é o contrário de contradição, também é válido.

- Contingência:

Toda a proposição composta, cujo valor lógico é intercalado entre verdadeiro e falso, não necessitando do mesmo número ou de uma equivalência (em quantidade). É uma mescla entre tautologia e contradição expressas na mesma tabela verdade.

Exemplo 1:

p, q (p^~q)
V  V   F
V  F   F
F  V   F
F  F   F

A tabela acima expressa uma tabela contra-válida.

Exemplo 2:

p, q (p->q) V  V   V
V  F   F
F  V   V
F  F   V

A tabela acima expressa uma tabela contingente.

Exemplo 3:

p, q p->(q->(q->p))
V  V       V
V  F       V
F  V       V
F  F       V

A tabela acima expressa uma tabela tautológica.

Para proposições compostas, pode-se resolver primeiramente proposições compostas/simples em partes, dividindo por precedência, ou seja, primeiramente os parênteses mais internos, e no final, cruzar informações a fim de definir uma ou mais proposições compostas para simples.

Como por exemplo:

   p, q (p->q)->(pvq)

O exemplo acima pode ser dividido em:

   p, q, p->q, pvq

A tabela verdade ficaria mais fácil para quem está iniciando, pois, depois de dividida, basta cruzar as informações.

Como por exemplo:

   p, q, p->q p^q (p->q)->(p^q)
   V  V   V    V        V
   V  F   F    F        V
   F  V   V    F        F
   F  F   V    F        F

Como observado, pode-se concluir que a proposição (p->q)->(p^q) é definida por: composta contingente.

Outro exemplo:

p, q, r ((p->r)->q) v ((p^q)->r), vamos dividir em:

p, q, r  p->r, (p->r)->q, p^q, (p^q)->r, ((p->r)->q) v ((p^q)->r)

A resolução é a seguinte:

p, q, r  p->r, (p->r)->q, p^q, (p^q)->r, ((p->r)->q) v ((p^q)->r)
V  V  V   V        V       V       V                 V
V  V  F   F        V       V       F                 V
V  F  V   V        F       F       V                 V
V  F  F   F        V       F       V                 V
F  V  V   V        V       F       V                 V
F  V  F   V        V       F       V                 V
F  F  V   V        F       F       V                 V
F  F  F   V        V       F       V                 V

O exemplo acima é definida por: composta tautológica.

Implicação lógica

É um símbolo de relação, aplicado à proposições compostas, para linhas que todos os valores lógicos sejam verdadeiro. É chamado de implicação lógica porque seu valor lógico pode implicar sobre outra proposição simples/composta. Como por exemplo:

p, q p^q pvq p<->q
V  V  V   V    V   -> Esta linha é uma implicação lógica, pois a implicação acontece sobre p^q, pvq e p<->q.
V  F  F   V    F
F  V  F   V    F
F  F  F   F    V

O exemplo acima é uma implicação lógica na primeira linha.

Outro exemplo: construir a tabela verdade da proposição (pvq)^~p e verificar se ela implica em outra proposição:

p, q pvq ~p  (pvq)^~p
V  V  V  F       F
V  F  V  F       F
F  V  V  V       V -> Esta linha é uma implicação lógica, pois a implicação acontece sobre pvq que implica sobre ~p.
F  F  F  V       F

Também pode ser definida uma proposição composta como implicada, utilizando o símbolo => (também conhecido como implicação).

Exemplo: pvq => p (lê-se p ou q implica em p).

Resolução do exemplo:

p, q pvq => p
V  V  V     V  -> É uma implicação, ou seja, pvq=>p é verdadeiro na primeira linha.
V  F  V     V
F  V  V     F  
F  F  F     F
    Próxima página

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

Ética na Programação

Lógica para Computação - Parte V

Lógica para computação - parte III

Lógica para computação - parte IV

MySQL, Apache2, PHP5, phpMyAdmin e o driver de conexão com o NetBeans no OpenSUSE 11.2

Leitura recomendada

GoblinX: Mais um filho do Slackware

Uma análise do software livre e de sua história

Veja o Linux com outros olhos

Completando o Ubuntu (para principiantes)

Linux - Só não usa quem não quer

  
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

[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.

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

Obrigado

[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.


[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

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

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

[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?

[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

[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!

[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.

[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...

[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.


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts