\documentclass[11pt,a4paper,french]{article}
\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage{a4}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{framed}
\usepackage[amsmath,thmmarks,thref,framed]{ntheorem}
\usepackage[dvips]{graphics}
\usepackage{epsfig}
\usepackage{calc}
\usepackage{tabls}
\usepackage{times}
\usepackage{tabularx}
\usepackage{textcomp}
\usepackage{pst-all}
\usepackage[a4paper]{geometry}

\input{symboles.sty}
\geometry{hmargin=1cm, vmargin=1.5cm}

\title{
DUT d'informatique. Contrôle de mathématiques discrètes.\\  
Semestre 1 (Octobre 2013). Durée 1h.}

\date{}

\begin{document}
\maketitle

\noindent Seule une fiche manuscrite de format A5 est autorisée. 
Tous les exercices de ce sujet sont indépendants les uns des autres. 
Dans tout ce qui suit, on considère une algèbre de Boole
munie des opérateurs classiques ``+'', ``.'', 
``$\overline{\begin{array}{l}~\end{array}}$'' et des variables booléennes 
$a$, $b$, $c$, $d$.


\section{Cours}

\begin{enumerate}
\item La première règle de suppression de la redondance est: ``dans une somme booléenne, tout terme absorbe ses  multiples''.   Démontrer cette règle (sans se servir des règles de suppression de redondance naturellement).
\item Donner la définition de \og la forme cannonique disjonctive d'une expression\fg{}.
\item Démontrer qu'il y a  1024 mintermes à 10 variables. 
Si vous utilisez un théorème pour faire la preuve, il faudra le prouver.
\item Que dire des colonnes adjacentes d'une table de Karnaugh? Et les lignes ?

\end{enumerate}




\section{Forme canonique disjonctive}
Donner la forme canonique disjonctive de l'expression suivante en détaillant les calculs:
$$
(a + b + \overline{c}).\overline{(\overline{a} + bc)}.
$$

\section{Table de Karnaugh}
On considère les deux expressions booléennes $E_1$ et $E_2$ suivantes:

$$
\begin{array}{rcl}
E_1 &= &\overline{a}.\overline{b} + a.c+ a.\overline{b}.\overline{c},\\
E_2 &=& a.\overline{b} + a.c.d + a.b.c +\overline{a}.\overline{b}.\overline{c}.
\end{array}
$$

\begin{enumerate}
\item A l'aide d'une table de Karnaugh donner l'expression $K_1$ qui 
  serait la forme la plus réduite de $E_1$. 

\item A l'aide d'une autre table de Karnaugh donner l'expression 
  $K_2$ qui serait la forme la plus réduite de $E_2$.

\item  Justifier algébriquement que l'on a l'égalité $E_1 = K_1$.

\item Justifier algébriquement que l'on a l'égalité $E_2 = K_2$.
\end{enumerate}

\section{Opérateur de Peirce}
On considère l'opérateur binaire de Peirce 
défini pour toute paire de variables booléennes $(a,b)$ par 
$$
a \downarrow b = \overline{a}.\overline{b}
$$.

\begin{enumerate}
\item Que valent  
$a \downarrow 0$ puis $0 \downarrow 0$ et enfin   $1 \downarrow 1$?
\item Que valent $(a \downarrow 0) \downarrow (b \downarrow 0)$ et
 $(a \downarrow b ) \downarrow 0$ ?
\item Réécrire l'expression  $\overline{a}.(b+c)$ sans utiliser 
les opérateurs ``+'', ``.'' et 
``$\overline{\begin{array}{l}~\end{array}}$'' mais en
n'utilisant que l'opérateur de Peirce et des parenthèses.
\item L'opérateur de Peirce est-il associatif? Le prouver.
\end{enumerate}

\end{document}
