\( %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Mes commandes %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\multirows}[3]{\multirow{#1}{#2}{$#3$}}%pour rester en mode math \renewcommand{\arraystretch}{1.3}%pour augmenter la taille des case \newcommand{\point}[1]{\marginnote{\small\vspace*{-1em} #1}}%pour indiquer les points ou le temps \newcommand{\dpl}[1]{\displaystyle{#1}}%megamode \newcommand{\A}{\mathscr{A}} \newcommand{\LN}{\mathscr{N}} \newcommand{\LL}{\mathscr{L}} \newcommand{\K}{\mathbb{K}} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\M}{\mathcal{M}} \newcommand{\D}{\mathbb{D}} \newcommand{\E}{\mathcal{E}} \renewcommand{\P}{\mathcal{P}} \newcommand{\G}{\mathcal{G}} \newcommand{\Kk}{\mathcal{K}} \newcommand{\Cc}{\mathcal{C}} \newcommand{\Zz}{\mathcal{Z}} \newcommand{\Ss}{\mathcal{S}} \newcommand{\B}{\mathbb{B}} \newcommand{\inde}{\bot\!\!\!\bot} \newcommand{\Proba}{\mathbb{P}} \newcommand{\Esp}[1]{\dpl{\mathbb{E}\left(#1\right)}} \newcommand{\Var}[1]{\dpl{\mathbb{V}\left(#1\right)}} \newcommand{\Cov}[1]{\dpl{Cov\left(#1\right)}} \newcommand{\base}{\mathcal{B}} \newcommand{\Som}{\textbf{Som}} \newcommand{\Chain}{\textbf{Chain}} \newcommand{\Ar}{\textbf{Ar}} \newcommand{\Arc}{\textbf{Arc}} \newcommand{\Min}{\text{Min}} \newcommand{\Max}{\text{Max}} \newcommand{\Ker}{\text{Ker}} \renewcommand{\Im}{\text{Im}} \newcommand{\Sup}{\text{Sup}} \newcommand{\Inf}{\text{Inf}} \renewcommand{\det}{\texttt{det}} \newcommand{\GL}{\text{GL}} \newcommand{\crossmark}{\text{\ding{55}}} \renewcommand{\checkmark}{\text{\ding{51}}} \newcommand{\Card}{\sharp} \newcommand{\Surligne}[2]{\text{\colorbox{#1}{ #2 }}} \newcommand{\SurligneMM}[2]{\text{\colorbox{#1}{ #2 }}} \newcommand{\norm}[1]{\left\lVert#1\right\rVert} \renewcommand{\lim}[1]{\underset{#1}{lim}\,} \newcommand{\nonor}[1]{\left|#1\right|} \newcommand{\Un}{1\!\!1} \newcommand{\sepon}{\setlength{\columnseprule}{0.5pt}} \newcommand{\sepoff}{\setlength{\columnseprule}{0pt}} \newcommand{\flux}{Flux} \newcommand{\Cpp}{\texttt{C++\ }} \newcommand{\Python}{\texttt{Python\ }} %\newcommand{\comb}[2]{\begin{pmatrix} #1\\ #2\end{pmatrix}} \newcommand{\comb}[2]{C_{#1}^{#2}} \newcommand{\arrang}[2]{A_{#1}^{#2}} \newcommand{\supp}[1]{Supp\left(#1\right)} \newcommand{\BB}{\mathcal{B}} \newcommand{\arc}[1]{\overset{\rotatebox{90}{)}}{#1}} \newcommand{\modpi}{\equiv_{2\pi}} \renewcommand{\Re}{Re} \renewcommand{\Im}{Im} \renewcommand{\bar}[1]{\overline{#1}} \newcommand{\mat}{\mathcal{M}} \newcommand{\und}[1]{{\mathbf{\color{red}\underline{#1}}}} \newcommand{\rdots}{\text{\reflectbox{$\ddots$}}} \newcommand{\Compa}{Compa} \newcommand{\dint}{\dpl{\int}} \newcommand{\intEFF}[2]{\left[\!\left[#1 ; #2\right]\!\right]} \newcommand{\intEFO}[2]{\left[\!\left[#1 ; #2\right[\!\right[} \newcommand{\intEOF}[2]{\left]\!\left]#1 ; #2\right]\!\right]} \newcommand{\intEOO}[2]{\left]\!\left]#1 ; #2\right[\!\right[} \newcommand{\ou}{\vee} \newcommand{\et}{\wedge} \newcommand{\non}{\neg} \newcommand{\implique}{\Rightarrow} \newcommand{\equivalent}{\Leftrightarrow} \newcommand{\Ab}{\overline{A}} \newcommand{\Bb}{\overline{B}} \newcommand{\Cb}{\overline{C}} \newcommand{\Cl}{\texttt{Cl}} \newcommand{\ab}{\overline{a}} \newcommand{\bb}{\overline{b}} \newcommand{\cb}{\overline{c}} \newcommand{\Rel}{\mathcal{R}} \newcommand{\superepsilon}{\varepsilon\!\!\varepsilon} \newcommand{\supere}{e\!\!e} \makeatletter \newenvironment{console}{\noindent\color{white}\begin{lrbox}{\@tempboxa}\begin{minipage}{\columnwidth} \ttfamily \bfseries\vspace*{0.5cm}} {\vspace*{0.5cm}\end{minipage}\end{lrbox}\colorbox{black}{\usebox{\@tempboxa}} } \makeatother \def\ie{\textit{i.e. }} \def\cf{\textit{c.f. }} \def\vide{ { $ {\text{ }} $ } } %Commande pour les vecteurs \newcommand{\grad}{\overrightarrow{Grad}} \newcommand{\Vv}{\overrightarrow{v}} \newcommand{\Vu}{\overrightarrow{u}} \newcommand{\Vw}{\overrightarrow{w}} \newcommand{\Vup}{\overrightarrow{u'}} \newcommand{\Zero}{\overrightarrow{0}} \newcommand{\Vx}{\overrightarrow{x}} \newcommand{\Vy}{\overrightarrow{y}} \newcommand{\Vz}{\overrightarrow{z}} \newcommand{\Vt}{\overrightarrow{t}} \newcommand{\Va}{\overrightarrow{a}} \newcommand{\Vb}{\overrightarrow{b}} \newcommand{\Vc}{\overrightarrow{c}} \newcommand{\Vd}{\overrightarrow{d}} \newcommand{\Ve}[1]{\overrightarrow{e_{#1}}} \newcommand{\Vf}[1]{\overrightarrow{f_{#1}}} \newcommand{\Vn}{\overrightarrow{0}} \newcommand{\Mat}{Mat} \newcommand{\Pass}{Pass} \newcommand{\mkF}{\mathfrak{F}} \renewcommand{\sp}{Sp} \newcommand{\Co}{Co} \newcommand{\vect}[1]{\texttt{Vect}\dpl{\left( #1\right)}} \newcommand{\prodscal}[2]{\dpl{\left\langle #1\left|\vphantom{#1 #2}\right. #2\right\rangle}} \newcommand{\trans}[1]{{\vphantom{#1}}^{t}{#1}} \newcommand{\ortho}[1]{{#1}^{\bot}} \newcommand{\oplusbot}{\overset{\bot}{\oplus}} \SelectTips{cm}{12}%Change le bout des flèches dans un xymatrix \newcommand{\pourDES}[8]{ \begin{itemize} \item Pour la ligne : le premier et dernier caractère forment $#1#2$ soit $#4$ en base 10. \item Pour la colonne : les autres caractères du bloc forment $#3$ soit $#5$ en base 10. \item A l'intersection de la ligne $#4+1$ et de la colonne $#5+1$ de $S_{#8}$ se trouve l'entier $#6$ qui, codé sur $4$ bits, est \textbf{\texttt{$#7$}}. \end{itemize} } \)

Logique propositionnelle

Proposition

Suis-je sûr de douter ?

Est-ce vrai ou est-ce faux ? Si je n'en doute pas c'est que je suis certain de douter. Si j'en doute c'est que j'envisage de ne pas douter. Cette phrase n'est donc ni vraie ni fausse et vraie et fausse en même temps. Une sorte de phrase quantique ! Lorsqu'on va voir un mathématicien, plus précisément un logicien, pour lui demander de rendre des comptes sur ce phénomène, il répond calmement que cette phrase ne rentre pas dans le cadre des phrases étudiables. Lorsque l'on tombe sur ce genre de paradoxe, c'est qu'il y a un problème de cadrage. Alors cadrons un peu tout ça.

Définition

Une proposition est un énoncé dont on peut dire sans ambigüité qu'il est vrai ou qu'il est faux.

Ainsi la proposition $ p=$ "$ 2+2=4$ " est une proposition vraie. De même $ q=$ "$ 2+2=5$ " est une proposition fausse. Mais $ r=$ "Suis-je sûr de douter ?" n'est pas une proposition de sorte que la question de la valeur de vérité (vrai ou faux) ne se pose pas. Tout comme $ s=$ "$ x+1{>}0$ ". C'est parfois vrai, parfois faux. Cela dépend de $ x$ . Il y a donc ambigüité, ce n'est donc pas une proposition. Maintenant que le cadre est placé nous pouvons enrober de quelques définitions et outils.

Définition

$ \bullet$: Une tautologie est un énoncé toujours vrai. On le note $ \top$ (ou $ 1$ ou $ \mathscr{V}$ ).
$ \bullet$: Une contradiction est un énoncé toujours faux. On le note $ \bot$ (ou $ 0$ ou $ \mathscr{F}$ ).

Connecteurs logique et tables de vérité

Pour travailler avec les propositions et définir des outils de calculs, on utilise des tables de vérité. Il s'agit de table décrivant toutes les combinaisons de vérité possible d'une expression propositionnelle.

Définition

On définit le connecteur logique OU entre deux propositions $ p$ et $ q$ , noté $ p\ou q$ , la proposition définie par la table de vérité ci-contre. \[ \begin{array}{c|c||c} p&q&p\ou q\\\hline\hline 0&0&0\\\hline 0&1&1\\\hline 1&0&1\\\hline 1&1&1 \end{array} \]

Définition

On définit le connecteur logique ET entre deux propositions $ p$ et $ q$ , noté $ p\et q$ , la proposition définie par la table de vérité ci-contre. \[ \begin{array}{c|c||c} p&q&p\et q\\\hline\hline 0&0&0\\\hline 0&1&0\\\hline 1&0&0\\\hline 1&1&1 \end{array} \]

Définition

On définit le NON, la négation logique d'une proposition $ p$ , noté $ \non p$ , par la table de vérité ci-contre. \[ \begin{array}{c||c} p&\non p\\\hline\hline 0&1\\\hline 1&0 \end{array} \]

Le parenthésage est important. Dressons la table de vérité de l'expression (bien définie) suivante : \[E=[p\ou (r\et\non(q\et p))]\et (\non r)\] \[ \begin{array}{c|c|c||c|c|c|c|c|c} & & & A&B&C&D & & D\et \non r\\ p&q&r&q\et p&\non A&r\et B&p\ou C & \non r & E\\\hline\hline 0&0&0&0&1&0&0&1&0\\\hline 0&0&1&0&1&1&1&0&0\\\hline 0&1&0&0&1&0&0&1&0\\\hline 0&1&1&0&1&1&1&0&0\\\hline 1&0&0&0&1&0&1&1&1\\\hline 1&0&1&0&1&1&1&0&0\\\hline 1&1&0&1&0&0&1&1&1\\\hline 1&1&1&1&0&0&1&0&0 \end{array} \] L'expression $ E=p\ou q\et r$ n'est pas bien définie. Nous ne savons pas quel connecteur appliquer en premier ni même si cela à une incidence sur le résultat. Cette expression peut soit se comprendre comme $ E_1=p\ou(q\et r)$ ou $ E_2=(p\ou q)\et r$ . Comparons leur table de vérité : \[ \begin{array}{c|c|c||c|c|c|c} p&q&r&q\et r&E_1&p\ou q&E_2\\\hline\hline 0&0&0&0&0&0&0\\\hline 0&0&1&0&0&0&0\\\hline 0&1&0&0&0&1&0\\\hline 0&1&1&1&1&1&1\\\hline 1&0&0&0&1&1&0\\\hline 1&0&1&0&1&1&1\\\hline 1&1&0&0&1&1&0\\\hline 1&1&1&1&1&1&1 \end{array} \] Les tables de vérités de $ E_1$ et $ E_2$ sont différentes ce qui laisse à penser que ces expressions le sont aussi. Cela motive la définition suivante.

Définition

Deux propositions $ p$ et $ q$ sont égales si elles ont les mêmes tables de vérité. Dans ce cas on note $ p=q$ .

CANDIMATICA\copyright

Passer par les tables de vérité peut s'avérer fastidieux. On observe en effet qu'une expression propositionnelle concernant trois propositions fait apparaitre une table de vérité à $ 8$ lignes. On peut montrer qu'une expression impliquant $ n$ propositions donnera une table de vérité de $ 2^n$ lignes. C'est à dire que si dix propositions sont impliquées alors la table de vérité aura plus de mille lignes ! Vite, un théorème.

Théorème [CANDIMATICA]

Commutativité.: $ p\ou q = q\ou p$ et $ p\et q=q\et p$ .
Associativité.: $ p\ou(q\ou r)=(p\ou q)\ou r$ et $ p\et(q\et r)=(p\et q) et r$ .
Neutralité.: $ p\et \top=p$ et $ p\ou \bot=p$ .
Distributivité.: $ p\et(q\ou r)=(p\et q)\ou(p\et r)$ et $ p\ou(q\et r)=(p\ou q)\et (p\ou r)$ .
Idempotence.: $ p\ou p=p$ et $ p\et p=p$ .
Morgan.: $ \non(p\ou q)=\non p \et \non q$ et $ \non (p\et q)=\non p \ou \non q$ .
Absorption 1.: $ p\ou \top=\top$ et $ p\et \bot=\bot$ .
Tiers exclus.: $ p\ou \non p = \top$ .
Involution.: $ \non(\non p)=p$ .
Contradiction.: $ p\et \non p=\bot$ .
Absoption 2.: $ p\ou(p\et q)=p$ et $ p\et(p\ou q)=p$ .

Le mot Candimatica est purement mnémotechnique. Il m'a été suggéré par Mahmoud.

Démonstration

Il s'agit de comparer les tables de vérité. Nous n'allons pas le faire pour tous. Détaillons une des deux égalités de Morgan¹ et une des deux propriétés d'absorption 2. \[ \begin{array}{c|c||c|c|c|c|c} & &A& & B & C & \\ p&q&p\et q&\non A & \non p & \non q & B\ou C\\\hline\hline 0&0&0&1&1&1&1\\\hline 0&1&0&1&1&0&1\\\hline 1&0&0&1&0&1&1\\\hline 1&1&1&0&0&0&0 \end{array} \] On observe ainsi que $ \non(p\et q)=\non p \ou \non q$ . \[ \begin{array}{c|c||c|c} &&A&\\ p&q&p\et q&p\ou A\\\hline 0&1&0&0\\\hline 0&1&0&0\\\hline 1&0&0&1\\\hline 1&1&1&1 \end{array} \] On observe que $ p\ou(p\et q)=p$ Il en va de même pour les autres propriétés.

La propriété de l'associativité permet en entre autre de considérer des connections logique entre plus de deux propositions. Tant que le connecteur est le même la priorité des opérations n'est pas problématique. On se permettra alors d'écrire $ p\ou q\ou r$ sous entendu qu'il s'agit de $ (p\ou q)\ou r$ et qu'il appartient à chacun de déplacer les parenthèses à sa convenance. Il est souvent plus facile de passer par ces règles que de revenir aux calculs sur les tables de vérité. Comme l'exemple suivant l'illustre. \begin{eqnarray*} (p\et q)\et \left[(\non p\et q) \ou (\non p \et \non q)\right] &=& (p\et q)\et \left[\non p\et (q \ou \non q)\right] \text{\qquad factorisation (distributivité)}\\ &=& (p\et q)\et \left[\non p\et \top\right] \text{\qquad tiers exclus}\\ &=& (p\et q)\et\non p \text{\qquad neutralité}\\ &=& (p\et\non p) \et q \text{\qquad associativité et commutativité}\\ &=& \bot \et q \text{\qquad contradiction}\\ &=& \bot\text{\qquad absorption 1} \end{eqnarray*}

Implication

Il s'agit à présent de mesurer le raisonnement. C'est à dire la mesure que partant d'une proposition $ p$ , dont la véracité n'est pas à établir, on arrive à une proposition $ q$ . Ce que l'on cherche à mesurer est le raisonnement, la méthode utilisée. Il s'agit de l'implication.

Définition

On définit l'implication d'une proposition $ p$ vers une proposition $ q$ , notée $ p\implique q$ , par la table de vérité ci-contre. \[ \begin{array}{c|c||c} p&q&p\implique q\\\hline\hline 0&0&1\\\hline 0&1&1\\\hline 1&0&0\\\hline 1&1&1 \end{array} \]

Partant d'une proposition $ p$ vraie, par un raisonnement logique, c'est à dire sans digression et fausseté, on ne peut arriver qu'à démontrer une proposition vraie. De sorte que $ 1\implique 1$ est vrai et $ 1\implique 0$ est faux. Mais lorsque le point de départ du raisonnement est faux, on peut faire n'importe quoi et arriver à un énoncé qui peut-être vrai comme faux tout en suivant un raisonnement correct ; cela traduit que $ 0\implique 0$ et $ 0\implique 1$ sont tous deux vrais. L'implication n'est pas vraiment un nouveau connecteur logique. D'une part, il a des propriétés très différentes du OU et du ET, ne serait-ce que la commutativité ($ (p\implique q) \neq (q\implique p)$ ) mais d'autre part le théorème suivant permet de s'y ramener.

Théorème

\[(p\implique q)=\non p \ou q\]

Démonstration

\[ \begin{array}{c|c||c|c} &&A&\\ p&q&\non p & A\ou q \\\hline\hline 0&0&1&1\\\hline 0&1&1&1\\\hline 1&0&0&0\\\hline 1&1&0&1 \end{array} \] On observe que la table de $ p\implique q$ et $ \non p \ou q$ sont identiques.

Définition

$ \bullet$: La réciproque de $ p\implique q$ est $ q\implique p$ .
$ \bullet$: La contraposé de $ p\implique q$ est $ \non q \implique \non p$ .

Proposition

Une implication et sa contraposé ont la même valeur de vérité.

Démonstration

$ (\non q\implique \non p) = (\non(\non q )\ou \non p)=(q\ou\non p)=(\non p \ou q)=(p\implique q)$ par involution et commutativité.

Considérons $ p$ ="$ n^2$ est impaire" et $ q$ ="$ n$ est impaire". Tout d'abord ce ne sont pas des propositions car elles dépendent toutes les deux d'un paramètre $ n$ . Ce n'est pas loin d'être des propositions : dès que l'on donne une valeur à $ n$ on peut dire sans ambigüité leur valeur de vérité. Nous verrons très bientôt que nous pouvons nous permettre de telle considération (il s'agit de prédicat). Pour cet exemple, faisons comme s'il s'agissait de bien belle proposition. Si nous souhaitons démontrer que tout nombre dont le carré est impaire est forcément impaire, il faut logiquement montrer que $ p\implique q$ . C'est un théorème difficile de prime abord. Mais le résultat précédent nous indique qu'il suffit de montrer sa contraposé $ \non q \implique \non p$ c'est à dire que tout nombre paire a un carré paire ce qui est laissé au lecteur (et ben plus facile). Un tel raisonnement s'appelle un raisonnement par contraposé².

Proposition

Si $ (p\et\non q)=\bot$ alors $ (p\implique q)=\top$ .

Démonstration

En effet, si $ (p\et\non q)=\bot$ alors en prenant la négation logique des deux cotés de cette égalité on a $ \non(p\et\non q)=\top$ . La propriété de Morgan et l'involution donne $ \top=\non p\ou\non\non q=\non p \ou q=p\implique q$ .

Ce résultat permet de démontrer le raisonnement par l'absurde. Lorsque l'on souhaite démontrer que $ p\implique q$ alors on montre que partant de $ p$ et $ \non q$ il y a une contradiction, c'est-à-dire $ p\et \non q=\bot$ .

Equivalence

Pour finir le si et seulement si.

Définition

On définit l'équivalence entre deux propositions $ p$ et $ q$ , notée $ p\equivalent q$ , par la table de vérité ci-contre. \[ \begin{array}{c|c||c} p&q&p\equivalent q\\\hline\hline 0&0&1\\\hline 0&1&0\\\hline 1&0&0\\\hline 1&1&1 \end{array} \]

Théorème

\[(p\equivalent q)=(p\implique q)\et(q\implique p)\]

Le précédent résultat sur l'implication permet par ailleurs d'écrire $ (p\equivalent q)=(\non p \ou q)\et(\non q \ou p)$ .

Démonstration

On laisse le soin au lecteur de comparer les tables de vérité.

¹Auguste de Morgan (1806-1871), mathématicien et logicien britannique.
²Original...