ajout de sujet de partiels

[cours-maths-dis.git] / logique / Propositions.tex

% \section{Introduction}

% Les liens étroits entre logique et informatique ne sont pas récents,
% avec pour  
% exemple la citation suivante de plus de 40 ans: 
% %\selectlanguage{english}
% {\emph "It is reasonable to hope that the relationship between computation %
% and mathematical logic will be as fruitful in the next century as %
% that between analysis and physics in the last. The development %
%  of this relationship demands a concern for both applications and %
%  mathematical elegance"}
% \cite{McCarthy63}.
% %\selectlanguage{french}


% Ce chapitre met l'accent sur le calcul des propositions, qui est un 
% des fondements de la logique classique, initié par Friedrich Ludwig 
% Gottlob Frege (1848--1925). Ce chapitre contient des extraits 
% de~\cite{CL93, Lip90,LBDg07}.





%\subsection{Objets de la logique} 
% L'objet de la logique est d'analyser le raisonnement humain et, si
% possible, de le formaliser de manière à le rendre aussi indépendant
% que possible des diverses contingences matérielles qui pourraient
% influer sur lui.
% C'est une discipline philosophique, dont on étudiera les aspects
% mathématiques. 


% Cette formalisation poursuit aussi d'autres buts:
% \begin{itemize}
%  \item essai d'unification de diverses théories qui présentent, du
%    point de vue des raisonnements qui sont utilisés, des analogies, 
%  \item essai de production automatique de résultats dans certains domaines.
% \end{itemize}


% Indépendamment de la \og beauté théorique\fg{}  de la chose, le
% premier point présente un intérêt pratique: faire profiter telle
% branche de la science des résultats qui pourraient avoir été obtenus
% ailleurs. 
% C'est surtout le deuxième aspect qui nous occupera dans ce chapitre
% (et les suivants). 


% \subsection{Production automatique}

% Chacun sait que, si un ordinateur calcule vite et bien, il est
% parfaitement incapable de produire de lui-même quelque \og
% raisonnement\fg{}  que ce soit. 
% Mais s'il était possible de programmer les raisonnements étudiés par
% la logique sous forme de calculs, précisément, il serait raisonnable
% de penser que l'ordinateur serait alors, de ce point de vue aussi,
% bien plus rapide et efficace que l'esprit humain. 
 


% Les divers domaines de recherche de ce que l'on appelle de nos jours
% l'\og Intelligence Artificielle\fg{}  convergent presque tous vers ce
% but.
% Même si certains espoirs ont été déçus, comme dans le domaine de la
% traduction automatique (on arrive tout juste à traduire quelques
% textes techniques \og standard\fg{}, et il s'avère très difficile de
% \og donner le sens des nuances\fg{}  à un algorithme\ldots), de nombreux
% résultats intéressants et prometteurs ont été obtenus dans divers
% autres domaines: diagnostic médical, vérification de programmes par
% preuve automatique, preuve formelle du théorème des quatre
% couleurs\ldots  



% \subsection{Des problèmes de l'évidence}

% Avant de chercher à \og programmer un raisonnement\fg{}, il convient
% de savoir précisément de quoi il s'agit.
% Il faut apprendre à disséquer nos démarches intellectuelles, et, avant
% tout, ne pas se laisser paralyser par l'\og évidence\fg{}: rien
% n'est évident pour un ordinateur. Le plus difficile est peut-être de
% pourchasser, pour les expliciter clairement, tous les sous-entendus
% qui nous permettent de produire des raisonnements intelligibles. 
% Finalement, il convient toujours d'adapter son discours au niveau de
% son auditoire: le niveau de l'ordinateur, de ce point de vue, peut
% être considéré comme égal à zéro. 




\section{Les fondements de la logique des propositions}

\emph{Qu'est-ce donc qu'un raisonnement ? Si l'on sait que tous les
écureuils sont des rongeurs, que tous les rongeurs sont des
mammifères, que tous les mammifères sont des vertébrés et que tous les
vertébrés sont des animaux, on peut en déduire que tous les écureuils
sont des animaux.[\ldots].%
\\%
\indent Ce raisonnement est simple à l'extrême, mais sa structure ne diffère
pas fondamentalement de celle d'un raisonnement mathématique. Dans les
deux cas, le raisonnement est formé d'une suite de propositions dans
laquelle chacune découle logiquement des précédentes, [\ldots].
Dans ce cas, on applique la même règle trois fois. Cette
règle permet, si l'on sait déjà que tous les $Y$ sont des $X$ et que tous
les $Z$ sont des $Y$, de déduire que tous les $Z$ sont des $X$}~\cite{Dowek07}.

Cette section formalise la notion de proposition
(Sec.~\ref{sub:prop:prop}),  montre comment les propositions peuvent être
connectées entre elles (Sec.~\ref{prop:sub:cnx}) et comment elles sont 
représentées syntaxiquement (Sec.~\ref{prop:sub:vars}).

\subsection{Les propositions}\label{sub:prop:prop}

%\subsubsection{Articulation d'un raisonnement}

% L'homme exprime son raisonnement par un discours, et ce discours
% utilise une langue (une langue naturelle, français, anglais,\ldots). 
% D'une manière générale, ce discours est articulé en phrases, d'un
% niveau de complexité variable, et c'est l'étude de ces \og
% énoncés\fg{}  que se propose de faire la logique. 


%\subsubsection{Les propositions, intuitivement}

\begin{Def}[Proposition]
Parmi tous les énoncés possibles qui peuvent être formulés dans une
langue, on distingue ceux auxquels il est possible d'attribuer une \og
valeur de vérité\fg{}: vrai ou faux. 
Ces énoncés porteront le nom de \emph{propositions}
\index{proposition}. 
\end{Def}


\begin{Ex}
 \og Henri IV est mort assassiné en 1610\fg{}, 
\og Napoléon  Bonaparte a été guillotiné en 1852\fg{} 
sont des propositions,
 puisqu'on peut leur attribuer une valeur de vérité (\og vrai\fg{}
 pour la première, \og faux\fg{}  pour la seconde). 
\end{Ex}





% \subsubsection{Des énoncés qui ne sont pas des propositions}

% Un énoncé \og hypothétique\fg{}  comme \og Dans six mois, il y aura
% une exceptionnelle période de beau temps\fg{}  est exclu du domaine
% des propositions et donc de notre étude. 
% Il en est de même pour ce qu'on appelle les \og paradoxes\fg{}  de la
% logique comme, par exemple, celui du menteur. 
% En effet, il est impossible d'attribuer une valeur de vérité à ces
% énoncés: nous les rejetons en dehors du cadre des propositions. 


% \begin{Exo} 
%  Si je dis: \og la présente affirmation est vraie\fg{}, cette
%  affirmation possède-t-elle une valeur de vérité ? 
% \end{Exo}


% \begin{Exo}
%  Les affirmations suivantes sont-elles des propositions ?
% \begin{enumerate}
%  \item \og l'affirmation qui suit est vraie\fg{},
% \item \og l'affirmation qui précède est fausse\fg{}.
% \end{enumerate}
% \end{Exo}
 


%\subsubsection{Principes fondateurs du calcul des propositions}

Le calcul que l'on étudie considère toujours comme acquises 
les vérités suivantes, élevées au rang d'axiomes.


\begin{description}
 \item[Principe de non-contradiction:] Une proposition ne peut être
   simultanément vraie et fausse.\index{principe!de non-contradiction} 
 \item[Principe du tiers-exclu:] Une proposition est vraie ou fausse
   (il n'y a pas d'autre possibilité).\index{principe!du tiers-exclu}
 \end{description}

% \subsubsection{D'autres logiques}

% \noindent Il existe, bien entendu, d'autres logiques:

% \begin{itemize}
%  \item fondées sur d'autres axiomes,
%  \item qui admettent d'autres \og valeurs de vérité\fg{}: le \og
%    possible\fg{}, par exemple 
%  \item qui attribuent des \og coefficients de vraisemblance\fg{}  aux
%    énoncés, 
% \item etc.
% \end{itemize}

% AG: j'aurais besoin d'ôter cette phrase pour pouvoir
% parler de logique intuitionniste.
% JFC: mis en commentaire
%Ces logiques sortent du cadre de notre étude.






\subsection{Les connecteurs logiques}\label{prop:sub:cnx}


% L'analyse logique d'une phrase (reconnue comme proposition) fait
% apparaître des sous-phrases qui constituent elles-mêmes des
% propositions.
% Ces \og membres de phrases\fg{}  sont reliés entre eux par des \og 
% connecteurs logiques\fg{}, comme expliqué dans la partie suivante\ldots

% \subsubsection{Analyse logique des propositions}

Considérons l'énoncé: \og J'ai obtenu une mauvaise note à cet examen
parce que je n'ai pas assez travaillé ou parce que le cours est trop
difficile\fg{}.
On suppose qu'il est possible d'attribuer une valeur de vérité à cet
énoncé \og global\fg{}, ce qui le classe parmi les propositions. 

On peut alors mener %ce qu'en grammaire française on appelle 
l'analyse logique de cette phrase, de manière à en extraire 
les propositions (ausens grammatical du terme): 
\og J'ai obtenu une mauvaise note à cet 
examen\fg{}, \og je n'ai pas assez travaillé\fg{}, \og le cours est
trop difficile\fg{}, qui sont aussi des propositions au sens logique
du terme. 


% Ces propositions, au sens grammatical du terme, sont reliées entre
% elles par \og parce que\fg{}  et par \og ou\fg{}, qui sont
% --grammaticalement parlant-- des conjonctions (respectivement de
% subordination et de coordination): 

% \begin{description}
% \item[parce que: ] introduit habituellement un lien de \og cause à effet\fg{},
% \item[ou: ] se contente de juxtaposer les propositions (au même niveau).
% \end{description}

% \subsubsection{Vers une formalisation}

%Globalement, 
Cet énoncé exprime que \og ma mauvaise note\fg{} est
conséquence de l'une (au moins) des deux causes suivantes: 
\begin{itemize}
\item \og mon manque de travail\fg{},
\item \og un cours trop difficile\fg{}, soit:
\end{itemize}
%\noindent Autrement posé (il s'agit d'un début de formalisation):
$$
\textrm{(
  \og mon manque de travail\fg{} ou 
  \og cours trop difficile\fg{}) entraîne 
  \og ma mauvaise note\fg{}}
$$



% \begin{Rem}
% Il ne faut pas sous-estimer la difficulté de ce travail d'analyse:
% \begin{itemize}
%  \item le langage courant est souvent imprécis ou ambigu, 
%  \item il faut souvent se livrer à une véritable interprétation pour
%    parvenir à formaliser une phrase. 
% \end{itemize}
% \end{Rem}


% \begin{Rem}
% L'analyse en logique des propositions s'arrête au niveau des
% connecteurs logiques (qui vont être présentés). 
% Elle ne permet pas de prendre en compte certaines nuances, la
% concordance des temps, ou d'autres liens qui peuvent exister entre des 
% propositions. 
% \end{Rem}
% % \begin{Ex}
% % En logique des propositions, les propositions \og il y a des gens qui font ceci ou cela\fg{}  et \og les gens font ceci ou cela\fg{} sont simplement différentes, et les connecteurs logiques ne permettent pas d'établir un rapport sémantique (au niveau du sens) entre les deux.
% % \end{Ex}




D'une manière générale, le calcul propositionnel ne se préoccupe que
des valeurs de vérité,  ;\emph{ et pas du tout des liens sémantiques qui
peuvent exister entre des propositions}. Ces dernières sont reliées
entre elles syntaxiquement par des connecteurs comme \og ou\fg{} ou
\og entraîne\fg{}. 
Les connecteurs logiques sont donc des symboles qui permettent de
produire des propositions (\og plus complexes\fg{}) à partir d'autres
propositions (\og plus simples\fg{}). 
% Ag: relativiser. C'est ainsi dans le calcul des propositions,
% mais pas en déduction naturelle.
En calcul propositionnel, 
ils sont définis axiomatiquement à partir de leurs tables de vérité. 

\subsubsection{Tables de vérité des connecteurs logiques}

\paragraph{Disjonction logique: } Connecteur \og ou\fg{}, symbole $\ou$.

\`A partir de deux propositions $P$ et $Q$, ce connecteur permet la
construction de la nouvelle proposition ($P$ ou $Q$) [notée $P\ou Q$],
dont la valeur de vérité est définie %en fonction de celles de $P$ et de $Q$ 
par la table de vérité: 

\centerline{\begin{tabular}{|c|c|c|}
\hline
$P$ & $Q$ & $P\ou Q$ \\ \hline
F & F & F \\ \hline
F & V & V \\ \hline
V & F & V \\ \hline
V & V & V \\ \hline \end{tabular}}

On remarque que $P \ou Q$ est fausse si et seulement si les deux
propositions $P$ et $Q$ sont fausses.

% AG: probleme manque espace apres guillemet fermant a resoudre.
% JFC: résolu
\begin{Rem}
Dans le langage courant, le mot \og ou\fg{}  est souvent employé de deux
façons distinctes: 
\begin{itemize}
\item  il est parfois utilisé avec le sens \og les deux cas peuvent se
produire\fg{} (comme ici) et, 
\item parfois avec le sens 
\og $p$ ou $q$ , mais pas les deux\fg{} (e.g. \og il ira à Paris ou à
Marseille\fg).
\end{itemize}
Sauf indication contraire, le \og ou\fg{} sera toujours employé avec
cette première signification.
\end{Rem}



\paragraph{Conjonction logique: } Connecteur \og et\fg{}, symbole $\et$.

\`A partir de deux propositions $P$ et $Q$, ce connecteur permet la construction de la
nouvelle proposition ($P$ et $Q$) [notée $P\et Q$], dont la valeur de
vérité est définie %en fonction de celles de $P$ et de $Q$ 
par la table de vérité:

\centerline{\begin{tabular}{|c|c|c|}
\hline
$P$ & $Q$ & $P\et Q$ \\ \hline
F & F & F \\ \hline
F & V & F \\ \hline
V & F & F \\ \hline
V & V & V \\ \hline \end{tabular}}
On remarque que $P \et Q$ est vraie si et seulement si les deux
propositions $P$ et $Q$ sont vraies.


% \begin{Exo}
% Rappelez quels sont les différents comportements des commandes shell suivantes:
% \begin{itemize}
% \item commmande1 ; commande2
% \item commande1 \&\& commande2
% \item commande1 $||$ commande2
% \end{itemize}
% Expliquez ces comportements à partir de ce qui précède.
% \end{Exo}

\paragraph{Négation logique: } Connecteur \og non\fg{}, symbole $\non$.

\`A partir d'une proposition $P$, ce connecteur permet de construire
la nouvelle proposition (non $P$) [notée $\non P$], dont la valeur de
vérité est définie %en fonction de celle de $P$ 
par la table de vérité

\centerline{ 
\begin{tabular}{|c|c|} \hline
$P$ & $\non P$ \\ \hline
F & V \\ \hline
V & F \\ \hline
\end{tabular}}

\paragraph{Implication logique: } Connecteur \og si\ldots 
alors\fg{}, symbole $\imp$.

% AG: A Besancon, l'implication est notée $\Rightarrow$.
% Ceci est adapté par un ``let \imp=\ldots'' transparent.
% idem pour equivalence


\`A partir de deux propositions $P$ et $Q$, ce connecteur
permet la construction de la proposition (Si $P$, alors $Q$) [notée $P
\imp Q$], dont la valeur de vérité est définie 
%en fonction de cellesde $P$ et de $Q$ 
par la table de vérité:  

\centerline{\begin{tabular}{|c|c|c|}
\hline
$P$ & $Q$ & $P\imp Q$ \\ \hline
F & F & V \\ \hline
F & V & V \\ \hline
V & F & F \\ \hline
V & V & V \\ \hline \end{tabular}}


\begin{Rem}
Lorsque la proposition $P$ est fausse, 
la proposition \og Si $P$, alors $Q$\fg{} est vraie, quelle que soit
la valeur de vérité de la proposition $Q$,  

% Par exemple, la proposition: \og Si le pôle Nord est l'endroit le
% plus chaud de 
%  la planète, alors les poules ont des dents\fg{}  doit être considérée 
%  comme ayant la valeur de vérité \og vrai\fg{}. 
% Le connecteur logique \og $\imp$\fg{} ne contient aucune idée de
% raisonnement, et ne s'occupe nullement (on l'a dit) des liens
% sémantiques qui peuvent exister entre la température qui règne au
% p\^ole Nord et la dentition des poules. 
\end{Rem}

% Il s'agit simplement d'une proposition, qui forme un tout, et qui a la
% valeur de vérité \og vrai\fg{}  lorsque, notamment, $P$ et $Q$ ont
% toutes les deux la valeur de vérité \og faux\fg{}. 


\begin{Exo}
Déterminer la valeur de vérité des propositions suivantes 
\emph{dans le monde actuel} (c.-à-d. celui dans lequel nous vivons):
\begin{enumerate}
\item \og si la terre est plate, alors la lune est carrée; \fg{}
\item \og si le soleil tourne autour de la terre alors la terre est ronde\fg{}
\item \og si la terre est ronde alors le soleil tourne autour de la terre\fg{}
\item \og si vous étudiez la logique alors $E=m.c^2$\fg{}
\item \og si Napoléon est mort alors il a gagné la bataille de Waterloo\fg{}
\item \og s'il pleut en ce moment alors il pleut en ce moment\fg{}
\item \og si tous les hommes sont passionnés par la logique alors Dieu existe\fg{}
\item \og si le Diable existe alors ceci est un exercice de logique\fg{}
\end{enumerate}
\end{Exo}


La manière de mener un raisonnement qui utilise éventuellement des
propositions qui se présentent sous la forme d'implications logiques
est l'objet de la théorie de la déduction qui sera étudiée plus loin. 

\paragraph{Équivalence logique: } Connecteur \og si et seulement
si\fg{}, notation: $\eqv$. 
% AG: ou \ssi dans symboles.sty
\`A partir de deux propositions $P$ et $Q$, ce
connecteur permet la construction de la nouvelle proposition ($P$ si
et seulement si $Q$) [notée $P\eqv Q$], dont la valeur de vérité est
donnée par la table de vérité

\centerline{\begin{tabular}{|c|c|c|} 
\hline
$P$ & $Q$ & $P\eqv Q$ \\ \hline
F & F & V \\ \hline
F & V & F \\ \hline
V & F & F \\ \hline
V & V & V \\ \hline \end{tabular}}


\begin{Rem}
Même remarque que pour l'implication logique: l'équivalence logique
de deux propositions fausses est une proposition vraie. 
\end{Rem}


% AG: exercices pas relus, mis dans diapos cours

%\paragraph{Exercices corrigés}

\begin{Exoc}
 En notant $M$ et $C$ les affirmations suivantes:
\begin{itemize}
\item $M$ = \og Jean est fort en Maths\fg{},
\item $C$ = \og Jean est fort en Chimie\fg{},
\end{itemize}

\noindent représenter les affirmations qui suivent sous forme
symbolique, à l'aide des lettres $M$ et $C$ et des connecteurs
usuels. 

\begin{enumerate}
\item \label{it:x1} \og Jean est fort en Maths mais faible en Chimie\fg{}
\item \label{it:x2} \og Jean n'est fort ni en Maths ni en Chimie\fg{}
\item \label{it:x3} \og Jean est fort en Maths ou il est à la fois fort en Chimie et faible en Maths\fg{}
\item \label{it:x4} \og Jean est fort en Maths s'il est fort en Chimie\fg{}
\item \label{it:x5} \og Jean est fort en Chimie et en Maths ou il est fort en Chimie et faible en Maths\fg{}
\end{enumerate}

% AG: je peux ajouter ici un mecanisme d'option qui fait que
% l'etudiant n'a pas la reponse dans son poly, mais le prof l'a.

Réponses: 

\ref{it:x1}. $M \et (\non C)$; 
\ref{it:x2}. $(\non M) \et (\non C)$; 
\ref{it:x3}. $M \ou ( C  \et \non M )$; 
\ref{it:x4}. $C \imp M$; 
\ref{it:x5}. $(M \et C) \ou (\non M \et Q)$.
\end{Exoc}

\begin{Exo}
 En notant $M$, $C$ et $A$ les trois affirmations suivantes:
\begin{itemize}
 \item $M$ = \og Pierre fait des Maths\fg{};
\item $C$ = \og Pierre fait de la Chimie\fg{};
\item $A$ = \og Pierre fait de l'Anglais\fg{}.
\end{itemize}

Représenter les affirmations qui suivent sous forme
symbolique, à l'aide des lettres $M$, $C$, $A$ et des connecteurs
usuels. 

\begin{enumerate}
 \item \label{ex2:1} \og Pierre fait des Maths et de l'Anglais mais pas de Chimie\fg{}
\item \label{ex2:2} \og Pierre fait des Maths et de la Chimie mais pas à la fois de la Chimie et de l'Anglais\fg{}
\item \label{ex2:3}\og Il est faux que Pierre fasse de l'Anglais sans faire de Maths\fg{}
% \item \label{ex2:4} \og Il est faux que Pierre ne fasse pas des Maths et fasse quand même de la chimie\fg{}
% \item \label{ex2:5} \og Il est faux que Pierre fasse de l'Anglais ou de la Chimie sans faire des Maths\fg{}
\item \label{ex2:6} \og Pierre ne fait ni Anglais ni Chimie mais il fait des Maths\fg{}
\end{enumerate}

\end{Exo}
% Réponses:

% \ref{ex2:1}. $M \et A \et (\non C)$; 
% \ref{ex2:2}. $(M \et C) \et (\non (C \et A))$; 
% \ref{ex2:3}. $\non (A \et (\non M))$; 
% \ref{ex2:4}. $\non ((\non M) \et C)$; 
% \ref{ex2:5}. $\non ((A \ou C) \et \non M)$;
% \ref{ex2:6}. $(\non A) \et (\non C) \et M$.
% \end{Exoc}

\begin{Exo}
 \'Enoncer la négation des affirmations suivantes en évitant d'employer l'expression: \og il est faux que\fg{}

\begin{enumerate}
 \item \og S'il pleut ou s'il fait froid je ne sors pas\fg{}
\item \og Le nombre 522 n'est pas divisible par 3 mais il est divisible par 7\fg{}
\item \og Ce quadrilatère n'est ni un rectangle ni un losange\fg{}
\item \og Si Paul ne va pas travailler ce matin il va perdre son emploi\fg{}
% \item \og Tout nombre entier impair peut être divisible par 3 ou par 5 mais jamais par 2\fg{}
% \item \og Tout triangle équilatéral a ses angles égaux à 60°\fg{}
\end{enumerate}


% Réponses:

% \begin{enumerate}
% \item il pleut ou il fait froid et pourtant, je sors
% \item Le nombre 522 est divisible par 3 ou il n'est pas divisible par 7
% \item Ce quadrilatère est un rectangle ou un losange
% \item Paul n'ira pas travailler ce matin mais il ne perdra pas son emploi
% \item Il existe un nombre entier impair, qui n'est pas divisible par 3
%   ni par 5 et qui est divisible par 2
% \item Il existe un triangle équilatéral dont les angles ne sont pas égaux à 60°
% \end{enumerate}
\end{Exo}

\begin{Exoc}
 Quelles sont les valeurs de vérité des propositions suivantes ?
\begin{enumerate}
\item \label{it:3:1}$\pi$ vaut 4 et la somme des angles d'un triangle
  vaut 180° 
\item \label{it:3:2} $\pi$ vaut 3,141592\ldots implique que la somme des
  angles d'un triangle vaut 180° 
\item \label{it:3:3} $\pi$ vaut 4 implique que la somme des angles
  d'un triangle vaut 182° 
\item \label{it:3:4}Il n'est pas vrai qu'un entier impair ne puisse
  pas être divisible par 6 
\item \label{it:3:5}Si 2 est plus grand que 3 alors l'eau bout à 100°C  
\item \label{it:3:6}Si 6 est plus petit que 7 alors 7 est plus petit
  que 6 
\item \label{it:3:7}Si 7 est plus petit que 6 alors 6 est plus petit
  que 7 
\item \label{it:3:8} 84 est divisible par 7 implique que 121 est
  divisible par 11 
\item \label{it:3:9}Si $531^{617}+1$ est divisible par 7 alors
  $531^{617}+1$ est plus grand que 7 
% \item \label{it:3:10} Si $531^{617}+1$ est divisible par 7 alors
%   $531^{617}-13$ est divisible par 43 
\item \label{it:3:11} La décimale $d$ de $\pi$ qui porte le numéro
  $10^{400}$ est 3 
  implique que si $d$ n'est pas 3 alors $d$ est 3. 
\end{enumerate}

Réponses:

\ref{it:3:1} F; 
\ref{it:3:2} V; 
\ref{it:3:3} V; 
\ref{it:3:4} F; 
\ref{it:3:5} V; 
\ref{it:3:6} F; 
\ref{it:3:7} V; 
\ref{it:3:8} V; 
\ref{it:3:9} V; 
%\ref{it:3:10} F; 
\ref{it:3:11} V. 
\end{Exoc}

% \begin{Exo}
% Partant des deux affirmations $P$ et $Q$, on peut en construire une autre, notée $P \downarrow Q$, bâtie sur le modèle: \og ni $P$, ni $Q$\fg{}.

% Cette opération est-elle une connexion ? Si oui, quelle est sa table de vérité ?
% \end{Exo}

% Réponse: c'est une connexion, puisque $P \downarrow Q = (\non P) \et (\non Q)$.



% AG: remplacer partout ``forme'' par ``formule'' ?
% JFC: oui, c'est fait.

\subsection{Variables et formules propositionnelles}\label{prop:sub:vars}



Le calcul propositionnel ne s'occupe que des valeurs de vérité: 
dans une expression logique on peut donc remplacer chaque
proposition par un symbole (une lettre de l'alphabet majuscule), appelé 
  \emph{variable  propositionnelle}\index{variable propositionnelle}.
Il reste à étudier ensuite les valeurs de vérité de l'expression en fonction
des valeurs de vérité de ces symboles.

%\subsubsection{Formalisation}

% \begin{Def}[Formules propositionnelles]
% Les expressions ainsi obtenues sont appelées
% \emph{formules propositionnelles} \index{formules propositionnelles}.
% \end{Def}

\begin{Th}
Les règles (de syntaxe) qui permettent de former des 
\emph{formules propositionnelles} sont les suivantes: 

% AG: Il est plus classique et plus pratique de mettre les
% parentheses autour des expressions plutot qu'a l'interieur.
% JFC: corrigé
\begin{itemize}

\item toute variable propositionnelle est une formule propositionnelle;
\item si $F$ et $G$ sont des formules propositionnelles, alors $(F)$, $\non
  F$, $F\ou G$, $F\et G$, $F\imp G$ et $F\eqv G$
  sont des formules propositionnelles. 
\end{itemize}
\end{Th}



\begin{Rem}
En général une formule propositionnelle n'a pas de valeur de vérité déterminée. 
Cette dernière dépend des valeurs de vérité de ses variables
propositionnelles.
\end{Rem}




\begin{Exo}
$A$ et $B$ sont des variables propositionnelles, susceptibles de
représenter n'importe quelle proposition. 
Formaliser, à l'aide de connecteurs logiques appropriés, les énoncés 
suivants: 

\begin{enumerate}
\item \og $A$ si $B$\fg{}
\item \og $A$ est condition nécessaire pour $B$\fg{} 
\item \og $A$ sauf si $B$\fg{}
\item \og $A$ seulement si $B$\fg{}
\item \og $A$ est condition suffisante pour $B$\fg{}
\item \og $A$ bien que $B$\fg{}
\item \og Non seulement $A$, mais aussi $B$\fg{}
\item \og $A$ et pourtant $B$\fg{}
\item \og $A$ à moins que $B$\fg{}
\item \og Ni $A$, ni $B$\fg{}
\end{enumerate}
\end{Exo}


\begin{Exo}
Dans cet exercice, les variables propositionnelles $N$ et $T$ servent
 à représenter (respectivement) les propositions \og Un
étudiant a de bonnes notes\fg{} et \og Un étudiant travaille\fg{}. 
\`A l'aide des variables propositionnelles $N$ et $T$, formaliser les
propositions suivantes.

\begin{enumerate}
\item C'est seulement si un étudiant travaille qu'il a de bonnes notes.
\item Un étudiant n'a de bonnes notes que s'il travaille.
\item Pour un étudiant, le travail est une condition nécessaire à l'obtention de bonnes notes.
\item Un étudiant a de mauvaises notes, à moins qu'il ne travaille.
\item Malgré son travail, un étudiant a de mauvaises notes.
\item Un étudiant travaille seulement s'il a de bonnes notes.
\item \`A quoi bon travailler, si c'est pour avoir de mauvaises notes?
\item Un étudiant a de bonnes notes sauf s'il ne travaille pas.
\end{enumerate}
\end{Exo}



\begin{Exo}
 Combien de lignes contient la table de vérité d'une formule propositionnelle qui dépend de $n$ variables ?
\end{Exo}

%Réponse: $2^n$.



Lorsqu'on remplace, dans une formule propositionnelle, les variables
propositionnelles par des propositions, l'assemblage obtenu est une
proposition. 
Cependant, une formule propositionnelle n'est pas une proposition: $A
\imp B$ n'est ni vrai ni faux. 

\begin{Th}[Règles de priorité des connecteurs logiques]
Les conventions de priorité des connecteurs logiques sont les
suivantes (par ordre de priorité décroissante): 
\begin{itemize}
 \item la négation,
 \item la conjonction et la disjonction (au même niveau),
 \item l'implication et l'équivalence (au même niveau).
\end{itemize}
\end{Th}


\begin{Ex}
$\non A\et B \imp C$ doit être interprété par $((\non A)\et B) \imp C$
et la formule $A\ou B\et C$ n'a pas de sens car les deux connecteurs ont même
niveau de priorité. 
\end{Ex}



\begin{Th}[Associativité des opérateurs $\ou$ et $\et$]
 Les opérateurs $\ou$ et $\et$ sont associatifs:
\begin{itemize}
\item $(A \ou B) \ou C = A \ou (B \ou C) = A \ou B \ou C$,
\item $(A \et B) \et C = A \et (B \et C) = A \et B \et C$.
\end{itemize}
Mais le parenthésage est obligatoire quand $\ou$ et $\et$ se trouvent
dans la même proposition, puisqu'il n'y a pas de priorité entre $\ou$
et $\et$: $(A \ou B) \et C \neq A \ou (B \et C)$. 
\end{Th}

\begin{Rem}
L'implication n'est pas associative: $A \imp (B \imp C) \neq (A \imp
B) \imp C$. Donc les parenthèses sont obligatoires. 
Il en est de même pour $\eqv$, et a fortiori quand ces deux opérateurs
sont mélangés dans une même proposition. 
\end{Rem}

% AG: On convient en général d'associer à droite quand il n'y a 
% pas de parenthèses.

% \begin{Exoc}
%  Quelles sont les façons de placer des parenthèses dans $\non P \ou Q
%  \et \non R$ afin d'obtenir l'expression correcte d'une formule
%  propositionnelle ? Déterminer la table de vérité de chacune des
%  formules obtenues. 



% Réponses: 

% 1) $\non P \ou (Q \et \non R)$; 
% 2) $(\non P \ou Q )
% \et \non R$; 
% 3) $(\non (P \ou Q)) \et \non R$; 
% 4) $\non (P \ou
% (Q \et \non R))$; 
% 5) $\non ((P \ou Q) \et \non R)$. 

% Tables de vérité:

% $$
% \begin{array}{|c|c|c||c|c|c|c|c|}
% \hline
% P & Q & R & 1 & 2 & 3 & 4 & 5 \\
% \hline
% V & V & V & F & F & F & F & V \\
% V & V & F & V & V & F & F & F \\
% V & F & V & F & F & F & F & V \\
% V & F & F & F & F & F & F & F \\
% F & V & V & V & F & F & V & V \\
% F & v & F & V & V & F & F & F \\
% F & F & V & V & F & F & V & V \\
% F & F & F & V & V & V & V & V \\
% \hline
% \end{array}
% $$

% \end{Exoc}



%\subsubsection{Exercices}



\begin{Exoc}
Construire les tables de vérité des formules propositionnelles suivantes:
\begin{enumerate}
\item $ \non P \et Q$
\item $\non P \imp P \ou Q$
\item $\non ( \non P \et \non Q)$
\item $P \et Q \imp \non Q$
\item $(P \imp Q) \ou (Q \imp P)$
\item $(P \imp \non Q ) \ou (Q \imp \non P)$
\item $(P \ou \non Q ) \et (\non P \ou Q)$
\item $P \imp (\non P \imp P)$
\end{enumerate}


Réponse:

$$\begin{array}{|c|c||c|c|c|c|c|c|c|c|}
\hline
P & Q & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\
\hline
V & V & F & V & V & F & V & F & V & V \\
V & F & F & V & V & V & V & V & F & V \\
F & V & V & V & V & V & V & V & F & V \\
F & F & F & F & F &  V & V & V & V & V \\
\hline
\end{array}
$$
\end{Exoc}

\begin{Exo}
 Faire de même avec
\begin{enumerate}
 \item $(P \ou Q) \ou (\non R)$
\item $P \ou (\non (Q \et R))$
\item $(\non P) \imp ((\non Q) \ou R)$
\item $(P \ou R) \imp (R \ou (\non P))$
\item $(P \imp (\non Q)) \ou (Q \imp R)$
\item $(P \ou (\non Q)) \imp ((\non P) \ou R)$
\item $(P \imp (\non R)) \ou (Q \et (\non R))$
\item $(P \imp Q) \imp ((Q \imp R) \imp (P \imp R))$
\end{enumerate}




% Réponse:

% $$\begin{array}{|c|c|c||c|c|c|c|c|c|c|c|}
% \hline
% P & Q & R & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\
% \hline
% V & V & V & V & V & V & V & V & V & V & V \\
% V & V & F & V & V & V & F & F & F & V & V \\
% V & F & V & V & V & V & V & V & V & F & V \\
% V & F & F & V & V & V & F & V & F & V & V \\
% F & V & V & V & F & V & V & V & V & V & V \\
% F & V & F & V & V & F & V & V & V & V & V \\
% F & F & V & F & V & V & V & V & V & V & V \\
% F & F & F & V & V & V & V & V & V & V & V \\
% \hline
% \end{array}
% $$
\end{Exo}

% \paragraph{Exercices sans correction}


% \begin{Exo}[Les animaux de la maison]
% Formalisez, en logique des propositions:
% \begin{enumerate}
% \item Les seuls animaux de cette maison sont des chats.
% \item Tout animal qui aime contempler la lune est apte à devenir un animal familier.
% \item Quand je déteste un animal, je l'évite soigneusement.
% \item Aucun animal n'est carnivore, à moins qu'il n'aille rôder dehors la nuit.
% \item Aucun chat ne manque jamais de tuer les souris.
% \item Aucun animal ne s'attache jamais à moi, sauf ceux qui sont dans cette
% maison.
% \item Les panthères ne sont pas aptes à devenir des animaux familiers.
% \item Aucun animal non carnivore ne tue de souris.
% \item Je déteste les animaux qui ne s'attachent pas à moi.
% \item Les animaux qui vont rôder dehors la nuit aiment toujours contempler la lune.
% \end{enumerate}
% \end{Exo}



% \begin{Exo}[Les exercices de Logique]
% Faire de même avec
% \begin{enumerate}
% \item Quand un étudiant résout un exercice de logique sans soupirer, vous pouvez être sûr qu'il le comprend.

% \item Ces exercices de logique ne se présentent pas sous la forme habituelle.

% \item Aucun exercice de logique facile ne donne mal à la tête.

% \item Les étudiants ne comprennent pas les exercices de logique qui ne se présentent pas sous la forme habituelle.

% \item Les étudiants ne soupirent jamais devant un exercice de logique, à moins qu'il ne leur donne mal à la tête.

% \end{enumerate}
% \end{Exo}



% \begin{Exo}[Mes idées sur les chaussons aux pommes]
% Toujours pareil avec
% \begin{enumerate}

% \item Toute idée de moi qui ne peut s'exprimer sous forme de syllogisme est vraiment ridicule.

% \item Aucune de mes idées sur les chaussons aux pommes ne mérite d'être notée par écrit.

% \item Aucune idée de moi que je ne parviens pas à vérifier ne peut être exprimée sous forme de syllogisme.

% \item Je n'ai jamais d'idée vraiment ridicule sans la soumettre sur le champ à mon avocat.

% \item Mes rêves ont tous trait aux chaussons aux pommes.

% \item Je ne soumets aucune de mes idées à mon avocat si elle ne mérite pas d'être notée par écrit.

% \end{enumerate}
% \end{Exo}


% AG: J'aurais besoin de ne pas faire apparaitre cet exercice.
% Je peux metre une option en place dans ce but.

% \begin{Exo}[Les matières enseignées à l'IUT]
% Formalisez, en logique des propositions:

% \begin{enumerate}

% \item Aucune matière n'est primordiale, sauf l'ACSI.

% \item Toute matière enseignée par des professeurs dynamiques est susceptible de plaire aux étudiants.

% \item Je ne travaille pas les matières que je n'aime pas.

% \item Les seules matières intéressantes sont les matières informatiques.

% \item Aucune matière informatique n'évite l'abstraction.

% \item Aucune matière ne me réussit, excepté les matières intéressantes.

% \item Les mathématiques ne sont pas susceptibles de plaire aux étudiants.

% \item Aucune matière non primordiale ne tombe dans l'abstraction.

% \item Je n'aime pas les matières qui ne me réussissent pas.

% \item L'ACSI est enseignée par des professeurs dynamiques.
% \end{enumerate}
% \end{Exo}



\section{Sémantique du calcul propositionnel} 

Dans ce qui suit, on donne un sens aux symboles représentant les
connecteurs logiques en fonction de la valeur de vérité des
propositions de base (ainsi $\non$ signifie non). 

\subsection{Fonctions de vérité}

Soit $F$ une formule propositionnelle, dans l'expression de laquelle
interviennent les variables propositionnelles 
$P_1$, $P_2$, $P_3$, \ldots, $P_n$. 
\`A chacune de ces variables propositionnelles, on associe une
variable booléenne 
$p_1$, $p_2$, $p_3$, \ldots, $p_n$,
qui représente la valeur de vérité qu'elle peut prendre (0 ou 1). 

% AG: Devrait etre précédé d'une présentation de l'algebre de Boole
% Certaines tables de vérité deviennent ``tables de Pythagore'' de . 
% et +.
% JFC: dans notre approche, l'algèbre de Boole est faite au S1 donc
% avant. Il y a un chapitre à ce sujet que tu peux prendre aussi.
\begin{Def}[Fonction de vérité de $F$]
La fonction de vérité de $F$ est la fonction booléenne
$\mathcal{F}_F$ des $n$ variables booléennes concernées, obtenue de la manière
suivante: 

\begin{enumerate}

\item Si $F$ est une variable propositionnelle $P$, alors $\mathcal{F}_F=p$. 

\item Si $F$ est de la forme $\non G$, o\`u $G$ est une formule
  propositionnelle, alors $\mathcal{F}_F=\overline{\mathcal{F}_G}$. 

\item Si $F$ est de la forme $G\ou H$, o\`u $G$ et $H$ sont des formules
  propositionnelles, alors  $\mathcal{F}_F=\mathcal{F}_G+\mathcal{F}_H$.  

\item Si $F$ est de la forme $G\et H$, o\`u $G$ et $H$ sont des formules
  propositionnelles, alors $\mathcal{F}_F=\mathcal{F}_G\cdot \mathcal{F}_H$.  

\item Si $F$ est de la forme $G\imp H$, o\`u $G$ et $H$ sont des
  formules propositionnelles, alors $\mathcal{F}_F=\overline{\mathcal{F}_G}+\mathcal{F}_H$.  

\item \label{item:eqv} Si F est de la forme $G\eqv H$, o\`u $G$ et $H$ sont des formules
  propositionnelles, alors 
 $\mathcal{F}_F=\overline{\mathcal{F}_G}\cdot\overline{\mathcal{F}_H}+\mathcal{F}_G\cdot\mathcal{F}_H$.

\end{enumerate}
\end{Def}

\begin{Rem}
Soit  $F = P \imp Q$ et  $G = \non Q \imp \non P$ qui dépendent de 
deux variables propositionnelles $P$ et $Q$. 
On construit ainsi deux fonctions $\mathcal{F}_F$ et  $\mathcal{F}_G$
qui dépendront des deux variables booléennes $p$ et $q$.

D'une part, on a $\mathcal{F}_F(p,q) = \overline{p}+q$.

D'autre part 
$
\mathcal{F}_G (p,q)= 
\overline{\mathcal{F}_{\non Q}} + \mathcal{F}_{\non P}=
\overline{\overline{q}} + \overline{p} = 
\mathcal{F}_F(p,q)$.

On remarque que les deux fonctions de vérités 
$\mathcal{F}_F(p,q)$ et $\mathcal{F}_G(p,q)$  sont identiques. 
On en déduit que $P \imp Q$ et $\neg Q \imp \neg P$ sont logiquement
équivalentes.

Au passage, $\neg Q \imp \neg P$ est appelée \emph{implication contraposée} de
l'implication  $P \imp Q$. 

\end{Rem}

% \begin{Exo}
% Démontrer la règle~\ref{item:eqv}. de la définition précédente à
% partir des règles énoncées avant.
% \end{Exo}





\begin{Ex}
Soit $F=A\ou\non B\eqv(B\imp C)$. On a alors:

\hfil$\mathcal{F}_F(a,b,c)=\overline{a+\overline b}\cdot
\overline{\overline b+c}+(a+\overline b)\cdot(\overline
b+c)=\overline a\cdot b\cdot b\cdot\overline c+\overline b+a\cdot
c=\overline b+\overline a\cdot\overline c+a\cdot 
c$.\hfil
\end{Ex}

% AG: Faux pour imp et eqv qui ne sont pas (utiles) dans l'algèbre
% et que l'interpretation ramene a ET, OU, NON. A modifier.
\begin{Rem}
Il est clair que les \og tables de vérité\fg{}  des connecteurs
logiques sont les mêmes que les tables des opérations booléennes sur
$\{\faux,\vrai\}$ 

\begin{itemize}
\item de la négation booléenne (pour la négation logique),
\item de la somme booléenne (pour la disjonction logique),
\item du produit booléen (pour la conjonction logique),
%\item de la fonction booléenne de deux variables appelée \og
%  implication\fg{}  (pour l'implication logique) 
%\item de la fonction booléenne de deux variables appelée \og
%  équivalence\fg{}  (pour l'équivalence logique). 
\end{itemize}

Ainsi, la détermination de la valeur de vérité d'une proposition composée se ramène à un simple calcul en algèbre de Boole sur la fonction de vérité de la formule propositionnelle associée.
\end{Rem}



\subsection{Formules propositionnelles particulières}
On verra dans cette section deux formules particulières:
les tautologies et les antilogies.

\subsubsection{Tautologies}
% AG: fonction referentielle ? Parler seulement de la fonction qui
% vaut toujours 1
\begin{Def}[Tautologie]
Toute formule propositionnelle dont la fonction de vérité est la
fonction référentielle est appelée \emph{tautologie}
\index{tautologie}. 
\end{Def}


Ainsi, une tautologie est une formule propositionnelle dont la fonction
de vérité est indépendante des valeurs de vérité associées à ses
variables. 
Autrement dit, quelle que soit la valeur de vérité des propositions
par lesquelles on remplacerait les variables propositionnelles, la
proposition obtenue serait vraie. 

\begin{Notation}
La notation utilisée pour marquer une tautologie F est $\tauto F$ (se
lit: \og F est une tautologie\fg{}). 
\end{Notation}

\begin{Ex}
Soit $F=A \imp A$. Comme 
$\mathcal{F}_F(a)=\overline a+a=1$, on a $\tauto F$.
%Par exemple: \og Si un étudiant est sérieux, alors il est sérieux\fg{}.
\end{Ex}

\begin{Ex}
 $F = (A \imp C ) \imp ((B \imp C) \imp (A \ou B \imp C))$.

% AG: J'aimerais un passage à la ligne avant chaque egal,
% forme generale de tous les raisonnements par egalités. 
% JFC: OK
 $\begin{array}{ll}
   \mathcal{F}_F(a,b,c) & = \\ 
 \overline{\mathcal{F}_{A \imp C}} + 
 \overline{\mathcal{F}_{B \imp C}} + 
 \mathcal{F}_{A \ou B \imp C} & = \\ 
 \overline{\overline{a}+c} + 
 \overline{\overline{b}+c} + 
 \overline{a+b}+c & = \\ 
 a \overline{c} + b \overline{c} + \overline{a}  \overline{b} + c & = \\ 
 a + b + \overline{a} \overline{b} + c & = 1 + c = 1
\end{array}
$

\end{Ex}


Il ne faudrait pas croire, au vu de ces exemples simples, que les
tautologies se ramènent toutes à des trivialités totalement
inintéressantes et indignes d'être énoncées. 
Ainsi, dans une théorie mathématique, tous les théorèmes sont des
tautologies; la reconnaissance de cette propriété n'est cependant pas
toujours complètement évidente\ldots 


\begin{Exoc}
Les formules propositionnelles suivantes sont-elles des tautologies ?

\begin{enumerate}
\item \label{item:taut:1} $(P \et Q) \imp P$
\item \label{item:taut:2} $(P \ou Q) \imp (P \et Q)$
\item \label{item:taut:3} $(P \et Q) \imp (P \ou Q)$
\item \label{item:taut:4} $P \imp (P \ou Q)$
\item \label{item:taut:5} $P \imp ((\non P ) \imp P)$
\item \label{item:taut:6} $P \imp (P \imp Q)$
\item \label{item:taut:7} $P \imp (P \imp P)$
\item \label{item:taut:8} $(P \imp Q) \imp ((Q \imp R) \imp (P \imp
  R))$ 
\end{enumerate}

Réponses: 
\ref{item:taut:1}., 
\ref{item:taut:3}., 
\ref{item:taut:4}.,
\ref{item:taut:5}., 
\ref{item:taut:7}. et 
\ref{item:taut:8}. sont des tautologies.

\end{Exoc}

% AG: Indiquer la méthode de ``preuve'' ou dire ``Montrer''
\begin{Exo}
Prouver les tautologies suivantes
\begin{enumerate}
\item $\tauto A\imp(B\imp A)$
\item $\tauto (A\imp B)\imp((A\imp(B\imp C))\imp(A\imp C))$
\item $\tauto A\imp(B\imp A\et B)$
\item $ \tauto A\et B\imp A\qquad\qquad\qquad \tauto A\et B\imp B $
\item $\tauto A\imp A\ou B$
\item $ \tauto B\imp A\ou B $
\item $\tauto (A\imp C)\imp((B\imp C)\imp(A\ou B\imp C))$
\item $\tauto (A\imp B)\imp((A\imp\non B)\imp\non A) $
\item $\tauto \non\non A\imp A $
%\item $\tauto (A\imp B)\imp((B\imp A)\imp(A\eqv B)) $
%\item $ \tauto (A\eqv B)\imp(A\imp B)\quad \tauto (A\eqv B)\imp (B\imp A)$
\end{enumerate}
\end{Exo}


\subsubsection{Antilogies}

\begin{Def}[Antilogie]
Toute formule propositionnelle dont la fonction de vérité est la
fonction nulle est appelée \emph{antilogie} \index{antilogie}. 
\end{Def}

La proposition obtenue en remplaçant les variables par des
propositions ne peut alors jamais être vraie. 

\begin{Ex}
Soit $F=A\et \non A$. 
$\mathcal{F}_F(a)=a\cdot\overline a=0$. Donc $F$ est bien une antilogie.
\end{Ex}

% \begin{Rem}
% Le caractère d'antilogie d'une formule propositionnelle n'est pas
% toujours aussi évident. 
% \end{Rem}


\begin{Exo}
Calculer les fonctions de vérité des formules propositionnelles suivantes, et
dire s'il s'agit éventuellement de tautologies ou d'antilogies:

\begin{enumerate}

\item $(A\imp B)\et(A\ou B)\imp B$
\item $(A\imp C)\et(B\imp D)\et(A\ou B)\imp C\ou D$
\item $\non(A\et B)\ou\non A\ou\non B\imp C$
\item $(A\imp C)\ou(B\imp D)\imp(A\ou B\imp C\ou D)$
\item $(A\imp C)\et(B\imp D)\imp(A\et B\imp C\et D)$
\item $(A\et B)\ou(\non A\et\non C)\imp(B\imp C)$
%\item $(\non(B\et C)\et\non\non(C\et A)\imp\non(B\et C)\et(C\et A))\imp
%(\non(A\ou\non C)\eqv(A\imp B))$
\item $(\non A\ou B)\et(C\imp(A\eqv B))$
\item $A\et\non A\imp(B\ou C\imp(C\imp\non A))$
\item $((A\imp B)\imp A)\imp A$
\item $(A\imp C)\et(B\imp D)\et(\non C\ou\non D)\imp\non A\ou\non B$
\item $A\et(A\ou B)\eqv A$
\item $(\non A\ou B\imp(A\imp\non A\ou B))\eqv(\non A\ou B\imp(A\imp
(A\imp B)))$
\item $(A\imp B)\et(A\ou C)\imp B\ou C$
\item $(A\imp B)\et(A\ou C)\imp(A\imp C)$

\end{enumerate}
\end{Exo}





\subsection{Conséquences logiques}

Soit ${\cal F} = \{F_1, \ldots, F_n \}$ un ensemble de formules
propositionnelles . 

\begin{Def}[Conséquence logique]
On dit que la formule propositionnelle $A$ est une \emph{conséquence
  logique}\index{conséquence logique} des formules propositionnelles
$F_1, \ldots, F_n$  lorsque, chaque fois que les
fonctions de vérité $\mathcal{F}_{F_1}$, \ldots, $\mathcal{F}_{F_n}$
prennent simultanément la valeur \og vrai\fg{}
(ou 1), il en est de même pour $\mathcal{F}_A$. 
\end{Def}

\begin{Notation}
On note ce résultat: $\{F_1, \ldots, F_n\} \tauto A$ (se lit: $A$ est
conséquence logique de $\{F_1, \ldots, F_n\}$). 
\end{Notation}





\begin{Ex}
On reconsidère l'ensemble des deux formules propositionnelles $$\{P, P
\imp Q\}$$ et on va montrer autrement que $Q$ est conséquence logique
de ces deux formules. 
Autrement dit, on va remontrer que: \{$P$, $P \imp Q$\}$\tauto Q$.

\begin{itemize}
\item $\mathcal{F}_P=p$: prend la valeur 1 lorsque $p$ prend la valeur
  1. 
\item $\mathcal{F}_{P\imp Q}=\overline p+q$ : prend la valeur 1 lorsque
  $p=0$ (quelle que soit la valeur de $q$) et lorsque $p=1$ et $q=1$. 
\item $\mathcal{F}_P$ et $\mathcal{F}_{P\imp Q}$ prennent simultanément la
  valeur 1 uniquement lorsque $p=1$ et $q=1$; dans ce cas,
  $\mathcal{F}_Q=q=1$ aussi. Donc $Q$ est conséquence logique de $\{P, P
  \imp Q\}$. 
\end{itemize}
\end{Ex}



% \begin{Ex}
% $\{ P \imp Q, P \} \tauto Q$. En effet:
% $$\begin{array}{|c|c|c|}
%    \hline
% P & Q & P \imp Q \\
% \hline
% F & F & V \\
% \hline
% F & V & V \\
% \hline
% V & F & F \\
% \hline
% V & V & V \\
% \hline
%   \end{array}
% $$
% \noindent Il n'y a qu'un seul cas dans lequel $P \imp Q$ et $P$ sont
% simultanément vrais. Dans ce cas, $Q$ est vrai. 
% \end{Ex}



\begin{Exo}
Dans chacun des cas suivants, déterminer si le  premier ensemble de  formules
a pour conséquence logique la deuxième formule:

$$\begin{array}{c  r  l}
1 & \{P \et Q\} & P\\
2 & \{(P \et Q) \ou R\} & P\ \et (Q \ou R) \\
3 & \{(P \et Q) \imp R \} & (P \imp R) \et (Q \imp R) \\
4 & \{P \imp (Q \ou R)\} & (P \imp Q) \ou (P \imp R) \\
5 & \{A \imp (P \ou Q), \neg S \lor A \} & (\neg P \lor S) \imp Q \\
5 & \{A \imp (B \et C), \neg C \lor D \lor R, R \imp \neg B \} & 
(A \land D) \imp \neg R \\
\end{array}
$$
\end{Exo}






\begin{Exo}
Dans chacun des cas suivants, que peut-on dire d'une formule propositionnelle:
\begin{enumerate}
\item \label{item:cons:1} qui a pour conséquence logique une antilogie,
\item  \label{item:cons:2}  qui a pour conséquence logique  une tautologie,
\item  \label{item:cons:3}  qui est conséquence logique d'une antilogie,
\item  \label{item:cons:4}  qui est conséquence logique  d'une tautologie.
\end{enumerate}
\end{Exo}

% Réponses: 
% \ref{item:cons:1}. c'est une antilogie, 
% \ref{item:cons:2}. rien, 
% \ref{item:cons:3}. rien et 
% \ref{item:cons:4}. c'est une tautologie.



\begin{Exo}
La formule propositionnelle $F$ étant fixée, que peut-on dire d'une
formule propositionnelle $G$ qui possède chacune des deux propriétés: 
\begin{itemize}
 \item $F \ou G$ est une tautologie,
 \item $F \et G$ est une antilogie.
\end{itemize}
\end{Exo}

%Réponse: la formule $g$ est équivalente à la négation de la formule $f$.



\subsection{Formules équivalentes} 

\begin{Def}[Formules équivalentes]
Si la formule propositionnelle $G$ est conséquence logique de la formule
propositionnelle $F$ et si $F$ est aussi conséquence logique de $G$, 
alors ces deux formules sont dites \emph{équivalentes}\index{formules
  équivalentes} (que l'on note $\approx$), soit: 
$$\{F\}\tauto G\hbox{ et }\{G\}\tauto F 
\textrm{ si et seulement si  } F \approx G.$$
\end{Def}


C'est cette notion de formules équivalentes qui autorise le remplacement
d'une expression par une autre (équivalente, bien sûr) dans une formule
propositionnelle. 

\begin{Rem}
 On est autorisé à remplacer $\non \non A$ par $A$, puisque ces formules 
 sont équivalentes. 
\end{Rem}


\begin{Exo}
Dans chacun des cas suivants, dire si les deux formules
propositionnelles inscrites sur la même ligne sont équivalentes: 
$$
\begin{array}{c  r  l}
1 & \non (\non P) & P\\
2 & P \et (P \imp Q) & P \et Q \\
3 & P \imp Q & (\non P ) \ou (P \et Q)\\
4 & P \imp Q & (\non P ) \imp (\non Q) \\
5 & P \ou Q & \non ((\non P) \et (\non Q))\\
6 & P \et Q & \non ((\non P) \ou (\non Q))\\
7 & \non P & (\non ( P \ou Q)) \ou ((\non P) \et Q) \\
8 & P \imp (Q \imp R) & (P \imp Q) \imp R\\
9 & P \imp (Q \et R) & (P \imp Q) \et (P \imp R) \\
10 & P \imp (Q \ou R) & (P \imp Q) \ou (P \imp R)\\
11 & (P \imp Q) \et (Q \imp P) & (P \et Q) \imp (P \et Q) \\
12 & (P \et Q) \ou (Q \et R) \ou (R \et P) & (P \ou Q) \et (Q \ou R)
\et (P \ou R)\\ 
\end{array}
$$


%Réponse: oui pour 1, 2, 3, 5, 6, 7, 9, 10, 12.
\end{Exo}

\begin{Exoc} 
Soit $F$ une formule propositionnelle dépendant de trois variables $P,
Q, R$ qui possède deux propriétés: 
\begin{itemize}
\item $F(P,Q,R)$ est vraie si $P, Q, R$ sont toutes les trois vraies, 
\item la valeur de vérité de $F(P,Q,R)$ change quand celle d'une
  seule des trois variables change. 
\end{itemize}
Construire la table de vérité de $F$, et déterminer une formule
possible pour $F$. 

Réponse: table de vérité

$$\begin{array}{|c c c|c|}
\hline
P & Q & R & F \\
\hline
V & V & V & V \\
V & V & F & F \\
V & F & V & F \\
F & V & V & F \\
V & F & F & V \\
F & F & V & V \\
F & V & F & V \\
F & F & F & F \\
\hline
  \end{array}
$$
\noindent Formule: 
$
(P \et Q \et R) \ou 
(P \et \non Q \et \non R) \ou 
(\non P \et \non Q \et R) \ou 
(\non P \et Q \et \non R)$ 
\end{Exoc}

\begin{Exo}
Déterminer des formules propositionnelles $F, G, H$ dépendant des
variables $P,Q,R$ qui admettent les tables de vérité: 
$$\begin{array}{ccc}
\begin{array}{|ccc|c|}
\hline

P & Q & R & F \\
\hline
V & V & V & V\\
V & V & F & F \\
V & F & V & V \\
V & F & F & F \\
F & V & V & F \\
F & V & F & V \\
F & F& V & V \\
F & F & F & V\\
\hline
\end{array}
& 
\begin{array}{|ccc|c|}
\hline
P & Q & R & G \\
\hline
V & V & V & F\\
V & V & F & V \\
V & F & V & V \\
V & F & F & F \\
F & V & V & F \\
F & V & F & V \\
F & F& V & V \\
F & F & F & F\\
\hline
\end{array}
&
\begin{array}{|ccc|c|}
\hline
P & Q & R & H \\
\hline
V & V & V & V\\
V & V & F & V \\
V & F & V & V \\
V & F & F & F \\
F & V & V & F \\
F & V & F & V \\
F & F& V & V \\
F & F & F & V\\
\hline
\end{array}
  \end{array}
$$
\end{Exo}

% Réponses:

% \noindent $ f = (P \et Q \et R) \ou (P \et (\non Q) \et R) \ou
% ((\non P) \et Q \et (\non R)) \ou ((\non P) \et (\non Q) \et R) \ou
% ((\non P) \et (\non Q) \et (\non R))$ 

% \noindent $ g = (P \et Q \et (\non R)) \ou (P \et (\non Q) \et R)
% \ou ((\non P) \et Q \et (\non R)) \ou ((\non P) \et (\non Q) \et R)$ 

% \noindent $ h = (P \et Q \et R) \ou (P \et Q \et (\non R)) \ou (p
% \et (\non Q) \et R) \ou ((\non P) \et Q \et (\non R)) \ou ((\non P)
% \et (\non Q) \et R) \ou ((\non P) \et (\non Q) \et (\non R))$ 

\subsection{Simplification du calcul des fonctions de vérité}

\subsubsection{Théorème de substitution}

\begin{Th}[Théorème de substitution]
 \index{théorème!de substitution} 
Soit $F$ une formule propositionnelle dans laquelle interviennent les
variables propositionnelles $P_1\,$, $P_2\,$, $P_3\,$,\ldots, $P_n$. 
Supposons que l'on remplace ces variables par des formules
propositionnelles $G_1\,$, $G_2\,$, $G_3\,$,\ldots, $G_n$; la nouvelle
formule propositionnelle obtenue est notée $F^*$. 


Dans ces conditions: si $\tauto F$, alors $\tauto F^*$. 
\end{Th}



\begin{Proof}
$F$ étant une tautologie, sa fonction de vérité ne dépend pas des
valeurs de vérité des variables booléennes, qui peuvent donc
être remplacées par n'importe quelle fonction booléenne. 
\end{Proof}

\begin{Rem}
Attention, la réciproque n'est pas vraie: 
soit $F=A\imp B$ et $F^*=(P\et \non P) \imp Q$, 
obtenue à partir de $F$ en remplaçant $A$ par
$P\et \non P$ et $B$ par $Q$.
Comme $\mathcal{F}_{F^*}(p,q)=\overline{p\cdot\overline
  p}+q=\overline 0+q=1+q=1$, alors $F^{*}$ est une tautologie.
Cependant de $\mathcal{F}_{F}(a,b)$, on ne peut pas dire que $F$ est une tautologie.
\end{Rem}


\begin{Ex}
La formule propositionnelle 
$$F^*=((P\imp Q\et\non R)\ou (\non S\eqv T))\imp ((P\imp
Q\et\non R)\ou(\non S\eqv T)),$$
est compliquée puisqu'elle contient 5 variables propositionnelle.
il y a donc 32 lignes
à calculer pour obtenir les valeurs de la fonction de vérité. 
Cependant, il suffit de remarquer que $F^*$ est obtenue à partir de
$F=A \imp A$, qui est une tautologie; donc $F^*$ en est une aussi. 
\end{Ex}



Ce résultat peut évidemment être appliqué aussi à des parties de
formules propositionnelles, pour accélérer le calcul de leurs fonctions
de vérité: 
si une partie d'une formule propositionnelle constitue à elle seule une
tautologie, la partie correspondante de la fonction de vérité peut
être avantageusement remplacée par 1. 

\subsubsection{Théorème de la validité}

\begin{Th}[Théorème de la validité]
Soit $\{G_1,G_2,\ldots,G_n\}$ un ensemble de formules propositionnelles
et $H$ une formule propositionnelle; alors: 
$$
\{G_1,G_2,\ldots,G_{n-1}\}\tauto G_n\imp H
\textrm{ si et seulement si }
\{G_1,G_2,\ldots,G_n\}\tauto H 
$$
\end{Th}



\begin{Proof}
\textbf{Si.}
\noindent Supposons $\{G_1,G_2,\ldots,G_n\}\tauto H$, c'est à dire, chaque
fois que les formules de $\{G_1,G_2,\ldots,G_n\}$ sont vraies, $H$ l'est
aussi). 
Supposons que les formules de $\{G_1,G_2,\ldots,G_{n-1}\}$ soient vraies:
\begin{itemize}
\item Alors, si $G_n$ est vraie, toutes les formules de
$\{G_1,G_2,\ldots,G_n\}$ sont vraies, et donc, d'après {l'hypothèse},
$H$ est vraie. 
Dans ce cas (voir table de vérité de l'implication logique), $G_n\imp
H$ est vraie. 
\item Et si $G_n$ n'est pas vraie, alors $G_n\imp H$ est vraie.
\end{itemize}
\textbf{Seulement si.}
\noindent Supposons
$\{G_1,G_2,\ldots,G_{n-1}\}\tauto  G_n\imp H$. 
En d'autres termes, chaque fois que les
formules de $\{G_1,G_2,\ldots,G_{n-1}\}$ sont vraies, $G_n\imp H$ est
vraie. 
Regardons si $H$ est une conséquence logique de
$\{G_1,G_2,\ldots,G_{n}\}$ en distinguant  selon que $G_n$ est vraie
ou pas.
\begin{itemize}
\item soit lorsque $G_n$ n'est pas vraie, indépendamment de la valeur
  de vérité de $H$ sur laquelle on ne peut alors rien dire, mais peu
  importe, puisque, dans ce cas, les formules de
  $\{G_1,G_2,\ldots,G_n\}$ ne sont pas 
toutes vraies, puisque $G_n$ n'est pas vraie.
\item soit lorsque $G_n$ est vraie, et, dans ce cas, on sait que $H$
  est obligatoirement vraie aussi. Ceci se produit chaque fois que
  toutes les formules de $\{G_1,G_2,\ldots,G_n\}$ sont vraies, et, dans
  ce cas, $H$ l'est aussi. 
Donc $\{G_1,G_2,\ldots,G_n\}\tauto H$.
\end{itemize}
\end{Proof}
% AG: Raisonnement typique de deduction naturelle, serait 
% mieux placé dans ce contexte.

\begin{Ex}[Exemple d'application]
 Soit à montrer que:
$$\tauto (A\imp(B\imp C))\imp((A\imp B)\imp(A\imp C)).$$

On pourrait bien entendu déterminer la fonction de vérité de cette formule.
Mais, d'après le théorème précédent, la démonstration du résultat
demandé est équivalente à celle de: 
$$\{A\imp(B\imp C)\}\tauto(A\imp B)\imp(A\imp C).$$

Une nouvelle application de ce même théorème nous montre que la
démonstration demandée est encore équivalente à celle de: 
$$\{A\imp(B\imp C), (A\imp B)\}\tauto (A\imp C).$$
Et enfin à celle de:
$$\{A\imp(B\imp C),(A\imp B),A\}\tauto C.$$

Or les fonctions de vérité de $\{A\imp(B\imp C),(A\imp B),A\}$
sont 
$$
\left\{
\begin{array}{l}
\overline{a} + \overline{b} + c \\
\overline{a} + b \\
a
\end{array}
\right.
\textrm{ qui valent sim. 1 quand }
\left\{
\begin{array}{l}
a = 1 \\
b = 1 \\
c = 1
\end{array}
\right.
$$
Ainsi $C$ est vraie et on a terminé la démonstration.
% Or, dire que les formules de $\{A\imp(B\imp C),(A\imp B),A\}$ sont
% simultanément vraies revient à dire que $A$ est vraie. 
% Dans ce cas, $(A\imp B)$ ne peut être aussi vraie que si $B$ est vraie
% et, de même, $A\imp(B\imp C)$ ne peut être vraie que si $(B\imp C)$
% est vraie. $B$ étant vraie, $(B\imp C)$ ne peut être vraie que si $C$
% est vraie.  

% Donc, chaque fois que  $\{A\imp(B\imp C),(A\imp B),A\}$ sont
% simultanément vraies, $C$ est nécessairement vraie. Donc 
% $$\{A\imp(B\imp C),(A\imp B), A\}\tauto C,$$
% ce qui, d'après le théorème énoncé ci-dessus, est équivalent
% à $$\tauto (A\imp(B\imp C))\imp((A\imp B)\imp(A\imp C)).$$ 


\end{Ex}






\begin{Exo}
Trois dirigeants d'une Société (Pierre P., Marc M. et Alain A.) sont
prévenus de malversations financières ; au cours de l'enquête, l'agent
du fisc enregistre leurs déclarations: 
\begin{itemize}
\item Pierre P.: ``Marc est coupable et Alain est innocent''.
\item Marc M.: ``Si Pierre est coupable, Alain l'est aussi''.
\item Alain A.: ``Je suis innocent, mais l'un au moins des deux
  autres est coupable''. 
\end{itemize}

\begin{enumerate}
\item Ces trois témoignages sont-ils compatibles? 
\item En supposant qu'ils sont
tous les trois innocents, lequel a menti? 
\item En supposant que chacun dit
la vérité, qui est innocent et qui est coupable? 
\item En supposant que les
innocents disent la vérité et que les coupables mentent, qui est
innocent et qui est coupable? 
\end{enumerate}
\end{Exo}



\begin{Exo}
Simplifier le règlement suivant:

\begin{itemize}
\item Les membres de la Direction Financière doivent être choisis
  parmi ceux de la Direction Générale. 
\item Nul ne peut être à la fois membre de la Direction Générale et de
  la Direction Technique s'il n'est membre de la Direction
  Financière. 
\item Aucun membre de la Direction Technique ne peut être membre de la
  Direction Financière. 
\end{itemize}
\end{Exo}


\begin{Exo}
Un inspecteur des services de santé visite un hôpital psychiatrique
o\`u des phénomènes étranges lui ont été signalés. 

Dans cet hôpital, il n'y a que des malades et des médecins, mais les
uns comme les autres peuvent être sains d'esprit ou totalement
fous. L'inspecteur doit faire sortir de 
l'hôpital les personnes qui n'ont rien à y faire, c'est à dire les
malades sains d'esprit et les médecins totalement fous (quitte à les
réintégrer ultérieurement en tant que malades\ldots). Il part du principe
que les personnes saines d'esprit ne disent que des choses vraies,
alors que les personnes folles ne disent que des choses fausses. 

Dans une salle, il rencontre deux personnes (appelons-les A et B pour
préserver leur anonymat). A affirme que B est fou et B affirme que A
est médecin. 
\begin{enumerate}
\item Après une intense réflexion, l'inspecteur fait sortir l'un des
  deux de l'hôpital. Lequel (et pourquoi ?) 
\item Peut-il dire quelque chose au sujet de l'autre ? 
\end{enumerate}
\end{Exo}


\begin{Exo}
Le prince de Beaudiscours est dans un cruel embarras. Le voici au pied
du manoir o\`u la méchante fée Antinomie maintient prisonnière la
douce princesse Vérité. Deux portes y donnent accès. L'une d'elles
conduit aux appartements de la princesse, mais l'autre s'ouvre sur
l'antre d'un dragon furieux. Le prince sait seulement que l'une de ces
deux portes s'ouvre lorsqu'on énonce une proposition vraie, et l'autre
si on énonce une proposition fausse. 

Comment peut-il délivrer la princesse?
\end{Exo}



\begin{Exo}
Que dire des raisonnements suivants?
\begin{enumerate}
\item Si Jean n'a pas rencontré Pierre l'autre nuit, 
c'est que Pierre est le meurtrier ou que Jean est un menteur.
Si Pierre n'est pas le meurtrier, alors Jean n'a pas rencontré Pierre 
l'autre nuit et le crime a eu lieu après minuit.
Si le crime a eu lieu après minuit, alors Pierre est 
le meurtrier ou Jean n'est pas un menteur.
Donc Pierre est le meurtrier
\item Manger de la vache folle est dangereux pour la santé; 
  manger du poulet aux hormones aussi, d'ailleurs. 
  Quand on ne mange pas de la vache folle, on mange du poulet aux hormones.
  Notre santé est donc en danger.
\item Si je n'étudie pas, j'ai des remords. 
  Mais si je ne vis pas à fond ma jeunesse, j'ai aussi des remords. 
  Or je n'ai pas de remords. 
  C'est donc que j'étudie tout en vivant à fond ma jeunesse.
\item Quand Marie est là, c'est qu'elle accompagne Paul ou Jean. 
  Paul ne vient jamais en même temps que son cousin Serge.
  Si Jean et Serge viennent tous les deux, leur s{\oe}ur Louise les accompagne.
  Si Louise se pointe, Raoul ne reste pas.
  Hier, Raoul et Serge étaient présents jusqu'au bout. Peut-on en conclure que 
  Marie n'était pas présente?  
\end{enumerate}
\end{Exo}
\subsection{Conclusion}

Le calcul sur les fonctions de vérité est simple et 
nécessite un minimum de réflexion: il est très facile à
programmer. 


Mais, pour une formule propositionnelle qui comporte 10 variables
propositionnelles (ce qui n'est pas beaucoup pour les problèmes que
l'on cherche à programmer!), la table des valeurs de la fonction de
vérité comporte $2^{10}=1024$ lignes. 
Celui qui opère à la main a déjà démissionné.
L'ordinateur démissionne un peu plus loin, certes, mais il finit aussi
par avouer son incapacité. 
Une méthode alternative guidée par le but à démontrer est 
présentée au chapitre suivant.


% \begin{itemize}
% \item Sur les machines modernes, il n'est plus impossible d'envisager
%   d'écrire et d'exécuter une \og boucle vide\fg{} qui porte sur toutes
%   les valeurs entières représentables sur 32 bits, donc de 0 à
%   $2^{32}-1$, le temps d'exécution est récemment devenu raisonnable. 
% \item Il ne faut cependant pas exiger que ce temps demeure raisonnable
%   dès qu'il s'agit d'exécuter un algorithme un peu compliqué. Et 32
%   variables constituent un nombre 
% ridiculement petit pour un système expert, dans lequel les expressions
% offrent souvent une complexité qui n'a aucune commune mesure avec ce
% que l'on peut imaginer de plus compliqué\ldots 
% \end{itemize}





% Les \og raccourcis\fg{}  qui viennent d'être étudiés et qui permettent
% d'accélérer, voire de supprimer totalement, le calcul d'une fonction
% de vérité, sont plus utiles lorsque l'on opère \og à la main\fg{}  que
% pour la programmation d'algorithmes de logique. 





% Il faut donc garder en réserve la méthode des fonctions de vérité:
% celle-ci peut être très utile dans certains cas, essentiellement
% lorsque le problème peut être résolu \og à la main\fg{}, mais il faut
% aussi trouver une autre méthode pour songer à aborder des problèmes
% plus complexes. 

% Cette méthode, qui supprime toute référence aux valeurs de vérité,

\gsaut
\centerline{\x{Fin du Chapitre}}