diapos/logique/boole.tex

   1
   2
   3 \begin{frame}
   4  \frametitle{Algèbre de Boole}
   5  \framesubtitle{Définition}
   6 Une \emph{algèbre de Boole} est une structure algébrique composée
   7 \begin{itemize}
   8 \item d'un ensemble $\mathcal{A}$ contenant au moins deux éléments
   9 notés $0$ et $1$
  10 \item \pause de deux lois de composition interne sur $\mathcal{A}$
  11 (opérations binaires) appelées ``somme'' et ``produit'' et
  12 respectivement notées \textcolor{red}{+} et \textcolor{red}{.}
  13 \item \pause d'une opération unaire appelée ``négation'' et notée
  14  \textcolor{red}{$\overline{\mathstrut\enskip}$} (ex.
  15   $\overline{a}$)
  16 \end{itemize}
  17 telles que
  18 \begin{enumerate}
  19 \item somme et produit sont \pause associatives, commutatives
  20 et idempotentes
  21 \item \pause ces deux lois sont distributives l'une par rapport à
  22 l'autre
  23 \item \pause $0$ est élément neutre de \pause la somme, \pause
  24 absorbant du produit
  25 \item \pause $1$ est élément neutre du produit, absorbant de la somme
  26 \item \pause la négation est une involution
  27 \item \pause $x$ et $\overline{x}$ sont opposés et inverses
  28 \item \pause les trois opérations sont reliées par les lois de De
  29 Morgan
  30 \end{enumerate}
  31 \end{frame}
  32
  33
  34 \begin{frame}
  35  \frametitle{Algèbre de Boole}
  36  \framesubtitle{Lois de De Morgan}
  37
  38 \begin{itemize}
  39   \item $\sur{a+b}=\sur a\cdot\sur b$
  40   \item $\sur{a\cdot b}=\sur a+\sur b$
  41 \end{itemize}
  42
  43 \pause Remarque : le point pour le produit est souvent omis
  44
  45 \pause On peut donc écrire
  46 \begin{itemize}
  47   \item $\sur{a+b}=\sur a \ \sur b$
  48   \item $\sur{a\  b}=\sur a+\sur b$
  49 \end{itemize}
  50 \end{frame}
  51
  52
  53 \begin{frame}
  54  \frametitle{Calcul booléen}
  55  \framesubtitle{}
  56 \begin{itemize}
  57 \item Le calcul booléen consiste à transformer des
  58 expressions booléennes en n'appliquant que des axiomes des algèbres de
  59 Boole
  60 \item \pause Tous ces axiomes sont des égalités (structure
  61 \emph{algébrique})
  62 \item \pause Raisonnement par égalités successives (un axiome par
  63 étape)
  64 \item \pause Automatisable ? \pause réécriture \ldots
  65 \end{itemize}
  66 \pause
  67 \textbf{Exercice 5.5}
  68
  69 Transformer les expressions suivantes par calcul booléen pour obtenir
  70 des expressions plus petites
  71
  72
  73 \begin{enumerate}
  74 \item $(a+b) \cdot (b+c) \cdot (c+a)$
  75 \item $(a+b) \cdot (a+c)+(b+c) \cdot (a+b)+(a+c) \cdot (b+c)$
  76 \item $(a+b+c) \cdot (a+\overline{b}+c) \cdot (a+\overline{b}+\overline{c})$
  77 \item $a+\overline{a} \cdot b \cdot c+\overline{a}+a \cdot b$
  78 \item $a \cdot b+\overline{a} \cdot b \cdot c+a \cdot \overline{b} \cdot c$
  79 \item $a \cdot \overline{b}+a \cdot b \cdot c+a \cdot \overline{b} \cdot c \cdot d$
  80 \item $(a+b+c) \cdot (\overline{a}+\overline{b}+\overline{c}+d)$
  81 \end{enumerate}
  82 \end{frame}
  83
  84
  85 \begin{frame}
  86  \frametitle{Algèbre de Boole}
  87  \framesubtitle{Lecture du support de cours}
  88  Chapitre 4
  89
  90  \begin{itemize}
  91     \item Maîtriser la partie I
  92     \item \pause Lire les parties II (fonctions booléennes), III
  93     (représentation et simplification des fonctions) et IV
  94     (résolution d'équations booléennes),
  95  utiles pour la synthèse logique (puces, hardware)
  96     \item \pause Mise en FCC (forme canonique conjonctive) pour la
  97     méthode de résolution (et les travaux pratiques)
  98  \end{itemize}
  99 \end{frame}
 100
 101 \begin{frame}
 102  \frametitle{Algèbre de Boole}
 103  \framesubtitle{Deux exemples importants}
 104 Choisir pour $\mathcal{A}$
 105 \begin{itemize}
 106   \item l'ensemble $\mathcal{P}(E)$ des parties d'un ensemble $E$
 107 % Historiquement, c'est l'apport de G. Boole
 108   \item \pause l'ensemble $\mathbb{B} =_{\textrm{def}} \{0, 1\}$
 109 \end{itemize}
 110 \pause Dans $\mathbb{B}$,
 111 l'op\'eration unaire $\mbox{}^{-}$ est d\'efinie par
 112 \pause $\overline{0} = 1$ et $\overline{1} = 0$
 113
 114 \pause Dans $\mathbb{B}$,
 115 les op\'erations binaires $+$ et $.$ sont d\'efinies
 116 par les tables
 117 $
 118 \begin{array}{c|c|c}
 119  + & 0 & 1 \\
 120 \hline
 121  0 & 0 & 1 \\
 122 \hline
 123  1 & 1 & 1
 124 \end{array}
 125 $
 126 et
 127 $
 128 \begin{array}{c|c|c}
 129  .  & 0 & 1 \\
 130 \hline
 131  0 & 0 & 0 \\
 132 \hline
 133  1 & 0 & 1
 134 \end{array}
 135 $
 136
 137 \pause Quelles règles déterminent ces ``tables de
 138 Pythagore'' de $+$, $.$ et $\overline{\mathstrut\enskip}$ ?
 139
 140 \pause Interprétation booléenne des propositions : variables
 141 propositionnelles à valeurs dans $\mathbb{B}$
 142 \end{frame}
 143
 144 \begin{frame}
 145  \frametitle{Sémantique de la logique propositionnelle}
 146  \framesubtitle{Interprétation booléenne}
 147 %``Table de vérité'' en $0$ (\textit{faux}) et $1$ (\textit{vrai})
 148 \begin{itemize}
 149   \item Soit $\mathcal{P}$ l'ensemble des variables qu'on peut trouver
 150 dans une formule propositionnelle
 151 \item \pause L'environnement d'une formule est donn\'e par une fonction
 152  $v$ de $\mathcal{P}$ dans $\mathbb{B}$, appel\'ee \emph{valuation},
 153 qui associe \`a toute variable de $\mathcal{P}$ la valeur $0$ ou $1$
 154 \item \pause Chaque valuation $v$ peut \^etre prolong\'ee en une
 155 \emph{interpr\'etation} $I_v$
 156 de chaque formule propositionnelle en une valeur bool\'eenne, par~:
 157 \begin{eqnarray}
 158  I_v(x) & = & v(x) \quad \text{ si } x \in X      \label{ivar} \\
 159  \pause I_v(\neg F) & = & \pause \overline{I_v(F)}
 160  \label{ineg} \\
 161  \pause I_v(F \wedge G) & = & \pause I_v(F) \ .  \ I_v(G)
 162  \label{iet} \\
 163  \pause I_v(F \vee G) & = & \pause I_v(F) \ +  \ I_v(G)
 164  \label{iou} \\
 165  \pause I_v(F \Rightarrow G) & = & \pause I_v(\neg F \vee G)
 166  \label{iimplique} \\
 167  \pause I_v(F \Leftrightarrow G) & = & \pause I_v( (F \Rightarrow G)
 168  \wedge (G \Rightarrow F))  \label{iequiv}
 169 \end{eqnarray}
 170 o\`u $F$ et $G$ sont des formules propositionnelles
 171 \end{itemize}
 172 % Prendre des notes, pas dans les supports
 173 % A partir du devoir LMD 1 de 2007
 174 \end{frame}
 175
 176 \begin{frame}
 177  \frametitle{Interprétation booléenne}
 178  \framesubtitle{Tautotogie}
 179 On appelle \emph{tautologie} toute formule propositionnelle valide dans
 180 le mod\`ele bool\'een.
 181 Autrement dit, une tautologie est une formule $f$ telle
 182 que $I_v(f)= 1$ pour toute valuation $v$ de ses variables.
 183
 184 \pause \noindent\textit{Exemple}~:
 185 La formule $p \vee \neg p$ est une tautologie
 186
 187 En effet, pour toute valuation $v$, on a~:
 188
 189 $I_v(p \vee \neg p) = I_v(p) + I_v(\neg p) = I_v(p) + \overline{I_v(p)}
 190  = v(p) +\overline{v(p)} = 1$
 191
 192
 193 \pause ``$F$ est une tautologie'' se note $\models F$
 194 \end{frame}
 195
 196 \begin{frame}
 197 \frametitle{Interprétation booléenne}
 198 \framesubtitle{Formules équivalentes}
 199 Deux formules propositionnelles $F$ et $G$ sont équivalentes si
 200 \pause
 201  $I_v(F)= I_v(G)$ pour toute valuation $v$ de leurs variables.
 202
 203 \pause Méta-théorème : Les formules $F$ et $G$ sont équivalentes
 204 si et seulement si $F \Leftrightarrow G$ est une tautologie.
 205 \end{frame}
 206
 207 \begin{frame}
 208 \frametitle{Interprétation booléenne}
 209 \framesubtitle{Exercices}
 210 \begin{enumerate}
 211 \item Soit $v$ une valuation telle que $v(x)=1$ et $v(y)=0$.
 212  Calculer $I_v(y \vee (x \wedge  y))$ et $I_v(x \Rightarrow (x \vee y))$.
 213 \item \pause Montrer que, pour toute formule $F$ et pour toute
 214 valuation $v$, on a $$I_v(\neg (\neg F)) = I_v(F).$$
 215 \item Montrer que, pour toutes les formules $F$ et $G$ et pour toute valuation $v$, on a
 216  \begin{enumerate}
 217  \item $I_v(F \vee G) = I_v(\neg ((\neg F) \wedge (\neg G)))$
 218  \item $I_v(F \wedge G) = I_v(\neg ( F \Rightarrow (\neg G)))$
 219  \item $I_v(\neg (F \vee G)) = I_v((\neg F) \wedge (\neg G))$
 220  \end{enumerate}
 221 \end{enumerate}
 222 \end{frame}
 223
 224
 225 \begin{frame}
 226  \frametitle{Interprétation booléenne}
 227  \framesubtitle{Satisfaire une formule}
 228 Pour chaque formule suivante, donner un environnement
 229 (donc une valuation) qui la
 230 satisfait
 231 \begin{enumerate}
 232 \item $(p \wedge q) \vee r$
 233 \item $r \vee (\neg s)$
 234 \item $p \Leftrightarrow (p \vee q)$
 235 \end{enumerate}
 236
 237 \pause On dit que ces formules sont \emph{satisfaisables}
 238
 239 \pause Comment décider si une formule propositionnelle est
 240 satisfaisable ?
 241
 242 \pause On cherche des algorithmes plus efficaces que la construction
 243 d'une table de v\'erit\'e pour décider la validité ou la
 244 satisfaisabilité d'une formule
 245
 246
 247 \pause Prochain cours : Déductions et démonstrations
 248 \end{frame}
 249
 250
 251
 252
 253 % Modele
 254 % \begin{frame}
 255 %  \frametitle{Calcul des propositions}
 256 %  \framesubtitle{Tables de vérité}
 257 %
 258 % \end{frame}