DS 4 (MPSI option 2021-2022) — Véridiques, menteurs et changeants¶

Devoir surveillé · MPSI (option informatique) · 2021-2022 · partie I du DS 4 (2 h au total)

Autres parties : II. Tas

Consignes

Tout document et dispositif électronique interdit.

I. Logique¶

Vous participez à un concours de mathématiques comportant une partie de raisonnement logique. Plusieurs orateurs font des déclarations et vous devez répondre à des questions en vous appuyant sur des informations déduites de ces déclarations. La règle suivante s'applique : « Les orateurs sont de trois natures : les véridiques, les menteurs et les changeants. Les véridiques disent toujours la vérité, les menteurs mentent toujours, et les changeants disent en alternance une vérité et un mensonge (c'est-à-dire, soit une vérité, puis un mensonge, puis une vérité, etc. ; soit un mensonge, puis une vérité, puis un mensonge, etc.). Pendant tout le concours, les orateurs ne peuvent pas changer de nature. »

Les épreuves comportent deux phases :

Les différents orateurs font plusieurs déclarations dont l'analyse permet de déterminer la nature de chaque orateur (véridique, menteur, changeant commençant par dire la vérité, ou changeant commençant par dire un mensonge).
Les orateurs font une seconde série de déclarations. Puis, vous devez répondre à des questions en exploitant les informations contenues dans ces déclarations.

Question 1

Dans la première phase, quel est le nombre minimum de déclarations que doit faire chaque orateur pour qu'il soit possible de déterminer sa nature ? Justifier votre réponse.

Question 2

Soit un orateur A qui fait une suite de \(n\) déclarations \(A_i\). Proposer des formules du calcul des propositions \(A_V\), \(A_M\), \(A_{CV}\) et \(A_{CM}\) qui permettent de caractériser la nature de A (respectivement véridique, menteur, changeant commençant par dire la vérité, ou changeant commençant par dire un mensonge).

Vous participez à une première épreuve avec un orateur A qui fait les déclarations suivantes :

J'aime le rouge mais pas le bleu.
Soit j'aime le rouge, soit j'aime le vert.
Si j'aime le rouge et le vert, alors j'aime le bleu.

Nous noterons R, V et B les variables propositionnelles associées au fait que l'orateur aime le rouge, le vert ou le bleu. Nous noterons \(A_1\), \(A_2\) et \(A_3\) les formules propositionnelles associées aux déclarations de A.

Question 3

Représenter les déclarations de l'orateur sous la forme de formules du calcul des propositions \(A_1\), \(A_2\) et \(A_3\) dépendant des variables R, V et B.

Question 4

Appliquer les formules permettant de caractériser la nature des orateurs \(A_V\), \(A_M\), \(A_{CV}\) et \(A_{CM}\) que vous avez proposées pour la question 2 pour l'orateur A dépendant des variables \(A_1\), \(A_2\) et \(A_3\).

Question 5

En utilisant le calcul des propositions (résolution avec les tables de vérité), déterminer la nature de l'orateur A. Quelles sont les couleurs qu'aime A ?