Exercice 3.1. Déduction naturelle
Montrez que les déductions suivantes sont valides. (J’utilise  au lieu du signe |- pour signifier la prouvabilité.) 
(1) p & p  p
(2)  (p&p)  p
(3) p & q  p  q
(4) p,  q  p  q		Commentaire: pour apprendre à manipuler I. Cela montre que tout ce qui est vrai s’implique. On voit bien ici que l’implication matérielle est différente du si... alors... intuitif!
(5) (p & q)  r  p  (q  r)	Commentaire: pour apprendre à manipuler I
(6)  p,  q  (p  r)  (q  r)	idem.
(7) p  q  (p & q)		idem.
(8)  (p&p)			Commentaire. pour apprendre à manipuler I. Venez-vous de démontrer le principe de non-contradiction?
(9)  p  (p  q)		Commentaire: pour apprendre à manipuler I.
(10) p  p  p		idem.
(11) p  q, p  q  p	idem.
(12) (p  q)  p  q		Commentaire. Long mais facile.
(13) (p  q)  r  p  (q  r)	Commentaire. Pour pratiquer E. Long mais facile. Indice: l’hypothèse est une disjonction. Il faut montrer que dans chaque cas on peut arriver à la conclusion.
(14) (p  q)  p&q	Commentaire. C’est une loi de Morgan. Pas facile. Il faut penser la dérivation à rebours: que doit-on démontrer? Puis utiliser I, c’est-à-dire faire des hypothèses et en dériver des contradictions pour arriver où on veut.
(15) (p&q)  p  q		Commentaire: même chose, en pire.