\begin{frame}
 \frametitle{Algèbre de Boole}
 \framesubtitle{Définition}
Une \emph{algèbre de Boole} est une structure algébrique composée
\begin{itemize}
\item d'un ensemble $\mathcal{A}$ contenant au moins deux éléments
notés $0$ et $1$
\item \pause de deux lois de composition interne sur $\mathcal{A}$
(opérations binaires) appelées ``somme'' et ``produit'' et
respectivement notées \textcolor{red}{+} et \textcolor{red}{.} 
\item \pause d'une opération unaire appelée ``négation'' et notée  
 \textcolor{red}{$\overline{\mathstrut\enskip}$} (ex.
  $\overline{a}$)
\end{itemize}
telles que 
\begin{enumerate}
\item somme et produit sont \pause associatives, commutatives
et idempotentes 
\item \pause ces deux lois sont distributives l'une par rapport à
l'autre
\item \pause $0$ est élément neutre de \pause la somme, \pause
absorbant du produit
\item \pause $1$ est élément neutre du produit, absorbant de la somme
\item \pause la négation est une involution
\item \pause $x$ et $\overline{x}$ sont opposés et inverses
\item \pause les trois opérations sont reliées par les lois de De
Morgan
\end{enumerate}
\end{frame}


\begin{frame}
 \frametitle{Algèbre de Boole}
 \framesubtitle{Lois de De Morgan}

\begin{itemize}
  \item $\sur{a+b}=\sur a\cdot\sur b$
  \item $\sur{a\cdot b}=\sur a+\sur b$
\end{itemize}

\pause Remarque : le point pour le produit est souvent omis

\pause On peut donc écrire
\begin{itemize}
  \item $\sur{a+b}=\sur a \ \sur b$
  \item $\sur{a\  b}=\sur a+\sur b$
\end{itemize}
\end{frame}


\begin{frame}
 \frametitle{Calcul booléen}
 \framesubtitle{}
\begin{itemize}
\item Le calcul booléen consiste à transformer des
expressions booléennes en n'appliquant que des axiomes des algèbres de
Boole
\item \pause Tous ces axiomes sont des égalités (structure
\emph{algébrique})
\item \pause Raisonnement par égalités successives (un axiome par
étape)
\item \pause Automatisable ? \pause réécriture \ldots
\end{itemize} 
\pause
\textbf{Exercice 5.5}

Transformer les expressions suivantes par calcul booléen pour obtenir
des expressions plus petites


\begin{enumerate}
\item $(a+b) \cdot (b+c) \cdot (c+a)$
\item $(a+b) \cdot (a+c)+(b+c) \cdot (a+b)+(a+c) \cdot (b+c)$
\item $(a+b+c) \cdot (a+\overline{b}+c) \cdot (a+\overline{b}+\overline{c})$
\item $a+\overline{a} \cdot b \cdot c+\overline{a}+a \cdot b$
\item $a \cdot b+\overline{a} \cdot b \cdot c+a \cdot \overline{b} \cdot c$
\item $a \cdot \overline{b}+a \cdot b \cdot c+a \cdot \overline{b} \cdot c \cdot d$
\item $(a+b+c) \cdot (\overline{a}+\overline{b}+\overline{c}+d)$
\end{enumerate}
\end{frame}


\begin{frame}
 \frametitle{Algèbre de Boole}
 \framesubtitle{Lecture du support de cours}
 Chapitre 4
 
 \begin{itemize}
    \item Maîtriser la partie I
    \item \pause Lire les parties II (fonctions booléennes), III
    (représentation et simplification des fonctions) et IV
    (résolution d'équations booléennes),
 utiles pour la synthèse logique (puces, hardware)
    \item \pause Mise en FCC (forme canonique conjonctive) pour la
    méthode de résolution (et les travaux pratiques)
 \end{itemize}    
\end{frame}

\begin{frame}
 \frametitle{Algèbre de Boole}
 \framesubtitle{Deux exemples importants}
Choisir pour $\mathcal{A}$ 
\begin{itemize}
  \item l'ensemble $\mathcal{P}(E)$ des parties d'un ensemble $E$
% Historiquement, c'est l'apport de G. Boole  
  \item \pause l'ensemble $\mathbb{B} =_{\textrm{def}} \{0, 1\}$
\end{itemize}
\pause Dans $\mathbb{B}$,
l'op\'eration unaire $\mbox{}^{-}$ est d\'efinie par 
\pause $\overline{0} = 1$ et $\overline{1} = 0$

\pause Dans $\mathbb{B}$,
les op\'erations binaires $+$ et $.$ sont d\'efinies
par les tables 
$
\begin{array}{c|c|c}
 + & 0 & 1 \\
\hline
 0 & 0 & 1 \\
\hline
 1 & 1 & 1 
\end{array}
$
et
$
\begin{array}{c|c|c}
 .  & 0 & 1 \\
\hline
 0 & 0 & 0 \\
\hline
 1 & 0 & 1 
\end{array}
$

\pause Quelles règles déterminent ces ``tables de
Pythagore'' de $+$, $.$ et $\overline{\mathstrut\enskip}$ ?

\pause Interprétation booléenne des propositions : variables
propositionnelles à valeurs dans $\mathbb{B}$ 
\end{frame}

\begin{frame}
 \frametitle{Sémantique de la logique propositionnelle}
 \framesubtitle{Interprétation booléenne}
%``Table de vérité'' en $0$ (\textit{faux}) et $1$ (\textit{vrai})
\begin{itemize}
  \item Soit $\mathcal{P}$ l'ensemble des variables qu'on peut trouver
dans une formule propositionnelle
\item \pause L'environnement d'une formule est donn\'e par une fonction
 $v$ de $\mathcal{P}$ dans $\mathbb{B}$, appel\'ee \emph{valuation},
qui associe \`a toute variable de $\mathcal{P}$ la valeur $0$ ou $1$
\item \pause Chaque valuation $v$ peut \^etre prolong\'ee en une
\emph{interpr\'etation} $I_v$ 
de chaque formule propositionnelle en une valeur bool\'eenne, par~:
\begin{eqnarray}
 I_v(x) & = & v(x) \quad \text{ si } x \in X      \label{ivar} \\
 \pause I_v(\neg F) & = & \pause \overline{I_v(F)}             
 \label{ineg} \\ 
 \pause I_v(F \wedge G) & = & \pause I_v(F) \ .  \ I_v(G)        
 \label{iet} \\
 \pause I_v(F \vee G) & = & \pause I_v(F) \ +  \ I_v(G)            
 \label{iou} \\ 
 \pause I_v(F \Rightarrow G) & = & \pause I_v(\neg F \vee G)
 \label{iimplique} \\ 
 \pause I_v(F \Leftrightarrow G) & = & \pause I_v( (F \Rightarrow G)
 \wedge (G \Rightarrow F))  \label{iequiv}
\end{eqnarray}
o\`u $F$ et $G$ sont des formules propositionnelles
\end{itemize}
% Prendre des notes, pas dans les supports
% A partir du devoir LMD 1 de 2007  
\end{frame}

\begin{frame}
 \frametitle{Interprétation booléenne}
 \framesubtitle{Tautotogie}
On appelle \emph{tautologie} toute formule propositionnelle valide dans 
le mod\`ele bool\'een.
Autrement dit, une tautologie est une formule $f$ telle
que $I_v(f)= 1$ pour toute valuation $v$ de ses variables.

\pause \noindent\textit{Exemple}~:
La formule $p \vee \neg p$ est une tautologie
 
En effet, pour toute valuation $v$, on a~:

$I_v(p \vee \neg p) = I_v(p) + I_v(\neg p) = I_v(p) + \overline{I_v(p)}
 = v(p) +\overline{v(p)} = 1$ 


\pause ``$F$ est une tautologie'' se note $\models F$
\end{frame}

\begin{frame}
\frametitle{Interprétation booléenne}
\framesubtitle{Formules équivalentes}
Deux formules propositionnelles $F$ et $G$ sont équivalentes si
\pause
 $I_v(F)= I_v(G)$ pour toute valuation $v$ de leurs variables.

\pause Méta-théorème : Les formules $F$ et $G$ sont équivalentes
si et seulement si $F \Leftrightarrow G$ est une tautologie.
\end{frame}

\begin{frame}
\frametitle{Interprétation booléenne}
\framesubtitle{Exercices}
\begin{enumerate}
\item Soit $v$ une valuation telle que $v(x)=1$ et $v(y)=0$. 
 Calculer $I_v(y \vee (x \wedge  y))$ et $I_v(x \Rightarrow (x \vee y))$.
\item \pause Montrer que, pour toute formule $F$ et pour toute
valuation $v$, on a $$I_v(\neg (\neg F)) = I_v(F).$$
\item Montrer que, pour toutes les formules $F$ et $G$ et pour toute valuation $v$, on a 
 \begin{enumerate}
 \item $I_v(F \vee G) = I_v(\neg ((\neg F) \wedge (\neg G)))$
 \item $I_v(F \wedge G) = I_v(\neg ( F \Rightarrow (\neg G)))$
 \item $I_v(\neg (F \vee G)) = I_v((\neg F) \wedge (\neg G))$
 \end{enumerate}
\end{enumerate}
\end{frame}


\begin{frame}
 \frametitle{Interprétation booléenne}
 \framesubtitle{Satisfaire une formule}
Pour chaque formule suivante, donner un environnement 
(donc une valuation) qui la 
satisfait
\begin{enumerate}
\item $(p \wedge q) \vee r$
\item $r \vee (\neg s)$
\item $p \Leftrightarrow (p \vee q)$
\end{enumerate}

\pause On dit que ces formules sont \emph{satisfaisables}

\pause Comment décider si une formule propositionnelle est
satisfaisable ?

\pause On cherche des algorithmes plus efficaces que la construction
d'une table de v\'erit\'e pour décider la validité ou la
satisfaisabilité d'une formule


\pause Prochain cours : Déductions et démonstrations
\end{frame}




% Modele
% \begin{frame}
%  \frametitle{Calcul des propositions}
%  \framesubtitle{Tables de vérité}
%  
% \end{frame}