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 Calcul propositionnel : Syntaxe On utilisera un langage formel pour écr

Cours 3 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. 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 identiﬁcateur, 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éﬁ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 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éﬁnitions sont équivalentes (déﬁnition par le haut et déﬁnition 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 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(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éﬁnissons 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 identiﬁe une formule et son abréviation. Ce qui nous intéresse dans une formule, ce n’est pas son écriture superﬁcielle, 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éﬁnitions 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éﬁnitions d’une façon récursive. 3.5.1 La longueur d’une formule Déﬁnition 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 ﬁgurant dans F et f[F] le nombre de paren- thèses fermantes ﬁgurant 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éﬁnition 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