--- /dev/null
+
+
+
+
+
+\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}.
+
+
+\section{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}
+ Ainsi, \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}
+
+
+
+
+
+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.
+
+
+
+
+
+
+\section{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{}.
+
+
+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.
+
+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{}}
+$$
+
+
+
+D'une manière générale, le calcul propositionnel ne se préoccupe que
+des valeurs de vérité, 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{}).
+
+
+\subsection{Tables de vérité des connecteurs logiques}
+
+
+\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}}
+
+\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}}
+
+\centerline{
+\begin{tabular}{|c|c|} \hline
+$P$ & $\non P$ \\ \hline
+F & V \\ \hline
+V & F \\ \hline
+\end{tabular}}
+
+\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}}
+
+\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}
+\begin{itemize}
+\item 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.
+\item 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$,
+\end{itemize}
+\end{Rem}
+
+
+
+
+\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.
+
+
+
+\begin{Rem}
+Même remarque que pour l'implication logique: l'équivalence logique
+de deux propositions fausses est une proposition vraie.
+\end{Rem}
+
+
+\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}
+$ $
+\begin{enumerate}
+\item Dans un même tableau, construire les tables de vérité de
+$ P\land Q$, $ \neg (P \land Q)$, $ \neg P \land \neg Q$, $ P \land \neg Q$
+$ P\lor Q$, $ \neg (P \lor Q) $ , $ \neg P \lor \neg Q$,
+$P \Rightarrow Q$ et $ \neg( P\Rightarrow Q)$
+\item Définir les négations de $ P\land Q$, $ P\lor Q$ et $P \Rightarrow Q$.
+\end{enumerate}
+
+\end{Exo}
+\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}
+
+
+
+Comme le calcul propositionnel ne s'occupe que des valeurs de vérité,
+il est possible, dans une expression logique, de remplacer chaque
+proposition donnée par un symbole (en général, une lettre de
+l'alphabet majuscule), ou \emph{variable
+ propositionnelle}\index{variable propositionnelle} et
+d'é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: ok, je te laisse le corriger
+\begin{itemize}
+
+\item toute variable propositionnelle est une formule propositionnelle;
+
+\item si $F$ et $G$ sont des formules propositionnelles, alors $\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}
+Ce ne sont plus des propositions, en ce sens qu'elles n'ont en général
+pas de valeur de vérité déterminée.
+Cette dernière est une fonction des valeurs de vérité des variables
+propositionnelles qui interviennent dans
+l'expression de la formule propositionnelle considérée.
+\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}
+Les variables propositionnelles $N$ et $T$ serviront, dans cet
+exercice, à 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 (si, pour l'une ou l'autre d'entre elles, la
+traduction vous paraît impossible, dites-le et expliquez pourquoi):
+
+\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 $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 (généralement la même lettre de l'alphabet, mais en
+minuscules), qui représente la valeur de vérité qu'elle peut prendre
+(faux ou vrai, F ou V, 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
+$\Phi_F$ des $n$ variables booléennes concernées, obtenue de la manière
+suivante:
+
+\begin{enumerate}
+
+\item Si $F$ est de la forme $P$, o\`u $P$ est une variable
+ propositionnelle, alors $\Phi_F(p)=p$.
+
+\item Si $F$ est de la forme $\non G$, o\`u $G$ est une formule
+ propositionnelle, alors $\Phi_F=\overline{\Phi_G}$.
+
+\item Si $F$ est de la forme $G\ou H$, o\`u $G$ et $H$ sont des formules
+ propositionnelles, alors $\Phi_F=\Phi_G+\Phi_H$.
+
+\item Si $F$ est de la forme $G\et H$, o\`u $G$ et $H$ sont des formules
+ propositionnelles, alors $\Phi_F=\Phi_G\cdot \Phi_H$.
+
+\item Si $F$ est de la forme $G\imp H$, o\`u $G$ et $H$ sont des
+ formules propositionnelles, alors $\Phi_F=\overline{\Phi_G}+\Phi_H$.
+
+\item \label{item:eqv} Si F est de la forme $G\eqv H$, o\`u $G$ et $H$ sont des formules
+ propositionnelles, alors
+ $\Phi_F=\overline{\Phi_G}\cdot\overline{\Phi_H}+\Phi_G\cdot\Phi_H$.
+
+\end{enumerate}
+\end{Def}
+
+% \begin{Rem}
+% Soit $F = P \imp Q$, $G = \non Q \imp \non P$.
+% On a $\Phi_F(p,q) = \overline{p}+q$ et
+% $\Phi_G (p,q)= \overline{\Phi_{\non Q}} + \Phi_{\non P} =
+% \overline{\overline{q}} + \overline{p} = \Phi_F(p,q)$.
+% On remarque que les deux fonctions de vérités $\Phi_F(p,q)$ et $\Phi_G(p,q)$
+% sont identiques.
+% On en déduit que $P \imp Q$ et $\neg Q \imp \neg P$ sont logiquement
+% équivalentes.
+
+% $\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$\Phi_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
+$\Phi_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}
+ \Phi_F(a,b,c) & = \\
+ \overline{\Phi_{A \imp C}}(a,c) +
+ \overline{\Phi_{B \imp C}}(b,c) +
+ \Phi_{A \ou B \imp C}(a,b,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}
+Les formules propositionnelles suivantes sont-elles des tautologies ?
+
+\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 \label{item:taut:5} $P \imp ((\non P ) \imp P)$
+\item $\tauto \non\non A\imp A $
+\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))$
+\item $\tauto (A\imp C)\imp((B\imp C)\imp(A\ou B\imp C))$
+\item \label{item:taut:6} $P \imp (P \imp Q)$
+\item $\tauto (A\imp B)\imp((A\imp\non B)\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$.
+$\Phi_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é $\Phi_{F_1}$, \ldots, $\Phi_{F_n}$
+prennent simultanément la valeur \og vrai\fg{}
+(ou 1), il en est de même pour la fonction de vérité de la forme $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 $\Phi_P(p)=p$: prend la valeur 1 lorsque $p$ prend la valeur
+ 1.
+\item $\Phi_{P\imp Q}(p,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 $\Phi_P(p)$ et $\Phi_{P\imp Q}(p,q)$ prennent simultanément la
+ valeur 1 uniquement lorsque $p=1$ et $q=1$; dans ce cas,
+ $\Phi_Q(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}
+
+Attention, la réciproque n'est pas vraie\ldots
+
+\begin{Ex}
+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 $\Phi_{F^*}(p,q)=\overline{p\cdot\overline
+ p}+q=\overline 0+q=1+q=1$, alors $F^{*}$ est une tautologie.
+Cependant de $\Phi_{F}(a,b)$, on ne peut pas dire que $F$ est une tautologie.
+\end{Ex}
+
+
+Exemple d'utilisation de ce résultat:
+
+\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é paraît tout-à-fait
+satisfaisant et séduisant, lorsqu'il s'agit de calculer des valeurs de
+vérité ou d'examiner des conséquences logiques.
+Il est vrai qu'il est simple, nécessite un minimum de réflexion (très
+important dans le cas des ordinateurs!) et qu'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é:
+\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é,
+fait l'objet du
+chapitre suivant.
+
+\gsaut
+\centerline{\x{Fin du Chapitre}}
+
+
+
+
+
+
+
+
