Cours 3 Calcul propositionnel : Syntaxe On utilisera un langage formel pour écr

Cours 3 Calcul propositionnel : Syntaxe On utilisera un langage formel pour écrire les propositions afin d’éviter les ambiguïtés du langage naturel ou des notations imprécises. Dans le langage naturel, le même mot peut refléter des situations logiques différentes. 3.1 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 identificateur, avec ou sans indice, par exemple x, y, z, x1, y2. • Les parenthèses : ouvrante ( et fermante ). • Les connecteurs : ¬, ∨, ∧, ⇒, ⇔respectivement appelés négation, disjonction(ou), conjonc- tion(et), implication et équivalence. 3.2 Syntaxe d’une formule La syntaxe définit les règles de construction d’une formule de la logique propositionnelle. (Formule stricte) : Première Définition Une formule stricte est définie 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érifie 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érifie les règles, c’est l’ensemble des mots définies sur le vocabulaire A = P ∪{(, ), ¬, ∧, ∨, ⇒, ⇔}. On le note M(A). Donc F est l’intersection de tous les ensembles qui vérifient les règles. Deuxième Définition-Théorème F0 = P. Pour tout n, Fn+1 = Fn ∪{¬F, F ∈Fn} ∪{(FαG) F, G ∈Fn, α ∈{∨, ∧, ⇒, ⇔}} Notons que : Fn ⊂Fm pour tout n ≤m (Croissance.) Théorème F = ∪n≥0Fn Les deux définitions sont équivalentes (définition par le haut et définition par le bas). 1 Hauteur 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 diffé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 effet, b formule(1) ; ¬b formule(3) ;c formule(1) ; (¬b ∧c) formule(4) ;a formule(1) ; alors (a ∨(¬b ∧c)) formule(4). 3.3 Structure des formules propositionnelles Théorème de lecture unique Pour toute formule A, un et un seul cas de ces cas se présente : • A est une variable ou une constante. • A est de la forme ¬B où B est une formule. • A s’écrit d’une unique façon sous la forme (BαC) où B et C sont des formules et α est un connecteur binaire : α ∈{∧, ∨, ⇒, ⇔}. 3.3.1 Arbre de structure d’une formule On déduit du théorème de lecture unique :l’unicité de l’arbre de décomposition d’une formule. On présente la structure d’une formule sous la forme d’un arbre, pour montrer comment on doit lire cette formule. Les arbres des formules suivantes (¬a ∧(b ⇒c)); ((¬a ∧b) ⇒c); ((a ∨c) ∧((c ⇔a) ⇒b)) sont représentés comme suit : ∧ ¬ a ⇒ b c ⇒ ∧ ¬ a b c ∧ ∨ a c ⇒ ⇔ c a b Figure 3.1 – Arbre de structure 3.3.2 Formule à priorité Pour éviter la surabondance des parenthèses, nous définissons les formules à priorité. Formule à priorité • Une variable est une formule à priorité. • Une constante est une formule à priorité. • Si A est une formule (a.p) alors ¬A est une formule (a.p) • Si A et B sont des formules (a.p) alors AαB est une formule (a.p). • Si A est une formule (a.p) alors (A) est une formule (a.p). Remarque : Noter (et démontrer) que toute formule est une formule à priorité. Problème d’ambiguité. Est ce que A ⇒B ⇒C veut dire ((A ⇒B) ⇒C) ou bien (A ⇒(B ⇒C))? 2 Pour lever l’ambiguïté on introduit les priorités : Les priorités Les priorités sont les suivantes : • La négation est prioritaire, puis dans l’ordre des priorités décroissantes, on trouve la conjonction, la disjonction, l’implication et l’équivalence. ↓(¬, ∧, ∨, ⇒, ⇔) • À priorité égale, la connective gauche est prioritaire, sauf pour l’implication. Exemples On donne plusieurs exemples d’abréviation de formule par une formule à priorité : • ¬a ∧b ⇒c est l’abréviation de ((¬a ∧b) ⇒c) • a ∧b ∨c est l’abréviation de ((a ∧b) ∨c) • a ⇒b ⇒c est l’abréviation de ((a ⇒(b ⇒c) Sauf exception, on identifie une formule et son abréviation. Ce qui nous intéresse dans une formule, ce n’est pas son écriture superficielle, c’est sa structure, qui est mise en évidence par la syntaxe "stricte". 3.3.3 Notations booléennes Ceux sont des notations condensées utilisées souvent dans le domaine du matériel, utiles pour des gros calculs : (a ∧b : a · b) ; (a ∨b : a + b) ; (a ⇔b : a = b) ; (¬a : a) (a ⇒b : a ⇒b) ; (⊤: 1) ; (⊥: 0). Comme en arithmétique, on peut aussi abréger a · b en ab. ¬a ∧b ⇒c ∨a : ab ⇒c + a 3.4 Preuve d’une propriété sur l’ensemble des formules On peut utiliser la preuve par récurrence classique en se basant sur les entiers, par exemple, la longueur, la hauteur, le nombre de connecteurs dans une formule, etc. Par exemple pour montrer qu’une propriété est vraie pour toute formule, on montre qu’elle est vraie pour les formule de longueur 1. Puis on montre si elle est vraie pour toutes les formules de longueurs inférieurs ou égals à n, elle est vraie pour les formules de longueur n + 1. Deuxième méthode de preuve par récurrence pour les formules On montre que 1 X(F) est vrai pour tout F ∈P.(F0) 2 Si F satisfait la propriété X, alors ¬F la satisfait aussi. 3 Si F et G satisfont la propriété X, il en est de même pour (F ∧G), (F ∨G), (F ⇒G), (F ⇔G) On déclare alors que la propriété X(F) est vraie pour toute forumle. Cette méthode est commode, parce que on fait pas apparaître la hauteur ni aucun entier. 3.5 Définitions inductives Une formule peut être vue comme une liste de symboles (connecteurs, parenthèses, variables, et constantes). Un facteur d’une telle liste est une suite de symboles consécutifs dans la liste. Dans cette section nous pré- sentons quelques définitions d’une façon récursive. 3.5.1 La longueur d’une formule Définition 3.1 (Longueur d’une formule). La longueur d’une formule A est le nombre de symboles utilisés pour écrire A, dénotée lg(A). Exemple. Soit A = (a ∨b) et B = (A ∧¬A), nous avons lg(A) = 5 et lg(B) = 4 + 5 + 5 = 14. Longueur • Si A est une variable ou une constante alors lg(A) = 1. • Si A est ¬B, lg(A) = lg(B) + 1. • Si A est (BαC), lg(A) = lg(B) + lg(C) + 3. 3 Lemme 3.1 (Équilibre des parenthèses). Toute formule a un nombre égal de parenthèses ouvrantes et de parenthèses fermantes. Preuve. Notons o[F] le nombre de parenthèses ouvrantes figurant dans F et f[F] le nombre de paren- thèses fermantes figurant dans F. • Pour toute formule F ∈P, on a o[F] = f[F] = 0. • Pour toute formule F ∈F telle que o[F] = f[F], puisque o[¬F] = o[F] et f[¬F] = f[F] on a o[¬F] = f[¬F]. • Pour toutes formules F et G appartenant à F telles que o[F] = f[F] et o[G] = f[G], et quel que soit le symbole de connecteur binaire α, on a : o[(FαG)] = o[F] + o[G] + 1 = f[F] + f[G] + 1 = f[(FαG)] Ainsi, o[F] = f[F] pour toute formule propositionnelle F. 3.5.2 La hauteur d’une formule La hauteur d’une formule est la hauteur de l’arbre de sa structure. Hauteur d’une formule • Si A est une variable ou une constante alors h(A) = 0. • Si A est ¬B, h(A) = h(B) + 1. • Si A est (BαC), h(A) = sup(h(B), h(C)) + 1. Preuve de la troisième égalité Notons A = (BαC). Comme A / ∈P, il existe n entier tel que h[A] = n + 1 : A ∈Fn+1 et A / ∈Fn. Par la définition du bas de F, il existe A1 et A2 ∈Fn tel que A = (A1βA2). Le théorème de lecture unique donne β = α, A1 = B, A2 = C. Alors B et C ∈Fn. S’il existe m < n tel que B et C ∈Fm, alors (BαC) ∈Fm+1 ∈Fn, uploads/Litterature/ cours-3 2 .pdf

  • 50
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager