\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{tabularx}
\usepackage{multicol}
\usepackage{textcomp}

\usepackage{pst-all}

\usepackage[a4paper]{geometry}

\input{symboles.sty}

\geometry{hmargin=1cm, vmargin=1.5cm}

\title{
Département d'informatique (décembre 09).\\
Partiel de mathématiques discrètes. Semestre 1}

\date{}

\begin{document}

\vspace{-5em}
\maketitle


\vspace{-5em}
\noindent Seule une fiche manuscrite de format A5 est autorisée.\\ 


\section{QCM}

Q. 1. Dans la formule
$(\forall x\,.\, p(x) \Rightarrow q(x)) \land r(x)$, la variable 
$x$ admet une occurence libre.
 L'assertion proposée est vraie ou fausse?

Q. 2. La négation de 
$(\forall x \, . \, p(x) \Rightarrow q(x))$ est 
$\exists x \, . \, p(x) \land \neg q(x)$.
L'assertion proposée est vraie ou fausse?

Q. 3. 
Soit la démonstration  syntaxique suivante: 
\begin{multicols}{2}
\begin{tabular}{lll}
\multicolumn{3}{l}{Démonstration}\\
1.&$\neg B \Rightarrow \neg A$ &$H_1$ \\
2.&$A$ &$H_2$ \\
3.&\_\_\_\_\_ &\_\_\_\_\_ \\
4.&\_\_\_\_\_ &\_\_\_\_\_ \\
5.&$\neg\neg B$ &réduction de l'absurde entre 4. et 1. \\
6.&$\neg \neg B \Rightarrow B$ &Axiome 9.\\
7.& $B$ &mp entre 5. et 6.
\end{tabular}
Si elle était complète cela permetrait de
démontrer syntaxiquement
$(\neg B \Rightarrow \neg A) \Rightarrow (A \Rightarrow B).
$
L'assertion proposée est vraie ou fausse ?
\end{multicols} 

Q. 4. On considère les prédicats et constantes suivants avec leur interprétation sur un univers constitué d'individus humains.

\begin{center}
\begin{tabular}{|r|l|}
\hline
 prédicat & sens \\
\hline
$\textit{aime}(x,y)$                 & $x$ aime $y$ \\
$\textit{maries}(x,y)$                & $x$ et $y$ sont mariés  \\
$\textit{femme}(x)$                  & $x$ est une femme \\
$\textit{homme}(x)$                  & $x$ est un  homme \\
$\textit{fidele}(x)$                 & $x$ est fidèle \\
$\textit{honete}(x)$                 & $x$ dit la vérité \\
$a$                                  & Alice \\
$b$                                  & Bob \\
$c$                                  & Clinton \\
\hline
\end{tabular}
\end{center}

$
\exists x,y  \, . \, (
       \textit{maries}(x,y) \land
  \neg \textit{aime}(x,y) \land
  \neg \textit{aime}(y,x))
$
peut se traduire en
\og dans certains couples, un conjoint n'aime pas l'autre \fg.
L'assertion proposée est vraie ou fausse ? 

Q. 5. 
Soit \textit{dodec} le prédicat unaire qui est vrai si son paramètre est un dodécaèdre, 
\textit{cube} le prédicat unaire qui est vrai si son paramètre est un cube, 
\textit{petit} le prédicat unaire qui est vrai si son paramètre est petit,
\textit{entre} le prédicat ternaire qui est vrai si son premier paramètre est entre le second et le troisième
et 
\textit{devant} le prédicat binaire qui est vrai si son premier paramètre est devant son second paramètre. 
\og les seuls grands cubes sont b et c \fg{} peut-elle se traduire en 
$
\forall x \, .\, 
(\neg petit(x) \land cube(x)) 
\leftrightarrow 
 ( x = b \lor  x = c).
$
L'assertion proposée est vraie ou fausse?

Q. 6. On considère les prédicats et constantes suivants avec leur interprétation sur un univers constitué d'individus humains.

\begin{center}
\begin{tabular}{|r|l|}
\hline
 prédicat & sens \\
\hline
$\textit{aime}(x,y)$                 & $x$ aime $y$ \\
$\textit{maries}(x,y)$                & $x$ et $y$ sont mariés  \\
$\textit{femme}(x)$                  & $x$ est une femme \\
$\textit{homme}(x)$                  & $x$ est un  homme \\
$\textit{fidele}(x)$                 & $x$ est fidèle \\
$\textit{honete}(x)$                 & $x$ dit la vérité \\
$a$                                  & Alice \\
$b$                                  & Bob \\
$c$                                  & Clinton \\
\hline
\end{tabular}
\end{center}
$
\exists x \, . \, (\forall y \, . \,
  \textit{homme}(x) \land
 (\textit{femme}(y) \Rightarrow
  \textit{aime}(x,y))
$
peut se traduire en \og certains hommes sont aimés de toutes les femmes \fg.
L'assertion proposée est vraie ou fausse ? 

Q. 7. La formule
$(\forall x\,.\, (\exists y\,.\, p(x) \land p(y))$ est équivalente à 
$(\forall y\,.\, (\exists x\,.\, p(y) \land p(x))$.
L'assertion proposée est vraie ou fausse?

Q. 8. La négation de 
$(\exists y \, . \, p(y) \land \neg q(y))$ est 
$(\forall y \, . \, \neg p(y) \lor \neg   q(y))$.
L'assertion proposée est vraie ou fausse?

Q. 9.  On considère la proposition 
$
  (A \Rightarrow B) \Rightarrow 
  ((A \Rightarrow C) \Rightarrow (A \Rightarrow B \land C))
$
Il existe une démonstration syntaxique sous hypothèses  qui prouve que cette proposition est un théorème. L'assertion proposée est vraie ou fausse ?


Q. 10. 
Soit \textit{dodec} le prédicat unaire qui est vrai si son paramètre est un dodécaèdre, 
\textit{cube} le prédicat unaire qui est vrai si son paramètre est un cube, 
\textit{petit} le prédicat unaire qui est vrai si son paramètre est petit,
\textit{entre} le prédicat ternaire qui est vrai si son premier paramètre est entre le second et le troisième
et 
\textit{devant} le prédicat binaire qui est vrai si son premier paramètre est devant son second paramètre. 
\og Il y a au moins deux objets qui n’ont rien derrière eux \fg{} peut-elle se traduire en 
$
\exists x,y\, .\,  
x \neq y \land
 (\forall w\, .\, (w = x \lor  w = y) \rightarrow (\forall z  ¬devant(z, w))).
$
L'assertion proposée est vraie ou fausse?

Q. 11. La formule
$\forall x \,.\, x > 0 \Rightarrow
  (\exists y \, . \, e^y = x )
$
est vraie sur l'univers $\mathds{R}$.
L'assertion proposée est vraie ou fausse ? 

Q. 12. 
Soit $a$ et $b$ des symboles de constante,
$f$ un symbole de fonction unaire,
$g$ un symbole de fonction binaire et
$S$ un symbole de relation binaire. 
L'expression $g(a,f(b))$  contient quatre termes.
L'assertion proposée est vraie ou fausse ?

Q. 13. 
Soit la démonstration  syntaxique suivante:
\begin{multicols}{2}
\begin{center}
\begin{tabular}{lll}
\multicolumn{3}{l}{Démonstration sous hypothèses 
$\{\neg B \Rightarrow \neg A, A\}$}\\
1.& $\neg B \Rightarrow \neg A$ &$H_1$ \\
2.&$A$ &$H_2$ \\
3.&\_\_\_\_\_ &\_\_\_\_\_ \\
4.&\_\_\_\_\_ &\_\_\_\_\_ \\
5.&$\neg\neg B$ &réduction de l'absurde entre 4. et 1. \\
6.&$\neg \neg B \Rightarrow B$ &Axiome 9 ($B/P$).\\
7.& $B$ &mp entre 5. et 6.\\
Conclusion
\end{tabular}
\end{center}
Si elle était complète cela permetrait
démontrer syntaxiquement le théorème de la contraposée. Vrai ou faux ?
\end{multicols} 

Q. 14. 
Soit $a$ et $b$ des symboles de constante,
$f$ un symbole de fonction unaire,
$g$ un symbole de fonction binaire et
$S$ un symbole de relation binaire. 
L'expression $S(f(a),g(x,f(y)))$ est un terme complexe. L'assertion proposée est vraie ou fausse ?

Q. 15. On considère les prédicats et constantes suivants avec leur interprétation sur un univers constitué d'individus humains.

\begin{center}
\begin{tabular}{|r|l|}
\hline
 prédicat & sens \\
\hline
$\textit{aime}(x,y)$                 & $x$ aime $y$ \\
$\textit{maries}(x,y)$                & $x$ et $y$ sont mariés  \\
$\textit{femme}(x)$                  & $x$ est une femme \\
$\textit{homme}(x)$                  & $x$ est un  homme \\
$\textit{fidele}(x)$                 & $x$ est fidèle \\
$\textit{honete}(x)$                 & $x$ dit la vérité \\
$a$                                  & Alice \\
$b$                                  & Bob \\
$c$                                  & Clinton \\
\hline
\end{tabular}
\end{center}
\og L'époux qui aime son épouse lui est fidèle \fg peut se traduire en
$
\forall x,y \, . \,
\textit{homme}(x) \land
\textit{femme}(y) \land
\textit{maries}(x,y) \land
\textit{aime}(x,y) \land
\textit{aime}(y,x).
$
L'assertion proposée est vraie ou fausse ? 

Q. 16. 
Soit $x$ et $y$ des entiers naturels.
$\forall x \, .\, (\exists y \, .\, x +y \ge x +1 )$
est vraie.
L'assertion proposée est vraie ou fausse ? 

Q. 17. 
Soit \textit{dodec} le prédicat unaire qui est vrai si son paramètre est un dodécaèdre, 
\textit{cube} le prédicat unaire qui est vrai si son paramètre est un cube, 
\textit{petit} le prédicat unaire qui est vrai si son paramètre est petit,
\textit{entre} le prédicat ternaire qui est vrai si son premier paramètre est entre le second et le troisième
et 
\textit{devant} le prédicat binaire qui est vrai si son premier paramètre est devant son second paramètre. 
Dans la formule suivante $y$ et $u$ ont des occurences libres
$
\forall x \, . \, 
\textit{dodec}(x) \lor  devant(x, y) \Rightarrow 
(
(\exists y \, .\, cube(y) \land \neg devant(x, y)) 
\land  entre(u,y,x).
)
$
L'assertion proposée est vraie ou fausse?

Q. 18. La négation de 
$(\exists y \, . \, p(y) \land \neg q(y))$ est 
$(\forall y \, . \, \neg p(y) \lor  q(y))$.
L'assertion proposée est vraie ou fausse?

Q. 19. Si j'étudie, je n'échoue pas en maths,
si je ne joue pas au basket-ball, alors j'étudie,
mais j'ai échoué en mathématiques.
Donc, j'ai joué au basket-ball.
Le raisonnement proposé est-il incorrect?
      
Q. 20. 
Soit $a$ et $b$ des symboles de constante,
$f$ un symbole de fonction unaire,
$g$ un symbole de fonction binaire et
$S$ un symbole de relation binaire. 
L'expression $g(a,f(b))$
contient 1 seul termeL'assertion proposée est vraie ou fausse ?

Q. 21. La formule
$\forall x \,.\, x > 0 \Rightarrow
  (\exists y \, . \, e^y = x)
$
est vraie sur l'univers $\mathds{N}$.
L'assertion proposée est vraie ou fausse ? 

Q. 22. 
Soit \textit{dodec} le prédicat unaire qui est vrai si son paramètre est un dodécaèdre, 
\textit{cube} le prédicat unaire qui est vrai si son paramètre est un cube, 
\textit{petit} le prédicat unaire qui est vrai si son paramètre est petit,
\textit{entre} le prédicat ternaire qui est vrai si son premier paramètre est entre le second et le troisième
et 
\textit{devant} le prédicat binaire qui est vrai si son premier paramètre est devant son second paramètre. 
Les formules
$
\exists x \, .\, dodec(x) \land petit(x)$ et  
$
\exists x \, .\, dodec(x) \Rightarrow petit(x)
$
n'ont jamais la même valeur de vérité.
L'assertion proposée est vraie ou fausse?

Q. 23. Si je travaille, je ne peux pas étudier;
Soit je travaille, soit je suis reçu en mathématiques;
j'ai été reçu en mathématiques.
Donc j'ai étudié.
 Le raisonnement proposé est-il incorrect?
      
Q. 24. La formule
$(\forall x\,.\, (\exists y\,.\, p(x) \land q(y))$ est équivalente à 
$(\exists y\,.\, (\forall x\,.\, p(x) \land q(y))$. L'assertion proposée est vraie ou fausse?

Q. 25. 
Soit \textit{dodec} le prédicat unaire qui est vrai si son paramètre est un dodécaèdre, 
\textit{cube} le prédicat unaire qui est vrai si son paramètre est un cube, 
\textit{petit} le prédicat unaire qui est vrai si son paramètre est petit,
\textit{entre} le prédicat ternaire qui est vrai si son premier paramètre est entre le second et le troisième
et 
\textit{devant} le prédicat binaire qui est vrai si son premier paramètre est devant son second paramètre. 
Dans la formule suivante toutes les occurences de $x$ sont liées.
$
\forall x \, . \, 
\textit{dodec}(x) \lor  devant(x, y) \Rightarrow 
(
(\exists y \, .\, cube(y) \land \neg devant(x, y)) 
\land  entre(u,y,x)
)
.$ 
L'assertion proposée est vraie ou fausse?

Q. 26. Pour l'anniversaire de mon épouse, je lui offre des fleurs;
soit il s'agit de l'anniversaire de mon épouse, soit je rentre tard;
aujourd'hui, je n'apporte pas de fleurs à mon épouse.
Donc aujourd'hui, je rentre tard.
 Le raisonnement proposé est-il correct?
      
Q. 27. 
En logique des propositions, $P$ se déduit syntaxiquement de
$H_1$, \ldots, $H_n$ si et seulement si
$P$ est une conséquence logique de $H_1$, \ldots, $H_n$.
L'assertion proposée est vraie ou fausse ? 

Q. 28. On considère les prédicats et constantes suivants avec leur interprétation sur un univers constitué d'individus humains.

\begin{center}
\begin{tabular}{|r|l|}
\hline
 prédicat & sens \\
\hline
$\textit{aime}(x,y)$                 & $x$ aime $y$ \\
$\textit{maries}(x,y)$                & $x$ et $y$ sont mariés  \\
$\textit{femme}(x)$                  & $x$ est une femme \\
$\textit{homme}(x)$                  & $x$ est un  homme \\
$\textit{fidele}(x)$                 & $x$ est fidèle \\
$\textit{honete}(x)$                 & $x$ dit la vérité \\
$a$                                  & Alice \\
$b$                                  & Bob \\
$c$                                  & Clinton \\
\hline
\end{tabular}
\end{center}
\og Chaque époux aiment son épouse et réciproquement \fg peut se  traduire en
$
\forall x,y \, . \,
(\textit{homme}(x) \land
\textit{femme}(y) \land
\textit{maries}(x,y)) \Rightarrow
(\textit{aime}(x,y) \land
\textit{aime}(y,x)).
$
L'assertion proposée est vraie ou fausse ?


Q. 29. 
Soit \textit{dodec} le prédicat unaire qui est vrai si son paramètre est un dodécaèdre, 
\textit{cube} le prédicat unaire qui est vrai si son paramètre est un cube, 
\textit{petit} le prédicat unaire qui est vrai si son paramètre est petit,
\textit{entre} le prédicat ternaire qui est vrai si son premier paramètre est entre le second et le troisième
et 
\textit{devant} le prédicat binaire qui est vrai si son premier paramètre est devant son second paramètre. 
\og si un cube a quelque chose devant lui alors il est petit \fg{} peut-elle se traduire en 
$
\forall x\, .\, 
( \exists y \, . \, cube(x) \land devant(x,y)) 
\Rightarrow  
petit(x)
.$ 
L'assertion proposée est vraie ou fausse?

Q. 30. 
Dans la formule
$(\forall x \, . \, x \ge 5) \land (\exists y \, . \, y \ge x)$
toutes les coccurences de la variable $x$ sont liées.
L'assertion proposée est vraie ou fausse ? 

Q. 31. 
Soit $x$ et $y$ des entiers naturels.
$\exists x \, .\, ( \forall y \, . \,  y  \neq x \Rightarrow  x  <1 )$
est vraie.
L'assertion proposée est vraie ou fausse ? 

Q. 32. 
En logique des propositions,
il est possible de déduire que $P$ est vraie chaque fois que
$H_1$, \ldots, $H_n$ le sont par la méthode des tables de vérités sans
qu'il n'existe nécessairement de démonstration syntaxique permettant
d'établir $P$ à partir des hypothèses $H_1$, \ldots, $H_n$.
L'assertion proposée est vraie ou fausse ? 

Q. 33. On considère les prédicats et constantes suivants avec leur interprétation sur un univers constitué d'individus humains.


\begin{center}
\begin{tabular}{|r|l|}
\hline
 prédicat & sens \\
\hline
$\textit{aime}(x,y)$                 & $x$ aime $y$ \\
$\textit{maries}(x,y)$                & $x$ et $y$ sont mariés  \\
$\textit{femme}(x)$                  & $x$ est une femme \\
$\textit{homme}(x)$                  & $x$ est un  homme \\
$\textit{fidele}(x)$                 & $x$ est fidèle \\
$\textit{honete}(x)$                 & $x$ dit la vérité \\
$a$                                  & Alice \\
$b$                                  & Bob \\
$c$                                  & Clinton \\
\hline
\end{tabular}
\end{center}
\og Les femmes aiment toujours les hommes fidèles et qui dis.nt la vérité \fg peut se traduire en
$
\forall x,y \, . \,
(\textit{homme}(x) \land
\textit{femme}(y) \land
\textit{fidele}(x) \land
\textit{honete}(x)
) \Rightarrow
\textit{aime}(y,x).
$
L'assertion proposée est vraie ou fausse ? 

Q. 34. La négation de 
$(\exists y \, . \, p(y) \land \neg q(y))$ est 
$(\forall y \, . \, p(y) \Rightarrow  q(y))$.
L'assertion proposée est vraie ou fausse?

Q. 35. Soit la démonstration  syntaxique suivante: 

\begin{tabular}{lll}
\multicolumn{3}{l}{Démonstration sous hypothèses 
$\{\neg B \Rightarrow \neg A, A\}$}\\
1.&$\neg B \Rightarrow \neg A$ &$H_1$ \\
2.&$A$ &$H_2$ \\
3.&\_\_\_\_\_ &\_\_\_\_\_ \\
4.&\_\_\_\_\_ &\_\_\_\_\_ \\
5.&$\neg\neg B$ &réduction de l'absurde entre 4. et 1. \\
6.&$\neg \neg B \Rightarrow B $&Axiome 9 ($B/P$).\\
7.& $B$ &mp entre 5. et 6.\\
Conclusion
\end{tabular}

La démonstration est correcte si en 3. et 4. on a: \newline
\begin{tabular}{lll}
3.& $(\neg B \Rightarrow \neg A )\Rightarrow (\neg \neg A \Rightarrow  \neg \neg B) $ &théoreme de la contraposée ($\neg B/P, \neg A /Q$). \\
4.&$\neg \neg A \Rightarrow A $ &Axiome 9 ($A/P $).
\end{tabular}


Q. 36. Dans la formule
$(\forall x\,.\, p(x) \Rightarrow q(x)) \land r(y)$, la variable 
$x$ admet une occurence libre. L'assertion proposée est vraie ou fausse?

Q. 37. La relation $\{P,Q\} \vdash R$    se lit-elle
\og $R$ est une conséquence logique de l'ensemble
                     $\{P,Q\}$ \fg{}?
                   
Q. 38. La négation de 
$(\forall x \, . \, p(x) \Rightarrow q(x))$ est 
$\exists x \, . \, \neg p(x) \Rightarrow  q(x)$.
L'assertion proposée est vraie ou fausse?

\section{Problèmes}
\subsection{Du $\forall$ à $\exists$}
\begin{enumerate}
\item En calcul propositionnel, montrer que 
$\{\neg p \lor q \} \models p \Rightarrow q $ et 
$\{p \Rightarrow q \} \models \neg p \lor q  $.
\item Exprimer la négation de $\forall x \,.\, r(x)$.
\item Montrer que $ (\forall x\, . \, r(x)) \Rightarrow q(y)$ est 
équivalent à $ \exists  x \, . \, \neg r(x) \lor q(y)$.
\end{enumerate}
\subsection{Démonstration syntaxique}

Dans le système \og PR \fg{} et en se servant éventuellement des théorèmes 
déjà démontrés dans le cours, démontrer syntaxiquement 
les deux formules propositionnelles suivantes:
\begin{enumerate}
\item 
$
\left(
  A \Rightarrow 
  \left( 
    B \Rightarrow
    (C \land D)
  \right)
\right)
\Rightarrow
\left(
  (A \land B)
  \Rightarrow
  (C \lor D)
\right)
$
      


\item $((A \Rightarrow C) \land (B \Rightarrow D)) \Rightarrow
  ((A \lor B) \Rightarrow (C \lor D))$
\end{enumerate}


\section*{Annexes : Axiomes de PR}

\begin{itemize}\item Axiome 1 : $P\imp (Q\imp P)$
\item Axiome 2 : $(P\imp Q)\imp((P\imp(Q\imp R))\imp (P\imp R))$
\item Axiome 3 : $P\imp(Q\imp P\et Q)$
\item Axiome 4 : $P\et Q\imp P$
\item Axiome 5 : $P\et Q\imp Q$
\item Axiome 6 : $P\imp P\ou Q$
\item Axiome 7 : $Q\imp P\ou Q$
\item Axiome 8: $(P\imp R)\imp((Q\imp R) \imp(P\ou Q\imp R))$
\item Axiome 9: $\non\non P\imp P$
\item Axiome 10: $(P\imp Q)\imp((P\imp\non Q)\Rightarrow \neg P)$
\item Axiome 11 : $(P\imp Q)\imp((Q\imp P)\imp(P\eqv Q))$
\item Axiome 12 : $(P\eqv Q)\imp(P\imp Q)$
\item Axiome 13 : $(P\eqv Q)\imp(Q\imp P)$
\end{itemize}


\newpage

\begin{huge}
\begin{center}
\begin{tabular}{|l|c|c||l|c|c||l|c|c|}
\hline
Numéro & V & F & Numéro & V & F & Numéro & V & F \\ 
\hline
Q. 1 & &  & Q. 2 & &  & Q. 3 & &  \\ 
\hline
Q. 4 & &  & Q. 5 & &  & Q. 6 & &  \\ 
\hline
Q. 7 & &  & Q. 8 & &  & Q. 9 & &  \\ 
\hline
Q. 10 & &  & Q. 11 & &  & Q. 12 & &  \\ 
\hline
Q. 13 & &  & Q. 14 & &  & Q. 15 & &  \\ 
\hline
Q. 16 & &  & Q. 17 & &  & Q. 18 & &  \\ 
\hline
Q. 19 & &  & Q. 20 & &  & Q. 21 & &  \\ 
\hline
Q. 22 & &  & Q. 23 & &  & Q. 24 & &  \\ 
\hline
Q. 25 & &  & Q. 26 & &  & Q. 27 & &  \\ 
\hline
Q. 28 & &  & Q. 29 & &  & Q. 30 & &  \\ 
\hline
Q. 31 & &  & Q. 32 & &  & Q. 33 & &  \\ 
\hline
Q. 34 & &  & Q. 35 & &  & Q. 36 & &  \\ 
\hline
Q. 37 & &  & Q. 38 & &  &  & &  \\ 
\hline
\end{tabular}
\end{center}
\end{huge}





\end{document}