Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Cours 3 2 Cours Calcul propositionnel Syntaxe On utilisera un langage formel pour écrire les propositions a ?n d ? éviter les ambigu? tés du langage naturel ou des notations imprécises Dans le langage naturel le même mot peut re éter des situations logiqu

Cours Calcul propositionnel Syntaxe On utilisera un langage formel pour écrire les propositions a ?n d ? éviter les ambigu? tés du langage naturel ou des notations imprécises Dans le langage naturel le même mot peut re éter des situations logiques di ?érentes Vocabulaire Vocabulaire Le langage du calcul propositionnel noté F est celui des formules expressions bien formées construites à partir du vocabulaire suivant ? Les constantes les ? et ? représentent respectivement le vrai et le faux ? Les variables une variable est un identi ?cateur avec ou sans indice par exemple x y z x y ? Les parenthèses ouvrante et fermante ? Les connecteurs ?? ?? ?? ?? respectivement appelés négation disjonction ou conjonc- tion et implication et équivalence Syntaxe d ? une formule La syntaxe dé ?nit les règles de construction d ? une formule de la logique propositionnelle Formule stricte Première Dé ?nition Une formule stricte est dé ?nie de manière inductive comme suit ? Une variable est une formule stricte ? ? et ? sont des formules strictes ? Si A est une formule stricte alors A est une formule stricte ? Si A et B sont des formules strictes et si est une des opérations connecteurs ?? ?? ?? ?? alors A B est une formule stricte Le langage du calcul propositionnel est le plus petit ensemble des expressions qui véri ?e ces règles Autrement dit F est le plus petit ensemble qui contient P et stable par les opérations F F ?? G F ?? G F ?? G F ?? G P désigne l ? ensemble des variables et les constantes Il existe au moins un ensemble qui véri ?e les règles c ? est l ? ensemble des mots dé ?nies sur le vocabulaire A P ?? ?? ?? ?? ?? On le note M A Donc F est l ? intersection de tous les ensembles qui véri ?ent les règles Deuxième Dé ?nition-Théorème F P Pour tout n Fn Fn ?? F F ?? Fn ?? F G F G ?? Fn ?? ?? ?? ?? ?? Notons que Fn ? Fm pour tout n ? m Croissance Théorème F ??n ? Fn Les deux dé ?nitions sont équivalentes dé ?nition par le haut et dé ?nition par le bas CHauteur La hauteur d ? une formule stricte F ?? F est le plus petit des entiers n tels que F ?? Fn Elle est notée h F Dans la suite nous appelons simplement formule une formule stricte Les variables et les constantes sont des formules atomiques Les formules di ?érentes de ? ? et des variables sont des formules décomposables Remarque C ? est un ensemble inductif donc on pourra appliquer le principe d ? induction Exemple a ?? b ?? c est une formule En e ?et b formule b formule c formule b ?? c formule a formule alors a ?? b ?? c formule Structure des formules propositionnelles Théorème de lecture unique Pour toute