\( %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 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}{\text{\Large$\varepsilon\!\!\varepsilon$}} \newcommand{\supere}{\text{\Large$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{\vv}{\overrightarrow{v}} \newcommand{\vu}{\overrightarrow{u}} \newcommand{\vup}{\overrightarrow{u'}} \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]{\dpl{\left\langle #1\right\rangle}} \newcommand{\trans}[1]{{\vphantom{#1}}^{t}{#1}} \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 vrai ni fausse et vrai 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


Un 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 vrai. 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éfinition 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$ défini 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$ défini 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éfini 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} $$
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 à pense 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ême tables de vérité. Dans ce cas on note $ p=q$ .
Comme nous l'avons observer dans la table précédente, 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} $$

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$ proposition 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 Morgan1 et une des deux propriété 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 et équivalence

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$ vrai, par un raisonnement logique, c'est à dire sans digression et fausseté, on ne peut arrivé qu'à démontrer une proposition vrai. 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 arrivé à 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 connecteur logique différent. 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)$ ) et 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 identique.

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é on 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 proposition 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 tel 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é2.

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$ . Pou 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é.
Img/Chat.jpg




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