\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, tmargin=-0.5cm, bmargin=1.5cm}

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

\date{}

\begin{document}
\maketitle

\vspace{-3em}
\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$.


\vspace{-1em}
\section{Cours (3pts) }

\begin{enumerate}
\item Soit $A$ et $B$ deux ensembles d'un 
univers $\Omega$ tels que $A \subseteq B$. Définir $B\setminus A$ en compréhension.
\item L'ensemble vide appartient-il à tout ensemble? Justifier.
\end{enumerate}




\vspace{-1em}
\section{(5 pts) Simplification de formules booléennes (d'après sujet de BTS-IG-2008)}
La société Jurabois exploite des forêts d'arbres constituées exclusivement de
feuillus et de résineux. Elle désire simplifier le règlement que les salariés 
doivent appliquer pour la coupe du bois.
Actuellement, le règlement dit qu'un arbre est à abattre dans les quatre cas 
suivants:
\begin{itemize}
\item si c'est un résineux au tronc droit mesurant plus de 20 m de hauteur;
\item si c'est un feuillus de 50 ans ou plus;
\item s'il a moins de 50 ans et mesure plus de 20 m de hauteur;
\item s'il est tordu. 
\end{itemize}
Pour un arbre quelconque, on définit les variables booléennes suivantes:
\begin{itemize}
\item $a=1$ si l'arbre est un résineux;
\item $b=1$ si l'arbre a moins de 50 ans;
\item $c=1$ si l'arbre mesure plus de 20 m de hauteur;
\item $d=1$ si l'arbre est tordu.
\end{itemize}


\begin{enumerate}
\item Écrire sans justifier 
  la fonction booléenne $f(a,b,c,d)$ qui traduit le règlement 
  actuel d'abattage d'un arbre. 

\item Grâce à une bonne gestion des forêts que la société exploite,
  il n'y a maintenant plus d'arbre tordu.
\begin{enumerate}
\item Montrer que le nouveau règlement d'abattage se traduit par la fonction 
$
g(a,b,c) = ac + \overline{a}\overline{b} + bc
$.
\item A l'aide d'une table de Karnaugh, donner sans justifier 
  l'expression $G$ qui 
  est la forme la plus réduite de $g$. 


\item Écrire la nouvelle règle d'abattage d'un arbre sous la forme 
  la plus simple possible.
\end{enumerate}
\end{enumerate}



\vspace{-1em}
\section{(6 pts) Démonstrations ensemblistes}
Soit $A$ et $B$ deux sous-ensembles de $\Omega$. 
\begin{enumerate}
\item Soit $A_0=\{1,2,3\}$ et $B_0=\{3,4\}$. 
Définir en extension $A_0 \cup B_0$, $P(A_0)$, $P(B_0)$, $P(A_0\cup B_0)$ et 
$P(A_0) \cup P(B_0)$.
\item A-t-on l'égalité $P(A \cup B) = P(A) \cup P(B)$? Justifier.
\item Montrer que l'on a $P(A \cap B) = P(A) \cap P(B)$. 
\end{enumerate}



\vspace{-1em}
\section{(6 pts) Relation entre puissances d'éléments}


Sur $\N^*$ on définit la relation
$a \mathcal{R} b$   si et seulement si
$a^b \leq b ^a$.

\begin{enumerate}
\item A-t-on $2 \mathcal{R} 3$? $2 \mathcal{R} 7$? $2 \mathcal{R} 4$? $4 \mathcal{R} 2$? Justifier à chaque fois.

\item La relation est-elle réflexive? Le démontrer. 

\item La fonction logarithme népérien $\ln: \R^{+*} \rightarrow \R$ étant 
  croissante, montrer que sur $\N^*$
  $$
  a \mathcal{R} b \textrm{ si et seulement si }
  \dfrac{\ln(a)}{a} \leq \dfrac{\ln(b)}{b}.
  $$
\item La relation est-elle transitive? Pour justifier votre réponse, on 
  pourra utiliser la question précédente.
\item La relation est-elle antisymétrique? Le justifier.
\end{enumerate}





\end{document}
