ajout relbin13

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

\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}}