[PDF] TD15 : Exercices de logique de CCP

View - Download TD15 : Exercices de logique de CCP

Previous PDF

Next PDF

TD15 MP 17-18EXERCICES DE LOGIQUE DE CCP

Exercice n

o1.Exo de logique de CCP 2017

Imaginez-vous ethnologue. Vous étudiez une peuplade primitive qui présente un comportement manichéen

extrême : lorsque plusieurs personnes participent à une même conversation sur un sujet donné, elles vont

toutes avoir le même comportement manichéen tant que la conversation reste sur le même sujet, c"est-à-dire

que toutes les affirmations seront soit des vérités, soit des mensonges. Par contre, si le sujet de la conversation

change, la nature des affirmations, soit mensonge, soit vérité, peut changer, mais toutes les affirmations seront

de la même nature tant que le sujet ne changera pas à nouveau.

Pour être autorisé à séjourner dans cette peuplade, vous devez respecter cette règle. Vous participez à une

conversation avec trois de leurs membres que nous appelleronsX,YetZ. Ceux-ci vous indiquent comment

rejoindre leur village. Si vous n"arrivez pas à le rejoindre, vous ne serez pas autorisé à y séjourner.

Le premier sujet abordé est la région dans laquelle se trouvele village : Xindique : " Le village se trouve dans la vallée »;

Zréplique : " Non, il ne s"y trouve pas »;

Xreprend : " Ou alors dans les collines ».

Nous noteronsVetCles variables propositionnelles associées à la région danslaquelle se trouve le village.

Nous noteronsX1etZ1les formules propositionnelles correspondant aux affirmations deXet deZsur le premier sujet.

Puis, le second sujet est abordé : le chemin qui permet de rejoindre le village dans la région concernée.

Xdit : " Le chemin de gauche conduit au village »;

Zrépond : " Tu as raison »;

Xcomplète : " Le chemin de droite y conduit aussi »; Yaffirme : " Si le chemin du milieu y conduit, alors celui de droite n"y conduit pas »; Zindique : " Celui du milieu n"y conduit pas ».

Nous noteronsG,MetDles variables propositionnelles correspondant respectivement au fait que le chemin

de gauche, du milieu et de droite, conduit au village. Nous noteronsX2,Y2etZ2les formules propositionnelles correspondant aux affirmations deX, deYet de

Zsur le second sujet.

a) Représenter le comportement manichéen des interlocuteurs dans le premier sujet abordé sous la forme

d"une formule du calcul des propositions dépendant des formules propositionnellesX1etZ1.

b) Représenter les informations données par les participants sous la forme de deux formules du calcul des

propositionsX1etZ1dépendant des variablesVetC.

c) En utilisant la résolution avec les propriétés des opérateurs booléens et les formules de De Morgan en

calcul des propositions, déterminer dans quelle région vous devez vous rendre pour rejoindre le village.

d) Représenter le comportement manichéen des interlocuteurs dans le second sujet abordé sous la forme

d"une formule du calcul des propositions dépendant des formules propositionnellesX2,Y2etZ2.

e) Représenter les informations données par les participants sous la forme de trois formules du calcul des

propositionsX2,Y2etZ2dépendant des variablesG,MetD.

f) En utilisant la résolution avec les tables de vérité en calcul des propositions, déterminer quel chemin

vous devez suivre pour rejoindre le village.

g) En admettant que les trois participants aient menti, pouviez-vous prendre d"autres chemins? Si oui, le

ou lesquels?

Correction

a) La règle peut s"écrire :X1Z1+X1Z1 b)X1=V+C Z 1= V c)X1Z1+ X1Z1 donc (V+C)

V+V+C·V

doncV

V+CV+VCV

1 doncCV Le village se trouve dans les collines et pas dans la vallée. d) Pour le deuxième sujet abordé, la règle peut s"écrire :X1Y1Z1+

X1Y1Z1

e)X2=GD Y

2=M→

D=M+D Z 2=G M f) Table de vérité :

GMDX2Y2Z2règle

0000100

0010100

0100100

0110001

1000110

1011111

1100100

1111000

La règle est respectée dans deux cas qui sont les casGMDetGMD. On ne sait pas dans quel cas on

se trouve. Néanmoins, dans un cas comme dans l"autre, le chemin de droite mène au village. Comme

on veut atteindre à coup sûr le village, la décision à prendreest indubitable : il faut prendre le chemin

de droite.

g) On suppose que les trois participants ont menti. Dans la table de vérité, on voit que ce cas ne se produit

que sur une seule ligne, à savoir la ligneG MD. On peut donc prendre le chemin de gauche, en plus du chemin de droite.

Exercice n

o2.Exo de logique de CCP 2015

De nombreux travaux sont réalisés en Intelligence Artificielle pour construire un programme qui imite le

raisonnement humain et soit capable de réussir le test de Turing, c"est-à-dire qu"il ne puisse pas être distingué

d"un être humain dans une conversation à l"aveugle. Vous êtes chargé(e)s de vérifier la correction des réponses

données par un tel programme lors des tests de bon fonctionnement. Dans le scénario de test considéré, le

comportement attendu est le respect de la règle suivante : pour chaque question, le programme répondra par

trois affirmations dont une seule sera correcte. Nous noteronsA1,A2,A3les propositions associées aux affirmations effectuées par leprogramme.

a) Représenter le comportement attendu sous la forme d"une formule du calcul des propositions qui dépend

deA1,A2etA3

1. Premier cas

Vous demandez au programme :Quels éléments doivent contenir les aliments que je dois consommer pour

préserver ma santé?

Il répond les affirmations suivantes :

A

1: Consommez au moins des aliments qui contiennent des glucides, mais pas de lipides !

A

2: Si vous consommez des aliments qui contiennent des glucides, alors ne consommez pas d"aliments qui

contiennent des lipides ! A

3: Ne consommez aucun aliment qui contient des lipides !

Nous noteronsG, respectivementL, les variables propositionnelles qui correspondent au fait de consommer

des aliments qui contiennent des glucides, respectivementdes lipides. b) ExprimerA1,A2etA3sous la forme de formules du calcul des propositions. Ces formules peuvent dépendre des variablesGetL

c) En utilisant le calcul des propositions (résolution avecles formules de De Morgan), déterminer ce que

doivent contenir les aliments que vous devrez consommer pour préserver votre santé.

2. Second cas

Vous demandez au programme :Quelles activités dois-je pratiquer si je veux préserver masanté?

Suite à une coupure de courant, la dernière affirmation est interrompue. 2 A1: Ne faites des activités sportives que si vous prenez également du repos ! A

2: Si vous ne faites pas d"activité intellectuelle, alors ne prenez pas de repos !

A

3: Prenez du repos ou faites des activités ... !

Nous noteronsS,IetRles variables propositionnelles qui correspondent au faitde faire des activités sportives,

des activités intellectuelles et de prendre du repos. d) ExprimerA1,A2etA3sous la forme de formule du calcul des propositions. Ces formules peuvent dépendre deS,IetR

e) En utilisant le calcul des propositions (résolution avecles tables de vérité), déterminer quelle(s) acti-

vité(s) vous devez pratiquer pour préserver votre santé.

Correction

a) La règle peut s"écrire :A1

A2A3+A1A2A3+A1A2A3

b)A1=G L A

2= (G→

L) =G+L

A 3= L c)A1

A2A3+A1A2A3+A1A2A3

doncG

L(G+L)L+GL(G+L)L+GL(G+L)L

donc (

G+L)(G+L)L+ (G+L)GLL

donc (G+L)GL donc GL Conclusion : Il convient donc de consommer des lipides mais pas de glucide. d)A1= (S→R) = S+R A 2=

I→R=I+R

A 3=R+x e) Table de vérité :

SIRA1A2A3six=Srègle six=SA3six=Irègle six=I

000110000

001101010

010110010

011111010

100011001

101101010

110011010

111111010

Dans le cas oùxdésigneS, la règle n"est jamais vérifiée. C"est donc quexdésigneI. On constate alors que la règle est vérifiée dans le cas oùS= 1,I= 0 etR= 0.

Conclusion : Il convient donc, pour préserver sa santé, de faire des activités sportives sans jamais prendre

de repos ni faire d"activités intellectuelles.

Exercice n

o3.Exercice de logique de CCP 2014

Dans une association de jeunes détectives, les membres s"entraînent à résoudre des problèmes logiques. Ceux-ci

respectent les règles suivantes : " Lors d"une conversation, un même membre aura un comportement constant :

il dira toujours la vérité, ou ne dira jamais la vérité. » et " Une conversation ne doit pas être absurde. »

a) Soientnmembres intervenant dans une même conversation. Chaque membre est représenté par une

variable propositionnelleMiaveci??1,n?qui représente le fait que ce membre dit, ou ne dit pas

la vérité. Chaque membre fait une seule déclaration représentée par la variable propositionnelleDi.

Représenter le respect des règles dans cette conversation sous la forme d"une formule du calcul des

propositions dépendant des variablesMietDiaveci??1,n?.

Vous assistez à deux conversations sur la véracité des déclarations de deux groupes de trois membres de cette

association. Nous nommeronsA,BetCles participants de la première conversation. 3 A: " Les seuls qui disent la vérité ici sontCet moi. »

B: "Cne dit pas la vérité. »

C: " SoitBdit la vérité. SoitAne dit pas la vérité. »

Nous noteronsA,BetCles variables propositionnelles associées au fait queA,BetCdisent respectivement

la vérité.

Nous noteronsDA,DBetDCles formules du calcul des propositions associées respectivement aux déclarations

deA,BetCdans la conversation.

b) Représenter les déclarations de la première conversation sous la forme de formules du calcul des propo-

sitionsDA,DBetDCdépendant des variablesA,BetC.

c) En utilisant le calcul des propositions (résolution avecles tables de vérité), déterminer siA,BetC

disent, ou ne disent pas, la vérité . Nous nommeronsD,EetFles participants de la seconde conversation.

D: " Personne ne doit croireF. »

E: "DetFdisent toujours la vérité. »

F: "Edit la vérité. »

Nous noteronsD,EetFles variables propositionnelles associées au fait queD,EetFdisent respectivement

la vérité.

Nous noteronsDD,DEetDFles formules du calcul des propositions associées respectivement aux déclarations

deD,EetFdans la seconde conversation.

d) Représenter les déclarations de la seconde conversationsous la forme de formules du calcul des propo-

sitionsDD,DEetDFdépendant des variablesD,EetF.

e) En utilisant le calcul des propositions (résolution avecles formules de De Morgan), déterminer siD,E

etFdisent, ou ne disent pas, la vérité.

Correction

a) Pour touti??1,n?, l"assertionDiprononcée par le membre numéroiest vraie si et seulement si ce

membre dit la vérité (ce qui est marqué par le variable propositionnelleDi).

On a donc?i??1,n?Di↔Mi

On peut donc écrire :

n? i=1(Di↔Mi) b)DA=A

BC(et pasAC)

D B= C D C=B? A(?représentexor, c"est-à-dire la disjonction exclusive) c) Table de vérité :

ABCDADBDCrègle

0000110

0010011

0100101

0110000

1000100

1011000

1100110

1110010

On n"arrive pas à conclure complètement. Les informations dont on dispose permettent seulement de

dire queAment et que l"un des autres dit la vérité. Peut-être y avait-il une erreur dans l"énoncé.

d)DD= F D E=DF D F=E 4 e) On remarquera que, pour toutes variables propositionnellesPetQ, on a : (P↔Q) = (PQ+PQ) On a la règle : (D↔DD)(E↔DE)(F↔DF) donc (DDD+

DDD)(EDE+EDE)(FDF+FDF)

donc (D

F+DF)(EDF+EDF)(FE+FE)

donc (D

F+DF)?EDF+E(D+F)?(FE+FE)

donc (D

F+DF)?EDF+ED+EF?(FE+FE)

On développe d"abord le produit (c"est-à-dire la conjonction) des deux premières parenthèses (en ne

gardant que les termes qui ne s"annulent pas) : on obtient : (D

EF+EDF)(FE+FE)

doncD EF Conclusion :Ddit la vérité alors queEetFmentent.

Exercice n

o4.Exercice de logique de CCP 2013

Lors d"une séance d"un jeu informatique dérivé de la mythologie grecque, vous êtes accompagné par un couple

de Sphinx. Ces créatures posent des énigmes logiques pour vous aider à progresser dans le jeu. Les énigmes

suivent une règle que les Sphinx respectent scrupuleusement. Lorsque les Sphinx énoncent cette règle, ils

disent toujours la vérité. Le premier Sphinx qui vous accompagne a énoncé la règle suivante :

" Dans les énigmes, je peux soit dire la vérité, soit mentir. Mais, pour une énigme donnée, la première et

la dernière de mes affirmations seront de la même nature (soit vérité, soit mensonge); et toutes les autres

affirmations seront de la nature opposée à ces deux-là (mensonge, respectivement vérité, si les premières et

dernières sont des vérités, respectivement des mensonges). »

a) Considérons que l"un des Sphinx fait une suite dendéclarationsAidans une même énigme. Proposer

une formule du calcul des propositions qui représente la règle qu"il respecte.

Vous vous retrouvez face à trois escaliers, l"un à gauche, l"autre à droite et le dernier au milieu entre les deux

autres. Le premier SphinxPénonce les affirmations suivantes : • l"escalier de gauche est sûr; • l"escalier du milieu est sûr ou celui de droite n"est pas sûr. Le second SphinxSénonce les affirmations suivantes : • ni l"escalier de gauche, ni celui du milieu ne sont sûrs; • si les escaliers de gauche ou de droite sont sûrs, alors l"escalier du milieu est sûr.

Nous noteronsG,MetDles variables propositionnelles associées au fait que les escaliers de gauche, du

milieu et de droite sont sûrs.

Nous noteronsP1etP2, respectivementS1etS2, les formules propositionnelles associées aux déclarations du

premier Sphinx, respectivement du second Sphinx.

b) Représenter les déclarations des deux Sphinx sous la forme de formules du calcul des propositionsP1,

P

2,S1etS2dépendant des variablesG,MetD

c) Appliquer la règle respectée par les Sphinx que vous avez proposée pour la première question. Nous

noteronsP, respectivementS, la formule du calcul des propositions dépendant des variablesP1etP2,

respectivementS1etS2, qui correspond au respect de la règle par le premier Sphinx,respectivement par

le second Sphinx, dans cette énigme. Nous noteronsRla formule du calcul des propositions dépendant

des variablesPetSqui décrit le respect global des règles par les deux Sphinx dans cette énigme.

d) En utilisant le calcul des propositions (résolution avecles tables de vérité), déterminer quel est (ou

quels sont) le (ou les) escalier(s) qui est (ou sont) sûr(s)?Vous indiquerez explicitement les résultats

intermédiaires correspondant aux formulesP1,P2,P,S1,S2etS. Vous vous retrouvez plus tard face à trois portes de couleursrouge, verte et bleue. Seul le premier Sphinx s"exprime et énonce les affirmations suivantes : • la porte rouge n"est pas sûre ou la porte verte est sûre; • si les portes rouge et verte sont sûres, alors la porte bleuen"est pas sûre; • la porte verte n"est pas sûre mais la porte bleue est sûre. 5

Nous noteronsP3,P4etP5les formules propositionnelles associées aux déclarations du premier Sphinx. Nous

noteronsR,VetBles variables propositionnelles associées au fait que les portes rouge, verte et bleue sont

sûres.

e) Représenter les déclarations du Sphinx sous la forme de formules du calcul des propositionsP3,P4et

P

5dépendant des variablesR,VetB

f) Appliquer la règle respectée par le premier Sphinx que vous avez proposée pour la première ques-

tion. Nous noteronsPla formule du calcul des propositions dépendant des variablesP3,P4etP5qui correspond au respect de la règle par le premier Sphinx dans cette énigme.

g) En utilisant le calcul des propositions (résolution avecles formules de De Morgan), déterminer quelle

est (ou quelles sont) la (ou les) porte(s) qui est (ou sont) sûre(s).

Correction

a) La règle que respecte le Sphinx est :A1 b)P1=G P 2=M+ D S 1= GM S

2=?(G+D)→M?=

G+D+M=GD+M

c)P=P1P2+ P1P2

S=S1S2+

S1S2 R=PS d) Table de vérité :

GMDP1P2PS1S2SR

0000101110

0010011000

0100100110

0110100100

1001110011

1011000010

1101110100

1111110100

Conclusion : Seul l"escalier de gauche est sûr. e)P3= R+V P

4= (RV→

B) =RV+B=R+V+B

P 5= V B f)P=P3

P4P5+P3P4P5

R+V)(R+V+B)V B+R+V(R+V+B)V B

R+V)RV BV B+RV(R+V+B)(V+B)

=R

VB(R+V+B)

=R VB

La seule porte sûre est donc la porte rouge.

Exercice n

o5.Exercice de logique de CCP 2012

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, 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. » 6

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çantpar 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.

a) 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 votreréponse.

b) Soit un orateurAqui fait une suite de déclarationsAi. Proposer des formules du calcul des propositions

A V,AM,ACVetACMqui permettent de caractériserla nature deA(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 orateurAqui 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 noteronsR,VetBles variables propositionnelles associées au fait que l"orateur aime le rouge, le vert

ou le bleu. Nous noteronsA1,A2etA3les formules propositionnelles associées aux déclarations deA.

c) Représenter les déclarations de l"orateur sous la forme de formules du calcul des propositionsA1,A2et

A

3dépendant des variablesR,VetB.

d) Appliquer les formules permettant de caractériser la nature des orateursAV,AM,ACVetACMque

vous avez proposées pour la deuxième question pour l"orateurAdépendant des variablesA1,A2etA3

e) En utilisant le calcul des propositions (résolution avecles tables de vérité), déterminer la nature de

l"orateurA. Quelles sont les couleurs qu"aimeA?

Vous participez à une seconde épreuve avec trois orateursG,HetI. Vous avez déterminé dans la première

phase avec succès queGest un menteur, queHest un véridique et queIest un changeant sans avoir s"il

doit dire la vérité ou un mensonge pour sa déclaration suivante. Ceux-ci font les déclarations :

•I: " Le losange est visible. » •G: " Le cercle est visible que si le losange est visible. » •I: " Le triangle n"est pas visible. » •H: " Soit le cercle est visible, soit le triangle est visible. »

Nous noteronsG1,H1,I1etI2les formules propositionnelles associées aux déclarations des orateursC,D

etEdans cette première épreuve.

Nous noteronsC,LetTles variables propositionnelles associées au fait que le cercle, le losange ou le triangle

soit visible.

f) Représenter les déclarations des orateurs sous la forme de formules du calcul des propositionsG1,H1,

I

1etI2dépendant des variablesC,LetT.

g) Représenter les informations sur la nature des orateurs sous la forme d"une formule du calcul des

propositions dépendant des variablesG1,H1,I1etI2.

h) En utilisant le calcul des propositions (résolution avecles formules de De Morgan), déterminer quelle

est (ou quelles sont) la (ou les) figure(s) visible(s) ainsi que la nature exacte deIl"orateur changeant.

Correction

a) Le nombre minimum de déclarations que doivent faire les orateurs pour que l"on puisse déterminer leur

nature est 2. Le tableau suivant indique la nature de l"orateur à partir des valeurs de vérités de ses deux

premières déclarations : (0,0)Mmenteur (0,1)CVchangeant commençant par une vérité (1,0)CMchangeant commençant pas un mensonge (1,1)Vvéridique b)AV=A1A2A3A4A5A6··· Aquotesdbs_dbs50.pdfusesText_50

[PDF] ccp chimie 1 pc 2010 corrigé

[PDF] ccp chimie 2 pc 2013 corrigé

[PDF] ccp chimie pc 2014

[PDF] ccp connect

[PDF] ccp ecoles

[PDF] ccp haut parleur

[PDF] ccp mp 2012 physique

[PDF] ccp mp 2016 physique chimie corrigé

[PDF] ccp mp 2016 physique corrigé

[PDF] ccp oraux

[PDF] ccp pc 2013 physique 2 corrigé

[PDF] ccp pc chimie 2016 corrigé

[PDF] ccp physique 1 pc 2011

[PDF] ccp physique 1 psi 2011 corrigé

[PDF] ccp physique 1 psi 2014