Chapitre 2 Logiques et Raisonnement PDF

Chapitre 2 Logiques et Raisonnement Pr. Meftah Boudjelal 11 1. Introduction Il est fréquent d’entendre "c’est logique" lorsque quelqu’un tente de partager son point de vue. Cette expression qui semble anodine, demande pourtant à ceux qui l’entendent d’adopt...

Chapitre 2 Logiques et Raisonnement Pr. Meftah Boudjelal 11 1. Introduction Il est fréquent d’entendre "c’est logique" lorsque quelqu’un tente de partager son point de vue. Cette expression qui semble anodine, demande pourtant à ceux qui l’entendent d’adopter le raisonnement de celui qui la dit. Typiquement, cette expression sous- entend une évidence dans les propos qui la précède, mais en réalité derrière cela se cache tout un raisonnement, qu’il soit par déduction, par l’absurde, ou par élimination. 1.1 Bref historique Les philosophes de la Grèce Antique ont posé les fondements de la logique. En particulier, Aristote expose les bases de la logique. La logique d'Aristote va être enseignés pendant très longtemps, elle prédomine jusqu'au Moyen Ages au moins, et ce n'est que très récemment qu'est apparu la logique moderne. C'est Frege qui a posé les bases de la logique moderne. La différence essentielle par rapport à la logique d'Aristote est que Frege a une approche mathématique de la logique, alors que la logique d'Aristote est teintée de Philosophie. Il va ainsi développer la logique des propositions et la logique des prédicats. Alors qu'Aristote se servait du langage courant pour faire des raisonnements logiques, Frege se sert d'un langage symbolique : l'idéographie. Leibniz avait déjà tenté de créer un langage logique qu'il appelait « la caractéristique universelle » malheureusement sans succès, et il n'aboutit pas à quelque chose qui puisse le satisfaire. Aujourd'hui le langage logique moderne n'est pas l'idéographie qui n'est plus utilisé, mais certains symboles sont dérivés de ce langage. 1.2. De l’importance de la logique La logique est l’étude de l’art de bien penser. La logique est devenue une pierre angulaire de la philosophie et des mathématiques, et plus récemment elle l’est aussi devenue pour la linguistique et l’informatique. 2. Définitions 2.1. Qu'est-ce que la logique ? La logique vient du grecque « logos » qui signifie « parole, discours », et par extension « rationalité », la logique est donc la science de la raison. Plus précisément, c'est la science qui étudie les règles que doivent respecter tout raisonnement valide, qui permet de distinguer un raisonnement valide d'un raisonnement qui ne l'est pas. 2.2. La logique propositionnelle La logique propositionnelle est la composante la plus simple de la logique classique. Les objets de cette logique, c’est à dire les éléments de son langage, sont des énoncés susceptibles d’être soit vrais, soit faux, et construits par composition à partir d’énoncés de base. La logique des propositions est un langage formel constitue d’une syntaxe et d’une sémantique. La syntaxe décrit l’ensemble des formules qui appartiennent au langage. La sémantique permet de donner un sens aux formules du langage. Pr. Meftah Boudjelal 12 2.3. Qu’est-ce qu’une proposition ? Une proposition (ou assertion) est une phrase déclarative qui peut-être soit vraie soit fausse (mais pas les deux). Exemple a) Il pleut b) Il fait beau c) 2+2=5 Ce qui exclut, entre autres, les questions (a), les impératifs (b), les exclamatifs (c), et plus généralement tous les énoncés dits non assertifs, comme certains performatifs (d), certains énoncés à fonction phatique (e), ou toute la classe des énoncés modalisés (f). a) Est-ce que Said assiste au cours ? b) Fermez la porte ! c) Qu’elle est gentille ! d) Je te promets de venir e) Tu m’entends ! f) L’examen aura lieu demain 2.4. Proposition atomique Une proposition atomique, également appelée proposition élémentaire, est une proposition qui ne peut pas être décomposée en propositions plus simples. Elle est la plus petite unité de signification logique et ne contient pas d'opérateurs logiques. 2.5. Proposition composée Une proposition composée est une proposition formée en combinant des propositions atomiques ou d'autres propositions composées à l'aide d'opérateurs logiques. Les propositions composées peuvent être décomposées en propositions plus simples. 2.6. Table de vérité Le table de vérité est un outil utilisé pour déterminer la valeur de vérité d'une proposition complexe en fonction des valeurs de vérité de ses composants. 2.7. Tautologie Une tautologie est une formule qui est vraie dans toutes les interprétations. 2.8. Proposition cohérente Une proposition est dite cohérente si elle n'est pas contradictoire, c'est-à-dire si elle ne conduit pas à une contradiction logique. En d'autres termes, une proposition cohérente est une proposition qui peut être vraie dans au moins un modèle possible. Pr. Meftah Boudjelal 13 3. Connecteurs logiques Les connecteurs sont des opérateurs qui permettent, en reliant deux propositions, de former une nouvelle proposition : avec cette définition, le prototype du connecteur est le mot et, qui (au moins dans certains cas) fonctionne en effet de cette manière-là : la phrase suivante est une proposition formée au moyen du connecteur et et de deux (autres) propositions. a. Il pleut à Mascara b. Il neige à Setif c. Il pleut à Mascara et il neige à Setif 3.1. Négation d’une proposition Soit P une proposition. On définit sa négation, notée 𝑃𝑃 (ou aussi nonP ou ¬𝑃𝑃), à partir de sa table de vérité. P ¬𝑃𝑃 V F F V 3.2. Le connecteur « ou » (disjonction) Ce connecteur permet de former des formules comme « P ou Q ». Ce connecteur s'écrit ∨. On a donc la table de vérité : P Q 𝑃𝑃 ∨ 𝑄𝑄 V V V V F V F V V F F F 3.3. Le connecteur « et » (conjonction) Ce connecteur permet de former des formules comme « P et Q ». Ce connecteur s'écrit ∧. On a donc la table de vérité : P Q 𝐴𝐴 ∧ 𝑄𝑄 V V V V F F F V F F F F 3.4. Le connecteur « si... alors » (implication) Il est représenté par le symbole ⇒: P Q 𝑃𝑃 ⇒ 𝑄𝑄 V V V V F F F V V F F V Pr. Meftah Boudjelal 14 3.5. Le connecteur « est équivalent à » Le connecteur « équivalence » s'écrit symboliquement : ⟺, et veut dire : « à la même valeur de vérité que ». P Q 𝑃𝑃 ⟺ 𝑄𝑄 V V V V F F F V F F F V 3.6. Lois de de Morgan Soient P et Q deux propositions. 𝑃𝑃 ∨ 𝑄𝑄 𝑃𝑃 ∧ 𝑄𝑄 ⟺ 𝑃𝑃 𝑃𝑃 ∧ 𝑄𝑄 ∨ 𝑄𝑄 ⟺ (Le contraire de « et » est « ou » et le contraire de « ou » est « et »). 4. Langage de la logique propositionnelle On peut maintenant définir le langage de la logique des propositions. On doit donc inclure les propositions (formules atomiques) ainsi toutes les formules composées possibles. L'alphabet de la logique propositionnelle est constitué : 1. d'un ensemble de formules atomiques, 2. des connecteurs : ¬ ∨ ∧ ⇒ ⟺ 3. des séparateurs (parenthèses) : « ( » et « ) ». Les parenthèses sont utiles dans les formules logiques car il faut se rendre compte par exemple que la formule : ¬P ∨ Q est différente de la formule : ¬ (P ∨ Q). On peut ensuite définir la syntaxe des formules bien formés : Syntaxe : l'ensemble des formules de la logique est le plus petit ensemble tel que : Si P est une formule atomique alors P est une formule, si P est une formule, alors : ¬P est une formule, si P et Q sont des formules, alors (P ∨ Q) est une formule, si P et Q sont des formules, alors (P ∧ Q) est une formule, si P et Q sont des formules, alors (P ⇒ Q) est une formule, si P et Q sont des formules, alors (P ⟺ Q) est une formule. 5. Limites de la logique propositionnelle La logique propositionnelle, bien qu'elle soit un outil puissant pour le raisonnement formel, présente certaines limites. Pr. Meftah Boudjelal 15  Absence de structure interne des propositions - La logique propositionnelle traite les propositions comme des unités indivisibles. Elle ne permet pas de décomposer les propositions en leurs composants internes (sujets, verbes, objets, etc.). Par conséquent, elle ne peut pas représenter les relations entre les éléments internes des propositions. - Exemple : La proposition "Tous les humains sont mortels" ne peut pas être décomposée en "humains" et "mortels" dans la logique propositionnelle. Limitation de l'expressivité - La logique propositionnelle ne peut pas exprimer des concepts complexes tels que les quantificateurs (comme "pour tout" et "il existe"), les relations entre objets, ou les propriétés des objets. - Exemple : La proposition "Il existe un nombre premier plus grand que 10" ne peut pas être exprimée directement en logique propositionnelle. Absence de raisonnement sur les objets - La logique propositionnelle ne permet pas de raisonner sur les objets et leurs propriétés. Elle ne peut pas représenter des énoncés tels que "Tous les chats sont des animaux" ou "Il existe un nombre premier plus grand que 10". - Exemple : La proposition "Tous les chats sont des animaux" nécessite une logique plus expressive, comme la logique des prédicats, pour être correctement représentée. Limitation des opérateurs logiques - Les opérateurs logiques de la logique propositionnelle (négation, conjonction, disjonction, implication, équivalence) sont limités à des opérations sur des propositions entières. Ils ne peuvent pas manipuler des parties spécifiques des propositions. - Exemple : La proposition "Si x est un humain, alors x est mortel" nécessite des quantificateurs et des prédicats pour être correctement représentée. Absence de raisonnement temporel et modal - La logique propositionnelle ne peut pas représenter des concepts temporels (comme "avant", "après", "toujours", "jamais") ou modaux (comme "possible", "nécessaire"). - Exemple : La proposition "Il est possible qu'il pleuve demain" nécessite une logique modale pour être correctement représentée. Pr. Meftah Boudjelal 16  Limitation des inférences complexes - La logique propositionnelle est limitée dans sa capacité à représenter des inférences complexes qui dépendent de la structure interne des propositions. - Exemple : La proposition "Si tous les humains sont mortels et Socrate est un humain, alors Socrate est mortel" nécessite une logique des prédicats pour être correctement représentée et déduite. Absence de représentation des connaissances contextuelles - La logique propositionnelle ne peut pas représenter des connaissances contextuelles ou des relations entre différents contextes. - Exemple : La proposition "Dans le contexte de la médecine, un virus est un agent infectieux" nécessite une logique plus expressive pour être correctement représentée. Pour surmonter ces limitations, des extensions de la logique propositionnelle ont été développées, telles que la logique des prédicats, la logique modale, la logique temporelle, et d'autres formes de logique plus expressives. Ces extensions permettent de représenter et de raisonner sur des concepts plus complexes et plus riches que ceux que la logique propositionnelle peut gérer. 6. Logique du 1er ordre La logique du premier ordre, également connue sous le nom de logique des prédicats ou calcul des prédicats du premier ordre, est une extension de la logique propositionnelle qui permet de représenter et de raisonner sur des énoncés plus complexes. Elle introduit des concepts tels que les prédicats, les variables, les quantificateurs et les fonctions, ce qui lui permet de traiter des structures internes des propositions et des relations entre objets. Elle est utilisée dans de nombreux domaines, notamment en mathématiques, en informatique, en intelligence artificielle et en philosophie, pour modéliser et analyser des structures logiques complexes. En mathématiques, la logique du premier ordre fournit un cadre uniforme pour exprimer des propositions, construire des preuves et définir des structures mathématiques. En informatique, elle sous-tend la conception de langages de programmation et d'algorithmes, et est utilisée pour formaliser des preuves et des raisonnements. 6.1. Prédicat Un prédicat est une fonction ou une relation qui prend un ou plusieurs arguments et retourne une valeur de vérité (vrai ou faux). En logique du premier ordre, les prédicats Pr. Meftah Boudjelal 17 sont utilisés pour exprimer des propriétés ou des relations entre objets. Ils permettent de formuler des énoncés plus complexes et plus expressifs que ceux de la logique propositionnelle. Un prédicat est une expression de la forme 𝑃𝑃(𝑥𝑥1 , 𝑥𝑥2 , … , 𝑥𝑥𝑛𝑛 ) , où : 𝑃𝑃 est le symbole du prédicat. 𝑥𝑥1 , 𝑥𝑥2 , … , 𝑥𝑥𝑛𝑛 sont des variables ou des constantes qui représentent des objets dans un domaine de discours. Exemples de prédicats Prédicat unaire (un seul argument) : 𝐻𝐻(𝑥𝑥) : "x est un humain". 𝐸𝐸(𝑥𝑥) : "x est un étudiant". Prédicat binaire (deux arguments) : 𝐴𝐴(𝑥𝑥, 𝑦𝑦) : "x est ami avec y" 𝐺𝐺(𝑥𝑥, 𝑦𝑦) : "x est plus grand que y". Prédicat ternaire (trois arguments) : 𝑆𝑆(𝑥𝑥, 𝑦𝑦, 𝑧𝑧) : "x est la somme de y et z". 6.2. Quantificateurs existentiels et universels Les quantificateurs existentiels et universels sont des opérateurs logiques utilisés en logique du premier ordre pour exprimer des énoncés sur des ensembles d'objets. Ils permettent de formuler des propositions qui s'appliquent à tous les éléments d'un domaine (quantificateur universel) ou à au moins un élément d'un domaine (quantificateur existentiel). 6.2.1. Quantificateur universel (∀) ∀ : "Quelque soit", "Pour tout" ou "Pour chaque". Le quantificateur universel ∀ est utilisé pour exprimer des énoncés qui s'appliquent à tous les éléments d'un domaine. Exemple : ∀𝑥𝑥𝑥𝑥(𝑥𝑥) signifie : quelque soit x, P(x) est vrai ∀𝑥𝑥(𝐻𝐻(𝑥𝑥) ⇒ 𝑀𝑀(𝑥𝑥)) signifie "Pour tout x, si x est un humain, alors x est mortel." Supposons que nous voulons exprimer l'énoncé "Tous les chats sont des animaux". Prédicats : 𝐶𝐶(𝑥𝑥): "x est un chat". 𝐴𝐴(𝑥𝑥): "x est un animal". Pr. Meftah Boudjelal 18 ∀𝑥𝑥 𝐶𝐶(𝑥𝑥) ⇒ 𝐴𝐴(𝑥𝑥) Pour tout x, si x est un chat, alors x est un animal." 6.2.2. Quantificateur existentiel (∃) ∃ : "Il existe" ou "Il y a au moins un". Le quantificateur existentiel est utilisé pour exprimer des énoncés qui s'appliquent à au moins un élément d'un domaine. Exemple ∃𝑥𝑥 (𝑃𝑃𝑃𝑃)) signifie "Il existe un x tel que x est un professeur." Supposons que nous voulons exprimer l'énoncé "Il existe un nombre premier plus grand que 10". Prédicats : 𝑃𝑃(𝑥𝑥): "x est un nombre premier". 𝐺𝐺(𝑥𝑥, 𝑦𝑦): " x est plus grand que y". ∃𝑥𝑥 𝑃𝑃(𝑥𝑥) ⇒ 𝐺𝐺(𝑥𝑥, 10 ) "Il existe un x tel que x est un nombre premier et x est plus grand que 10." 6.2.3. Combinaison des quantificateurs Les quantificateurs peuvent être combinés pour exprimer des énoncés plus complexes. Exemple combinant les quantificateurs Supposons que nous voulons exprimer l'énoncé "Pour chaque humain, il existe un autre humain qui est son ami". Prédicats : 𝐻𝐻(𝑥𝑥): "x est un humain". 𝐴𝐴(𝑥𝑥, 𝑦𝑦): "x est ami avec y". ∀𝑥𝑥 𝐻𝐻(𝑥𝑥) ⇒ ∃𝑦𝑦 (𝐻𝐻(𝑦𝑦) ∧ 𝐴𝐴(𝑥𝑥, 𝑦𝑦)) "Pour tout x, si x est un humain, alors il existe un y tel que y est un humain et x est ami avec y." 6.3. Alphabet et syntaxe Le langage de la logique du premier ordre est constitué des ensembles suivants : 1. un ensemble infini de symboles appelés prédicats 2. un ensemble infini de symboles appelés variables – que l'on note souvent avec une lettre minuscule 3. l'ensemble des symboles logiques et les parenthèse : ¬ ∨ ∧ ⇒ ⟺ ∀ ∃ ( ) Remarque : on utilise des symboles de ponctuations comme « , » et parfois « : » qui ne font pas partie de l'alphabet mais qui servent à la lisibilité. Pr. Meftah Boudjelal 19 Par exemple, on devrait écrire, si on veut être vraiment stricte, P(t1t2t3) au lieu de P(t1, t2, t3) ou encore ou ne devrait pas écrire ∀x,y,z, P(x,y,z) mais plutôt : ∀x∀y∀z P(xyz). On s'autorise malgré tout ce (léger) abus de notation, car cela deviendrait très vite illisible. 7. Introduction aux logiques non classiques Les logiques non classiques sont des systèmes logiques qui s'écartent des principes de la logique classique, telle que la logique propositionnelle et la logique du premier ordre. Ces logiques ont été développées pour répondre à des besoins spécifiques et pour traiter des situations où la logique classique est insuffisante ou inadéquate. Les logiques non classiques offrent des outils puissants pour raisonner sur des situations complexes et non standard. Elles permettent de traiter des concepts tels que la possibilité, la nécessité, le temps, l'incertitude, et les contradictions, qui ne peuvent pas être facilement modélisés par la logique classique. Ces logiques sont utilisées dans de nombreux domaines, notamment en informatique, en intelligence artificielle, en philosophie, et en sciences cognitives, pour résoudre des problèmes spécifiques et pour développer des systèmes de raisonnement avancés. 7.1. Logique intuitionniste - Description : La logique intuitionniste est une forme de logique constructive qui rejette le principe du tiers exclu (une proposition est soit vraie, soit fausse) et la loi de double négation (non(non(P)) implique P). Elle a été développée par L.E.J. Brouwer et Arend Heyting. - Applications : Utilisée en mathématiques constructives et en informatique théorique, notamment pour la vérification de programmes. 7.2. Logique modale - Description : La logique modale étend la logique classique en introduisant des opérateurs modaux tels que "possible" (◊) et "nécessaire" (□). Elle permet de raisonner sur des concepts tels que la possibilité, la nécessité, la croyance, et le temps. - Applications : Utilisée en philosophie, en intelligence artificielle, et en informatique pour modéliser des systèmes de croyance, des systèmes de connaissance, et des systèmes temporels. 7.3. Logique temporelle - Description : La logique temporelle est une extension de la logique modale qui introduit des opérateurs pour raisonner sur le temps. Elle permet de formuler des énoncés sur le passé, le présent, et le futur. Pr. Meftah Boudjelal 20  - Applications : Utilisée en informatique pour la vérification de systèmes réactifs, en intelligence artificielle pour la planification, et en linguistique pour l'analyse des temps verbaux. 7.4. Logique floue - Description : La logique floue est une forme de logique qui permet de raisonner sur des énoncés vagues ou imprécis. Elle utilise des valeurs de vérité continues (entre 0 et 1) plutôt que des valeurs de vérité binaires (vrai ou faux). - Applications : Utilisée en intelligence artificielle pour les systèmes de contrôle, en traitement d'images, et en reconnaissance de formes. 7.5. Logique paraconsistante - Description : La logique paraconsistante est une forme de logique qui permet de raisonner en présence de contradictions. Elle rejette la loi de non-contradiction (une proposition ne peut pas être à la fois vraie et fausse). - Applications : Utilisée en intelligence artificielle pour la gestion des bases de données inconsistantes, en philosophie pour l'analyse des paradoxes, et en sciences cognitives pour modéliser le raisonnement humain. 7.6. Logique quantique - Description : La logique quantique est une forme de logique qui s'applique aux systèmes quantiques, tels que ceux décrits par la mécanique quantique. Elle rejette certains principes de la logique classique, tels que la distributivité des opérateurs logiques. - Applications : Utilisée en physique quantique pour modéliser les phénomènes quantiques, en informatique quantique pour la conception d'algorithmes quantiques. 7.7. Logique épistémique - Description : La logique épistémique est une forme de logique modale qui s'intéresse à la connaissance et à la croyance. Elle introduit des opérateurs pour exprimer des énoncés tels que "x sait que P" ou "x croit que P". - Applications : Utilisée en intelligence artificielle pour la modélisation des systèmes de croyance, en philosophie pour l'analyse de la connaissance, et en informatique pour la vérification de protocoles de communication. Pr. Meftah Boudjelal 21