Remerciez-le!

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

Chapitre 3 Calcul propositionnel La logique propositionnelle permet essentielle

Chapitre 3 Calcul propositionnel La logique propositionnelle permet essentiellement de discuter des connecteurs grammaticaux comme la négation, la conjonction et la disjonction, en composant des propositions à partir de propositions données. Ces connecteurs sont parfois appelés aristotéliciens , car ils ont été mis en évidence par Aristote. Le calcul propositionnel permet essentiellement de parler de fonctions booléennes, c’est-à-dire de fonctions de {0, 1}n →{0, 1}. En effet, les variables, c’est-à-dire les propositions, ne peuvent prendre que deux valeurs, vrai ou faux. Le calcul propositionnel tient une grande place en informatique : ne serait-ce parce que nos ordinateurs actuels sont digitaux, et travaillent en binaire. Ce qui fait que nos processeurs sont essentiellement constitués de portes binaires du type de celles que l’on va étudier dans ce chapitre. D’un point de vue expressivité logique, le calcul propositionnel reste très limité : par exemple, on ne peut pas écrire en calcul propositionnel l’existence d’un objet ayant une propriété donnée. Le calcul des prédicats, plus général, que nous étudierons dans le chapitre 5Calcul des prédicatschapter.5, permet lui d’exprimer des propriétés d’ob- jets et des relations entre objets, et plus généralement de formaliser le raisonnement mathématique. Puisque le calcul propositionnel forme toutefois la base commune de nombreux systèmes logiques, et nous allons nous y attarder dans ce chapitre. 3.1 Syntaxe Pour déﬁnir formellement et proprement ce langage, nous devons distinguer la syn- taxe de la sémantique : la syntaxe décrit comment on écrit les formules. La sémantique décrit leur sens. Fixons un ensemble ﬁni ou dénombrable P = {p0, p1, · · · } de symboles que l’on appelle variables propositionnelles. Déﬁnition 3.1 (Formules propositionnelles) L’ensemble des formules propositionnelles F sur P est le langage sur l’alphabet P ∪{¬, ∧, ∨, ⇒, ⇔, (, )} déﬁni inductivement par les règles suivantes : 1 2 CHAPITRE 3. CALCUL PROPOSITIONNEL (B) il contient P : toute variable propositionnelle est une formule proposition- nelle ; (I) si F ∈F alors ¬F ∈F ; (I) si F, G ∈F alors (F ∧G) ∈F, (F ∨G) ∈F, (F ⇒G) ∈F, et (F ⇔G) ∈ F. Il s’agit d’une déﬁnition inductive qui est légitime par les considérations du chapitre précédent. Il s’agit d’une déﬁnition inductive non ambiguë : on peut reformuler ce fait par la proposition suivante, parfois appelé théorème de lecture unique. Remarque 3.1 La non-ambiguïté vient essentiellement des parenthèses explicites. On utilise ici l’astuce utilisée dans le chapitre précédent qui considérait Arith′ plutôt que Arith pour permettre d’écrire des expressions sans aucune ambiguïté de lecture. Proposition 3.1 (Décomposition / Lecture unique) Soit F une formule proposition- nelle. Alors F est d’une, et exactement d’une, des formes suivantes 1. une variable propositionnelle p ∈P ; 2. ¬G, où G est une formule propositionnelle ; 3. (G ∧H) où G et H sont des formules propositionnelles ; 4. (G ∨H) où G et H sont des formules propositionnelles ; 5. (G ⇒H) où G et H sont des formules propositionnelles ; 6. (G ⇔H) où G et H sont des formules propositionnelles. De plus dans les cas 2., 3., 4., 5. et 6., il y a unicité de la formule G et de la formule H avec ces propriétés. Le fait qu’une formule se décompose toujours dans un des 6 cas plus hauts est facile à établir inductivement. L’unicité de la décomposition découle de l’exercice suivant : Exercice 3.1. Montrer que la déﬁnition inductive précédente est non-ambiguë, c’est- à-dire que G et H sont uniquement déﬁnis dans chacun des cas plus haut. On pourra procéder de la façon suivante. – Montrer que dans toute formule F le nombre de parenthèses ouvrantes est égal au nombre de parenthèses fermantes. – Montrer que dans tout mot M préﬁxe de F, on a o(M) ≥f(M), où o(M) est le nombre de parenthèses ouvrantes, et f(M) le nombre de parenthèses fermantes. – Montrer que pour toute formule F dont le premier symbole est une parenthèse ouvrante, et pour tout mot M préﬁxe propre de F, on a o(M) > f(M). – Montrer que tout mot M préﬁxe propre de F n’est pas une formule. – En déduire le résultat. On appelle sous-formule de F une formule qui apparaît dans la décomposition récursive de F. 3.2. SÉMANTIQUE 3 p ¬p q p ∨q p ∧q p ⇒q p ⇔q 0 1 0 0 0 1 1 1 0 0 1 0 0 0 0 1 1 1 0 1 0 1 0 1 1 1 1 1 FIGURE 3.1 – Tableau de vérité. 3.2 Sémantique Nous allons maintenant déﬁnir la sémantique d’une formule propositionnelle, c’est- à-dire le sens qu’on lui donne. La valeur de vérité d’une formule se déﬁnit comme l’interprétation de cette for- mule, une fois que l’on s’est ﬁxé la valeur de vérité des variables propositionnelles : le principe est d’interpréter les symboles ¬, ∨, ∧, ⇒, ⇔par la négation logique, le ou lo- gique (appelé aussi disjonction), le et logique (appelé aussi conjonction), l’implication et la double implication (aussi appelée équivalence ) logique. Formellement, Déﬁnition 3.2 (Valuation) Une valuation est une distribution de valeurs de vérité aux variables propositionnelles, c’est-à-dire une fonction de P vers {0, 1}. Dans tout ce qui suit, 0 représente faux, et 1 représente vrai. On représente souvent les conditions de la déﬁnition suivante sous la forme d’un tableau de vérité : voir la ﬁgure 3.1. Proposition 3.2 Soit v une valuation. Par le théorème 2.5Fonction déﬁnie inductivementtheorem.2.5, il existe une unique fonction v déﬁnie sur tout F qui vériﬁe les conditions suivantes (B) v étend v : pour toute variable propositionnelle p ∈P, v(p) = v(p) ; (I) la négation s’interprète par la négation logique : si F est de la forme ¬G, alors v(F) = 1 ssi v(G) = 0 ; (I) ∧s’interprète comme le et logique : si F est de la forme G ∧H, alors v(F) = 1 ssi v(G) = 1 et v(H) = 1 ; (I) ∨s’interprète comme le ou logique : si F est de la forme G ∨H, alors v(F) = 1 ssi v(G) = 1 ou v(H) = 1 ; (I) ⇒s’interprète comme l’implication logique : si F est de la forme G ⇒H, alors v(F) = 1 ssi v(H) = 1 ou v(G) = 0 ; (I) ⇔s’interprète comme l’équivalence logique : si F est de la forme G ⇔H, alors v(F) = 1 ssi v(G) = v(H). On écrit v | = F pour v(F) = 1, et on dit que v est un modèle de F, ou que v satisfait F. On note v ̸| = F dans le cas contraire. La valeur de v(F) pour la valuation v est appelée la valeur de vérité de F sur v. 4 CHAPITRE 3. CALCUL PROPOSITIONNEL 3.3 Tautologies, formules équivalentes On souhaite classer les formules selon leur interprétation. Une classe particulière de formules est celles qui sont toujours vraies que l’on appelle les tautologies. Déﬁnition 3.3 (Tautologie) Une tautologie est une formule F qui est satisfaite par toute valuation. On note dans ce cas | = F. Déﬁnition 3.4 (Equivalence) Deux formules F et G sont dites équivalentes si pour toute valuation v, v(F) = v(G). On écrit dans ce cas F ≡G. Exemple 3.1 La formule p ∨¬p est une tautologie. Les formules p et ¬¬p sont équi- valentes. Remarque 3.2 Il est important de bien comprendre que ≡est un symbole que l’on utilise pour écrire une relation entre deux formules, mais que F ≡G n’est pas une formule propositionnelle. Exercice 3.2. Montrer que ≡est une relation d’équivalence sur les formules. 3.4 Quelques faits élémentaires Exercice 3.3. Montrer que pour toutes formules F et G, les formules suivantes sont des tautologies : (F ⇒F), (F ⇒(G ⇒F)), (F ⇒(G ⇒H)) ⇒((F ⇒G) ⇒(F ⇒H))). Exercice 3.4. [Idempotence] Montrer que pour toute formule F on a les équiva- lences : (F ∨F) ≡F, (F ∧F) ≡F. Exercice 3.5. [Associativité] Montrer que pour toutes formules F, G, H on a les équivalences : (F ∧(G ∧H)) ≡((F ∧G) ∧H), (F ∨(G ∨H)) ≡((F ∨G) ∨H). En raison de l’associativité, on note souvent F1 ∨F2 ∨· · · ∨Fk pour (((F1 ∨F2) ∨ F3) · · · ∨Fk), et F1 ∧F2 ∧· · · ∧Fk pour (((F1 ∧F2) ∧F3) · · · ∧Fk). 3.5. REMPLACEMENTS D’UNE FORMULE PAR UNE AUTRE ÉQUIVALENTE5 Remarque 3.3 Exactement comme on le fait avec les expressions arithmétiques : on écrit 1+2+3 pour ((1+2)+3) comme pour (1+(2+3)). Voir toutes les discussions sur Arith et Arith′ dans le chapitre précédent. Exercice 3.6. [Commutativité] Montrer que pour toutes formules F et G on a les équivalences : (F ∧G) ≡(G ∧F), (F ∨G) ≡(G ∨F). Exercice 3.7. [Distributivité] Montrer que pour toutes formules F, G, H on a les équivalences : (F ∧(G ∨H)) ≡((F ∧G) ∨(F ∧H)), (F ∨(G ∧H)) ≡((F ∨G) ∧(F ∨H)). Exercice 3.8. [Lois de Morgan] Montrer que pour toutes formules F et G on a les équivalences : ¬(F ∧G) ≡(¬F ∨¬G), ¬(F ∨G) ≡(¬F ∧¬G). Exercice 3.9. [Absorption] Montrer que pour toutes uploads/s3/ logique-prop-pdf.pdf