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 \date{}
  28
  29 \begin{document}
  30 \maketitle
  31
  32 \noindent Seule une fiche manuscrite de format A5 est autorisée.
  33 Tous les exercices de ce sujet sont indépendants les uns des autres.
  34 Dans tout ce qui suit, on considère une algèbre de Boole
  35 munie des opérateurs classiques ``+'', ``.'',
  36 ``$\overline{\begin{array}{l}~\end{array}}$'' et des variables booléennes
  37 $a$, $b$, $c$, $d$.
  38
  39
  40 \section{Cours}
  41
  42 \begin{enumerate}
  43 \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).
  44 \item Donner la définition de \og la forme cannonique disjonctive d'une expression\fg{}.
  45 \item Démontrer qu'il y a  1024 mintermes à 10 variables.
  46 Si vous utilisez un théorème pour faire la preuve, il faudra le prouver.
  47 \item Que dire des colonnes adjacentes d'une table de Karnaugh? Et les lignes ?
  48
  49 \end{enumerate}
  50
  51
  52
  53
  54 \section{Forme canonique disjonctive}
  55 Donner la forme canonique disjonctive de l'expression suivante en détaillant les calculs:
  56 $$
  57 (a + b + \overline{c}).\overline{(\overline{a} + bc)}.
  58 $$
  59
  60 \section{Table de Karnaugh}
  61 On considère les deux expressions booléennes $E_1$ et $E_2$ suivantes:
  62
  63 $$
  64 \begin{array}{rcl}
  65 E_1 &= &\overline{a}.\overline{b} + a.c+ a.\overline{b}.\overline{c},\\
  66 E_2 &=& a.\overline{b} + a.c.d + a.b.c +\overline{a}.\overline{b}.\overline{c}.
  67 \end{array}
  68 $$
  69
  70 \begin{enumerate}
  71 \item A l'aide d'une table de Karnaugh donner l'expression $K_1$ qui
  72   serait la forme la plus réduite de $E_1$.
  73
  74 \item A l'aide d'une autre table de Karnaugh donner l'expression
  75   $K_2$ qui serait la forme la plus réduite de $E_2$.
  76
  77 \item  Justifier algébriquement que l'on a l'égalité $E_1 = K_1$.
  78
  79 \item Justifier algébriquement que l'on a l'égalité $E_2 = K_2$.
  80 \end{enumerate}
  81
  82 \section{Opérateur de Peirce}
  83 On considère l'opérateur binaire de Peirce
  84 défini pour toute paire de variables booléennes $(a,b)$ par
  85 $$
  86 a \downarrow b = \overline{a}.\overline{b}
  87 $$.
  88
  89 \begin{enumerate}
  90 \item Que valent
  91 $a \downarrow 0$ puis $0 \downarrow 0$ et enfin   $1 \downarrow 1$?
  92 \item Que valent $(a \downarrow 0) \downarrow (b \downarrow 0)$ et
  93  $(a \downarrow b ) \downarrow 0$ ?
  94 \item Réécrire l'expression  $\overline{a}.(b+c)$ sans utiliser
  95 les opérateurs ``+'', ``.'' et
  96 ``$\overline{\begin{array}{l}~\end{array}}$'' mais en
  97 n'utilisant que l'opérateur de Peirce et des parenthèses.
  98 \item L'opérateur de Peirce est-il associatif? Le prouver.
  99 \end{enumerate}
 100
 101 \end{document}