Aula 07 de Lógica

Interpretação

Estabelecer critérios e métodos para identificar a verdade é um dos principais objetivos do trabalho cognitivo humano, pois, frequentemente perguntamos se alguma coisa é verdadeira ou não. Podemos ter algo verdadeiro em uma situação, de um certo ponto de vista, e falso um outra. Mas, o melhor mesmo seria encontrar um método para identificar a verdade que correspondesse, de forma exata, ao critério semântico de verdade que temos na cabeça. De posse de tal aparato, poderíamos buscar por verdades universais, ou seja, algo verdadeiro em qualquer situação, em todos os pontos de vista. Entretanto, é claro, um aparato assim está muito além do que podemos fazer. Isso é definitivamente um problema não trivial, pois entender o que significa a verdade é um profundo problema filosófico. Mais ainda, estabelecer critérios e métodos para definir tal verdade, parece estar além da nossa capacidade cognitiva. E sobre isso tem até alguns resultados, em textos mais avançados de lógica (Teorema de Henkin). Mas nem tudo está perdido, pois, em Lógica Proposicional (LP) os problemas são simples e tratáveis. Ou seja, nesse contexto, é possível definir verdades universais, as tautologias, e encontrar métodos para identifica-las. Um dos passos frequentemente utilizados no estudo da lógica corresponde à análise desses métodos.

Tabela Verdade.

Estudamos na unidade passada as demonstrações e provas de proposições lógicas com o uso de tabela verdade. Foram analisados anteriormente proposições onde o custo para o  uso de tabelas verdade não era alto, ou seja, proposições com dois, três ou quatro símbolos. Já vimos que o número de símbolos em uma proposição determina o número de linhas que uma tabela verdade terá, esse número é dado por 2ⁿ onde n é o número de símbolos e a base é o número dois pois só operamos com duas possibilidades em lógica o verdadeiro e o falso. O custo para analisar uma tabela verdade cresce de maneira exponencial e a partir de um determinado ponto se torna inviável para seres humanos sendo necessário o uso de computadores. Veja a tabela abaixo:

 

Estamos considerando apenas o número de linhas geradas, se uma rigorosa abordagem de custo computacional para se achar um termo verdadeiro em uma determinada tabela fosse efetuado, teríamos um esforço proporcional a 2ⁿ+n² onde n é o número de símbolos(saber mais). Por estas explicações é que estudaremos outros métodos que não a tabela verdade apenas.

Interpretação.

Ou semântica dos elementos sintáticos da linguagem da lógica proposicional (LP) é determinado por uma função I denominada interpretação.

Uma operação em I é uma função se, para cada elemento de x de seu domínio, existe apenas um limite y no seu contradomínio tal que y=I(x) (definição de função, veja mais).

Portanto, se I é uma função e x um elemento de seu domínio, então não podemos ter: y=I(x) e z=I(x), tal que y≠z (conceito muto útil para resolução de problemas em LP).

Outra consequência advêm das propriedades especiais do contradomínio da LP, ou seja, o contradomínio da LP é composto apenas de VERDADEIRO e FALSO. Matematicamente falando o a função I é binária.

Ainda temos que a função I é uma função total que nada mais que uma função que esta completamente definida para todos seus elementos. Esta propriedade traz outra consequência bastante óbvia, mas muito importante. Vejamos então a função I é binária (só pode ser VERDADEIRO ou FALSO), a função I é completa, ou seja todos os elementos do domínio tem um correspondente no contradomínio. Então não existe nenhuma resposta para a função I que não seja VERDADEIRO ou FALSO, ou seja, se não é VERDADEIRO, é FALSO e vice-versa. Este princípio é chamado de Princípio do Terceiro Excluído (muito útil para resolução de problemas em LP).

Interpretação de Fórmulas.

Dadas uma fórmula E e uma interpretação I que é uma função binária tem-se:

1. O domínio de I é constituído pelo conjunto de fórmulas da lógica proposicional.
2. O contradomínio de I é o conjunto {V,F}.

Regras

Tendo uma fórmula E de lógica proposicional P, então a interpretação de E, indicada por I[E], é determinada pelas regras:

1. se E é do tipo P, então I[E]=I[P] e I[P] ∈ {V,F}.
2. se E é do tipo ¬H (H∈P), então I[E]=I[(¬H)]=V se I[H]=F e I[E]=[(¬H)]=F se I[H]=V;
3. se E é do tipo (H∨G) (H, G ∈P), então I[E]=I[H∨G]=V se I[H]=V e/ou I[G]=V e I[E]=I[H∨G]=F se I[H]=F e I[G]=F;
4. se E é do tipo (H∧G) (H, G ∈P), então I[E]=I[H∧G]=V se I[H]=V e I[G]=V e I[E]=I[H∧G]=F se I[H]=F e/ou I[G]=F;
5. se E é do tipo (H→G) (H, G ∈P), então I[E]=I[H→G]=V se I[H]=F e I[G]=V e I[E]=I[H→G]=F se I[H]=V e I[G]=F;
6. se E é do tipo (H↔G) (H, G ∈P), então I[E]=I[H↔G]=V se I[H]= I[G] e I[E]=I[H↔G]=F se I[H]≠I[G].

Para ajudar no entendimento do assunto acima, abaixo temos a tabela verdade de todas as operações. Lembre-se que o custo de tabela verdade pode ser muito alto.

Método da Negação, ou Redução ao Absurdo

É um método de prova matemática indireta, não-construtiva. Este tipo de prova é feito assumindo-se como verdade o contrário do que queremos provar e então chegando-se a uma contradição.

A prova por contradição é muito usada em teoremas de existência. Neste caso, é usada para provar a existência de um elemento com determinada característica, sem no entanto mostrar tal elemento. Por esta razão, alguns matemáticos a evitam quando possível, preferindo métodos de prova construtivos. O fato é que existem teoremas para os quais só se conhece prova por contradição.

Exemplos:

Prove que existem infinitos números primos.

Prova: Suponha por absurdo, que existem n (uma quantidade finita) números primos, denotados por p1, p2, …, pn. Considere o número x = p1p2…pn + 1. O número x não é divisível por nenhum dos números p1, p2, …, pn (o resto da divisão é sempre 1). Logo, existe um primo diferente de p1, p2 … pn que divide x. Isto contradiz a nossa hipótese inicial de que existem apenas n números primos. Então nossa hipótese inicial está errada e portanto existem infinitos números primos.

Outra prova interessante é a do Problema da Parada que esta ilustrada de forma animada no vídeo abaixo (coloque a legenda):

Fundamentos para o método da negação.

1. Nega-se o que se deseja demonstrar.
2. Da suposição inicial seguem-se deduções que ao final levam o raciocínio a uma contradição ou absurdo.
3. Dessa forma pelo princípio do terceiro excluído (OU é Verdadeiro, OU é Falso não existe terceira opção e também não pode ser os dois.) se falso é um absurdo, então verdadeiro é o correto e vice-versa.

Exemplos:

1. Se a é um número racional e b um irracional, então a soma a +b é irracional.
   Prova por absurdo.
   Nossa tese é T =(a +b é irracional). Dizer que ela é falsa é dizer que a +b é um número racional c (pois estamos tratando de números reais). Ora, de c = a +b tiramos b = c − a, o que implicaria b ser racional (pois seria a diferença de dois racionais). Resumindo, chegamos ao absurdo: b é irracional (da nossa hipótese) e também racional (consequência obtida ao supor a +b ser racional, junto com a parte da hipótese que afirma a ser racional).
2. Prove que (P→Q)^(Q→R)→(P→R) é uma tautologia.

Faremos H=(P→Q)^(Q→R)→(P→R) e para H ser uma tautologia é necessário que toda a última coluna da tabela verdade seja verdade. Veja a tabela verdade abaixo:

Agora que temos a certeza que é uma tautologia vamos provar por contradição:

Por contradição teremos que admitir que H=F, se H=F então (P→Q)^(Q→R)→(P→R) = F para que isso seja verdade, temos:

1. (P→Q)^(Q→R) = V e (P→R) = F, mas se (P→R) = F então P=V e R=F.
2. (P→Q)^(Q→R) = V então (P→Q) = V e (Q→R) = V.
3. (P→Q) = V e de 1. Temos P=V então Q=V.
4. (Q→R) = V e de 3. Temos Q=V então R=V.
5. Mas em 1. Temos R=F e em 4. Temos R=V então encontramos uma contradição quando fizemos H=F pelo princípio do terceiro excluído, além da contradição, H=V. CQD (Como Queríamos Demonstrar).