\documentclass[12pt,a4paper,french]{article}
\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage{a4}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{framed}
\usepackage{dsfont}
\usepackage[amsmath,thmmarks,thref,framed]{ntheorem}
\usepackage[dvips]{graphics}
\usepackage{epsfig}
\usepackage{calc}
\usepackage{tabls}
%\usepackage{slashbox}
\usepackage{times}
\usepackage{multicol}
\usepackage{tabularx}
\usepackage{textcomp}
\usepackage{pst-all}
\usepackage[a4paper]{geometry}
\input{symboles.sty}

\geometry{hmargin=1cm, vmargin=1.5cm}
\title{Département d'informatique, partiel de Mathématiques discrètes\\  
Semestre 2, mars 2013, 2 heures.\\ 
}

\date{}

\begin{document}
\vspace{-7em}
\maketitle
\vspace{-5em}

\noindent Seule une fiche manuscrite RV de format A5 est autorisée. 

\section*{Relations particulières}

\subsection*{Exercice 1 :}
    On note $A$ l'ensemble des entiers de 1 à 6 ($A=\{1,2,3,4,5,6\}$).\\
    Soit l'application $f:A\longrightarrow A$ définie par le système suivant :\\
    $$\left\lbrace
    \begin{array}{ll}
    f(n)=n+3 & \mbox{si $n \leq 3$}\\
    f(n)=7-n & \mbox{sinon}
    \end{array}
    \right.$$  
    
    En admettant que $f$ est une bijection, compléter les tableaux de valeurs suivants :\\
    \\
    $\begin{array}{cc}
     \begin{tabular}{|l|l|l|l|l|l|l|l|}
    \hline
    $n$ & 1&2&3&4&5&6 \\ 
    \hline
    $f(n)$&  &  &  &  &  &  \\ 
    \hline
    \end{tabular}
   &
   \begin{tabular}{|l|l|l|l|l|l|l|l|}
    \hline
    $n$ & 1&2&3&4&5&6 \\ 
    \hline
    $f^{-1}(n)$&  &  &  &  &  &  \\ 
    \hline
    \end{tabular}
   
    \end{array}$

    
  \subsection*{Exercice 2 :}
  Dans cet exercice, on utilise l'application $f$ définie par :\\
  $$\begin{array}{clcl}
    f : & \mathbb{R} &\longrightarrow &\mathbb{R}\\
    \nonumber  & x &\longmapsto& \displaystyle{\frac{2x}{1+x^2}}
     \end{array}$$

  
    \begin{enumerate}
     \item Vérifier que $f$ est bien définie sur $\mathbb{R}$.
     \item Montrer que : \\
      $\forall x, x' \in \mathbb{R}, f(x')=f(x) \Rightarrow \left( \left( x'=x \right)
      \vee \left(\displaystyle{x'=\frac{1}{x}}\right) \right)$.
     \item L'application $f$ est-elle injective?
     \item Résoudre dans $\mathbb{R}$ l'équation $f(x)=3$.
     \item L'application $f$ est-elle surjective ?
    \end{enumerate}

  
\section*{Logique des propositions}

\subsection*{Exercice 3:}
%\subsection*{Tautologies, antilogie et autres}
Pour chacun des propositions suivantes, dire si c'est une tautologie, 
une antilogie ou ni l'une ni l'autre. Justifier.
\begin{enumerate}
\item 
$
\big( (\neg P \Rightarrow Q) \land 
(\neg P \Rightarrow \neg Q) \big)
\Rightarrow P.$
\item 
$
P \lor Q \Rightarrow
\big(
P \land( Q \Rightarrow Q)
\big).$
\item
$
\big(
( \neg Q \land P ) \Rightarrow ( Q \lor P )
\big)
\Rightarrow
\neg ( Q \lor P \lor \neg Q ).
$
\end{enumerate}

\subsection*{Exercice 4:}
%\subsection*{Formalisation de connecteurs logiques}
$A$ et $B$ sont des variables propositionnelles. Formaliser à l'aide 
de connecteurs logiques les énoncés suivants:
\begin{enumerate}
\item \og $A$ seulement si $B$. \fg{}
\item \og $B$ à moins que $A$.\fg{}
\item \og$B$, bien que $A$.\fg{}
\item \og $B$ est une condition nécessaire pour $A$.\fg{}
\end{enumerate}



\subsection*{Exercice 5:}
%\subsection*{Vers la logique propositionnelle}
Pour chaque phrase suivante, définir une variable propositionnelle pour 
chaque proposition élémentaire et formaliser ensuite la phrase
en  logique propositionnelle.
\begin{enumerate}
\item  \og Si le système fonctionne normalement, le noyau est en état de marche.\fg{}

\item \og  Le fait que le système ne soit pas en mode ``multi-user''
  est une condition suffisante pour être en mode ``interruption'.\fg{}
\item \og Le système est en mode ``multi-user'' seulement s'il fonctionne normalement.\fg{}
\item \og  Soit le noyau est en état de marche, soit le système est en mode ``interruption''.\fg{}
\end{enumerate}



%\subsection*{Exercice 6:}
%\subsection*{Conséquences logiques}
%Dire si chacune des deux propositions suivantes est vraie en justifiant:
%\begin{enumerate}
%\item $\{B \Rightarrow C\lor D, 
%  C \Rightarrow \neg A \land \neg B,
%  \} \models
%  B \Rightarrow \neg C \land  D.$
%\item $\{A \Rightarrow B \land C, 
%  \neg D  \land \neg E \Rightarrow \neg B,
%  D \Rightarrow \neg C \land B \} \models 
%  (E \Rightarrow \neg B) \Rightarrow \neg A.$
%\end{enumerate}

  



\subsection*{Exercice 6:}
%\subsection*{L'Île de Puro Pira}
L'île de Puro Pira est peuplée 
de \emph{Purs} qui disent toujours la vérité et de 
de \emph{Pires} qui ne disent que des mensonges.
Débarqué sur l'île, l'anthropologue Abercrombie rencontre trois indigènes Alice, Bernard et Chloé.
\begin{enumerate}
\item\label{item1} Alice affirme \og C’est moi le chef\fg{}. 
\item\label{item2} Bernard affirme aussi \og C’est moi le chef\fg{}. 
\item Quant à Chloé elle ajoute \og Au plus l’un de nous trois dit la vérité.\fg{}
\end{enumerate}
On sait de plus qu'il n'y a qu'un seul chef. Par la suite:
\begin{itemize}
\item $A$, $B$ et $C$ sont les variables propositionnelles qui valent chacune 
  vrai si et seulement si Alice est un pur, Bernard est un pur et Chloé est un pur respectivement; 
\item $Ac$, $Bc$ et $Cc$ sont les variables propositionnelles qui 
  valent chacune vrai si et seulement si Alice est un chef, Bernard est un chef
  et Chloé est un chef respectivement?
\end{itemize}


\begin{enumerate}
\item Montrer que l'affirmation \og il n'y a qu'un seul chef \fg{} 
  peut se représenter par la formule: 
  $$ (Ac \lor Bc \lor Cc) \land 
  \neg (Ac \land Bc) \land \neg (Ac \land Cc) \land \neg (Bc \land Cc).
  $$ 
\item Montrer que l'affirmation de Chloé peut se représenter par la formule:
  $$
  (C \Rightarrow \neg A \land \neg B ) \land
  (\neg C \Rightarrow A \land B ).
  $$
\item Traduire en logique propositionnelle les propositions des 
  items~\ref{item1}. et~\ref{item2}. relatives aux affirmations d'Alice et 
  Bernard.  
\item (Bonus) Montrer que le status en termes de chef, purs, pires, 
  de chacun des indigène peut se déduire comme 
  une conséquence logique de ces quatre formules. 
\end{enumerate}  

\end{document}

