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
+Ce discours est articulé en phrases et c'est l'étude de ces \og
énoncés\fg{} que se propose de faire la logique.
-D'une manière générale, le calcul propositionnel ne se préoccupe que
+Attention, 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
\subsection{Tables de vérité des connecteurs logiques}
-\centerline{\begin{tabular}{|c|c|c|}
+\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|}
+ \end{tabular}
+~
+\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
+V & V & V \\ \hline \end{tabular}
+~
+{ \begin{tabular}{|c|c|} \hline
$P$ & $\non P$ \\ \hline
F & V \\ \hline
V & F \\ \hline
\end{tabular}}
-
-\centerline{\begin{tabular}{|c|c|c|}
+~
+{\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|}
+~
+{\begin{tabular}{|c|c|c|}
\hline
$P$ & $Q$ & $P\eqv Q$ \\ \hline
F & F & V \\ \hline
\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{}
+% \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.
+% 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{Rem}
+% Même remarque que pour l'implication logique: l'équivalence logique
+% de deux propositions fausses est une proposition vraie.
+% \end{Rem}
-\begin{Exoc}
+\begin{Exo}
En notant $M$ et $C$ les affirmations suivantes:
\begin{itemize}
\item $M$ = \og Jean est fort en Maths\fg{},
\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{}
+% \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.
+% % 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:
+% 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}
+% \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{Exo}
-\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}
+% \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.
+% 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}
+% \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}
+% \end{Exo}
% Réponses:
% \ref{ex2:1}. $M \et A \et (\non C)$;
% \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}
+% \end{Exo}
\begin{Exo}
\item Définir les négations de $ P\land Q$, $ P\lor Q$ et $P \Rightarrow Q$.
\end{enumerate}
+
+\begin{Th}
+On a les règles syntaxiques suivantes de simplification de négations:
+\begin{itemize}
+\item $\neg (A \lor B) = (\neg A) \land (\neg B)$;
+\item $\neg (A \land B) = (\neg A) \lor (\neg B)$;
+\item $\neg \neg A = A $;
+\item $\neg (A \Rightarrow B) = A \land (\neg B)$.
+\end{itemize}
+On remarque que la troisième règle se déduit des trois autres:
+$\neg (A \Rightarrow B) = \neg (\neg A \lor B) = (\neg \neg A) \land (\neg B)$.
+\end{Th}
+
+
+
\end{Exo}
\begin{Exo}
\'Enoncer la négation des affirmations suivantes en évitant d'employer l'expression: \og il est faux que\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{}
+% \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}
% \end{enumerate}
\end{Exo}
-% \begin{Exoc}
+% \begin{Exo}
% 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
% \ref{it:3:9} V;
% %\ref{it:3:10} F;
% \ref{it:3:11} V.
-% \end{Exoc}
+% \end{Exo}
% \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{}.
\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$ 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 $A$ à moins que $B$\fg{}
\item \og Ni $A$, ni $B$\fg{}
\end{enumerate}
\end{Exo}
\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 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.
+%\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}
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}
+% \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.
+% \begin{Exo}
+% 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:
+% 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)$.
+% 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é:
+% 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}
-$$
+% $$
+% \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}
+% \end{Exo}
-\begin{Exoc}
+\begin{Exo}
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}
+% \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:
+% 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{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{Exo}
-\begin{Exo}
- Faire de même avec
+% \begin{Exo}
+% Faire de même avec
\begin{enumerate}
\item $(P \ou Q) \ou (\non R)$
\item $P \ou (\non (Q \et R))$
\begin{enumerate}
-\item Si $F$ est de la forme $P$, o\`u $P$ est une variable
- propositionnelle, alors $\Phi_F(p)=p$.
+\item Si c'est une variable $P$, propositionnelle, alors $\Phi_P(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 c'est une négation d'une formule
+ propositionnelle $G$, alors $\Phi_{\non G}=\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 c'est une disjonction entre deux formules
+ propositionnelle $G$ ou $H$, alors $\Phi_{G \lor H}=\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 c'est une conjonction entre deux formules
+ propositionnelle $G$ et $H$, alors $\Phi_{G \land H}=\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 Si elle est de la forme $G\imp H$, o\`u $G$ et $H$ sont des
+ formules propositionnelles, alors
+ $\Phi_{G\imp H}=\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$.
+\item \label{item:eqv} Si c'est une équivalence entre
+les formules propostionnelles $G$ et $H$, alors
+ $\Phi_{G \Leftrightarrow H}=\overline{\Phi_G}\cdot\overline{\Phi_H}+\Phi_G\cdot\Phi_H$.
\end{enumerate}
\end{Def}
\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
+Soit $F=(A\ou\non B) \land (B\imp C)$. Cette formule dépend des trois variables
+$A$, $B$ et $C$.On a alors:
+$$
+\begin{array}{l}
+\Phi_F(a,b,c)= \Phi_{(A\ou\non B) \land (B\imp C)}(a,b,c) = \\
+\Phi_{A\ou\non B}(a,b) \cdot \Phi_{B\imp C}(b,c) =
+(\Phi_{A}(a) + \Phi_{\non B}(b)) \cdot (\overline{\Phi_{B}(b)}+ \Phi_{C}(c))=\\
+(a+ \overline{\Phi_{B}(b)}) \cdot (\overline{b}+ c)=
+(a+ \overline{b}) \cdot (\overline{b}+ c)= \overline{b} + ac
+\end{array}
+$$
\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{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}
+% \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}
+%
+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}
toujours complètement évidente\ldots
-% \begin{Exoc}
+% \begin{Exo}
% Les formules propositionnelles suivantes sont-elles des tautologies ?
% \begin{enumerate}
% \ref{item:taut:7}. et
% \ref{item:taut:8}. sont des tautologies.
-% \end{Exoc}
+% \end{Exo}
% AG: Indiquer la méthode de ``preuve'' ou dire ``Montrer''
\begin{Exo}
% 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 \} &
+1 & \{P \imp (Q \ou R)\} & (P \imp Q) \ou (P \imp R) \\
+2 & \{A \imp (P \ou Q), \neg S \lor A \} & (\neg P \lor S) \imp Q \\
+3 & \{A \imp (B \et C), \neg C \lor D \lor R, R \imp \neg B \} &
(A \land D) \imp \neg R \\
\end{array}
$$
%Réponse: oui pour 1, 2, 3, 5, 6, 7, 9, 10, 12.
\end{Exo}
-\begin{Exoc}
+\begin{Exo}
Soit $F$ une formule propositionnelle dépendant de trois variables $P,
Q, R$ qui possède deux propriétés:
\begin{itemize}
(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}
+\end{Exo}
-\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
+% \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}
+% 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:
\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
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}
+% \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.
+% 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.
+% 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.
+% Cette méthode, qui supprime toute référence aux valeurs de vérité,
+% fait l'objet du
+% chapitre suivant.
-\gsaut
+% \gsaut
\centerline{\x{Fin du Chapitre}}
