\documentclass{article} \usepackage{amsmath} \usepackage[ansinew]{inputenc} \usepackage[francais]{babel} \usepackage[dvips]{graphicx} \textwidth=15truecm \textheight=22.8truecm \hoffset=-12mm \voffset=-9mm \baselineskip=12pt \newdimen\finwidth \finwidth=\textwidth \advance \finwidth by -3cm \def\finducours#1{ \vskip.5cm \hbox{{\vrule height 2pt width \finwidth} Fin du cours $n^0$#1} \vskip.5cm\par} \title{BASES DU RAISONNEMENT} \author{P. Pansu} \newtheorem{theo}{Th{\'e}or{\`e}me} \newtheorem{lemme}{Lemme} \newtheorem{prop}[lemme]{Proposition} \newtheorem{cor}[lemme]{Corollaire} \newtheorem{defi}[lemme]{D{\'e}finition} \newtheorem{rem}[lemme]{Remarque} \newtheorem{exo}[lemme]{Exercice} \newtheorem{exemple}[lemme]{Exemple} \newtheorem{rappel}[lemme]{Rappel} \long\def\sol#1#2#3{\par\medskip\noindent {\bf Solution de l'exercice \ref{#1}.}\hskip1em{\em #2.}\par{#3}\par} \def\R{{\bf R}} \def\C{{\bf C}} \def\Q{{\bf Q}} \def\Z{{\bf Z}} \def\N{{\bf N}} \def\inv#1{\frac{1}{#1}} \def\ri{\Rightarrow} \def\lr{\Leftrightarrow} \def\et{~\textrm{et}~} \def\ou{~\textrm{ou}~} \def\non{\textrm{non}\,} \def\cR{\,\mathcal{R}\,} \def\P{\mathcal{P}} \def\q{\mathcal{Q}} \def\titre#1{\par\vskip1cm\centerline{#1}\par\vskip1cm} \def\qed{\vbox{\hrule height 5pt width 5pt}} \def\d{\displaystyle} \def\inv#1{\frac{1}{#1}} \def\solution{\par\medskip{\bf Solution.}\hskip5pt} \def\preuve{\par\medskip{\bf Preuve.}\hskip5pt} \begin{document} \maketitle \section*{Rappel du programme officiel} Logique, différents types de raisonnement.\par Ensembles, éléments.\par Fonctions et applications.\par Produit, puissances.\par Union, intersection, somme disjointe.\par Cardinalités.\par Relations.\par Ensembles ordonnés, diagramme de Hasse.\par \section{Vocabulaire de la logique} \subsection{Assertions} Les assertions du monde mathématique sont celles qui peuvent se traduire par une formule où interviennent les ensembles de nombres (entiers, réels,...), des constantes (0, 1,...), des variables ($x$, $a$,...), les opérations ($+$, $\times$,..), les relations ($=$, $\leq$,...), et les symboles $\forall$, $\exists$, $\in$, $\ri$, $\lr$, et qui respectent la syntaxe. \begin{exemple} \label{exassinc} Les formules $(1>0)$, $(1=0)$, $(x>1)$ sont des assertions. \end{exemple} Les assertions $(1>0)$ et $(1=0)$ sont complètes, elles ont une signification indépendante de tout contexte : la première est vraie, la seconde fausse. L'assertion $(x>1)$ n'est pas complète, car elle contient une variable libre $x$, et on ne peut pas répondre à la question \emph{l'assertion $(x>1)$ est elle vraie ?}, car la réponse dépend de $x$. \begin{defi} \label{defasscompl} Une assertion est \emph{complète} si toutes les variables sont quantifiées par un \emph{quantificateur} $\forall$ ou $\exists$. \end{defi} \begin{itemize} \item $(\forall x\in E)$ se lit \emph{quel que soit $x$ appartenant à $E$}, ou \emph{pour tout $x$ dans $E$}. \item $(\exists x\in E)$ se lit \emph{il existe un élément de $E$ tel que}. \end{itemize} \begin{exemple} \label{exasscomplok} $((\forall x\in\R)(x>1))$ est une assertion complète. Elle est évidemment fausse, mais c'est son droit. \end{exemple} \subsection{Traduction} Le jeu mathématique consiste à établir si des assertions complètes sont vraies ou fausses. Il faut savoir convertir en formules mathématiques des énoncés du langage courant et inversement. \begin{exo} \label{exass} Ecrire sous forme de formule mathématique l'assertion suivante. {\em Pour tout rationnel strictement positif, il existe un entier strictement plus grand que lui.} \end{exo} \sol{exass}{Propriété archimédienne des rationnels}{ \begin{eqnarray*} (\forall x\in\Q)\quad((x> 0)\Rightarrow((\exists n\in \N)(n>x))). \end{eqnarray*} } \begin{exo} \label{exass2} Traduire en langage courant l'assertion exprimée par la formule \begin{eqnarray*} &&(\forall x\in\N)\quad(\forall x'\in\N)\\ &&((x\not=0)\et(x'\not=0))\Rightarrow(\exists y\in\N)(\exists q\in\N)(\exists q'\in\N)\quad((y=qx)\et(y=q'x')\et(y\not=0))). \end{eqnarray*} \end{exo} \sol{exass2}{Multiple commun}{ Deux entiers strictement positifs possèdent un multiple commun non nul.} \subsection{Dictionnaire} Ci-dessous, une liste de termes mathématiques avec leur description en langage courant. \medskip \textbf{Négation}. C'est dire le contraire. La négation de \emph{j'ai 18 ans} est \emph{je n'ai pas 18 ans}. On \emph{note} $\non\P$ la négation de l'assertion $\P$. \medskip \textbf{Et}. Si $\P$ et $\q$ sont des assertions, $(\P\et\q)$ est l'assertion qui est vraie lorsque $\P$ et $\q$ sont toutes les deux vraies. \emph{J'ai 18 ans et je suis étudiant à l'IFIPS}. \medskip \textbf{Ou}. Si $\P$ et $\q$ sont des assertions, $(\P\et\q)$ est l'assertion qui est vraie sauf si $\P$ et $\q$ sont toutes les deux fausses. C'est donc un \emph{ou} au sens large, non exclusif. C'est le \emph{ou} de \emph{mon père ou ma mère viendra me chercher à la gare} et non celui de \emph{je dois choisir entre prendre le RER ou la voiture}. \medskip \textbf{Implication}. Si $\P$ et $\q$ sont des assertions, l'assertion $\P\ri\q$ exprime l'idée que si $\P$ est vraie, alors $\q$ doit être vraie aussi, sans qu'il y ait pour autant une relation de cause à effet. Par exemple, \emph{j'ai mon permis de conduire} implique \emph{j'ai plus de 18 ans}, même si ce n'est pas d'obtenir le permis de conduire qui m'a fait vieillir. \medskip \textbf{Equivalence}. Si $\P$ et $\q$ sont des assertions, l'assertion $\P\lr\q$ exprime l'idée que $\P$ et $\q$ sont vraies simultanément. Autrement dit, \begin{eqnarray*} (\P\lr\q)\quad\textrm{signifie}\quad((\P\ri\q)\et(\q\ri\P)). \end{eqnarray*} Par conséquent, démontrer une équivalence, c'est démontrer deux implications. Sauf dans des situations très simples d'application immédiate de règles, on a en général intérêt à les démontrer séparément. \medskip \textbf{Réciproque}. Soient $\P$ et $\q$ sont des assertions. La \emph{réciproque} de l'implication $(\P\ri\q)$, c'est l'assertion $(\q\ri\P)$. Elles sont vraies toutes les deux si et seulement si $\P\lr\q$ est vraie. \begin{exo} \label{recip} Quelle est la réciproque de l'assertion \emph{Tout professeur a été étudiant} ? \end{exo} \sol{recip}{Réciproque}{ Toute personne ayant été étudiant est professeur. } \medskip \textbf{Contraposée}. Soient $\P$ et $\q$ sont des assertions. On appelle l'assertion $\non\q\ri\non\P$ la \emph{contraposée} de $\P\ri\q$. \begin{prop} \label{contrap} Soient $\P$ et $\q$ des assertions. L'assertion $(\non\q)\ri(\non\P)$ est synonyme de $\P\ri\q$. \end{prop} \preuve Donnée en exercice plus loin.\qed \begin{rem} \label{symb} Les symboles $\forall$, $\exists$, $\ri$, $\lr$ ne sont pas des abbréviations à insérer dans un texte. Ils n'ont leur place que dans des formules mathématiques. \end{rem} \finducours1 \subsection{Ambiguïtés du langage courant} Ci-dessous, une liste de termes du langage courant et leur traduction (parfois problématique) en formule mathématique. \medskip \textbf{Si}. La phrase \emph{les étudiants viennent voir le prof s'ils n'ont rien compris} peut avoir plusieurs sens suivant le contexte. Pour le prof surmené qui manque de temps après un cours, ça peut vouloir dire : \emph{ne viennent me voir aujourd'hui que les étudiants qui n'ont rien compris}. Pour un prof qui travaille dans des conditions normales, ça devrait vouloir dire : \emph{tout étudiant qui ne comprend pas devrait venir me voir}. La version speedée se traduit par \begin{eqnarray*} \textrm{vient me voir aujourd'hui}\quad\ri\quad\textrm{ n'a rien compris}. \end{eqnarray*} La version cool par \begin{eqnarray*} \textrm{n'a rien compris}\quad\ri\quad\textrm{vient me voir aujourd'hui}, \end{eqnarray*} c'est-à-dire, la réciproque. On nage en pleine confusion. En mathématiques, pour éviter toute confusion, \emph{si $\P$, alors $\q$} est synonyme de $(\P\ri\q)$. \emph{$\P$ si et seulement si $\q$} est synonyme de $(\P\lr\q)$. \medskip \textbf{Pour}. A la question \emph{pour quelles valeurs de $a$ a-t-on $a^2 \frac{1}{y}))$ ? -- Tu sait prendre l'inverse d'une inégalité entre nombres positifs ? -- Ben oui. -- Y faut donc que tu montres d'abord que $x^2 +x+1$ est toujours positif." En réalité, il \emph{suffit} que $x^2 +x+1>0$ pour que l'implication à démontrer soit vraie. En effet, \begin{eqnarray*} (\forall x\in\R)(\forall y\in\R)\quad((x^2 +x+1>0)\ri((x^2 +x+1\frac{1}{y}))). \end{eqnarray*} Si $\P\ri\q$, il \emph{suffit} que $\P$ soit vraie pour que $\q$ soit vraie, et il \emph{faut} que $\q$ soit vraie pour que $\P$ soit vraie. On dit parfois que $\P$ \emph{est une condition suffisante pour} $\q$, et que $\q$ est une \emph{condition nécessaire} pour $\P$. Par exemple, \emph{avoir au moins 18 ans} est une condition nécessaire pour \emph{avoir le permis de conduire}, mais ce n'est pas suffisant. \begin{exo} \label{excncs} Dans $\Q$, \emph{être positif ou nul} est-il \begin{itemize} \item une condition nécessaire, \item une condition suffisante, \item une condition nécessaire et suffisante \end{itemize} pour \emph{être un carré} ? Et si on remplace $\Q$ par $\R$ ? par $\C$ ? \end{exo} \sol{excncs}{Condition nécessaire ou suffisante}{ Sur $\Q$, c'est une condition nécessaire (car un carré est toujours positif ou nul) mais non suffisante (car 2 n'est pas le carré d'un rationnel, bien qu'il soit positif ou nul). Sur $\C$ c'est une condition suffisante, puisque tout nombre complexe est le carré d'un nombre complexe, mais ce n'est pas necessaire (ça n'a même pas de sens). Sur $\R$, c'est une condition nécessaire et suffisante. } \subsection{Opérations sur les assertions} On rassemble une série de recettes qui rendent les exercices en partie mécaniques. \subsubsection{Règles relatives à la négation} \begin{itemize} \item $\non(x0)\et(\forall n\in \N)(x\leq n)). \end{eqnarray*} } \begin{exo} \label{contrapo} Soient $\P$ et $\q$ des assertions. Les assertions $\P\ri\q$ et $(\non\q)\ri(\non\P)$ sont équivalentes. \end{exo} \sol{contrap}{Contraposition}{ \begin{eqnarray*} ((\non\q)\ri(\non\P))\lr(\q\ou(\non\P))\lr((\non\P)\ou\q)\lr(\P\ri\q). \end{eqnarray*}} \section{Différents types de raisonnement} Un théorème n'est rien d'autre qu'une assertion complète, dont on affirme qu'elle est vraie, en s'appuyant sur une démonstration. Une démonstration de l'assertion $\P$, c'est la mise en oeuvre d'une succession de définitions, de règles ou de théorèmes connus permettant de déduire que $\P$ est vraie. On décrit différentes façons typiques d'organiser une démonstration. \subsection{Raisonnement direct} \begin{exo} \label{exdem} Pour tout rationnel strictement positif, il existe un entier strictement plus grand que lui. \end{exo} On aura besoin de l'écriture d'un rationnel sous forme de fraction \emph{irréductible}. \begin{rappel} \label{Q} Un nombre \emph{rationnel} est le quotient de deux entiers. L'ensemble des nombres rationnels est noté $\Q$. Tout rationnel $r\in\Q$ s'écrit de manière unique $\d r=\frac{p}{q}$ avec $q>0$ et $p$ et $q$ n'ont pas de diviseur commun (autre que $\pm 1$). \end{rappel} \sol{exdem}{Toujours plus haut}{ Soit $x\in\Q$. Il existe des entiers $p$ et $q$ avec $q>0$ tels que $x=\frac{p}{q}$ (propriété de $\Q$). Comme $q$ est entier strictement positif, $q\geq 1$ (propriété de $\N$). Alors $p=xq\geq x$ (règle). En particulier, $p>0$ (règle). D'où $2p>p$ (règle). Il vient $2p>x$ (règle). Comme $2p\geq 0$ (règle), on remarque que $2p\in\N$ (définition de $\Z$). On conclut que le double du numérateur $n=2p$ convient.} \subsection{Disjonction de cas} \begin{exo} \label{disj} En se ramenant au cas des rationnels positifs, montrer que pour tout rationnel, il existe un entier plus grand que lui. \end{exo} \sol{disj}{Propriété archimédienne de $\Q$}{ On distingue deux cas. Ou bien $x\leq 0$. Dans ce cas, l'entier $n=1$ convient. Ou bien $x>0$. Dans ce cas, on applique l'exemple \ref{exdem}, qui fournit l'entier cherché.\qed } \subsection{Raisonnement par contraposée} Pour démontrer une assertion du type $\P\ri\q$, il suffit de démontrer sa contraposée $\non\q\ri\non\P$. \begin{exo} \label{exa=>b} Montrer que si $x$ et $y$ sont des réels distincts de 1, et si $x\not=y$, alors $\frac{1}{x-1}\not=\frac{1}{y-1}$. \end{exo} \sol{exa=>b}{Contraposition}{ La contraposée de l'énoncé est \emph{si $x$ et $y$ sont des réels distincts de 1, et si $\frac{1}{x-1}=\frac{1}{y-1}$, alors $x=y$}. Et c'est vrai, car \begin{eqnarray*} \frac{1}{x-1}=\frac{1}{y-1}\ri x-1= y-1 \ri x=y. \end{eqnarray*} } \subsection{Raisonnement par l'absurde} \begin{exo} \label{sqrt2} Montrer que $\sqrt{2}$ n'est pas rationnel. \end{exo} \sol{sqrt2}{$\sqrt{2}$ est irrationnel}{ Par l'absurde. Supposons $\sqrt{2}$ rationnel. Alors il existe des entiers $p$ et $q$ sans diviseurs communs tels que $\sqrt{2}=\frac{p}{q}$. On l'écrit $p^2 =2q^2$. On remarque que si $p$ est impair, $p^2$ est aussi impair. Donc forcément $p$ est pair, $p=2p'$. Alors $q^2 =2p'^2$. Pour la même raison, $q$ est pair, $q=2q'$. Cela signifie que $p$ et $q$ admettent 2 comme diviseur commun, contradiction. On conclut que $\sqrt{2}$ est irrationnel. } \subsection{Utiliser un contre exemple} Pour démontrer une assertion du type $(\exists x\in E)\P(x)$, il suffit de donner un exemple d'un $x$ qui convient. En passant à la négation, pour démontrer qu'une assertion du type $(\forall x\in E)\P(x)$ est fausse, il suffit de donner un exemple d'un $x$ qui ne convient pas. On appelle cela un \emph{contre-exemple} à la propriété $\P$. \begin{exo} \label{exexemple} L'assertion \emph{tout entier positif est somme de trois carrés} est-elle vraie ? fausse ? \end{exo} \sol{exexemple}{Sommes de trois carrés}{ Sachant qu'il n'y a que deux carrés non nuls inférieurs ou égaux à 7, à savoir 1 et 4, le nombre 7 n'est pas somme de trois carrés. Cela prouve que l'assertion est fausse. } \finducours2 \subsection{Raisonnement par récurrence} \begin{exo} \label{exorecurr} Pour $n\in\N$, on note $\P(n)$ l'assertion $n! \geq 2^{n}$. Montrer que $\P(n)$ est vraie à partir d'un certain rang. Lequel ? \end{exo} \sol{exorecurr}{Récurrence}{ Supposons que $\mathcal{P}(n)$ est vraie. Alors \begin{eqnarray*} (n+1)!&=&(n+1)n!\\ &\geq&(n+1)2^{n}\\ &\geq&2\,2^{n}\\ &=&2^{n+1}, \end{eqnarray*} pourvu que $n\geq 1$. Autrement dit, \begin{eqnarray*} (\forall n\in\N)\quad((n\geq 1)\ri(\P(n)\ri\P(n+1))). \end{eqnarray*} Est-ce que cela suffit à montrer que $\mathcal{P}(n)$ est vraie pour tout $n\geq 1$ ? $\mathcal{P}(0)$ s'écrit $1=0!\geq 2^{0}=1$, c'est vrai. Malheureusement, on n'a pas su démontrer l'assertion $(\P(0)\ri\P(1))$. D'ailleurs, elle est fausse. En effet, $\mathcal{P}(1)$ s'écrit $1=1!\geq 2^{1}=2$, c'est faux. $\mathcal{P}(2)$ s'écrit $2=2!\geq 2^{2}=4$, c'est faux. $\mathcal{P}(3)$ s'écrit $6=3!\geq 2^{3}=8$, c'est faux. $\mathcal{P}(4)$ s'écrit $24=4!\geq 2^{4}=16$, c'est vrai. Ouf! On conclut que $\mathcal{P}(n)$ est vraie pour tout $n\geq 4$. } \section{A retenir/à savoir faire} A retenir \begin{itemize} \item On s'efforce de n'écrire que des assertions \emph{complètes}. \item Changer la nature ou l'ordre des quantificateurs change le sens de l'assertion. \item En mathématiques, le mot \emph{si} a un sens précis. \item Attention à la traduction mathématique du mot \emph{pour}. \item Les termes \emph{il faut} et \emph{il suffit} ne sont pas interchangeables. \item \emph{Si et seulement si} recouvre deux énoncés, et requiert deux démonstrations, une implication et sa réciproque. \end{itemize} \medskip A savoir faire \begin{itemize} \item Déchiffrer une assertion mathématique présentant des quantificateurs. \item Traduire une phrase du langage courant en assertion mathématique. \item Ecrire la négation, la contraposée et la réciproque d'une assertion, sans les confondre. \item Rédiger un raisonnement par l'absurde, un raisonnement par récurrence. \end{itemize} \end{document}