Exercice 3.1 Déduction naturelle pour les preuves
Rappel: le signe  est utilisé ici (cause Microsoft) au lieu de |-, pour désigner la prouvabilité. 
1) p & p  p
1	p&p		
2	p&p	R (1)	
3	p	&E (2)	
Cette preuve est conditionnelle: on prouve p, mais à partir d’une prémisse donnée (p&p). A cette preuve correspond une tautologie, qu’on établit dans la preuve suivante:

2)  (p & p)  p
(0)				
1		p&p	H	
2		p&p	R (1)	
3		p	&E (2)	
4	(p&p)  p		I(1-3)	
Ceci est une preuve inconditionnelle. On prouve que (p&p)  p, sans partir d’aucune prémisse. (Cf ligne 0, qui est vide.) Entre-temps, toutefois, on a fait une hypothèse (ligne 1). Mais cette hypothèse a été “ déchargée ” (ligne 4), c’est-à-dire qu’on a établit une conclusion qui ne dépend pas de cette hypothèse.
Seules deux règles permettent de “ décharger ” des hypothèses: la réduction à l’absurde I, et l’intro de l’implication, I. Il faut comprendre comment fonctionnent ces règles pour comprendre la déduction naturelle. (L’utilisation des autres règles est plus mécanique.) Cet exercice devrait vous y aider. (questions 4 à 7 sur I, questions 8 à 11 sur I)

3) p & q  p  q
1	p & q		
2	p & q	R(1)	
3	p	&E (2)	
4	p  q	I(3)	
Utilisation facile des règles &E et I. 

Preuves utilisant I
4) p, q  pq
1	p			
2	q			
3		p	H	
4		q	R(2)	
5	p  q		I(3-4)	
6		q	H	
7		p	R (1)	
8	q  p		I(6-7)	
9	p  q		I(5,8)	
Il faut penser la dérivation (preuve) à rebours. On veut pq. Pour y arriver il faut utiliser l’introduction de . Pour pouvoir l’utiliser, il faut avoir prouvé (p  q) et (q  p). Ces derniers s’obtiennent avec I. Pour (p  q) par ex., il faut faire l’hypothèse que p, et dériver q.
La sous-dérivation 3-4 peut sembler étrange, pour deux raisons. 1) pourquoi a-t-on le droit de poser q à la ligne 4? 2) pourquoi faire l’hypothèse que p, alors qu’on a déjà p (ligne 1) et qu’on n’a pas besoin de faire l’hypothèse que p pour dériver q (puisque p est déjà posé ligne 2).
(1) Dans une sous-dérivation (c-à-d dans la colonne qui s’ouvre à partir de l’hypothèse H, jusqu’à qu’on “ décharge ” l’hypothèse H), on a le droit de poser tout ce qui est posé dans la dérivation principale, et donc dans le cas présent, q. L’hypothèse qui ouvre une dérivation (ligne 3 ici) est en effet une hypothèse additionnelle, i.e. qui s’ajoute à celles déjà faites. Ce n’est pas une hypothèse indépendante. Comparer:
(Cluedo 1) “ En supposant que le meutrier n’est pas l’un d’entre nous, il a dû entrer dans la maison d’une façon ou d’une autre. En supposant en outre qu’il avait la clef, il n’a pas pu partir et laisser toutes les portes fermées à clef de l’intérieur. L’une des portes doit donc être ouverte ou fermée de l’extérieur. ” 
(Cluedo 2) “ En supposant que le meurtrier n’est pas l’un d’entre nous, il a dû entrer dans la maison d’une façon ou d’une autre. On sait par ailleurs que, en supposant que quelqu’un n’ait pas d’échelle ou de corde, il ne peut sortir que par l’une de ces trois portes ”.
Dans Cluedo (1), la seconde hypothèse (que le meurtrier a la clef) est ajoutée à la première. Ce qu’on en dérive (que toutes les portes ne sont pas fermées de l’intérieur) ne découle pas de cette hypothèse seulement, mais de la première hypothèse + ce qu’on en a déduit + la seconde hypothèse.
Dans Cluedo (2), on introduit (“ on sait par ailleurs que ”un raisonnement indépendant, qui aurait pu être fait hors du cadre de l’hypothèse principale. Ce raisonnement n’a qu’une prémisse (“ quelqu’un n’a pas d’échelle ou de corde ”). On n’a pas le droit d’y faire jouer les éléments du premier raisonnement (prémisse: “ le meurtrier n’est pas l’un d’entre nous ”, conclusions: “ il a dû entrer... ”). Ou, si on le fait, cela revient à intégrer le raisonnement indépendant dans le premier comme une hypothèse additionnelle - i.e. on revient au raisonnement type Cluedo (1).
Dans la déduction naturelle, les hypothèses sont toujours additionnelles (modèle Cluedo 1).
2) pourquoi faire l’hypothèse que p, et pourquoi faire cette hypothèse pour en dériver q? Ces deux pas semblent inutiles: on a déjà p et q. Oui, mais ce qu’on veut, ce n’est pas dériver p ou dériver q, mais dériver que p implique q (p  q), étant données les prémisses. Pour faire ça, il faut faire l’hypothèse (additionnelle) que p, et parvenir à poser q, ce qui est trivial ici.
Dernier commentaire. Qu’a-t-on prouvé? Que si p et si q, alors p est vrai si et seulement si q. Exemple: “ Les baleines sont des mammifères. Les oiseaux volent. Donc, les oiseaux volent si et seulement si les baleines sont des mammifères. ” La conclusion a l’air fausse. L’étonnement vient de ce que tout ce qui est vrai s’implique matériellement. Ex: “ Les camions de pompiers sont rouges;  le soleil se couche à l’ouest. Donc: Si les camions de pompiers sont rouges, le soleil se couche à l’ouest ”. Cela est peut-être faux avec le sens qu’a “ si...alors ” dans la langue naturelle. Mais en logique, on utilise l’implication matérielle, pour laquelle, quand p et q sont tous les deux vrais, p  q est vrai.

5) (p & q)  r  p  (q  r)
1	(p & q)  r				
2		p		H	
3			q	H	
4			p	R(2)	
5			q	R(3)	
6			p & q	&I (4,5)	
7			(p & q)  r 	R(1)	
8			r	E (6,7)	
9		q  r		I (3-8)	
10	p  (q  r)			I (2-9)	
2 indices pour démarrer: 1) penser la preuve à rebours. 2) se demander dans quelles circonstances la prémisse (ligne 1) vous sera utile; et garder ça en tête. Lorsque (1) et (2) se rencontrent, vous avez trouvé la preuve!
Il faut démontrer qqch de la forme (p  X). Pour ça il faut I, et donc mettre p en hypothèse, et dériver X . La formule X est (q  r) : même chose, il faut I et donc mettre q en hypothèse. Ensuite on cherche les étapes à faire pour arriver à utiliser notre prémisse.

6) p, q  (p  r)  q  r
1	p			
2	q  (p  r)			
3		q	H	
4		q	R (3)	
5		q  (p  r)	R (2)	
6		p  r	E (4, 5)	
7		p	R (1)	
8		r	E (6, 7)	
9	q  r		I (3-8)	
Pas même la peine de penser toute la preuve à rebours: on se contente de savoir qu’il faut mettre q en hypothèse, et qu’on doit en dériver r. En appliquant mécaniquement les règles (en fait juste une règle, le modus ponens = E) on y arrive tout de suite.

7) p  q  (p & q)
1	p			
2		q	H	
3		p	R (1)	
4		q	R (2)	
5		p & q	&I (3, 4)	
6	q  (p & q)		I (2-5)	
Sans commentaire.

Preuves utilisant I
8)  (p & p)
(0)				
1		p & p	H	
2		p & p	R (1)	
3		p	&E (2)	
4		p	&E (2)	
5	(p & p)		I (1-4)	
Cas le plus simple d’utilisation de I. La règle I, bien nommée ‘réduction  à l’absurde’, marche de la façon suivante: vous voulez prouver que non-X (X). Pour ça, vous supposez que X, vous dérivez une contradiction (p puis non-p), et vous concluez que non-X. Exemple:
“ En supposant que ce que vous dites est vrai (X), les poules ont des dents (p), or les poules n’ont pas de dents (non-p), donc ce que vous dites est faux. ”
Ici on veut démontrer que (p & p). L’hypothèse à faire pour y arriver est donc: p & p. Il n’est pas difficile d’en dériver une contradiction: c’est déjà une contradiction, ramassée en une formule. Il suffit de la développer sur deux lignes.
Remarque. Nous avons donc une preuve, sans prémisse, du principe de non-contradiction! Avons-nous établit en trois lignes le principe, qu’Aristote a essayé de défendre en 5 pages obscures au début de la Métaphysique? En un sens oui, en un sens non. En un sens oui: c’est bien une preuve inconditionnelle. En un sens non: ce n’est une preuve que pour celui qui accepte d’abord les règles intro-élimination. Or la règle I suppose en fait le principe. A partir de là les avis sont partagés: certains soutiennent que cette preuve est un cercle vicieux, qui présuppose sous la forme de règles celles qu’elle doit prouver. D’autres (dans la lignée d’un philosophe d’Oxford et New York University, Christopher Peacocke) soutiennent qu’on ne peut pas avoir les concepts de négation sans accepter les règles (ce qui est assez proche de la défense aristotélicienne du principe). Parmi eux, un philosophe de New York University, Paul Boghossian, soutient une thèse très débattue en ce moment, selon laquelle il peut y avoir des preuves circulaires précisément dans les cas où les conditions minimales de compréhension d’un concept sont impliquées, comme ici.

9)  p  (p  q)
(0)						
1		p			H	
2			p		H	
3				q	H	
4				p	R(2)	
5				p	R (1)	
6			q		I(3-5)	
7			q		E(6)	
8		p  q			I (2-7)	
9	p   (p  q)				I (1-8)	
Combinaison de I et I.
I: nous donne les deux premières hypothèses. Pour montrer (p  X) il faut faire l’hypothèse p, puis dériver X. X est p  q. Pour montrer p  q il faut faire l’hypothèse p, puis dériver q.
Là (ligne 2) on semble être à une impasse: comment arriver à q ? Il n’y a pas de moyen direct. On utilise donc un moyen indirect, la règle I. Il faut y penser à chaque fois que vous êtes dans une impasse:
I: on veut q. Pour y arriver, on fait l’hypothèse de sa négation q (ligne 3), et on dérive une contradiction (lignes 4-5). Cela nous permet de conclure que l’hypothèse était fausse, i.e. (q), ligne 6, c’est-à-dire q (ligne 7). Et c’est dans la poche.
Remarque: Mais la contradiction (p et p, lignes 4-5) ne ‘dérive’ pas vraiment de  q! En fait elle dérive des hypothèses p et p, indépendamment de q! Réponse: cela n’a aucune importance - c’est autorisé par les règles. Il faut justement s’habituer à utiliser la règle I comme un outil pour arriver où l’on veut, sans se poser la question de savoir si la contradiction vient bien de l’hypothèse posée. 
Cela dit, l’utilisation de I dans les preuves n’est jamais absurde, même si, comme c’est peut-être le cas ici, le sens ne vous apparaît pas au moment où vous l’utilisez juste comme un moyen de dériver ce qui vous intéresse. Ici, on veut démontrer que des hypothèses p et p on peut déduire q. Or, la raison pour laquelle cela est possible, c’est que ces hypothèses sont contradictoires: d’une contradiction on peut tout déduire. Cela se traduit dans la preuve ci-dessus de la façon suivante: quelque soit l’hypothèse que vous fassiez ligne 3, vous en dériverez une contradiction lignes 4-5. Donc vous pouvez déduire ce que vous voulez ligne 6, en choisissant la bonne hypothèse ligne 3.

10) p  p  p
1	p  p			
2		p	H	
3		p	R (2)	
4		p  p	R (1)	
5		p	E (3,4)	
6	p		I (2-5)	
On veut arriver à p. Il n’y a pas de moyen direct: il faut donc utiliser I. Pour que I nous permette de conclure p, il faut faire l’hypothèse que p, et trouver une contradiction. Une fois l’hypothèse posée, le reste est facile.
Remarque. Signification de la preuve? Si une proposition p se contredit elle-même (p  p), alors cette proposition est fausse (p).

11) p  q, p  q  p
1	p  q			
2	p  q			
3		p	H	
4		p	R (2)	
5		p  q	R (1)	
6		q	E (4,5)	
7		p  q	R(2)	
8		q	E (4, 7)	
9	p		I (3-8)	
Même chose.
Remarque: signification de la preuve? Si une proposition p implique une chose q et son contraire q (p  q, p  q), alors cette proposition est fausse (p).

Autres preuves
Licences.
A partir d’ici j’utilise les licences qui permettent de raccourcir la présentation des preuves:
- les prémisses ou les hypothèses n’ont pas à être réitérées. Il suffit de donner leur numéro de ligne dans l’application de la règle. (NB: on doit toutefois réitérer lorsqu’on met en évidence une contradiction pour appliquer I)
- on saute l’application de la double négation. Lorsque I est appliqué à une hypothèse de la forme X, on pose directement X et non X.
Dans les preuves qui suivent, j’indique par des * les endroits où ces licences sont employées. (C’est pour vous, inutile de faire ça en exam.)

12) (p  q)  p  q
1	(p  q)  p					
2		q			H	
3			p		H	
4			p  q		E (1, 3)*	
5			q		E (3, 4)*	
6		p  q			I (3-7)	
7			q		H	
8				p	H	
9				q	R(7)	
10				q	R(2)	
11			p		I (8-10)*	
12		q  p			I (7-11)	
13		p  q			I (6, 12)	
14		p 			E (1, 13)*	
15		q			E (13, 14)	
16		q			R (2)	
17	q				I (2-16)*	
Comment trouver la preuve. Ok, j’avoue qu’on peut se perdre dans les différentes possibilités qu’il y a d’appliquer des règles, et que ce n’est pas si facile. Voici comment trouver la preuve:
On ne peut arriver à la conclusion directement. De la prémisse on peut seulement déduire p  (p  q) ou (p  q)  p, en faisant des hypothèses puis en appliquant E, mais on ne peut rien déduire de ces dernières.
I: il faut donc arriver à q indirectement, en utilisant I. Il faut donc faire l’hypothèse q et tenter de trouver une contradiction.
C’est là qu’on peut se perdre. On a la prémisse, (p  q)  p, on a q, et il faut trouver une contradiction. Mais quelle contradiction? 1) déduire q? (on a déjà q comme hypothèse)? 2) déduire p et p? 3) Une autre contradiction? Il faut envisager ces différentes possibilités ; la première (1) s’avère être la bonne.
Comment pourrait-on déduire q? Pas indirectement, en posant q : c’est ce qu’on vient juste de faire, on tournerait en rond. Donc directement, c’est-à-dire par le modus ponens, version équivalence: X  q, or X, donc q. Le peut-on? 
La prémisse (p  q)  p nous donnerait qqch de la forme X  q, à savoir p  q, si on avait p. (Parce que (p  q)  p avec p donne p  q, par E.) Et du même coup, toujours si on avait p, p  q nous donnerait q. Il faudrait donc déduire p. Le peut-on?
La prémisse  (p  q)  p nous donnerait p, si on avait p  q. (Par E.) Il faudrait donc déduire p  q. Le peut-on?
Il n’y a qu’une façon d’avoir p  q (directement): déduire p  q et déduire q  p. On essaie.  c’est ce qui se passe aux lignes 3-5 pour p  q, et 7-11 pour q  p. On trouve que ça marche; le reste découle facilement: on déduit p, lignes 13-14, et on déduit q facilement ligne 15 (parce qu’on a déja prouvé que p  q et on vient d’avoir p), on a notre contradiction.
Commentaire de la preuve.
(1) Pour arriver à q, je fais l’hypothèse que q et cherche une contradiction (lignes 2-16)
(2) Je cherche à prouver que p  q (lignes 3-13).
	(a) je cherche à prouver que p  q: je fais l’hypothèse que p et essaie de déduire q, lignes 3-5. Là c’est facile, il suffit de ‘dérouler’ les implications () contenues dans la prémisse.
	(b) je cherche à prouver que q  p: je fais l’hypothèse que q et essaie de déduire p, lignes 7-11. Là on dirait l’impasse: je n’ai rien dans la prémisse. (La prémisse me donnerait bien q  p, et comme j’ai fait l’hypothese que q, j’aurais p. Mais pour que la prémisse me donne q  p, il faudrait déjà que j’ai p, ce que je cherche justement à trouver.)
Quand on est dans l’impasse, on pense méthode indirecte: je veux p? je fais l’hypothèse p (ligne 10), et je cherche une contradiction. Le ciel s’éclaircit, les nuages s’écartent, le soleil apparaît: il y a une contradiction facile sous la main: j’ai fait l’hypothèse que q ligne 2, et que q ligne 9. 
(3) J’ai p  q (ligne 13). Avec la prémisse, ça me donne p (lignes 13-14). Le chemin jusqu’à q est désormais facile (ligne 15).

13) p  (q  r)  (p  q)  r
1	p  (q  r)				
2		p		H	
3		p  q		I (2)*	
4		(p  q)  r		I (3)	
					
5		q  r		H	
6			q	H	
7			p  q 	I (6)*	
8			(p  q)  r	I (7)	
					
9			r	H	
10			(p  q)  r	I (9)*	
11		(p  q)  r		E (5,  6-8, 9-10)*	
12	(p  q)  r			E (1, 2-4, 5-11)*	
La prémisse est de la forme ...... . Pour en tirer qqch il faut éliminer le . Pour éliminer A  B, il faut faire l’hypothèse que A et en déduire qqch C, faire l’hypothèse que B et en déduire la même chose C. Ici C est directement la conclusion qu’on cherche, i.e. (p  q)  r. Dans d’autres preuves, ce pourra être qqch qui mène rapidement à la conclusion cherchée.
Donc on examine la première branche de l’alternative, i.e. p, lignes 2-4, puis la seconde, i.e. (q  r), lignes 5-11. La seconde est elle-même une disjonction: même chose, on examine les deux branches, q, lignes 6-8, et r, lignes 9-10.
Le reste repose sur I. I est très souple, on peut introduire n’importe quoi. Si j’ai p, je peux poser p  X (ou  également X  p), et mettre ce que je veux à la place de X. Cf. par exemple lignes 9-10: j’ai r, donc je peux poser (p  q)  r.

14) (p  q)  p & q
1	(p  q)			
2		p	H	
3		p  q	I (2)*	
4		(p  q)	R (1)	
5	p		I (2-4)*	
6		q	H	
7		p  q	I (6)*	
8		(p  q)	R(1)	
9	q		I (6-8)*	
10	p & q		&I (5, 9)	
Comment trouver la preuve. A rebours: je veux p & q. Deux façons, directe et indirecte.
- indirecte. Je fais l’hypothèse  (p & q). Problème: cette hypothèse, pas plus que la prémisse (p  q), ne mène à rien. Nous n’avons aucune règle qui s’applique aux formules de type (...&...) ou (......). 
- directe. Il faudrait prouver p, puis prouver q.
	- prouver p. Directement, sans espoir (on n’a pas de règle à appliquer à la prémisse). Il faut donc faire indirectement. Je fais l’hypothèse de p (ligne 2). Là il faut penser à la règle I, qui me permet de dériver ce que la prémisse nie (ligne 3). J’ai une contradiction (ligne 4), et c’est gagné (ligne 5).
	- même chose pour prouver q.

15) (p & q)  p  q
1	(p & q)				
2		(p  q)		H	
3			p	H	
4			p  q	I (3)*	
5			(p  q)	R (2)	
6		p		I (3-5)*	
7			q	H	
8			p  q	I (7)*	
9			(p  q)	R(2)	
10		q		I (7-9)*	
11		p&q		&I (6, 10)	
12		(p&q)		R(1)	
13	p  q			I (2-12)*	
On ne peut pas arriver directement à la conclusion. Pour y arriver directement, il faudrait démontrer que p (ou sinon que q), puis appliquer I. Autrement dit il faudrait montrer qqch de plus fort que la conclusion. La conclusion dit seulement que p ou q ou les deux sont faux;  ce serait plus fort de pouvoir montrer, par ex, que p est faux. Pour cette raison, à savoir que I demande de montrer plus que ce que  dit, il est rare qu’on puisse obtenir une conclusion ...... directement.
Ici on ne peut pas: la prémisse dit que p et q ne sont pas tous deux vrais: impossible de déduire, par exemple, que p est faux.
On part donc sur la méthode indirecte. On fait l’hypothèse que (p  q), et on veut trouver une contradiction. Laquelle? On peut tenter de dériver le contraire de la prémisse (p&q): c’est justement ce qu’on a prouvé à la question précédente (preuve recopiée ici lignes 2-12).