A Lógica é uma área da Filosofia que estuda as possíveis deduções e inferências a partir de proposições ou argumentos lógicos, conforme regras e princípios pré-estabelecidos. Em outras palavras, é o estudo sistemático de proposições.

Aristóteles é o pai da Lógica, tendo a criado em cerca de 300 a.C.. A lógica criada por Aristóteles é chamada de Lógica Aristotélica a qual tem por base o silogismo – um tipo de raciocínio formalizado em que uma proposição é deduzida através de outras proposições e . A Lógica Aristotélica, na verdade, é realizada de forma inteiramente verbal. De fato, a notação para Lógica só foi estabelecida em 1879 com a publicação do livro Begriffsschrift de Gottlob Frege, juntamente com a apresentação de um sistema formal. A notação utilizada atualmente segue, em sua maior parte, aquela descrita na gigantesca obra Principia Mathematica, de Bertrand Russell e Alfred North Whitehead.

Embora existam diversos tipos de lógicas, como fuzzy, modal, quântica, clássica…; iremos focar na lógica clássica, em que proposições são estritamente verdadeiras ou falsas, e inicialmente no Cálculo Proposicional (CP). O CP é a lógica que estuda proposições quanto a seus valores-verdade e formações de outras proposições através de conectivos lógicos. Iremos definir todos esses conceitos a seguir.

Dentro do contexto do CP, fórmulas atômicas são proposições. Por exemplo, frases como “o dia está ensolarado”, “o carro é azul” e “Brasil é uma cidade” são fórmulas atômicas, portanto preposições. Usualmente as fórmulas atômicas são denotadas por , em que é um natural, e são chamadas de variáveis. Note que o valor-verdade das fórmulas atômicas (verdadeiras ou falsas) não interfere em sua classificação como fórmulas atômicas, mas sim a ausência de subfórmulas e conectivos lógicos. Conectivos lógicos, por sua vez, são símbolos do CP que correspondem a algumas palavras da linguagem natural. O CP tem os seguintes conectivos lógicos:

• – corresponde à negação, “não”;
• – corresponde a  “e”;
• – corresponde a “ou”;
• – corresponde a “implica”;
• – corresponde a “se e somente se” ou “sse”.

Adicionalmente, o alfabeto do CP contém os símbolos e , os quais podem alterar a precedência de conectivos lógicos. Para minimizar o número de definições, podemos chamar e de conectivos lógicos primitivos e definir os outros a partir deles. Fórmulas ou proposições podem ser definidas indutivamente da seguinte maneira:

• Uma variável é uma fórmula;
• Se é uma fórmula, é fórmula;
• Se e são fórmulas, é fórmula;
• Fórmulas são construídas de acordo com as regras acima.

Para definir os conectivos lógicos quanto a semântica, precisamos introduzir os conceitos de tabelas-verdade e equivalências lógicas. Tabelas-verdades são tabelas que mapeiam todos os possíveis valores-verdade de uma fórmula de acordo com os valores-verdade de suas sub-fórmulas. Por exemplo, vamos escrever a tabela verdade da (meta)fórmula :

V	F
F	V

Observe que a tabela-verdade contém todos os possíveis valores de – 0 ou 1, verdadeiro ou falso -, e os respectivos valores da fórmula . Se é verdadeiro, é falso e vice-versa. Podemos escrever a tabela-verdade de :

F	F	F
F	V	F
V	F	F
V	V	V

A tabela-verdade  reflete o significado da fórmula na linguagem natural, ou seja, a fórmula só é verdadeira quando ambas as sub-fórmulas e são verdadeiras. Novamente a tabela-verdade precisa conter todas as possibilidades dos valores-verdades das sub-fórmulas.

Finalmente, podemos definir o conceito de equivalência lógica. Duas fórmulas e são logicamente equivales se elas têm a mesma tabela verdade. Representamos essa característica entre as fórmulas através do símbolo . significa “ é logicamente equivalente a “. Vamos escrever algumas equivalências lógicas que nos permitem definir os outros conectivos lógicos:

• ,
• ,
• .

Construindo as tabelas-verdade, podemos verificar que  é verdadeiro quando ou são verdadeiros, sem exclusão;  é verdadeiro quando é falso ou e são verdadeiros;  é verdadeiro quando ambos e têm o mesmo valor-verdade. A verificação das tabelas-verdade fica como exercício ao leitor (sugestão: fazer uma coluna para cada sub-fórmula).

A tabela-verdade do conectivo lógico pode ser uma fonte de confusão inicialmente, pois se a premissa da implicação é falsa, a implicação como um todo é verdadeira ou “válida”. Alonzo Church, em seu livro Introduction to Mathematical Logic, vol. I dedicou a 89ª nota de rodapé e meia página para explicar que se trata de uma implicação materialística e a razão disso. Devemos ter em mente que se alguma premissa é falsa, não importa qual é a conclusão, pois é como se considerássemos um universo em que a premissa é verdadeira. Por exemplo, considere a implicação “se unicórnios existem, então a lua é de queijo”: se unicórnios de fato existissem, não haveria problema nenhum em concluir que a lua é de queijo, portanto a implicação é válida no CP mas talvez não em nosso universo. A frase é logicamente equivalente, dentro do CP, a “unicórnios não existem ou a lua é de queijo” – como unicórnios não existem, a fórmula é verdadeira. Vamos ver outro exemplo, “se unicórnios não existem, a lua é de queijo”: como unicórnios de fato não existem no nosso universo, precisamos levar em consideração a conclusão da implicação. A lua obviamente não é de queijo, logo concluímos a implicação é falsa. Utilizando a equivalência lógica, podemos reescrever a implicação como “unicórnios existem ou a lua é de queijo” e observamos que nenhuma das duas proposições é verdadeira, então a implicação é realmente falsa. Esse aspecto das implicações é frequentemente a raiz de diversos erros em demonstrações matemáticas. Se a premissa é falsa, então pode-se concluir qualquer coisa a partir dela. “Demonstrações” de quase sempre utilizam de alguma premissa falsa e obtêm conclusões a partir dela (e.g. a premissa de que ).

Para facilitar a leitura de fórmulas lógicas e reduzir o número de parênteses, podemos utilizar a seguinte ordem de precedência dos conectivos lógicos:

.

Se uma fórmula é verdadeira em pelo menos uma das linhas de sua tabela verdade, dizemos que é satisfazível. Verificar a satisfabilidade de uma fórmula não é uma tarefa trivial. Se for composta por sub-fórmulas atômicas (ou literais), temos que construir uma tabela-verdade com linhas, mas cada linha corresponde a um valor-verdade de , que pode ser V ou F. Logo temos que verificar possíveis valores. De fato, esse problema é conhecido como o Problema da Satisfabilidade Booleana ou simplesmente SAT, e foi um dos primeiros a ser considerado NP-completo.

A partir da introdução formal acima, vamos formalizar as noções de satisfabilidade. Considere um conjunto de fórmulas atômicas. Seja o conjunto de todas as fórmulas que podem ser formadas a partir daquelas em . Definimos a função de atribuição como e, através dela, atribuímos valores-verdade às fórmulas. Uma fórmula é satisfazível se existe alguma função de atribuição tal que . Usualmente escrevemos (lê-se “ modela “). Se é satisfazível independentemente de , dizemos que é uma tautologia; se é insatisfazível, dizemos que é uma contradição. Representamos tautologias por e contradições por . O exemplo de tautologia mais simples é ou  .

Uma fórmula é consequência de outra fórmula se e , em que é uma função atribuição. Escrevemos para denotar esse fato. Retomando o conceito de equivalência lógica, se e somente se e .

Vamos apresentar algumas regras do CP envolvendo tautologias e equivalências lógicas:

• Para quaisquer fórmula e tautologia , e ;
• Para quaisquer fórmula e contradição , e ;
• ;
• ;
• ;
• ;
• ;
• ;
• ;
• .

Por fim, dizemos que uma função de atribuição satisfaz um conjunto de fórmulas se para cada .

Com este post, concluímos a parte semântica do CP em sua essência. Por enquanto não é possível fazer nada além de checar a satisfabilidade de uma fórmula e utilizar equivalências lógicas para simplificar fórmulas. A parte 2 dessa série de posts sobre Lógica irá discursar sobre a construção de fórmulas a partir de tabelas-verdade, a sintaxe do CP, um pouco sobre teoria de demonstrações ou provas, formas normais de fórmulas, dois teoremas que relacionam a sintaxe com a semântica do CP e algoritmos que verificam a satisfabilidade de fórmulas.

Para ilustrar uma aplicação prática porém um pouco infantil do CP até agora – resolver analiticamente os famosos “problemas de lógica”, como o famigerado Teste de Einstein. Obviamente o teste não foi proposto por Einstein e não apenas 2% da população mundial é capaz de resolvê-lo, mas ele é facilmente resolvido com auxílio de um computador e a transformação das dicas fornecidas em fórmulas do CP.

---