From 86be95127ca8ca59052d395b45375110b70cbf17 Mon Sep 17 00:00:00 2001 From: couchot Date: Thu, 17 Oct 2013 09:10:28 +0200 Subject: [PATCH] ajout de proposition13 --- logique/Propositions13.tex | 1599 ++++++++++++++++++++++++++++++++++++ 1 file changed, 1599 insertions(+) create mode 100644 logique/Propositions13.tex diff --git a/logique/Propositions13.tex b/logique/Propositions13.tex new file mode 100644 index 0000000..c6cf86d --- /dev/null +++ b/logique/Propositions13.tex @@ -0,0 +1,1599 @@ + + + + + +\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}} + + + + + + + + -- 2.39.5