partiels/131105S1/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, tmargin=-0.5cm, bmargin=1.5cm}
  22
  23 \title{
  24 DUT d'informatique. Contrôle de mathématiques discrètes.\\
  25 Semestre 1 (Novembre 2013). Durée 1h.}
  26
  27 \date{}
  28
  29 \begin{document}
  30 \maketitle
  31
  32 \vspace{-3em}
  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$.
  39
  40
  41 \vspace{-1em}
  42 \section{Cours (3pts) }
  43
  44 \begin{enumerate}
  45 \item Soit $A$ et $B$ deux ensembles d'un
  46 univers $\Omega$ tels que $A \subseteq B$. Définir $B\setminus A$ en compréhension.
  47 \item L'ensemble vide appartient-il à tout ensemble? Justifier.
  48 \end{enumerate}
  49
  50
  51
  52
  53 \vspace{-1em}
  54 \section{(6pts) Simplification de formules booléennes (d'après sujet de BTS-IG-2008)}
  55 La société Jurabois exploite des coupes d'arbres constitués exclusivement de
  56 feuillus et de résineux. Elle désire simplifier le règlement que les salariés
  57 doivent appliquer pour la coupe du bois.
  58 Actuellement, le règlement dit qu'un arbre est à abattre dans les quatre cas
  59 suivants:
  60 \begin{itemize}
  61 \item si c'est un résineux au tronc droit mesurant plus de 20 m de hauteur;
  62 \item si c'est un feuillus de 50 ans ou plus;
  63 \item s'il a moins de 50 ans et mesure plus de 20 m de hauteur;
  64 \item s'il est tordu.
  65 \end{itemize}
  66 Pour un arbre quelconque, on définit les variables booléennes suivantes par:
  67 \begin{itemize}
  68 \item $a=1$ si l'arbre est un résineux;
  69 \item $b=1$ si l'arbre a moins de 50 ans;
  70 \item $c=1$ si l'arbre mesure plus de 20 m de hauteur;
  71 \item $d=1$ si l'arbre est tordu.
  72 \end{itemize}
  73
  74
  75 \begin{enumerate}
  76 \item Écrire la fonction booléenne $f(a,b,c,d)$ qui traduit le règlement
  77   actuel d'abattage d'un arbre.
  78
  79 \item Grâce à une bonne gestion des forêts que la société exploite,
  80   il n'y a maintenant plus d'arbre tordu.
  81 \begin{enumerate}
  82 \item Montrer que le nouveau règlement d'abattage se traduit par la fonction
  83 $
  84 g(a,b,c) = ac + \overline{a}\overline{b} + bc
  85 $.
  86 \item A l'aide d'une table de Karnaugh donner l'expression $G$ qui
  87   serait la forme la plus réduite de $g$.
  88
  89 \item Justifier algébriquement que l'on a l'égalité $G = g$.
  90
  91 \item Écrire la nouvelle règle d'abattage d'un arbre sous la forme
  92   la plus simple possible.
  93 \end{enumerate}
  94 \end{enumerate}
  95
  96
  97
  98 \vspace{-1em}
  99 \section{(5pts) Démonstrations ensemblistes}
 100 Soit $A$ et $B$ deux sous-ensembles de $\Omega$.
 101 \begin{enumerate}
 102 \item Soit $A_0=\{1,2,3\}$ et $B_0=\{3,4\}$.
 103 Définir $A_0 \cup B_0$, $P(A_0)$, $P(B_0)$, $P(A_0\cup B_0)$ et
 104 $P(A_0) \cup P(B_0)$.
 105 \item A-t-on l'égalité $P(A \cup B) = P(A) \cup P(B)$? Justifier.
 106 \item Montrer que l'on a $P(A \cap B) = P(A) \cap P(B)$.
 107 \end{enumerate}
 108
 109
 110
 111 \vspace{-1em}
 112 \section{(6 pts) Relation entre puissances d'éléments}
 113
 114
 115 Sur $\N^*$ on définit la relation
 116 $a \mathcal{R} b$ si   $a^b \leq b ^a$.
 117 \begin{enumerate}
 118 \item A-t-on $2 \mathcal{R} 3$? $2 \mathcal{R} 7$? $2 \mathcal{R} 4$? $3 \mathcal{R} 3$? $4 \mathcal{R} 2$? Justifier à chaque fois.
 119
 120 \item La relation est-elle réflexive? Le démontrer.
 121
 122 \item La fonction logarithme népérien $\ln: \R^{+*} \rightarrow \R$ étant
 123   croissante, montrer que sur $\N^*$
 124   $a \mathcal{R} b$ si   $\dfrac{\ln(a)}{a} \leq \dfrac{\ln(b)}{b}$.
 125 \item La relation est-elle transitive? Pour justifier votre réponse, on
 126   pourra utiliser  la question précédente.
 127 \item La relation est-elle antisymétrique? Le justifier.
 128 \end{enumerate}
 129
 130
 131
 132
 133
 134 \end{document}