partiels/131003S1/controle.tex~

   1 \documentclass[11pt,a4paper,french]{article}
   2 \usepackage[francais]{babel}
   3 \usepackage[utf8]{inputenc}
   4 \usepackage{a4}
   5 \usepackage{amsmath}
   6 \usepackage{amsfonts}
   7 \usepackage{amssymb}
   8 \usepackage{framed}
   9 \usepackage[amsmath,thmmarks,thref,framed]{ntheorem}
  10 \usepackage[dvips]{graphics}
  11 \usepackage{epsfig}
  12 \usepackage{calc}
  13 \usepackage{tabls}
  14 \usepackage{times}
  15 \usepackage{tabularx}
  16 \usepackage{textcomp}
  17 \usepackage{pst-all}
  18 \usepackage[a4paper]{geometry}
  19
  20 \input{symboles.sty}
  21 \geometry{hmargin=1cm, vmargin=1.5cm}
  22
  23 \title{
  24 DUT d'informatique. Contrôle de mathématiques discrètes.\\
  25 Semestre 1 (Octobre 2013). Durée 1h\\
  26 }
  27
  28 \date{}
  29
  30 \begin{document}
  31 \maketitle
  32
  33 \noindent Seule une fiche manuscrite de format A5 est autorisée.
  34 Tous les exercices de ce sujet sont indépendants les uns des autres.
  35 Dans tout ce qui suit, on considère une algèbre de Boole
  36 munie des opérateurs classiques ``+'', ``.'',
  37 ``$\overline{\begin{array}{l}~\end{array}}$'' et des variables booléennes
  38 $a$, $b$, $c$, $d$\ldots
  39
  40
  41 \section{Cours}
  42
  43 \begin{enumerate}
  44 \item La première règle de suppression de la redondance est: ``Dans une somme booléenne, tout terme absorbe ses  multiples: $a + a.b = a$.''.   Démontrer cette règles (sans se servir des règles de suppression de redondance naturellement).
  45 \item Donner la définition de \og la forme cannonique disjonctive d'une expression\fg{}.
  46 \item Démontrer qu'il y a  1024 mintermes à 10 variables.
  47 Si vous utilisez un théorème pour faire la preuve, il faudra le prouver.
  48 \item Que dire des colonnes adjacentes d'une table de Karnaugh? Et les lignes ?
  49
  50 \end{enumerate}
  51
  52
  53
  54
  55 \section{Forme canonique disjonctive}
  56 Donner la forme canonique disjonctive de l'expression suivante en détaillant les calculs:
  57 $$
  58 (a + b + \overline{c}).\overline{(\overline{a} + bc)}.
  59 $$
  60
  61 \section{Table de Karnaugh}
  62 On considère les deux expressions booléennes $E_1$ et $E_2$ suivantes:
  63
  64 $$
  65 \begin{array}{rcl}
  66 E_1 &= &\overline{a}.\overline{b} + a.c+ a.\overline{b}.\overline{c},\\
  67 E_2 &=& a.\overline{b} + a.c.d + a.b.c +\overline{a}.\overline{b}.\overline{c}.
  68 \end{array}
  69 $$
  70
  71 \begin{enumerate}
  72 \item A l'aide d'une table de Karnaugh donner l'expression $K_1$ qui
  73   serait la forme la plus réduite de $E_1$.
  74
  75 \item A l'aide d'une autre table de Karnaugh donner l'expression
  76   $K_2$ qui serait la forme la plus réduite de $E_2$.
  77
  78 \item  Justifier algébriquement que l'on a l'égalité $E_1 = K_1$.
  79
  80 \item Justifier algébriquement que l'on a l'égalité $E_2 = K_2$.
  81 \end{enumerate}
  82
  83 \section{Opérateur de Peirce}
  84 On considère l'opérateur binaire de Peirce
  85 défini pour toute paire de variables booléenne $(a,b)$ par
  86 $$
  87 a \downarrow b = \overline{a}.\overline{b}
  88 $$.
  89
  90 \begin{enumerate}
  91 \item Que valent
  92 $a \downarrow 0$ puis $0 \downarrow 0$ et enfin   $1 \downarrow 1$?
  93 \item Que valent $(a \downarrow 0) \downarrow (b \downarrow 0)$ et
  94  $(a \downarrow b ) \downarrow 0$ ?
  95 \item Réécrire l'expression  $\overline{a}.(b+c)$ sans utiliser
  96 les opérateurs ``+'', ``.'' et
  97 ``$\overline{\begin{array}{l}~\end{array}}$'' mais en
  98 n'utilisant que l'opérateur de Peirce et des parenthèses.
  99 \item L'opérateur de Peirce est-il associatif? Le prouver.
 100 \end{enumerate}
 101
 102 \end{document}