Notes de Cours T.Mellah
LA LOGIQUE PROPOSITIONNELLE
SOMMAIRE OBJET DE LA LOGIQUE I- DEFINITION ET NOTATION II- OPERATIONS LOGIQUES SUR LES PROPOSITIONS II-1 CONNECTEURS TABLE DE VERITE II-2 REGLES DE FORMATION II-3 LOIS LOGIQUES II-3-1 CONSEQUENCES LOGIQUES Définition 1. Tautologie et antilogie 2. Equivalence et implication logique 3. Argument II-3-2 ALGEBRES DES PROPOSITIONS III THEORIE DE DEMONSTRATION III-1 DEFINITION III-2 AXIOMES ET REGLES D’INFERENCES III-3 THEOREMES IV TABLE DE BETH IV-1 THEOREME DE BETH IV-2 PRINCIPE DE LA METHODE IV-3 EXERCICE
2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 6 7 7 7 7
A.U 2019-2020
1
Notes de Cours T.Mellah
IV Table de Beth
C’est une autre méthode de démonstration formelle sauf qu’elle est non axiomatique mais repose sur plusieurs règles d’inférences. Cette méthode se fonde sur le théorème suivant
IV-1 Théorème de Beth
Publicité
La formule f est un théorème si et seulement si + est la racine d’un arbre dont toutes les branches sont closes.
IV-2 Principe de la méthode
On démontre qu’une formule f est un théorème ( ⊢ + ) en suivant un raisonnement par l’absurde, c’est à dire en montrant que la réfutation de f , noté, + conduit à une contradiction.
La réfutation se conduit dans un arbre, appelé tableau de Beth. Réfuter f, c’est le « nier », selon sa forme en suivant les règles d’inférences suivants :
Règle d’affirmation
Règle de réfutation
¬J J
J ∨ K ↙↘ J K
J ∧ K J K
J → K ↙↘ J K
Publicité
J ↔ K ↙↘ J J K K
¬J J
J ∨ K J K
J ∧ K ↙↘ J K
J → K J K
J ↔ K ↙↘ J J K K
Ecrire dans tableau de Beth : A signifie « j’affirme A », et J signifie « de nie A »
Une branche de tableau de Beth est considérée comme terminée lorsque plus aucune règle ne peut s’appliquer.
Une branche est dite « close » lorsqu’elle contient une contradiction, notée ⊥. La règle de contradiction
J J ⊥
Publicité
IV-3 Exercice
Les formules suivantes sont-elles des théorèmes ? Justifier en appliquant un raisonnement par l’absurde.
1. P®( Q®PÙQ) 2.
(A®B)Ù(B®C)® (A®C)
A.U 2019-2020
7