Fundamentos de lógica

Por RabiD Son (CC BY-NC-ND 2.0).

Matemática e filosofia parecem estar a milhas de distância um do outro, mas coincidem quando o assunto é lógica. O estudo dos processos lógicos faz parte de uma longa busca aos fundamentos do raciocínio humano: a base de todas as ciências, de todo novo conhecimento. Ao mesmo tempo, fornece uma ferramenta rigorosa que ajuda a construir a linguagem matemática.

Confira neste post o básico da lógica matemática clássica, um pouco de lógica modal, e algumas das diversas aplicações.

Por que estudar lógica?

Como dito neste post sobre assuntos interessantes em matemática, é possível investigar muitos problemas de raciocínio através de estratégias sistemáticas, principalmente linguagem simbólica e tabelas verdade. Além de aplicações práticas, outros motivos importantes são:

• Compreender a linguagem matemática e métodos de prova.
• Conhecer as bases lógicas das operações computacionais.
• Conhecer os princípios por trás de modelos semânticos.
• Estudar de forma abstrata os sistemas lógicos.

Proposições

Na lógica matemática clássica, uma proposição é uma sentença que tem um valor verdadeiro ou falso. Talvez seja mais fácil mostrar um exemplo do que não constitui uma proposição para compreender melhor: "Seja bem-vindo". Em contrapartida, a sentença "A soma dos x primeiros números ímpares é igual a x²" pode ser qualificada como verdadeira ou falsa.

É muito comum que uma proposição esteja em função de uma ou mais variáveis, como "x + 5 > 5". Se chamarmos P(x) a essa proposição, sabe-se que P(1) é verdadeiro, pois 5 + 1 > 5. Similarmente, P(-1) é falso, pois 5 - 1 < 5. Neste caso, x é uma variável livre e P(x) uma sentença aberta.

Entretanto, "(a + b)² = a² + 2ab + b²" é verdadeira para quaisquer valores de a e b, que são variáveis ligadas. Por convenção, só usamos a notação P(x) para sentenças abertas, sendo x uma variável livre.

Quantificadores, conectivos lógicos e tabelas verdade

Podemos atribuir quantificadores lógicos às proposições, o que lhe conferem novos sentidos. O quantificador universal, ∀x, dá o sentido de "para todo x". O quantificador existencial, ∃x, dá o sentido de "para algum x". Contraste as duas proposições abaixo:

P: "∀x ∈ ℤ, x = 2a"
Q: "∃x ∈ ℤ, x = 2a"

Fica claro que P é falso, pois nem todo inteiro é par, múltiplo de 2. Entretanto, certamente existe algum inteiro x para o qual x = 2a; por exemplo, 2.

Os conectivos lógicos são utilizados para compor expressões mais complexas a partir de proposições individuais. Podemos obter um sentido oposto através da negação, ¬P, ou ainda ~P. Se P: "29 é um número par", então ¬P: "29 não é um número par". Observe a seguinte tabela verdade:

P	¬P
V	F
F	V

Fica claro, pela tabela, que ¬P é verdadeiro quando P é falso e falso quando P é verdadeiro; essa ferramenta é particularmente útil para analisar relações mais complicadas. Outros conectivos lógicos são:

• Disjunção: A proposição "P ∨ Q" significa "P ou Q" e representa disjunção. Mais precisamente, essa proposição é verdadeira se pelo menos uma das proposições for verdadeira.

• Conjunção: A proposição "P ∧ Q" significa "P e Q" e representa conjunção. A proposição é verdadeira se ambas as proposições forem verdadeiras.

• Afirmação condicional: A proposição "P ⇒ Q" significa "Se P, então Q" e é uma proposição condicional. Note que pode acontecer de P ser falso e Q ser verdadeiro ao mesmo tempo, mas se P for verdadeiro, obrigatoriamente Q deve ser verdadeiro.

• Afirmação bi-condicional: A proposição "P ⇔ Q" significa "Q se, e somente se, P". Ou seja, Q só pode ser verdadeiro quando P for verdadeiro, e vice-versa.

Aplicação em problemas de lógica

Vejamos como aplicar a lógica para analisar questões típicas de concursos públicos envolvendo lógica, a partir de um exemplo tirado deste post com outros problemas simples:

Existem duas caixas, "A" e "B". Um aviso na caixa A diz "O aviso na caixa B é verdadeiro e o ouro está na caixa A". Um aviso na caixa B diz "O aviso na caixa A é falso e o ouro está na caixa A". Assumindo que existe ouro em uma das caixas, qual delas contém o ouro?

Sejam duas proposições A: "O aviso na caixa B é verdadeiro e o ouro está na caixa A" e B: "O aviso na caixa A é falso e o ouro está na caixa A", montamos a tabela verdade com os valores possíveis:

A	B
V	V
V	F
F	V
F	F

Entretanto, A e B não podem ser verdadeiros ao mesmo tempo, pois B ⇒ ¬A. Na linha abaixo, temos A verdadeiro e B falso, mas A ⇒ B, então temos outra contradição lógica. Se A for falso e B verdadeiro, então o aviso na caixa B é verdadeiro e o ouro está na caixa A. Mas isso torna A verdadeiro! Portanto, conclui-se que ambos os avisos são falsos e o ouro está na caixa B.

Outra forma de abordar o problema é supondo que o ouro esteja em uma das caixas. Se estiver na caixa A, as proposições A e B ficam reduzidas a A: "O aviso na caixa B é verdadeiro" e B: "O aviso na caixa A é falso", pois é certo que o ouro está na caixa A. Isso nos leva a um paradoxo, já que A ⇒ B ⇒ ¬A, e ¬A ⇒ B ⇒ A (A é verdadeiro quando falso, e falso quando verdadeiro). A única resolução lógica é colocar o ouro na caixa B.

Álgebra booleana

A álgebra booleana é a base do modelo lógico do computador, baseado em operações nos bits 0 e 1. A ideia básica é considerar o bit 0 como um indicador de valor "falso" e o bit 1 como "verdadeiro". Daí, definimos três operações básicas análogas aos conectivos lógicos:

• OU: Sejam A e B duas variáveis, A OU B, também escrito A + B, retorna 1 se pelo menos uma das variáveis for 1.
• E: A E B, ou A x B, retorna 1 se ambas as variáveis forem 1.
• NÃO: NÃO A, ou \(\bar{A}\), inverte o valor de A. Se A for 1, retorna 0; se A for 0, retorna 1.

A partir dessas operações, montamos dispositivos eletrônicos conhecidos como portas lógicas, que compõem os diversos circuitos lógicos de um computador. Veja um exemplo de circuito lógico com 3 variáveis de entrada e 1 saída:

Circuito lógico montado no The Logic Lab.

Cada porta lógica representa uma operação, que pode ser uma combinação das operações básicas descritas acima. Qualquer operação aritmética básica é definida pelos circuitos lógicos. Outra importante aplicação prática é facilmente observada nas linguagens de programação em estruturas de decisão:

if(a == 2 and b == 4)
  // Fazer alguma coisa.


if(a == 2 or c == 2)
  // Fazer outra coisa.


while(<exp>)
  // Executar instruções repetidamente enquanto <exp> for verdadeira.

Lógica modal e linguística

O objetivo principal da lógica é o estudo dos argumentos válidos em um dado sistema lógico, para isso utilizando uma linguagem simbólica capaz de realizar a abstração necessária. A lógica modal em particular preocupa-se em representar sistematicamente as ditas modalidades: a princípio possibilidade e necessidade, mas também enquadram-se outros sistemas que lidam com temporalidade, obrigatoriedade etc.

Linguística é o estudo da linguagem verbal humana, também conhecida como linguagem natural. Em contraste existem as linguagens artificiais, construções humanas arbitrárias nas quais se encaixam linguagens de programação. O problema é que linguagens naturais estão propensas a um alto grau de ambiguidade, o que torna difícil sua formalização e interpretação. A lógica entra aqui na elaboração de uma versão idealizada da linguagem objeto para fins de estudo.

A lógica modal parte do princípio abstrato de mundos possíveis. Algo é necessário quando permanece verídico em todos os mundos, e possível quando é verídico em pelo menos um mundo. Pode parecer coisa de maluco, mas a ideia de vários mundos diferentes nos quais os significados das frases variam é compreendida de maneira intuitiva. Compare:

"É certo que você encontrará um emprego, e é possível que ele pague bem."

"É possível que você encontrará um emprego, e é certo que ele pague bem."

"É possível que você encontrará um emprego, e, se encontrá-lo, é certo que ele pague bem."

Podemos analisar as sentenças visualizando um mundo atual e vários mundos futuros. A primeira sentença sugere que o emprego é encontrado em todos esses mundos futuros, e em alguns deles o emprego paga bem. A segunda sentença causa estranheza porque sugere que há pelo menos um mundo onde o emprego é encontrado, mas ao mesmo tempo implica que em todos os mundos o emprego paga bem, uma contradição!

A terceira é uma versão semanticamente válida da segunda. Nela, em alguns dos mundos futuros o trabalho é encontrado. Dentre esses mundos onde o trabalho é encontrado, todos são trabalhos que pagam bem. Note a diferença causada pela afirmação condicional. Daí a necessidade de se preocupar com a lógica nos estudos de semântica.

Fontes

Álgebra Booleana e Aplicações - Notas de aula
Applications of Modal Logic in Linguistics
Book of Proof
Lógica Matemática - Provas