Logique

Un peu de logique

Programme des réjouissances

Conventions et définitions

Naturellement, ceux qui possèdent des rudiments de logique peuvent passer sans remords aux autres parties :

En logique, l'équivalent d'une phrase est appelé proposition.
Etant données deux propositions A et B, on peut les regrouper pour former les propositions suivantes dont voici les tables de vérité :

A ou B :

  B = vrai B = faux
A = vrai vrai vrai
A = faux vrai faux

A et B

  B = vrai B = faux
A = vrai vrai faux
A = faux faux faux

non( A) :

A non( A )
A = vrai faux
A = faux vrai

Enfin, la table de vérité de la relation "implique" est un peu moins intuitive :

A implique B :

  B = vrai B = faux
A = vrai vrai faux
A = faux vrai vrai

Le côté artificiel de cette définition vient de ce qu'elle n'a aucun rapport avec les notions de cause et d'effet. On peut néanmoins justifier cette définition par les arguments suivants : si A est vraie et si B ne l'est pas, ceci prouve par l'exemple que A n'implique pas B. Inversement, si A et B sont vraies, la notion intuitive de l'implication est confirmée. Enfin, si A est fausse, rien ne permet de dire qu'elle n'implique pas B, au sens intuitif du terme.

On peut alors définir la relation d'équivalence.
On dit que A équivaut è B si A implique B et B implique A. D'où la table de vérité:

A équivaut à

  B = vrai B = faux
A = vrai vrai faux
A = faux faux vrai

Propriétés élémentaires

Ces propriétés découlant directement des tables de vérité données ci-dessus. elles sont bien évidemment valables pour toutes les propositions.
Elles sont particulièrement utiles pour résoudre des problèmes comportant des menteurs et des sincères.

Tout d'abord, "et" et "ou" sont commutatives, c'est-à-dire :

( A et B ) = ( B et A )
( A ou B ) = ( B ou A )

Ensuite, "et" est distributif sur "ou" et vice-versa, c'est-à-dire :

A et ( B ou C ) = ( A et B ) ou ( A et C )
A ou ( B et C ) = ( A ou B ) et ( A ou C )

Voici comment nier une proposition :

non( A et B ) = ( non(A) ou non(B) )
non( A ou B ) = ( non(A) et non(B) )

Enfin, il découle directement de la définition de l'implication :

( A implique B ) = ( non(A) ou B )

Retour au sommaire de cette page

Enigme des marins :

Trois marins entrent dans un bar, et chacun commande une bière à dix francs. Après avoir payé, ils regrettent néanmoins le prix élevé des boissons. Le patron compatissant ordonne alors au serveur de leur rendre 5 F. Mais le serveur garde deux francs en guise de pourboire, et il rend un franc à chaque marin.

Faisons les comptes : chaque marin a payé sa bière neuf francs, ce qui fait vingt-sept francs. De plus, le garçon s'est mis deux francs dans les poches. Au total, cela fait donc vingt-neuf francs.

Où est passé le trentième franc ?

Solution :

Remarquons tout d'abord qu'il est absurde de chercher un trentième franc car, le serveur leur ayant rendu trois francs, les marins n'ont payé, en tout, que 27 francs. Il ne manque donc pas un franc, mais il y a, au contraire, 2 francs en trop dans nos comptes.

L'erreur vient de ce que les bières n'ont pas coûté 27 francs mais 25 : c'est la somme qui reste dans la caisse du patron après qu'il ait donné au serveur les 5 francs à rendre. Les 27 francs que l'on avait comptés comprennent donc les trois bières ET le pourboire du serveur. On avait donc compté 2 fois le pourboire, ce qui conduisait au résultat erronné de 29 francs.

Retour au sommaire de cette page

Enigme de l'interrogation surprise

C'est une classe où un professeur excédé par le chahut de ses élèves leur déclare brusquement : * "vous aurez une interrogation écrite la semaine prochaine, et je peux vous dire que, pas un instant à l'avance, vous ne pourrez prévoir avec certitude le jour où elle tombera."*

A la fin du cours, les élèves tentent malgré tout de deviner la date fatidique, et ils tiennent le raisonnement suivant :

L'interrogation ne peut pas avoir lieu le samedi, sinon ils en connaîtraient la date le vendredi à la fin du cours.
Elle ne peut pas non plus avoir lieu le vendredi, sinon, le jeudi soir, sachant que le samedi n'est pas un jour possible pour cette interrogation, ils en déduiraient la date.
En raisonnant de même, ils en déduisent que l'interrogation ne peut pas avoir lieu le jeudi, ni le mercredi, ni le mardi.
Reste le lundi. Mais alors ils ont prévu la date et entrent en contradiction avec ce qu'a dit le professeur.
L'interrogation ne peut donc avoir lieu aucun jour de la semaine, donc ce n'est pas la peine de se fatiguer à réviser !

Malheureusement pour eux, ils sont bien surpris le mercredi, lorsqu'on leur ordonne de ranger leurs notes de cours et de sortir une feuille de papier. Aucun d'eux ne l'a prévu, bien sûr, et leur beau raisonnement comporte une lacune. Laquelle ?

N.B : On suppose que les élèves ont cours tous les jours, du Lundi au Samedi inclus.

Solution ( Partielle )

Le fait d'avoir décelé une contradiction dans les paroles du professeur ne permet pas aux élèves de prédire le jour de l'interrogation.

Remarquons une chose : si le professeur avait tu le fait qu'ils ne pourraient rien prévoir à l'avance, tout en prévoyant en secret de mettre le contrôle un jour quelconque entre Lundi et Vendredi inclus, les élèves n'auraient eu en effet aucun moyen de prévoir la date.

Le fait d'introduire cette pseudo-précision dans l'énoncé le rend contradictoire, ce dont les élèves se rendent compte par leur raisonnement.
Malheureusement pour eux, le fait qu'ils aient détecté une contradiction dans les propos de leur professeur ne leur permet nullement de prédire le jour du contrôle.
Tout se passe donc comme l'a dit le professeur.

Ce type de contradiction ne relève pas de la logique du premier ordre, et il est fort difficile à mettre en évidence à l'aide des mots du langage courant.

Je risque cependant une comparaison avec le fameux paradoxe que constitue la phrase : "Cette phrase est fausse". Si on la suppose vraie ( comme les élèves l'ont fait ), on en déduit qu'elle est fausse ( conclusion des élèves ), ce qui entraîne qu'elle est vraie ( car il y avait bien une interrogation à la clef ). Ici s'arrête la comparaison, car, dans l'énigme de l'interrogation surprise, on a un moyen de vérifier la véracité de l'énoncé : c'est là que réside toute sa subtilité, puisque l'on a ainsi réussi à fabriquer un énoncé contradictoire mais vérifiable, du moins en apparence.

En effet, le fait que l'énoncé ait l'air vérifié est trompeur : si les élèves refont leur raisonnement, ils trouveront qu'ils auraient dû prévoir le jour fatidique ...

Le même genre d'erreur apparaîtra peut-être de manière plus claire dans l'énigme suivante.

Retour au sommaire de cette page

Enigme des coffrets

On vous propose l'épreuve suivante : on vous montre deux coffrets et on vous dit que dans l'un d'eux est caché un trésor ( Vous pouvez être sûr que c'est vrai ).


Sur le premier coffret figure l'inscription "Le trésor n'est pas ici".
Sur le second coffret figure l'inscription "Un seul de ces deux coffrets porte une inscription vraie"

Vous tenez alors le raisonnement suivant : "Si la seconde inscription est vraie, alors la première est fausse. Si la seconde inscription est fausse, alors la première l'est aussi ( sinon la seconde inscription serait vraie ). Dans les deux cas, la première inscription est fausse et le trésor est donc dans le premier coffret.

Malheureusement pour vous, il s'avère que le trésor était dans le second coffret. Où est l'erreur ?

Solution

Votre erreur est d'avoir supposé que les inscriptions sur les coffrets étaient cohérentes. Or on ne vous a rien dit à ce sujet. En l'occurrence, le fait que le trésor se trouve dans le second coffret entraîne l'incohérence des inscriptions. Pour autant, on ne vous a pas menti, puisque on vous a seulement dit que le trésor était dans l'un des deux coffrets. On ne peut rien déduire des inscriptions portées par les coffrets, tant que l'on ne sait pas si elles sont cohérentes ou non.

C'est le même genre d'erreur que dans l'énigme de l'interrrogation surprise : les élèves ont mené un raisonnement juste mais ils ont juste montré l'incohérence de la déclaration faite par le professeur, et pas la fausseté d'une hypothèse ( il y aura une interro la semaine prochaine ).

Retour au sommaire de cette page

Comment démontrer n'importe-quoi

La manière la plus simple de le faire consiste vraisemblablement à utiliser un raisonnement du style suivant :
"Si je ne me trompe pas, alors je suis un martien"
Cette phrase ne peut être que vraie. Donc je ne me suis pas trompé, donc je suis un martien.
Où est l'erreur ?

Solution

La tromperie vient, dans ce genre de raisonnement, de ce que l'on utilise une proposition qui n'est pas "bien fondée", comme disent les logiciens. ( Voir à ce sujet le livre de Raymond Smullyan : Quel est le titre de ce livre ? ). Intuitivement, on peut dire qu'une telle proposition n'a pas de sens, car elle ne nous fournit aucun critère permettant de décider si elle est vraie ou fausse. On ne sait pas, pour une telle proposition, ce que veut dire "être vraie" ou "être fausse". Une proposition mal fondée ouvre la porte à toutes les contradictions. En effet, la proposition du raisonnement est du type :

A : ( A implique B )

ce qui équivaut, par définition de la relation d'implication, à :

A : non(A) ou B
Cette écriture révèle que si A est fausse, alors elle est vraie, ce qui est absurde. Reste le cas où elle est vraie. Alors A a la même valeur logique que B, donc B est vraie.
L'escroquerie réside dans le fait que l'on s'est arrangé pour que cette proposition ne soit non-contradictoire que dans un unique cas, celui où B est vraie.

C'est pour se prémunir contre de tels abus que les logiciens ne considèrent que des propositions bien fondées.

Retour au sommaire de cette page

L'île des sincères et des menteurs

Dans cette île vivent deux catégories d'habitants : les sincères qui disent toujours la vérité, et les menteurs qui mentent toujours. Malheureusement pour nous, les deux catégories d'habitants sont totalement indiscernables. C'est le problème d'un jeune homme qui se demande si sa fiancée est sincère ou non, et qui aborde le frère de sa dulcinée ( sans savoir s'il est sincère, ni s'il appartient à la même catégorie que sa soeur ), dans le but de résoudre son dilemme.


Quelle question doit poser le fiancé pour être fixé ?
On précise que le frère, peu bavard, ne répondra que par oui ou non, et qu'il connaît la réponse aux préoccupations du fiancé.

Solution

Il existe une méthode systématique pour trouver la question

à poser.
Cherchons une question à laquelle le frère répondra oui si sa soeur est sincère, non si elle ne l'est pas.

La table des réponses données par le frère doit donc être :

  frère sincère frère menteur
fiancée sincère oui oui
fiancée menteuse non non

En distinguant les cas où le frère ment de ceux où il dit la vérité, on en déduit la table de vérité des (bonnes) réponses à la question posée :


  frère sincère frère menteur
fiancée sincère vrai faux
fiancée menteuse faux vrai
Il faut donc poser une question dont la ( vraie ) réponse soit oui si et seulement si le frère et sa soeur sont tous les deux sincères ou tous les deux menteurs.
S'il a raisonné comme nous, le jeune homme demandera donc quelque-chose comme :
"Appartenez-vous à la même catégorie d'habitants que votre soeur ?"
Une autre solution m'a été soumise par mail :
" Que répondriez-vous si je vous demandais si votre soeur est sincère ?"
Cette solution a l'avantage d'être très générale : le "Que répondriez-vous si ..." obligeant les menteurs à toujours dire le contraire du mensonge qu'ils répondraient, ce qui revient à leur faire donner le renseignement recherché. En plus, on économise la construction du tableau.

Retour au sommaire de cette page