Remerciez-le!

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

1 Université Alger 1 / Faculté des sciences / Département Maths-Informatique Co

1 Université Alger 1 / Faculté des sciences / Département Maths-Informatique Cours de Logique mathématique 2eme année Maths et Informatique Enseignant : R. ZEBDI Année universitaire 2016 - 2017 2 Programme 1. Logique propositionnelle o Le langage o Les formes normales o Théorie de la démonstration o Consistance et complétude o La résolution 2. Logique des prédicats o Langage o Interprétation o Forme prénexe et forme de skolem 3. Calculabilité o Les fonctions récursives o La machine de turing 3 Introduction La logique au sens philosophique du terme, remonte à la période grecque. Le premier qui a enseigné la logique est le philosophe « Aristote ». Par la suite, ces livres ont été traduits en Arabe, par les savants musulmans Ibn sina Farabi dans la période Abbasside. On peut définir la logique comme : « la science qui étudie les règles générales du raisonnement correcte » Le but de l’étude de la logique est donc : 4. Raisonner correctement 5. Résoudre les problèmes complexes 6. Trouver les solutions rapidement Quand à la logique mathématique, elle est apparue vers la fin du XIXème siècle, Russel et Frege se sont parmi les fondateurs de cette science. A cette époque il y avait beaucoup de problèmes en mathématiques ; énoncés non encore démontrés, paradoxes, … Ces leaders ont fondé les bases de la logique mathématique afin de résoudre ces problèmes en représentant les énoncés mathématiques sous forme de formules ensuite les démontrer avec des méthodes de raisonnement rigoureuses. L’utilisation de la logique mathématique n’est pas limitée dans le domaine théorique pur, mais elle a fortement contribué à la naissance des premiers ordinateurs. La binarité de la valeur de vérité est la base de tous les circuits électronique qui composent l’ordinateur. Par la suite les bases de la logique mathématique ont beaucoup contribué dans les applications de l’intelligence artificielle. 4 Chapitre 1 Logique propositionnelle 5 La proposition (assertion) C’est une phrase informative qu’on peut juger vraie ou fausse Exemple : 1. La terre est sphérique … Vrai 2. Le soleil tourne autour de la terre … Faux On dit que la valeur de vérité de la première phrase = Vrai La proposition peut être affirmative ou négative Exemple : 7. La phrase 1 est affirmative 8. Sa forme négative : la terre n’est pas sphérique La proposition peut être composée. Dans ce cas sa valeur de vérité dépend des valeurs de vérité des propositions qui la composent : « La terre est sphérique et tourne autour du soleil » Cette proposition est vraie car elle est la conjonction de deux propositions vraies Il y a des phrases qui ne sont pas informatives : 9. Quel âge avez-vous ? 10. Rangez vos affaires. Ces phrases bien évidement ne sont pas considérées comme propositions car on ne peut pas dire vrai ou faux Le paradoxe C’est une phrase informative Mais elle n’est ni vraie ni fausse Exemple : « je ment » 6 Langage propositionnel Il est composé de : 1- L’Alphabet 11. Les propositions P, Q, R, … 12. Les connecteurs logiques :  ,  ,  ,  , ↔ 13. Les parenthèses symbole Appellation Prononciation  Négation Non P  Conjonction P et Q  Disjonction P ou Q  Implication P implique Q ↔ Equivalence P est équivalent à Q P si et seulement si Q 2- La syntaxe Une formule est une composition de propositions à l’aide de connecteurs logiques. On note α , β , … La composition se fait en respectant les règles suivantes : 14. Toute proposition est une formule 15. Si α est une formule alors  α est aussi une formule 16. Si α est β sont deux formules alors α o β est aussi une formule, tel que o  {  ,  ,  , ↔ } 17. Si α est une formule alors (α) est aussi une formule Exemple P , Q , P ,  Q , PQ ,QPR : des formules bien formées )PQ) , (P1)P2P3)) : formules mal formées 7 Priorité des connecteurs La connaissance des priorités permet la bonne lecture de la formule et évite les parenthèses supplémentaires. - La priorité des connecteurs de la plus forte à la plus faible: , , , , ↔ - Lorsque le même connecteur se répète dans la même formule, la priorité est donné à celui le plus à gauche. - Lorsqu’un connecteur est mis entre parenthèse alors il est prioritaire Exemples : 1. P  Q 1. Négation, 2.Conjonction 2.  P  Q  R 1. Négation, 2.Conjonction, 3. Implication 3. (P  Q)  R 1. Disjonction, 2. Conjonction 4. P  Q  R 1. Première implication 2. Deuxième implication Structure d’une formule On peut représenter une formule sous forme d’un arbre. Cela permet de bien lire la formule. Exemple : R   P  (Q  S)   Q P  R  S 8 3- Sémantique la sémantique du langage propositionnelle s’intéresse à donner une valeur de vérité à chaque formule du langage. On peut définir une fonction v : EF  } V , F { ; Tel que EF: ensemble des formules. Les valeurs de vérité des formules de base sont montrées dans les tableaux suivant , on les nomme les tables de vérité : Supposons que α est une formule qui contient n propositions, la table de vérité correspondante va contenir 2n lignes . Exemple α : Q  R  P  P P P↔Q PQ P  Q P  Q Q P F V V V V V V V V F F F V F F V F V V F V F V V F F F F α Q  R R Q P V V V V V V V F V V V V V F V F F F F V V V V V F V V F V F V V V F F V F F F F 9 Satisfiabilité Une formule α est satisfiable, ssi, sa table de vérité contient au moins une ligne dont la valeur de vérité de α est V Exemple R  Q  P est satisfiable P  Q   (P  Q) n’est pas satisfiable En généralisant, on dit qu’un ensemble de formules  ={α1 , α2 , … ,αn} est satisfiable ssi, dans sa table de vérité contient au moins une ligne tel que toutes les valeurs sont vraies. Exemple : {(PQ),(PQ), (PQ),(P↔Q)} est un ensemble satisfiable (voir le tableau précédant), par contre l’ensemble {(PQ),(PQ),P} est non satisfiable. Tautologie On dit qu’une formule β est une tautologie, si elle est vraie dans toutes les lignes de sa table de vérité. On note  β = Exemple : β : P  Q  Q P Q P  Q β V V V V V F F V F V F V F F F V On a donc  β = Une antilogie est une formule fausse dans toutes les lignes de sa table de vérité 10 Conséquence logique On dit que La formule β est une conséquence logique de la formule α (on note α β = ) si la valeur de vérité de β est V dans toutes les lignes où la valeur de vérité de α est V. En généralisant, on dit que La formule β est une conséquence logique de l’Ensemble de formules  ={α1 , α2 , … ,αn} (on note = β) si la valeur de vérité de β est V dans toutes les lignes où les valeurs de vérité des formules de  sont toutes vraies. Exemples : P  Q = P  Q {P  Q ,  Q} =  P P Q P  Q  Q  P V V V F F V F F V F F V V F V F F V V V Remarque : Toutes les formules sont conséquences logiques de tout ensemble de formules non satisfiable. Equivalence logique On dit que α et β sont logiquement équivalentes si elles ont la même table de vérité (on note : α  β) Exemple : P  Q   P  Q 11 Théorème 1 Démonstration des deux implications avec la contraposée 1) Si α1, … , αn = β alors α1, … , αn-1 = αn  β On suppose que la partie droite est fausse, donc αn  β n’est pas conséquence logique de α1, … , αn-1, cela veut dire qu’il existe une ligne dans la table de vérité où α1, … , αn-1 sont toutes V, avec αn  β est F, c-à-d la valeur de β est F alors que αn est V. On conclut qu’il y a une ligne dans laquelle α1, … , αn valent V et β vaut F, donc la partie gauche est fausse. 2) Si α1, … , αn-1 = αn  β alors α1, … , αn = uploads/Philosophie/ cours-logique-mathematiqe-17-18-m-zebdi.pdf