%% Time-stamp: <version du Thu 26 Oct 2000 à 08h10 par Pierre Lescanne>
%% /MIM-1/LOGIQUE/00-01/COURS+TRANSP/HILBERT/transp.tex
% \documentclass[%
%   slidesonly,%  Pour sortir les transparents seuls
%   semrot,%      Permettre des rotations eventuelles
%   semhelv,%    Helvetica
%   a4%           A4 paper
%   ]{seminar}

% %\renewenvironment{slide}[1]{#1} 
% %\def\printlandscape{}  % pour sortir en portrait
% %\slidesmag{1} 
% %\usepackage{fullpage}

% \def\printlandscape{\special{landscape}}     % pour sortir en landscape
% \slidesmag{5}

\documentclass{article}
\usepackage{fancybox}
\usepackage[francais]{babel}
\usepackage[latin1]{inputenc}
\usepackage{color}

% %% Time-stamping  
% %% compute the time in hours and minutes; 
%  \newcount\timehh\newcount\timemm \timehh=\time 
%  \divide\timehh by 60 \timemm=\time
%  \count255=\timehh\multiply\count255 by -60 \advance\timemm by \count255
%  \newcommand{\timestamp}
%  { {\protect\small\sl\today\ -- 
%  \ifnum\timehh<10 0\fi\number\timehh\,h\,
%    \ifnum\timemm<10 0\fi\number\timemm}}
%                                           % avec dvips


% \articlemag{1}

% \rotateheaderstrue       % si tu combines slide et slide*

\title{{\textit{Introduction à la Logique}}}

\author{}

\date{}

% \pagestyle{}

% \slidestyle{empty}

% \slideframe{}   

\newcommand{\rouge}[1]{{\color{red}#1}}
\newcommand{\VERT}[1]{{\color{green}#1}}
\newcommand{\bleu}[1]{\textcolor{blue}{$#1$}}
\newcommand{\bl}[1]{\textcolor{blue}{#1}}
\newcommand{\Ra}{\ensuremath{\Rightarrow}}
\newcommand{\et}{\mathop{\&}}
\newcommand{\sh}{\mathop{|}}
\newcommand{\inferTwoLabel}[4]{\bl{
 {#1} \quad 
 \begin{array}{c}
   #2 \hspace{2em} #3\\
   \hline \noalign{\vskip 1pt}#4
  \end{array}}}

\newcommand{\leafLabel}[2]{\bl{
 {#1} \quad
  \begin{array}{c}
  #2
  \end{array} }}

\newcommand{\inferLabel}[3]{\bl{
    {#1} \quad 
    \begin{array}{c}
      #2\\
      \hline \noalign{\vskip 1pt}#3
    \end{array}
  }}

    
% \newcommand{\heading}[1]{%      % ca c'est des commandes a moi
%   \begin{center}                % mais ca peut t'interesser
%     \large\bf
%     \color{cyan}{\shadowbox{#1}}%
%   \end{center}
%   \markright{#1}
%   \vspace{1ex minus 1ex}}

% \newcommand{\subheading}[1]{%
%   \begin{center}
%     \color{green}{\bf\Ovalbox{#1}}
%   \end{center}}

\begin{document}
\maketitle

\section{Quels sont les buts de la logique ?}

\subsection{Pour tous}

\begin{itemize}
  
\item \rouge{Comprendre} la nature intime du \bl{raisonnement mathématique}
  \footnote{et du raisonnement non mathématique !}
 
\item Faire du ``raisonnement'' une \rouge{théorie mathématique}
  comme les autres.

\item Donner un sens précis à ce que peut-être le \rouge{vrai} dès qu'il s'agit de raisonnement et d'argumentation.
\end{itemize}

\subsection{Pour les mathématiciens}
\begin{itemize}
\item S'assurer (se convaincre ?) que les mathématiques sont \rouge{exemptes
  de contradictions} et de paradoxes.

\item \rouge{Apprendre} une branche des mathématiques.

\end{itemize}
\subsection{Pour les informaticiens}

\begin{itemize}

\item \rouge{Mécaniser} les processus de raisonnement.

\item \rouge{Exhiber les liens} entre \emph{démonstrations} et \emph{calculs}.


\item \rouge{Formaliser} les objets informatiques.
 
\end{itemize}

\section{Ce que la logique n'est pas : Point de vue personnel}
\begin{itemize}
\item Le \rouge{fondement ultime} auquel se réduisent les
  mathématiques, (point de vue réductionniste)
\item La discipline qui va faire \rouge{remplacer les humains} (en
  général) et les mathématiciens (en particulier) par des machines
  (point de vue mécaniste).
\end{itemize}

\section{La logique, une théorie mathématique}
 
La logique est une théorie mathématique comme les autres !
\begin{itemize}
\item elle \rouge{utilise les mathématiques} comme le font les autres branches 
  des mathématiques,
\item elle \rouge{étudie des sortes particuliers d'objets mathématiques} : les
  propositions, les théorèmes, les jugements, les démonstrations, etc.
\end{itemize}

\section{Un peu d'histoire}

L'histoire montre que \VERT{tout ce qui est susceptible de se
  mathématiser se mathématise.}


Au début, seuls les \rouge{entiers} sont des êtres mathématiques.

Puis les Anciens acceptent les \rouge{rationnels} et les \rouge{relatifs}.  

A la Renaissance, les \rouge{complexes} (ou imaginaires) deviennent eux-aussi
des êtres mathématiques.
 
Au dix-neuf-ième siècle 
  \begin{itemize}
  \item les \rouge{réels} (Dedekind), 
  \item puis les \rouge{fonctions} (en
    ``extension'') 
  \item et les \rouge{ensembles} (Cantor) deviennent des
    êtres mathématiques.
\end{itemize}  
Au début vingtième siècle, les \rouge{fonctions} (en ``intention'')
(Church et Curry) et les \rouge{théorèmes} (Boole, Frege etc.)
deviennent des êtres mathématiques.
  
Aujourd'hui (1980), les \rouge{démonstrations} (Curry et Howard)
deviennent des êtres mathématiques.

\section{Mécaniser la logique ?}

Deux positions  s'affrontent.

\begin{description}
\item[\rouge{Le mathématicien ne sera jamais battu par une machine}]~\\ 
\VERT{Alain Connes} (le triangle de la pensée)
\item[\rouge{Il existe un théorème qui ne peut être prouvé que par un
  ordinateur}]~\\[-2pt]\VERT{Veroff and McCune}

Les algèbres de Boole peuvent être axiomatisées par le seul axiome
\[\bl{
((x \sh z) \sh y) \sh ((x \sh (x \sh y)) \sh x) = y
}\]

\end{description}
où \bleu{|} est le symbole de Sheffer qui peut être interprété
comme
\bl{
\begin{eqnarray*}
x \sh y &=& \bar{x} \et \bar{y}.
\end{eqnarray*}
}

\section{Les deux niveaux de la logique}

En logique, il y a deux niveaux qui interfèrent et qu'il ne
faut pas confondre.

\begin{itemize}
\item La \rouge{théorie}, (on dit aussi parfois la \rouge{théorie objet}, si
  l'on veut être plus précis).  
  
\item La \rouge{méta-théorie}, c'est une mathématique dans laquelle on
  va raisonner sur l'objet.   C'est aussi un système logique !
  
\end{itemize}
  
La \rouge{théorie objet} est l'objet logique que l'on étudie et que l'on
souhaite donc formaliser.

\vspace*{12pt}

En général, on accepte dans la \rouge{méta-théorie} toute la puissance du
raisonnement traditionnel.  Si elle est mécanisée, cela peut-être par
un système formel plus ou moins puissant.
 
Dans la méta-théorie, on prouve des \VERT{méta-théorèmes}, c-à-d des  théorèmes à propos de la théorie objet.

Quelques méta-théorèmes courants sont:
\begin{itemize}
\item la \rouge{correction},
\item la \rouge{cohérence},
\item la \rouge{complétude}.
\end{itemize}


\section{Les ingrédients de la logique}
\subsection{Les aspects preuves}

En logique on trouve :
\begin{itemize}
\item un \rouge{langage} d'expressions bien formées : les
  \VERT{propositions} (construites avec des \emph{connecteurs}),
  les \VERT{jugements}, etc. \\
On dit aussi que c'est la \emph{syntaxe}.
\item des \rouge{axiomes},
\item des \rouge{règles}.
\end{itemize}

Les \rouge{axiomes} affirment que \VERT{certaines propositions sont des
  théorèmes}: on définit un prédicat unaire dans la méta-théorie.

Les \rouge{règles} montrent comment \VERT{construire des théorèmes à
  partir d'autres théorèmes}.  On définit dans la méta-théorie, 
\begin{itemize}
\item des fonctions des propositions vers les propositions (règles
  monadiques) 
\item ou des fonctions des couples de propositions vers les propositions
  (règles dyadiques)
\end{itemize}

Le but des axiomes et des règles est de former des expressions
particulières, les \rouge{théorèmes} en construisant des objets
mathématiques particuliers les \rouge{démonstrations} (ou
\rouge{preuves}).

Il y a différentes sortes d'objets: \VERT{propositions}\footnote{qui
  ne sont pas théorèmes}, \VERT{théorèmes}, etc.

Dans une logique, l'appartenance d'un objet à telle ou telle sorte se
décrète par un \rouge{jugement}.

\subsection{Syntaxe concrète et syntaxe abstraite}

Un \bl{ordinateur} a besoin qu'on lui parle de la syntaxe à un bas
niveau, c'est la \rouge{syntaxe concrète}, c-à-d les \VERT{virgules},
les \VERT{parenthèses}, les \VERT{retours à la ligne}, etc.

Un \bl{humain} préfère une syntaxe lisible et flexible, il a besoin de
la \rouge{syntaxe abstraite}, c-à-d plutôt la structure arborescente,
donc il souhaite des \VERT{opérateurs infixes},
l'\VERT{associativité}.

\subsection{Les aspects modèles}

On interprète le langage dans un univers mathématique particulier: les 
\rouge{modèles}.   On parle aussi de \rouge{sémantique}.

Les propositions qui sont ``satisfaites'' (dans un sens à préciser) par le
modèle sont dites \rouge{valides}.

Correction, cohérence et complétude établissent des \rouge{liens} entre 
\begin{itemize}
\item les \VERT{théorèmes} (propositions prouvables)
\item  et les \VERT{tautologies} (propositions valides),
\end{itemize}
c'est-à-dire entre la prouvabilité et la validité.

\subsection{Les deux branches de la logique}

La partie de la logique où l'on s'intéresse plutôt aux démonstrations
s'appelle la la \rouge{théorie de la démonstration} ou théorie de la preuve
(proof theory).

La partie de la logique où l'on s'intéresse plutôt à la validité
s'appelle la \rouge{théorie des modèles}.


\section{Bibliographie}

Un \rouge{livre de base} :

\begin{quote}
  R.~Lalement.  \bl{ Logique, Réduction, Résolution}.  Études et
  recherches en informatique. Masson, Paris, 1990.
\end{quote}


Ma \rouge{référence} :

  \begin{quote}
  D.~van Dalen.  \bl{ Logic and Structure}.  Springer Verlag, 1994.
\end{quote}
\vskip 2 mm
Un livre assez complet sur la logique de l'informatique en
\rouge{français} :
  \begin{quote}
  P.~Gochet, P.~Gribomont. \bl{Logique. Volume 1 : méthodes pour
    l'informatique fondamentale}, HERMES, 1990
\end{quote}

\vskip 2 mm
Sur la logique \rouge{épistémique} :

 \begin{quote}
  R.~Fagin, Y.~Halpern, Y.~Moses, and M.~Y.  Vardi.  \bl{ Reasoning
  about Knowledge}.  The MIT Press, 1995.
\end{quote}

\end{document}