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{(5 pts) Simplification de formules booléennes (d'après sujet de BTS-IG-2008)}
  55 La société Jurabois exploite des forêts d'arbres constituées 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:
  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 sans justifier
  77   la fonction booléenne $f(a,b,c,d)$ qui traduit le règlement
  78   actuel d'abattage d'un arbre.
  79
  80 \item Grâce à une bonne gestion des forêts que la société exploite,
  81   il n'y a maintenant plus d'arbre tordu.
  82 \begin{enumerate}
  83 \item Montrer que le nouveau règlement d'abattage se traduit par la fonction
  84 $
  85 g(a,b,c) = ac + \overline{a}\overline{b} + bc
  86 $.
  87 \item A l'aide d'une table de Karnaugh, donner sans justifier
  88   l'expression $G$ qui
  89   est la forme la plus réduite de $g$.
  90
  91
  92 \item Écrire la nouvelle règle d'abattage d'un arbre sous la forme
  93   la plus simple possible.
  94 \end{enumerate}
  95 \end{enumerate}
  96
  97
  98
  99 \vspace{-1em}
 100 \section{(6 pts) Démonstrations ensemblistes}
 101 Soit $A$ et $B$ deux sous-ensembles de $\Omega$.
 102 \begin{enumerate}
 103 \item Soit $A_0=\{1,2,3\}$ et $B_0=\{3,4\}$.
 104 Définir en extension $A_0 \cup B_0$, $P(A_0)$, $P(B_0)$, $P(A_0\cup B_0)$ et
 105 $P(A_0) \cup P(B_0)$.
 106 \item A-t-on l'égalité $P(A \cup B) = P(A) \cup P(B)$? Justifier.
 107 \item Montrer que l'on a $P(A \cap B) = P(A) \cap P(B)$.
 108 \end{enumerate}
 109
 110
 111
 112 \vspace{-1em}
 113 \section{(6 pts) Relation entre puissances d'éléments}
 114
 115
 116 Sur $\N^*$ on définit la relation
 117 $a \mathcal{R} b$   si et seulement si
 118 $a^b \leq b ^a$.
 119
 120 \begin{enumerate}
 121 \item A-t-on $2 \mathcal{R} 3$? $2 \mathcal{R} 7$? $2 \mathcal{R} 4$? $4 \mathcal{R} 2$? Justifier à chaque fois.
 122
 123 \item La relation est-elle réflexive? Le démontrer.
 124
 125 \item La fonction logarithme népérien $\ln: \R^{+*} \rightarrow \R$ étant
 126   croissante, montrer que sur $\N^*$
 127   $$
 128   a \mathcal{R} b \textrm{ si et seulement si }
 129   \dfrac{\ln(a)}{a} \leq \dfrac{\ln(b)}{b}.
 130   $$
 131 \item La relation est-elle transitive? Pour justifier votre réponse, on
 132   pourra utiliser la question précédente.
 133 \item La relation est-elle antisymétrique? Le justifier.
 134 \end{enumerate}
 135
 136
 137
 138
 139
 140 \end{document}