Hypothèse et raisonnement déductif

B. Les chaines et les arbres d’implications.
Evidemment, on ne se limite pas à un seul « Si truc Alors machin ».
On enfile les si..Alors.. comme des perles. Mais il y plusieurs façons de s’y prendre :

1) chaine d’implication amnésique ou à candidature persistante.
Voici une (petite) chaine d’implication :
Si X alors Y donc Z

a) Chaine d’implication amnésique
Si dans le raisonnement précédant Z n’est que la conséquence de Y, on dira que c’est une chaine amnésique (inutile de se soucier de X pour la suite du raisonnement).
La plupart des motifs reposent sur des chaines amnésiques.

b) Chaine d’implication à candidature persistante
A l’inverse si pour conclure Z il faut X et Y (ou même seulement X), la candidature de X est persistante.

2) Imbrication de disjonction de cas
Selon le motif :
Si X alors
ou bien A et alors…
ou bien B et alors…
ou bien C et alors…
…
et Si pas X alors.. .
…

Vous vous demandez à quoi servent des raisonnements aussi compliqués ?
… A justifier les triplets, les swordfish (3-3-3), les quadruplets… ! (en somme les raisonnements sur les ensembles complets – entre autre)


III. Technique générale de résolution
Dans cette partie je n’évoquerais pas les motifs reposant sur la règle d’unicité.

Les motifs simples ont l’avantage d’être facile à repérer, mais leur portée est limitée. A ma connaissance tous sont des cas particuliers d’une (ou même bien souvent plusieurs) techniques « générales » de résolution.
Ces techniques générales de résolution sont des cadres théoriques, avec leur vocabulaire et leur notation propre (quelque fois propre à chacun…).

Voici les cadres théoriques dont je vais parler :
Les chaines mixtes
Le coloriage
Les ALS/EQC
Les ensembles forts et les transformations (dérivations) d’ensembles forts.

Les chaines mixtes et le coloriage pour l’essentiel c’est la même chose. La nuance est que le coloriage propose en plus une « méthodologie » papier-crayon pour mettre en évidence des chaines mixtes. Mais en exploitant le marquage des candidats, on peut aussi pousser des raisonnements plus « complets »…

Les ALS/EQC et les ensembles forts sont équivalents il me semble (voir les échanges avec léon1789 à ce sujet). Mais les points de vues de départ diffèrent, et chacun de ces cadres à ses spécificités les rendant plus ou moins appropriés à certaines configurations.

1) Les chaines mixtes et le coloriage : les chaines d’implications amnésiques.
Les deux s’appuient sur des ensembles forts de deux candidats (les jumeaux) et sur des conflits entre candidats (contraintes).
a, A, b et B sont des propositions de candidat dans une case où a et A sont jumeaux (c'est-à-dire au moins une des deux propositions est vraie) et il en va de même pour b et B.
Les coloristes notent cette situation {aA} et {bB}. Ceux qui pratiquent les chaines mixtes ont chacun leur notation…Mettons qu’ils notent a-A et b-B (pour reprendre les notations de papyg)…
Quand A et b sont en conflits (au plus un est juste) :
On établit qu’au moins a ou B est juste : {aB}
En chaine mixte : a-A / b-B.

On peut rédiger le raisonnement de différentes façons.
Si un candidat est incompatible (en conflit) avec a et B alors la situation est absurde : on l’élimine.
Ou par disjonction de cas :

Code:

Ou bien a (et les candidats en conflit avec a sont éliminés) Ou bien pas a et alors B (et les candidats en conflit avec B sont éliminés)

Dans ces chaines mixtes (ou dans les gestions de conflits et de tenailles) le « morceau » :

Code:

A / b-B correspond à l’implication : Si ( A ) Alors (pas b) et donc ( B ) En résumé : Si A alors B

Toutes les chaines d’implications amnésiques (simple – qui ne font pas intervenir d’objet) reposent sur des chaines mixtes (ou du coloriage).
Ex
Si a1=1 alors d2=3 : pour pouvoir conclure ainsi, c’est que a1=1 élimine un candidat (en l’occurrence un chiffre 1) de d2. Si l’on conclut d2=3 c’est que d1=1 et d1=3 sont jumeaux (ce sont les deux seuls candidats).

La conséquence c’est que les raisonnements par l’absurde qui se ramènent à :
Si A alors … alors (pas A), par une chaine d’implications amnésiques cache une chaine mixte.

Les chaines mixtes (et le coloriage classique) ne permettent pas de disjonction de plus de deux cas.

Il est important de noter que la majorité des motifs simples sont des chaines mixtes.

2) Une spécificité du coloriage.
Passage corrigé suite aux explications de PhB (merci PhB)

Le coloriage classique (sur la base de jumeaux) se résume à mettre en évidence des chaines mixtes.

Mais le coloriage peut s'étendre en coloriant les candidats d'un ensemble fort de plus de deux candidats (ensemble ternaire ou plus -> voir les articles de PhB à ce sujet).

Dans ce cas le coloriage donne accès aux "déplacements" (ou "transports" ou "dérivation") d'ensemble fort par des chaines mixtes.

Il s'agit alors de raisonnements qui font intervenir une disjonction de plus de deux cas.

Les raisonnements à candidatures persistantes restent prohibés pour le coloriage car les candidatures persistantes empechent "l'equivalence des marques".

3) les réseaux d’ALS et les ensembles forts.

Avec de tels réseaux on peut présenter tous les raisonnements déductifs : les candidatures persistantes, et les multiples disjonctions de cas (ce qui peut correspondre entre autre à la résolution récursive naïve d’un solveur).

Les chaines objets sont aussi de cette nature, mais elles ne permettent pas de présenter n’importe quel raisonnement. D'autre, elles sont amnésiques entre deux relations de voisinage : seuls les objets au sein des jumeaux sont succeptibles de mettre en ooeuvre des disjonction de plus de deux cas et/ou des candidatures persistantes.

Au sujet des transformations d’ensemble fort.
La dérivation :
Des ensembles forts sont des ensembles dont au moins une des propositions est vraie.
Exemple {a1=1 a1=2 a1=3} et {b1=1 b1=3 b1=4} sont deux ensembles forts natifs (dès lors que les seuls candidats possibles en a1 sont 1, 2 et 3 et en b1 1, 3 et 4).
La contrainte entre a1=1 et b1=1 permet de conclure que {a1=2 a1=3 b1=3 b1=4} est un nouvel ensemble fort.

En transformant les ensembles forts on peut justifier toutes les éliminations des mauvais candidats d’une grille (du moins je crois).
Présenté ainsi, les démonstrations s’apparentent à des arbres généalogiques : deux ensembles forts donnent un nouvel ensemble fort.
On élimine alors les candidats en contradiction avec toutes les propositions d’un ensemble fort.

Mais on peut aussi présenter les choses sous la forme de réseau mixte – inspiré des réseaux d’ALS. Voir les discutions avec léon1789.
A ma connaissance je suis le seul à pratiquer ce sport
On utilise alors le principe des tiroirs : chaque entité (une case pour les ALS) doit être remplie par un candidat. Les contraintes limite le nombre de candidat. Si un voyeur rend l’ensemble sous-complet la situation devient absurde et ce candidat (voyeur) est éliminé.



IV Les ensembles complets.

Il y a deux raisons qui m’amènent à parler plus spécifiquement des ensembles complets :
- ils sont la base des ESC, et via le principe des tiroirs ils aboutissent à la mise en œuvre des réseaux.
- ils me donnent l’occasion de revenir sur une notion polémique et/car opaque : celle de « méthode à hypothèse ».

1) Qu’est ce qu’un ensemble complet ?
Evidemment typiquement les ensembles complets sous les n-uplets (paire, triplet, quadruplet, francs ou cachés).
Et évidemment, ce sont les « presque » n-uplet francs qui servent intégralement de support au ESC.
Par un jeu de miroir, on peut étendre un peu la notion d’ensemble complet.
Tout le monde connait la dualité entre les n-uplets francs et les n-uplets cachés.

Un n-uplet est franc lorsque n cases d’une même zone sont constituées (au plus) des même n chiffres-candidats.
En renversant les rôles :
Un n-uplet est caché lorsque n chiffres-candidats occupents les n mêmes cases (au plus) d’une zone.

Mais il y a d’autres renversements possibles.
Un x-wing est une paire de position :
On a par exemple un x-wing lorsqu’un chiffre donné (équivalent à la zone) occupe les deux mêmes colonnes (équivalent aux chiffres) pour deux lignes données (équivalents aux deux cases). On a alors une paire franche de colonnes dans les deux lignes considérées, ou bien une paire cachée de lignes dans les deux colonnes en questions…

Les deux tableaux suivants sont de même nature :

Code:

Les candidats en ligne 1 a b c d... cases 1 X o X o o... 2 X o X o o... 3 X ... ... chiffre paire cachée 12 en a1 c1

Code:

Les 1 dans la grille a b c d... colonne 1 X o X o o... 2 X o X o o... 3 X ... ... ligne x-wing ligne 1 et 2 (sur les colonnes a et c)

La notion d'ensemble complet ne se limite donc pas au n-uplet franc : il y a des ensembles complets de positions et un n-uplet caché et aussi un n-uplet franc en renversant les rôle des cases et des chiffres.

2) Le principe des tiroirs.
C’est le principe simple qu’on utilise sur les ensembles complets :
Pour remplir n entités avec des objets différents, il faut au moins n objets.

Et c’est ce principe qui est aussi à la base des ESC.
Un réseau d’ESC qui devient sous-complet est un réseau d’ESC qui a moins de libertés que de contraintes. La différence (liberté – contrainte) évalue en quelque sorte le nombre d’objets disponibles. Si un voyeur en fait trop disparaitre : on ne peut plus remplir tous les tiroirs-ESC…

Un dernier mot encore : les ESC se limitent à des ensembles de cases q ui forment des presque n-uplets francs. Mais on peut assouplir encore les choses pour obtenir des réseaux d’ensembles presque complets qui ne sont plus nécessairement des n-uplets presque francs.
On peut par exemple intégrer dans un réseau d’ESC des presque n-uplets cachés, ou des presque swordfish.
Un peu dans l’esprit des chaines objets qui étendent, assouplissent et rendent plus puissantes les chaines mixtes…

3) « Méthode à hypothèse » ?
Il y a à mon avis deux raisons pour lesquels beaucoup de motifs et de techniques générales privilégient les jumeaux :
- il y est plus facile de travailler sur deux éventualités que sur trois…

mais surtout :
- dès qu’un des jumeaux est faux, alors l’autre est vrai.

Presque plus personne ne dit qu’un motif qui ne met en œuvre que des jumeaux, est une méthode à hypothèse ou une technique essai-erreur… avec tout ce qu’il y a de péjoratif dans ces expressions. D’ailleurs s’interdire ces méthodes c’est se limiter aux alignements…

Et par conséquent, sans doute pour dessiner une ligne de partage entre les méthodes nobles et les méthodes essai-erreur tant honnies, des définitions de « méthodes à hypothèses » sont apparues :" lorsqu’une même assertion est utilisée plusieurs fois dans le raisonnement déductif".

Ce n’est pas très clair (pour moi), mais l'idée est de pointer ce qui paraît être la spéficité de la méthode essai-erreur : la candidature persistante, et donc dans une certaine mesure les disjonctions de cas.

Car il y a un lien très fort entre candidature persistante et disjonction de plus de deux cas...
En effet : si une candidature persistante est nécessaires c'est forcement parcequ'on en déduit quelque chose sur un ensemble fort d'au moins 3 candidats ! ( = disjonction d'au moins 3 cas ! Typiquement on déduit la valeur d'une case qui au départ possédait trois candidats)


Le cas d’un simple triplet pose problème. Démontrer les éliminations causées par un triplet oblige à des candidatures persistantes (et une disjonction de cas) :

Avec un triplet franc : a1=123 a2=123 a3=123
On peut évidemment éliminer a4=1…
Mais pour le démontrer de façon élémentaire – sans le principe des tiroirs :

si a4=1 alors
ou bien a1=2 alors a2=3 et il n’y a plus de candidat pour a3 (absurde) : candidature persistante de a1=2 et a4=1
ou bien a1=3 alors a2=2 et il n’y a plus de candidat pour a3 (absurde) : candidature persistante de a1=3 et a4=1
Donc a4=1 est absurde.

En implications "élémentaires" :

Code:

a4=1 => a1=2 ou 3 a1=2 et a4=1 => a2=3 a4=1 et a1=2 et a2=3 => a3 vide a1=3 et a4=1 => a2=2 a4=1 et a1=3 et a2=2 => a3 vide conclusion a4=1 impossible

Si on s’autorise le principe des tiroirs, il n’y a plus de problèmes, mais tout les travaux de léon1789 montre alors qu’avec le principe des tiroirs (les réseaux d’ESC) aucune méthode n’est plus à hypothèse, puisque toutes peuvent se traduire en ESC !

Evidemment le même problème se pose avec les swordfish, les quadruplets et les ESC en général…

S'interdire de telles "méthodes à hypothèse" parce qu'elles correspondent aux "méthodes essai-erreur" contraint à ne plus appliquer les triplets...!!!


Quelques liens (réseaux d'ESC et réseaux mixtes)
Technique ESC
et en particuliers : Traduction d'un raisonnement persistant par ESC

Réseaux (mixte) d'ESC - hypothèse imbriquée

Et la désormais référence :
Technique ALS/EQC/ESC

Sans oublier : Technique : Chaîne de Jumeaux/Voisins (de papyg)

Dernière édition par dxp le Dim 04/02/2007 0:50; édité 3 fois