4. Règles d'inférence
Les règles du cours sont les suivantes.
| Règle | Prémisses | Conclusion |
|---|---|---|
| Modus ponens | p→q, p |
q |
| Modus tollens | p→q, ¬q |
¬p |
| Transitivité | p→q, q→r |
p→r |
| Conjonction | p, q |
p∧q |
| Syllogisme disjonctif | p∨q, ¬p |
q |
| Simplification | p∧q |
p — ou symétriquement q |
| Addition | p |
p∨q |
| Résolution | p∨q, ¬p∨r |
q∨r |
Le modus ponens exige que l'implication et son antécédent soient déjà établis. Connaître seulement p→q et q ne permet pas de conclure p : ce serait l'affirmation du conséquent.
La résolution recherche une paire de littéraux complémentaires, ici p et ¬p, les élimine et réunit les littéraux restants. Elle deviendra centrale dans la forme clausale et la résolution-réfutation.
Une preuve peut réutiliser une prémisse ou une conséquence autant de fois que nécessaire. Plusieurs suites de règles peuvent mener au même but.