1. Preuve simple
Définition
Faire une déduction consiste à montrer le chemin qui mène des prémisses à la conclusion d’un raisonnement. Il s’agit de montrer qu’on peut déduire la conclusion indiquée des prémisses données en utilisant certaines règles de déduction et lois logiques :
- Les règles de déduction (RD) sont des schémas de raisonnement qui ont pour effet de décomposer une formule complexe en une ou des parties plus simples. Les RD ne s’appliquent que sur des lignes entières, jamais sur des parties d’expressions.
- Les lois logiques (LL) servent à transformer des propositions données en d’autres propositions plus facilement décomposables à l’aide des règles de déduction. Les LL peuvent être appliquées sur des parties d’expressions.
Pour faire une déduction par preuve formelle, on ne peut pas donner une démarche à suivre définitive et univoque.
Exemple 1
On raisonne d’abord à rebours, de la conclusion vers les prémisses, pour trouver le chemin. Ensuite on écrit la déduction dans l’ordre inverse.
Raisonnement
À démontrer : ⊢ B
(1)A → B
(2)A → C
(3)C ∨ D
(4)D
Déduction
(5)CSD 3;4
(6)AMT 2;5
(7)BMP 1;6
Exemple 2
Les mêmes trois règles, mais dans un autre ordre.
Raisonnement
À démontrer : ⊢ A
(1)A → B
(2)C ∨ B
(3)D → C
(4)D
Déduction
(5)CMP 3;4
(6)BSD 2;5
(7)AMT 1;6
Exemple 3
D’autres règles de déduction : syllogisme hypothétique, simplification et conjonction.
Raisonnement
À démontrer : ⊢ (D ∧ A) ∧ B
(1)A ∧ B
(2)A → C
(3)C → D
Déduction
(4)A → DSH 2;3
(5)ASIMP 1
(6)DMP 4;5
(7)D ∧ ACONJ 5;6
(8)BSIMP 1
(9)(D ∧ A) ∧ BCONJ 7;8