From b2ebfe30883d87d73ffc39392a3173e64bdf60b5 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Jean-Fran=C3=A7ois=20Couchot?= Date: Wed, 13 Mar 2013 21:05:26 +0100 Subject: [PATCH] ajout d'un partiel --- partiels/130311S2/main.tex | 208 +++++++++++++++++++++++ partiels/130311S2/symboles.sty | 293 +++++++++++++++++++++++++++++++++ 2 files changed, 501 insertions(+) create mode 100644 partiels/130311S2/main.tex create mode 100755 partiels/130311S2/symboles.sty diff --git a/partiels/130311S2/main.tex b/partiels/130311S2/main.tex new file mode 100644 index 0000000..d23e8fb --- /dev/null +++ b/partiels/130311S2/main.tex @@ -0,0 +1,208 @@ +\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 7:} +%\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 A l'aide de la méthode de résolution trouver le statut de chaque +indigène. +\item 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. Le déduire. +\end{enumerate} + +\end{document} \ No newline at end of file diff --git a/partiels/130311S2/symboles.sty b/partiels/130311S2/symboles.sty new file mode 100755 index 0000000..40d3100 --- /dev/null +++ b/partiels/130311S2/symboles.sty @@ -0,0 +1,293 @@ + +%___________________ PARAGRAPHES ___________________ + +\let\sx\section +\let\ssx\subsection +\let\sssx\subsubsection + +%___________________ STYLES __________________________ + +\let\ts=\textstyle +\let\ds=\displaystyle +\let\ssc=\scriptstyle +\let\sss=\scriptscriptstyle + +\let\dl=\displaylines + +\let\sou=\underline +\let\sur=\overline + +% \font\large=cmr12 +\font\grand=cmr12 +\font\giga=cmr17 + +%______ EXPOSANTS, INDICES EN MODE NON MATH _________ + +\def\up#1{\raisebox{1ex}{{\scriptsize #1}}} +\def\down#1{\raisebox{-1ex}{{\scriptsize #1}}} +\def\no{n\up{$\circ$}} + +%__________ ENCADREMENTS , TRAITS DIVERS _____________________ + +\def\entoure#1#2{\setbox1=\hbox{\kern#1{#2}\kern#1}% +\dimen1=\ht1 \advance\dimen1 by #1 \dimen2=\dp1 +\advance\dimen2 by #1 +\setbox1=\hbox{\vrule height\dimen1 +depth\dimen2\box1\vrule}% +\setbox1=\vbox{\hrule\box1\hrule}% +\advance\dimen1 by .4pt \ht1=\dimen1 +\advance\dimen2 by .4pt \dp1=\dimen2 \box1\relax} + +\def\x#1{\entoure{4pt}{#1}} + +\def\cvirp{\raise 2pt\hbox{,}} + +\def\cqfd{\unskip\kern 6pt\penalty 500\raise +-2pt\hbox{\vrule\vbox to 10pt{\hrule width +4pt\vfill\hrule}\vrule}\par} + +\def\clv{\hbox{\vrule\vbox to 6 pt{\hrule width +4pt\vfill\hrule}\vrule}} + +\def\trait {\hrule height 1pt depth 0pt} + +\def\traith {\hrule height 1pt depth 0pt} +\def\traitb {\hrule height 0pt depth 1pt} + +\def\tvi#1#2{\vrule height #1 pt depth #2 pt width 0pt} +\def\tvii#1{\vrule height #1 pt depth 5pt width 0pt} +\def\tv{\tvii{12}\vrule} +\def\ttv{\left\Vert\tvi{12}\right.} + +%____________ INF OU EGAL __________________________ + +\let\infeg\leqslant +\let\supeg\geqslant + +%____________ SUPERPOSITION DE SYMBOLES _____________ + +\def\superpose#1_#2^#3{\mathrel{\mathop{\kern +0pt#1}\limits_{#2}^{#3}}} + +\def\fr #1#2{\ds {\raise -2pt\hbox{$#1$}\over + \raise 2pt\hbox{$#2$}}} + +%______ Lignes de titre _________________ + +\def\ligne#1#2{#1 \hfill #2} +\def\titre#1{\centerline{\entoure{5pt}{\bf #1}}} + +%__________ N, Z, Q, R, C __________ + +\def\nmat{\hbox{\it I\hskip -2pt N}} +\def\zmat{\hbox{\it Z\hskip -4pt Z}} +\def\qmat{\hbox{\it l\hskip -5.5pt Q}} +\def\rmat{\hbox{\it I\hskip -2pt R}} +\def\cmat{\hbox{\it l\hskip -5.5pt C\/}} + +\def\N{{\mathbb N}} +\def\Net{{\mathbb N}^*} +\def\Z{{\mathbb Z}} +\def\Q{{\mathbb Q}} +\def\R{{\mathbb R}} +\def\Ret{{\mathbb R}^*} +\def\Rpl{{\mathbb R}_+} +\def\Rplet{{\mathbb R}_+^*} +\def\Rmn{{\mathbb R}_-} +\def\Rmnet{{\mathbb R}_-^*} +\def\C{{\mathbb C}} +\def\K{{\mathbb K}} +\def\D{{\mathbb D}} + +%__________ FLECHES ET LOGIQUE __________ + +\let\fc=\longmapsto % pour "x donne f(x)" +\let\vers=\rightarrow % pour "tend vers" +\let\flg=\leftarrow % fleche simple courte vers la gauche +\let\rec=\longleftarrow % symbole d'affectation +\let\Rec=\Longleftarrow % fleche double longue vers la gauche +\let\Imp=\Rightarrow % implique (double barre) +\let\Ssi=\Leftrightarrow % est equivalent a (double barre) + +\let\ou=\vee % disjonction logique +\let\et=\wedge % conjonction logique +\let\non=\neg % negation logique +\let\imp=\Rightarrow % implication logique +\let\ssi=\Longleftrightarrow % equivalence logique +\let\eqv=\Longleftrightarrow + +\let\qqs=\forall % quantificateur universel +\let\exi=\exists % quantificateur existentiel + +\let\theor=\vdash % déduction +\let\tauto=\models % conséquence logique +\def\vrai{\textit{vrai}} % vrai +\def\faux{\textit{faux}} % faux + + + +%___________ COMBINATOIRE ET ENSEMBLES ______________ + +\def\cnp{\mathop{\raise -1pt\hbox{\large C}}\nolimits} +\def\card{\mathop{\rm Card}\nolimits} + +\let\vide=\emptyset +\def\void{\not{\kern -1.55pt\rm o}} + +\let\union=\cup +\let\inter=\cap +\let\moins=\setminus +\let\sse=\subset + +\def\enspart#1{{\cal P}(#1)} + +\def\rest#1#2{{#1}_{\left|\mathstrut #2\right.}} +\def\idl#1{{\goth #1}} + +%__________ TOPO ____________________________ + +\def\min{\mathop{\rm Min}\limits} +\def\max{\mathop{\rm Max}\limits} +\def\sup{\mathop{\rm Sup}\limits} +\def\inf{\mathop{\rm Inf}\limits} + +\let\nor=\Vert % norme +\def\nme#1{\nor #1\nor} +\def\trnme#1{|||#1|||} % "triple" norme +\def\nmex#1{\left|\!\left|#1\right|\!\right|} + % norme extensible + +\let\Inf=\infty % infini +\def\plinf{{+\infty}} % plus l'infini +\def\moinf{{-\infty}} % moins l'infini + +\def\Rpl{\R_{\sss +}} % double R plus +\def\Rmo{\R_{\sss -}} % double R moins + +\def\intr#1{\,\buildrel{\kern 2pt\circ}\over{#1}} % int�rieur + +%_____________________ FONCTIONS _______________________ + +\def\tg{\mathop{\rm tg}\nolimits} +\def\arcsin{\mathop{\rm Arcsin}\nolimits} +\def\arccos{\mathop{\rm Arccos}\nolimits} +\def\arctg{\mathop{\rm Arctg}\nolimits} +\def\ch{\mathop{\rm ch}\nolimits} +\def\sh{\mathop{\rm sh}\nolimits} +\def\th{\mathop{\rm th}\nolimits} +\def\argsh{\mathop{\rm Argsh}\nolimits} +\def\argch{\mathop{\rm Argch}\nolimits} +\def\argth{\mathop{\rm Argth}\nolimits} +\def\log{\mathop{\rm ln}\nolimits} +\def\Log{\mathop{\rm Log}\nolimits} +\def\E{\mathop{\rm E}\nolimits} % partie entiere +\def\e{\mathop{\rm e}\nolimits} % exponentielle + +%______________ ANALYSE _______________ + +\def\cl{{\cal C}} % classe d'une fonction + +\def\intint{\int\!\!\!\!\int} % int. double +\def\intintint{\int\!\!\!\!\int\!\!\!\!\int} % int. triple + +\let\dep=\partial % d rond +\def\ddr{{\rm d\,}} % d droit +\def\dpar#1#2{\fr{\partial#1}{\partial#2}} % d rond #1 sur d rond #2 +\def\dtot#1#2{\fr{{\rm d}#1}{{\rm d}#2}} % d droit #1 sur d droit #2 + +\def\ste#1#2#3{\left(#1_#2\right)_{#2\in #3}} +\def\sten#1#2{\ste{#1}{#2}\N} +\def\stenet#1#2{\ste{#1}{#2}{\N^*}} +\def\stenn#1{\sten{#1}n} +\def\stennet#1{\stenet{#1}n} + +%______________ ALGEBRE _______________ + +\def\Re{{\goth Re}} +\def\Im{{\goth Im}} + +\def\deg{\mathop{\hbox{d\up{o}}}\nolimits} + +%_______________ ALGEBRE LINEAIRE ______________________ + +\def\com{\mathop{\rm Com}\nolimits} +\def\det{\mathop{\rm D\acute e t}\nolimits} +\def\dim{\mathop{\rm dim}\nolimits} +\def\ker{\mathop{\rm Ker}\nolimits} +\def\id{\mathop{\rm id}\nolimits} +\def\im{\mathop{\rm Im}\nolimits} +\def\tr{\mathop{\rm Tr}\limits} +\def\vect{\mathop{\rm Vect}\nolimits} +\def\rang{\mathop{\rm rang}\nolimits} +\def\diag{\mathop{\rm diag}\nolimits} +\def\sp{\mathop{\rm Sp}\nolimits} +\def\GL#1#2{{\cal GL}_{#1}(#2)} +\def\gl#1{{\cal GL}(#1)} +\def\mat#1#2{{\rm Mat}\,\left(#1\vir#2\right)} +\def\matb#1#2#3{{\rm Mat}\left(#1\vir#2\vir#3\right)} +\def\matbb#1{{\rm Mat}_{\cal B}\left(#1\right)} +\def\matcar#1#2{{\cal M}_{#1}\left(#2\right)} +\def\mn#1{\matcar n{#1}} +\def\matrect#1#2#3{{\cal M}_{#1,#2}\left(#3\right)} +\def\apl#1#2{{\cal L}\left(#1,#2\right)} +\def\aplr#1#2{{\cal L}\left(\R^#1,\R^#2\right)} +\def\endo#1{{\cal L}\left(#1\right)} +\def\endor#1{{\cal L}\left(\R^#1\right)} +\def\nul#1{0_{#1}} +\def\endonul#1{O_{{\cal L}(#1)}} +\def\evnul#1{\left\{\nul#1\right\}} +\def\fami#1#2{({#2}_1\,,\,{#2}_2\,,\,\ldots\,,\,{#2}_{#1})} +\def\famn#1{\fami{n}{#1}} + +%_____ POUR MATRICES, points parall�les � diag 2 _____ + +\def\adots{\mathinner{\mkern2mu\raise1pt\hbox{.} +\mkern3mu\raise4pt\hbox{.}\mkern1mu\raise7pt\hbox{.}}} + +%__________ GEOMETRIE _______________________________ + +\def\grad{\mathop{\rm grad}\nolimits} +\def\so{\mathop{\cal SO}\nolimits} +\def\og#1{{\cal O}(#1)} +\let\vc=\overrightarrow + +\def\arc#1{\buildrel\frown\over{#1}} +\def\arcfl#1{\buildrel{\ds\bb y}\over{#1}} + +\def\pscal#1#2{\langle #1\vir #2\rangle} + +%__________ ARITHMETIQUE _______________________________ + +\def\mod{\mathop{\rm mod}\nolimits} +\def\dv{\mathop{\rm div}\nolimits} + +%__________ Programmes _______________ + +\def\prol{\parindent=1cm\obeylines\tt } +\def\dec {\advance\parindent by 1cm} + +\def\prog#1{\advance\parindent by #1 cm\obeylines\tt} +\def\ind#1{\advance\parindent by #1 cm} + +%__________ en-dessus, au-dessous d'un symbole __________ + +\def\build#1_#2^#3{\mathrel{ +\mathop{\kern 0pt#1}\limits_{#2}^{#3}}} + +%____________________ DIVERS ____________________________ + +\def\bs{\char"5C} % le backslash !!! + +\def\vir{\,,\,} \def\cdotv{\raise 2pt\hbox{,}} + +\def\jbar{\sur{\mathstrut\,j\,}} + +\def\psaut{\vskip 2pt} +\def\saut{\vskip 5pt} +\def\gsaut{\vskip 8pt} +\def\Saut{\vskip 8pt} + +\def\fin{\gsaut\centerline{\hbox to 3cm{\hrulefill}}} + +\def\nopagenumbers{\def\folio{\hfil}} + -- 2.39.5