% \newcommand{\lastedit}{2021-06-18 17:41:50 by jstolfi}
% _*_ iso-latin-1 _*_

\chapter{Introdução à lógica matemática}
\label{s.logic}

\section{Como ter certeza?}

  \index{algoritmo!demonstração}
  Você escreveu um programa, ou inventou um algoritmo, para resolver um
  certo problema. Como pode você se convencer que ele funciona? Como
  pode você convencer os outros que ele funciona?

  Uma maneira de adquirir confiança sobre um algoritmo é testá-lo.
  Porém, para a maioria dos algoritmos, é impossível montar testes que
  verifiquem absolutamente todos os casos possíveis que podem ocorrer
  durante sua execução. Muitos programadores podem citar exemplos de
  programas que funcionaram perfeitamente em todos os testes, mas
  falharam imediatamente quando usados na prática.

\section{A invenção da lógica}
\index{lógica|(}

  \index{axioma}
  \index{retórica}
  \index{regra de inferência}
  Essa questão --- como ter certeza que nosso raciocínio é correto, e
  como transmitir aos outros essa certeza --- foi estudada pelos
  gregos séculos antes de Cristo.  Eles observaram que uma maneira de conseguir esse tipo de
  certeza, e para passar essa certeza a outras pessoas, é começar por
  um conjunto de \emph{axiomas}, fatos simples que todos concordam que
  são verdade; e desenvolver um raciocínio a partir desses axiomas,
  usando \emph{regras de inferência}, maneiras de raciocinar que todos
  concordam que são válidas. Com isso eles inventaram a \emph{lógica}, que eles
  consideravam um ramo da \emph{retórica}, a arte de discursar e convencer pessoas.
  
  \index{Aristóteles}
  \index{Sócrates}
  \index{mamífero}
  \index{morcego}
  O filósofo grego Aristóteles (384--322 A.C.), em particular, estudou
  os chamados \emph{silogismos}, raciocínios em que, partindo de duas
  premissas cuja verdade é aceita, obtém-se uma conclusão nova que é
  necessariamente verdadeira. Por exemplo, se acreditamos nas
  premissas ``todos os homens são mortais'' e ``Sócrates é um homem'',
  então temos que acreditar também que ``Sócrates é mortal.''. Ou
  então, se acreditamos que ``nenhum mamífero tem penas'', e que
  ``morcegos são mamíferos'', então temos que acreditar que ``morcegos
  não tem penas''.
  
\index{lógica|)}
  
\section{Euclides e demonstrações geométricas}
\index{geometria!euclidiana|(}

  \index{algoritmo!geométrico}
  \index{régua e compasso}
  \index{pentágono!construção}
  Enquanto isso, os arquitetos e engenheiros gregos
  tinham preocupações semelhantes em relação aos ``algoritmos geométricos''
  --- construções com régua e compasso --- que eles usavam em seus
  projetos. Por exemplo, a receita da figura~\ref{fig.penta} supostamente constrói um
  pentágono com todos os lados e ângulos iguais.

   \jsfig
     {fig.penta}
     {%
      \vbox{%
        \hbox{%
          \epsbox{pentagono-0}{0.175}%
          \epsbox{pentagono-2}{0.175}%
          \epsbox{pentagono-3}{0.175}%
          \epsbox{pentagono-4}{0.175}%
        }%
        \hbox{%
          \epsbox{pentagono-5}{0.175}%
          \epsbox{pentagono-6}{0.175}%
          \epsbox{pentagono-7}{0.175}%
          \epsbox{pentagono-8}{0.175}%
        }%
      } 
    }
    {%
      \textbf{Construção de um pentágono regular.}
    }

  \noindent
  Como podemos ter certeza de que essa construção
  realmente faz isso? Podemos efetuá-la numa folha de papel e medir os
  ângulos; mas tanto os passos da construção quanto a medida final tem
  sempre pequenos erros, e portanto esse teste não vai dizer se a
  construção é matematicamente correta ou apenas aproximada. Se as
  diferenças entre os ângulos são desprezíveis no papel, será que serão
  desprezíveis quando esse algoritmo for usado na construção de um
  anfiteatro?

  \index{Euclides}
  \index{axioma!de Euclides}
  \index{círculo}
  \index{reta}
  \index{reta!paralela}
  \index{triângulo}
  \index{ponto}
  O primeiro a descrever um sistema lógico completo para a geometria da
  época foi o geômetra grego Euclides (que viveu por volta do século III antes de Cristo), no seu livro
  \emph{Elementos de Geometria}~\cite{hea-euc-56-elemg}. Euclides começou enumerando dez
  axiomas sobre conceitos geométricos (pontos, retas, círculos,
  distâncias, ângulos), como por exemplo

    \begin{itemize}
      \item \emph{Por dois pontos distintos do plano passa uma  única reta.}
      \item \emph{Qualquer segmento de reta pode ser prolongado indefinidamente nos dois sentidos.}
      \item \emph{É possível contruir um círculo com quaisquer centro e raio dados.}
      \item \emph{Todos os ângulos retos são iguais.}
    \end{itemize}

  \noindent
  \index{Pitágoras!teorema de}
  \index{reta!perpendicular}
  \index{triângulo!retângulo}
  \index{triângulo!congruência}
  \index{teorema}
  Em seguida Euclides mostrou centenas de outras afirmações (\emph{teoremas}) que
  decorrem desses axiomas, como por exemplo
    \begin{itemize}
      \item \emph{Se um triângulo tem os três lados iguais, ele tem os três ângulos iguais.}
      \item \emph{Duas retas que são perpendiculares a uma terceira são paralelas entre si.}
      \item \emph{Num triângulo retângulo, o quadrado do maior lado é a soma dos quadrados dos
      outros dois lados.}
    \end{itemize}

  \noindent
  \index{demonstração}
  \index{prova}
  Muitos desses teoremas são afirmações de que certas construções
  geométricas, como a da figura~\ref{fig.penta}, produzem o resultado
  desejado. Principalmente, para cada teorema, ele também escreveu uma
  \emph{prova} ou \emph{demonstração} --- uma sequência de passos
  lógicos que, começando com os axiomas e teoremas já provados,
  convence qualquer leitor de que o novo teorema é verdadeiro.

\index{geometria!euclidiana|)}

\section{Álgebra}
\index{álgebra|(}

  \index{divisor!comum}
  \index{número primo}
  \index{algoritmo!de Euclides}
  \index{máximo!divisor comum}
  \index{Euclides}
  A lógica de Euclides e outros filósofos gregos foi extensamente
  usada por mais de dois mil anos. Entretanto, por muitos séculos o
  hábito de provar as afirmações foi limitado apenas à geometria.
  Embora os gregos conhecessem muitas propriedades de números (por
  exemplo, os conceitos de divisor comum e número primo), para
  demonstrar tais propriedades eles geralmente convertiam os números
  em comprimentos de retas, e usavam a linguagem da geometria. Esse é
  o caso, por exemplo, do \emph{algoritmo de Euclides} para calcular o
  máximo divisor comum de dois números --- que é considerado por
  muitos o mais antigo algoritmo não trivial. Na descrição original de
  Euclides, o problema é dividir dois segmentos de reta dados em
  partes iguais e de maior tamanho possível.
  
  \index{Al-Khowarizmi}
  \index{operação!aritmética}
  \index{relação!entre números}
  \index{variável}
  Na idáde média, entretanto, o matemático árabe Al-Khowarizmi
  inventou a \emph{álgebra}, outra maneira de provar afirmações sobre
  números e convencer pessoas de que uma dada sequência de operações
  aritméticas alcança o resultado desejado. Na álgebra, os números são
  representados abstratamente por letras, e as operações ou afirmações
  sobre esses números são indicadas com símbolos como `$+$' ou `$>$'.
  A álgebra também fornece algumas fórmulas, como $A+B = B+A$ e
  $A\times(B+C) = (A\times B) + (A\times C)$, que representam
  afirmações que são sempre verdadeiras, quaiquer que sejam os números
  que vierem a substituir as variáveis. A álgebra também fornece
  certas regras fundamentais que permitem transformar uma fórmula em
  outra fórmula equivalente, ou combinar fórmulas corretas para
  produzir novas fórmulas corretas. Por exemplo, se sabemos que 
  $A > B$ e $B > C$ podemos concluir com certeza que $A > C$.

  \index{René Descartes}
  \index{geometria!analítica}
  \index{álgebra!linear}
  A geometria e a álgebra foram enfim unidas pelo matemático René Descartes (1596--1650), 
  que mostrou como usar pares de números reais para representar pontos do plano. 
  Entre outras consequências, essa idéia revolucionária criou toda a área da geometria analítica e 
  forneceu uma interpretação geométrica para álgebra linear.

\index{álgebra|)}
  
\section{As linguagens da lógica matemática}
\index{lógica|(}
 
  \index{lógica!clássica}
  \index{teoria!de conjuntos}
  \index{cálculo!de predicados}
  Em seguida à revolução de Descartes, outros matemáticos,
  principalmente no século 19, mostraram como aplicar a idéia geral da 
  álgebra também à lógica. Esse trabalho produziu dois principais
  sistemas de notação, ou \emph{linguagens formais}, para expressar
  raciocínios lógicos de maneira matematicamente clara, sucinta, e,
  principalmente, livre de ambiguidades. Estas linguagens são a
  \emph{teoria de conjuntos} e o \emph{cálculo de predicados}. 
  
  As duas linguagens são essencialmente equivalentes, mas continuam
  sendo usadas e misturadas, inclusive na mesma sentença, conforme a que
  for mais conveniente ou clara em cada momento.

  \index{teoria!da probabilidade}
  \index{estatística}
  A lógica clássica somente lida com afirmações que são verdadeiras ou
  falsas. Essa característica praticamente restringe o uso da lógica
  para afirmações matemáticas. Mas no século 16 e 17 matemáticos
  começaram a estudar o cálculo de chances em jogos de azar (dados,
  roletas, loteria, etc.). No iníco do século 20 estas investigações
  haviam evoluído para a \emph{teoria da probabilidade}, que permite
  expressar nosso grau de confiança a respeito de afirmações incertas,
  e raciocinar com precisão sobre elas; e para a \emph{estatística},
  um conjunto de técnicas para analisar dados experimentais que
  supostamente confirmam ou refutam tais afirmações.
  
  \index{teoria!da informação}
  \index{análise de algoritmos}
  \index{teoria!da computabilidade}
  \index{criptografia digital}
  Em meados do século XX, motivada pela expansão do rádio, telefone e
  outros meios eletrônicos de comunicação, a teoria da probabilidade
  por sua vez deu origem à \emph{teoria da informação}, que permite
  determinar, por exemplo, a capacidade real de canais de comunicação
  na presença de distúrbios aleatórios no sinal recebido. Finalmente,
  com o surgimento do computador digital, surgiram disciplinas
  matemáticas específicas para raciocinar precisamente com programas e
  estruturas de dados, incluindo \emph{análise de algoritmos},
  \emph{teoria da computabilidade e complexidade de funções},
  \emph{criptografia digital}, e muitas outras.

\index{lógica|)}
