Remerciez-le!

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

Logiques Mathématiques Leila Jemni Ben Ayed Faculté des Sciences de Tunis Dépar

Logiques Mathématiques Leila Jemni Ben Ayed Faculté des Sciences de Tunis Département des Sciences de l’Informatique Ce cours est une introduction aux logiques mathématiques et aux techniques de déduction automatique. Il présente deux modèles de raisonnement fondés sur la logique des propositions et la logique des prédicats, permettant, d’avoir une approche mathématique de la programmation. Nous examinons la logique propositionnelle et la logique des prédicats du premier ordre. Nous discutons les liens entre les aspects formels dans ces logiques et les énoncés exprimés informellement. Différentes méthodes de preuve formelle sont présentées et appliquées. Références. - J.P. Delahaye, Outils Logiques pour l’Intelligence Artificielle, Eyrolles, Paris, 1988. - J. Vélu, Méthodes Mathématiques pour l’Informatique, Dunod, Paris, 2005. 1. Introduction 2. Propositions logiques 3. Opérateurs de base 4. Implications et équivalences 5. Quantificateurs • Définition 1. Une proposition atomique ou variable est une affirmation simple soit vraie, soit fausse. • Définition 2. Une proposition est composée de propositions atomiques, reliées entre-elles par des connecteurs logiques (⊃, ¬, ∨, ∧) On va revenir sur ce qu’est les connecteurs logiques tout de suite. Théorie des langages Leila Jemni Ben Ayed 3 Introduction Théorie des langages Leila Jemni Ben Ayed 4 Quelques exemples: A : « Le nombre de lettres dans l'alphabet français est 15. » La proposition A est fausse. B : « 5+2=7 » La proposition B est vraie. C : « x>10» C n'est pas une proposition logique complète car elle contient une variable libre x. On ne sait pas ce qu'est x (un point ? un nombre entier ? un vecteur ? une étoile de l'univers ?). On ne peut donc pas attribuer de valeur de vérité à la proposition C. C′ : « Soit x un nombre réel, alors x>7 » La proposition C′ est fausse. En effet C′ est une proposition logique car on a défini la variable x comme étant un nombre réel. Mais elle est fausse car par exemple 6 est un nombre réel et 6<7. Opérateurs de base • Les opérateurs permettent de construire de nouvelles propositions à partir d'une ou de plusieurs propositions initiales. Théorie des langages Leila Jemni Ben Ayed 5 Théorie des langages Leila Jemni Ben Ayed 6 Opérateurs de base\La négation Soit A une proposition. On définit une proposition « non A » que l'on note ¬A (avec une sorte de petit L allongé vers le bas). Si A est vraie alors ¬A est fausse. Si A est fausse alors ¬A est vraie. Théorie des langages Leila Jemni Ben Ayed 7 Définition : Une table de vérité est un tableau définissant la valeur d'une fonction logique pour chacune des combinaisons possibles des entrées. Construction : Dans la première colonne, je place toutes les valeurs que peut prendre A (c'est à dire Vrai ou Faux). Dans la seconde colonne, je place la valeur de vérité de ¬A correspondante. Par convention et pour faciliter la lecture de grandes tables, on écrit 0 pour la valeur FAUX et 1 pour la valeur VRAI. p p 0 1 1 0 Opérateurs de base\La négation Théorie des langages Leila Jemni Ben Ayed 8 Quelques exemples : A : « Paris est la capitale de la France » (1) ¬A : « Paris n'est pas la capitale de la France » (0) B : « π est un nombre entier » (0) ¬B : « π n'est pas un nombre entier » (1) C : « 5 est un nombre impair » (1) ¬C : « 5 est un nombre pair » (0) Opérateurs de base\La négation Logic CSCE 235, Spring 2010 9 Opérateurs de base\La conjonction • Soient A et B deux propositions. • On définit une nouvelle proposition « A ET B » que l'on note « A ∧B » • Le connecteur logique Et n'est vrai que lorsque les deux propositions sont vraies. On l'appelle aussi une conjonction • Examples – Il pleut et il fait chaud – (2+3=5) ET (1<2) • Table de vérité p q pq 0 0 0 0 1 0 1 0 0 1 1 1 Logic CSCE 235, Spring 2010 10 Opérateurs de base\La disjonction • Soient A et B deux propositions. • On définit une nouvelle proposition « A OU B » que l'on note « A ∨B » • La disjonction logique, ou logique, est vraie si l'une ou les deux propositions sont vraies. Examples – Il pleut ou c'est la deuxième conférence – (2 + 2 = 5)v(1 <2) – Vous pouvez avoir un gâteau ou une glace Table de vérité p q pq 0 0 0 0 1 1 1 0 1 1 1 1 Théorie des langages Leila Jemni Ben Ayed 11 Opérateurs de base Combinons maintenant les trois opérateurs vus précédemment ! Comme toujours, on considère A et B deux propositions. Cherchons les propositions équivalentes aux propositions P et Q telles que P: ¬(A ∧B) Q: ¬(A ∨B) Définition : On dit que deux propositions sont équivalentes lorsqu'elles ont les même valeurs de vérité. On va donc une nouvelle fois utiliser les tables de vérité. Exercice 3 : Établissez les tables de vérité des propositions P et Q Théorie des langages Leila Jemni Ben Ayed 12 A B A ∧B P 1 1 1 0 1 0 0 1 0 1 0 1 0 0 0 1 La tables de vérité de P Opérateurs de base Théorie des langages Leila Jemni Ben Ayed 13 A B A ∨B Q 1 1 1 0 1 0 1 0 0 1 1 0 0 0 0 1 La tables de vérité de Q Opérateurs de base Théorie des langages Leila Jemni Ben Ayed 14 Établissez maintenant les tables de vérité des proposions P' et Q' telles que P' : ¬A ∨¬B Q' : ¬A ∧¬B Puis comparez les valeurs de vérités de P et P' et de Q et Q' Opérateurs de base Théorie des langages Leila Jemni Ben Ayed 15 A B ¬A ¬B P' P Q' Q 1 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 1 1 0 1 1 0 0 0 0 1 1 1 1 1 1 On remarque que P et P' (respectivement Q et Q') ont les même valeurs de vérité. Les propositions P et P' (respectivement Q et Q') sont donc équivalentes. Si la proposition P est vraie alors la proposition P' est vraie. Si la proposition P est fausse alors la proposition P' est fausse. Si la proposition P' est vraie alors la proposition P est vraie Si la proposition P' est fausse alors la proposition P est fausse. De même avec Q et Q'. Opérateurs de base Théorie des langages Leila Jemni Ben Ayed 16 Cette conclusion nous permet d'écrire les lois de Morgan : ¬(A ∧B) équivaut à ¬A ∨¬B ¬(A ∨B) équivaut à ¬A ∧¬B Opérateurs de base Exercice: A : « Il est grand et a 15 ans ou plus. » B : « (pi>3∧π≤2) » Ecrivez ¬A et ¬B. • Le contraire de l'opérateur inférieur strict (respectivement supérieur strict) est supérieur ou égal (respectivement inférieur ou égal). Théorie des langages Leila Jemni Ben Ayed 17 Opérateurs de base\L’implication • Soient A et B deux propositions. • On définit une nouvelle proposition « A IMPLIQUE B » que l'on note « A ⇒B » • La définition mathématique est la suivante : L’assertion « (non P) ou Q » est notée « P ⇒Q ». • Sa table de vérité est donc la suivante : Table de vérité p q p⇒q 0 0 0 0 1 1 1 0 1 1 1 1 Opérateurs de base\L’implication L’assertion « P ⇒Q » se lit en français « P implique Q ». Elle se lit souvent aussi « si P est vraie alors Q est vraie » ou « si P alors Q ». Par exemple : • « 0 <=x <=25⇒√x <=5» est vraie (prendre la racine carrée). • « x ∈] −∞,−4[ ⇒x 2 + 3x − 4 > 0 » est vraie (étudier le binôme). • « sin(θ) = 0 ⇒θ = 0 » est fausse (regarder pour θ = 2π par exemple). • « 2 + 2 = 5 ⇒√2 = 2 » est vraie ! Eh oui, si P est fausse alors l’assertion « P ⇒Q » est toujours vraie. Opérateurs de base\ L’équivalence • L’équivalence est définie par : • « P ↔Q » est l’assertion « (P ⇒Q) et (Q ⇒P) ». • On dira « P est équivalent à Q » ou « P équivaut à Q » ou « P si et seulement si Q ». • Cette assertion est vrai lorsque P et Q sont vraies ou lorsque P et Q sont fausses. • Sa table de vérité est donc la suivante : Table de vérité p q p↔q 0 0 1 0 1 0 1 0 0 1 1 1 Opérateurs de base\ L’équivalence • Proposition 1. Soient P,Q,R trois assertions. Nous avons les équivalences (vraies) uploads/Philosophie/ cours-logique-farid 1 .pdf