Remerciez-le!

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

Introduction La logique est utile dans beaucoup de domaines : Conception de cir

Introduction La logique est utile dans beaucoup de domaines : Conception de circuits. Preuves de programmes. Programmation logique. Simulation de raisonnements en intelligence artiﬁcielle. . . . Nous n’utiliserons que le calcul des propositions : bien que limité, c’est la première étape dans la déﬁnition de la logique et du raisonnement. Le calcul des prédicats qui englobe le calcul des propositions et qui permet une formalisation achevée du raisonnement mathématique, ne sera pas abordé. G. Koepﬂer Numération et Logique Calcul des propositions L1 2014-2015 180 Introduction Une proposition est une afﬁrmation du type "il pleut" ou "2+2=3" . On peut lui affecter une valeur de vérité : vrai ou faux. Une proposition ne contient ni des variables, ni des quantiﬁcateurs. Un prédicat est une proposition dont la valeur de vérité dépend de variables. Par exemple “L ’étudiant.e XY habite à Paris” est vrai ou faux en fonction de l’étudiant. En calcul des prédicats on utilise les quantiﬁcateurs : “Tout étudiant.e habite à Paris”. Le calcul des propositions traite du raisonnement sur les propositions. Il déﬁnit les règles de déduction qui relient les propositions, tout ceci indépendamment de leur contenu. On ne traite que des valeurs booléennes {vrai, faux} ou {1,0}. G. Koepﬂer Numération et Logique Calcul des propositions L1 2014-2015 181 Syntaxe et sémantique Dans les théories de la logique mathématique, en particulier en calcul des propositions, on considère deux aspects : La syntaxe, où l’on déﬁnit le langage du calcul des propositions par les règles d’écriture des formules. La sémantique qui détermine les règles d’interprétation des formules. On attribue des valeurs de vérité (vrai/faux) aux propositions élémentaires et on explique comment les connecteurs se comportent vis-à-vis de ces valeurs de vérité. On exprime souvent ce comportement par une table de vérité. G. Koepﬂer Numération et Logique Calcul des propositions L1 2014-2015 182 Exemple de syntaxe et sémantique On considère les phrases dans une langue : La syntaxe ﬁxe les règles d’écriture des phrases. PHRASE = ( SUJET | VERBE | COMPLÉMENT ) La sémantique permet l’interprétation des phrases. Exemples : 1 “le chat boit son lait” 2 “le fermier conduit un troupeau” 3 “le lait boit son chat” 4 “un troupeau conduit le fermier” Une phrase dont la syntaxe est correcte, n’a pas nécessairement un sens G. Koepﬂer Numération et Logique Calcul des propositions L1 2014-2015 183 Les constituants du langage La syntaxe du calcul des propositions utilise Les variables propositionnelles ou propositions atomiques. Notées p1, p2, . . . ou p, q, r,. . . Les opérateurs ou connecteurs. Ils permettent la construction de propositions plus complexes. ¬ non négation ∧ et conjonction ∨ ou disjonction →ou ⇒ implique implication ↔ou ⇔ équivaut équivalence La ponctuation “(“ et ”)”, les parenthèses permettent de lever les ambiguïtés. Ces éléments constituent l’alphabet du calcul propositionnel. G. Koepﬂer Numération et Logique Calcul des propositions L1 2014-2015 184 Les formules propositionnelles Grâce à cet alphabet, on peut construire l’ensemble des mots qui est l’ensemble des suites ﬁnies d’éléments de l’alphabet. L ’ensemble des formules ou expressions bien formées du calcul des propositions est le plus petit ensemble de mots tel que 1 les variables propositionnelles, ou atomes, sont des formules ; 2 si A est une formule, alors ¬A est une formule ; 3 si A et B sont des formules, alors (A ∗B) est une formule, où ∗est l’un des connecteurs binaires, ∗∈{∧, ∨, →, ↔}. G. Koepﬂer Numération et Logique Calcul des propositions L1 2014-2015 185 Exemple Considérons la formule (((¬a ∨b) ∧c) →(¬¬a ∧¬b)) On omet en général les parenthèses extrêmes des formules, d’où ((¬a ∨b) ∧c) →(¬¬a ∧¬b) Vériﬁcation de la cohérence des parenthèses : On attribue un poids +1 à la parenthèse ouvrante, un poids -1 à la parenthèse fermante et 0 aux autres symboles. La somme des poids d’une formule est alors nulle. Attention : ceci ne sufﬁt pas à garantir que la formule est syntaxiquement correcte. Les parenthèses sont importantes pour lever les ambiguïtés lorsque l’on utilise des connecteurs binaires. Exemple : comment interpréter p →q →r ? Soit (p →q) →r, soit p →(q →r). G. Koepﬂer Numération et Logique Calcul des propositions L1 2014-2015 186 Distribution de vérité Une distribution de vérité δ est une application de l’ensemble des variables propositionnelles dans l’ensemble des valeurs de vérité {0, 1}. Exemple : δ : {a, b} − →{0, 1}, or comme δ(a) = 0 ou 1, et de même pour δ(b), il y a 22 = 4 distributions de vérité possible : a 0 0 1 1 b 0 1 0 1 Une distribution δ étant ﬁxée, on déﬁnit δ(F), ou val(F, δ), pour toute formule F, à partir des tables de vérité. Une distribution de vérité δ se prolonge ainsi en une application de l’ensemble des formules dans {0, 1}. G. Koepﬂer Numération et Logique Calcul des propositions L1 2014-2015 187 Tables de vérité des connecteurs On peut écrire δ(¬a) : a ¬a 1 0 0 1 Les tables de vérité des connecteurs binaires sont a b a ∧b a ∨b a →b a ↔b 0 0 0 0 1 1 0 1 0 1 1 0 1 0 0 1 0 0 1 1 1 1 1 1 On peut ainsi donner le comportement associé à chaque formule : ¬a prend la valeur 1 si et seulement si a prend la valeur 0. a →b prend la valeur 0 si et seulement si a prend la valeur 1 et b prend la valeur 0. . . . G. Koepﬂer Numération et Logique Calcul des propositions L1 2014-2015 188 Sémantique : valeurs d’une formule Une distribution δ donnée est un modèle de F si δ(F) = 1. Exemple : la distribution δ(a) = 1 et δ(b) = 0 est un modèle pour la formule F = a ∨b. Une formule F est une tautologie si pour toute distribution δ, on a δ(F) = 1. On dit aussi que F est valide. On note | = F. Exemple : La formule a ∨¬a est une tautologie, donc | = (a ∨¬a) Une formule F est une antilogie si pour toute distribution δ, on a δ(F) = 0. On dit aussi que F est une contradiction ou insatisfaisable. Exemple : La formule a ∧¬a est une antilogie. G. Koepﬂer Numération et Logique Calcul des propositions L1 2014-2015 189 Sémantique : valeurs d’une formule Si la formule F prend au moins une fois la valeur 1, on dit que F est satisfaisable. Deux formules F et G sont équivalentes si et seulement si pour toute distribution δ on a δ(F) = δ(G). On note "Feq G" la propriété "les formule F et G sont équivalentes". Attention : ne pas confondre "↔" et eq . Le premier est un symbole du langage formel, le second un symbole du métalangage. Ainsi (F ↔G) est une formule, tandis que "Feq G" énonce une propriété des formules F et G. Et "Feq G" est un énoncé équivalent à | = F ↔G . G. Koepﬂer Numération et Logique Calcul des propositions L1 2014-2015 190 Exemple 1 Évaluons A = ((¬a ∨b) ∧c) →(¬¬a ∧¬b) . On pose F = ((¬a ∨b) ∧c) et G = (¬¬a ∧¬b). a b c ¬a ∨b F G F →G 0 0 0 1 0 0 1 0 0 1 1 1 0 0 0 1 0 1 0 0 1 0 1 1 1 1 0 0 1 0 0 0 0 1 1 1 0 1 0 0 1 1 1 1 0 1 0 0 1 1 1 1 1 1 0 0 La formule A est satisfaisable et la distribution (0, 0, 0) est un modèle de A. G. Koepﬂer Numération et Logique Calcul des propositions L1 2014-2015 191 Exemple 2 Évaluons B = ((p ∨r) ∧(q ∨¬r)) →(p ∨q) . On pose F = (p ∨r) ∧(q ∨¬r) . p q r p ∨r q ∨¬ r F p∨q B 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 1 0 1 0 0 1 0 1 1 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 La formule B est une tautologie : | = ((p ∨r) ∧(q ∨¬r)) →(p ∨q) G. Koepﬂer Numération et Logique Calcul des propositions L1 2014-2015 192 Quelques tautologies Pour toutes formules A, B : | = (A →A) identité | = (A ∨¬A) tiers exclus | = (A →(A ∨B)) | = (A ∧¬A) →B | = ((A ∧B) →A) | = [A →(B →A)] Pour toutes formules A, B et C : | = (A →B) →[(B →C) →(A →C)] exemple de syllogisme | = {[A →(B →C)] →[(A →B) →(A →C)]} | = {(¬B →¬A) →[(¬B →A) →B)]} G. Koepﬂer Numération et Logique Calcul des propositions L1 2014-2015 193 Formules équivalentes Lois de uploads/Philosophie/ nl-cm7.pdf