Remerciez-le!

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

Logique propositionnelle 1 Salem BENFERHAT Centre de Recherche en Informatique

Logique propositionnelle 1 Salem BENFERHAT Centre de Recherche en Informatique de Lens (CRIL-CNRS) email : benferhat@cril.fr 1Version pr´ eliminaire du cours. Tout retour sur la forme comme sur le fond est le bienvenu. 1 / 65 La logique propositionnelle 2 / 65 Rappels sur la logique propositionnelle Qu’est ce que la logique propositionnelle • Un langage formel pour exprimer des connaissances 3 / 65 Rappels sur la logique propositionnelle Qu’est ce que la logique propositionnelle • Un langage formel pour exprimer des connaissances • La forme la plus simple des logiques math´ ematiques 3 / 65 Rappels sur la logique propositionnelle Qu’est ce que la logique propositionnelle • Un langage formel pour exprimer des connaissances • La forme la plus simple des logiques math´ ematiques • Un langage symbolique pour d´ ecrire des propositions et de raisonner avec. 3 / 65 Rappels sur la logique propositionnelle Qu’est ce que la logique propositionnelle • Un langage formel pour exprimer des connaissances • La forme la plus simple des logiques math´ ematiques • Un langage symbolique pour d´ ecrire des propositions et de raisonner avec. Qu’est-ce qu’une proposition? Une proposition (ou assertion) est une phrase d´ eclarative qui peut-ˆ etre soit vraie soit fausse (mais pas les deux, enﬁn dans des langages simples de repr´ esentation des connaissances!) 3 / 65 Rappels sur la logique propositionnelle Quelques exemples • RCL est champion de France en 1998 • 7 est un nombre premier 4 / 65 Ingr´ edients d’un langage logique Syntaxe • Vocabulaire : Un ensemble de symboles (dits propositionnels) et de connecteurs • Un langage obtenu ` a partir des r` egles qui combinent ces symboles 5 / 65 Ingr´ edients d’un langage logique Syntaxe • Vocabulaire : Un ensemble de symboles (dits propositionnels) et de connecteurs • Un langage obtenu ` a partir des r` egles qui combinent ces symboles S´ emantique • Sens associ´ e aux symboles et connecteurs • Tables de v´ erit´ e 5 / 65 Ingr´ edients d’un langage logique Syntaxe • Vocabulaire : Un ensemble de symboles (dits propositionnels) et de connecteurs • Un langage obtenu ` a partir des r` egles qui combinent ces symboles S´ emantique • Sens associ´ e aux symboles et connecteurs • Tables de v´ erit´ e Proc´ edure d’inf´ erence • Ce sont des r` egles qui permettent de d´ eriver de nouvelles propositions ` a partir des propositions consid´ er´ ees comme vraies. 5 / 65 Syntaxe de la logique propositionnelle 6 / 65 Les connecteurs logiques N´ egation • Si ”p” d´ esigne une proposition alors on note souvent ”¬ p” comme la n´ egation de ”p” 7 / 65 Les connecteurs logiques N´ egation • Si ”p” d´ esigne une proposition alors on note souvent ”¬ p” comme la n´ egation de ”p” • ”¬ p” signiﬁe : il n’est vraie que ”p” 7 / 65 Les connecteurs logiques N´ egation • Si ”p” d´ esigne une proposition alors on note souvent ”¬ p” comme la n´ egation de ”p” • ”¬ p” signiﬁe : il n’est vraie que ”p” • Il n’est pas vraie que ”8 est un nombre premier” 7 / 65 Les connecteurs logiques Conjonction et Disjonction • Si ”p” et ”q” d´ esignent deux propositions, alors on note souvent ”p ∧q”, pour exprimer le fait que les deux assertions p et q sont toutes les deux sont vraies. 8 / 65 Les connecteurs logiques Conjonction et Disjonction • Si ”p” et ”q” d´ esignent deux propositions, alors on note souvent ”p ∧q”, pour exprimer le fait que les deux assertions p et q sont toutes les deux sont vraies. • Si ”p” et ”q” d´ esignent deux propositions, alors on note souvent ”p ∨q”, pour exprimer le fait que au moins l’une des deux assertions p et q est vraie (elles peuvent ˆ etre vraies toutes les deux). 8 / 65 Les connecteurs logiques Remarques • La n´ egation d’une proposition est une proposition • La conjonction (respectivement la disjonction) de deux propositions est ´ egalement une proposition. 9 / 65 Les connecteurs logiques Implication mat´ erielle • Tr` es importante pour exprimer des informations conditionnelles et contextuelles 10 / 65 Les connecteurs logiques Implication mat´ erielle • Tr` es importante pour exprimer des informations conditionnelles et contextuelles • Si ”p” et ”q” d´ esignent deux propositions, alors on note souvent ”p ⇒q”, pour exprimer le fait que si p est vraie alors q ´ egalement vraie. 10 / 65 Les connecteurs logiques Implication mat´ erielle • Tr` es importante pour exprimer des informations conditionnelles et contextuelles • Si ”p” et ”q” d´ esignent deux propositions, alors on note souvent ”p ⇒q”, pour exprimer le fait que si p est vraie alors q ´ egalement vraie. • Noter que si la proposition ”p” est fausse alors l’implication ”p ⇒q est consid´ er´ ee comme vraie! 10 / 65 Les connecteurs logiques Implication mat´ erielle • Tr` es importante pour exprimer des informations conditionnelles et contextuelles • Si ”p” et ”q” d´ esignent deux propositions, alors on note souvent ”p ⇒q”, pour exprimer le fait que si p est vraie alors q ´ egalement vraie. • Noter que si la proposition ”p” est fausse alors l’implication ”p ⇒q est consid´ er´ ee comme vraie! • L ’implication mat´ erielle ”p ⇒q est logiquement ´ equivalente ` a ¬p ∨q” 10 / 65 Les connecteurs logiques Equivalence logique • Si ”p” et ”q” d´ esignent deux propositions alors on note souvent ”p ⇔q” (not´ e aussi p ≡q), pour exprimer le fait que les deux propositions p et q sont ´ equivalentes. 11 / 65 Les connecteurs logiques Equivalence logique • Si ”p” et ”q” d´ esignent deux propositions alors on note souvent ”p ⇔q” (not´ e aussi p ≡q), pour exprimer le fait que les deux propositions p et q sont ´ equivalentes. • ”p ⇔q” est vue comme une conjonction de ”p ⇒q” et ”q ⇒p” 11 / 65 Un peu de formel : d´ eﬁnition du langage propositionnelle Vocabulaire Le vocabulaire est compos´ e : • D’un ensemble symboles propositionnels V 12 / 65 Un peu de formel : d´ eﬁnition du langage propositionnelle Vocabulaire Le vocabulaire est compos´ e : • D’un ensemble symboles propositionnels V • D’un ensemble de connecteurs logiques : ¬, ∧, ∨, ⇒, ⇔ 12 / 65 Un peu de formel : d´ eﬁnition du langage propositionnelle Vocabulaire Le vocabulaire est compos´ e : • D’un ensemble symboles propositionnels V • D’un ensemble de connecteurs logiques : ¬, ∧, ∨, ⇒, ⇔ • D’un ensemble de s´ eparateurs tr` es utiles pour lever les ambiguit´ es : ”,”, ”)”, ”(”,... 12 / 65 Un peu de formel : d´ eﬁnition du langage propositionnelle Le langage : ensemble de formules propositionnelles L ’ensemble des formules propositionnelles (formules propositionnelles bien form´ ees, propositions) est d´ eﬁni par les r` egles suivantes 1 Si p ∈V alors p est une formule propositionnelle. 13 / 65 Un peu de formel : d´ eﬁnition du langage propositionnelle Le langage : ensemble de formules propositionnelles L ’ensemble des formules propositionnelles (formules propositionnelles bien form´ ees, propositions) est d´ eﬁni par les r` egles suivantes 1 Si p ∈V alors p est une formule propositionnelle. 2 SI p est une formule propositionnelle alors ¬p est une formule propositionnelle. 13 / 65 Un peu de formel : d´ eﬁnition du langage propositionnelle Le langage : ensemble de formules propositionnelles L ’ensemble des formules propositionnelles (formules propositionnelles bien form´ ees, propositions) est d´ eﬁni par les r` egles suivantes 1 Si p ∈V alors p est une formule propositionnelle. 2 SI p est une formule propositionnelle alors ¬p est une formule propositionnelle. 3 SI p et q sont des formules propositionnelles alors p ∧q, p ∨q, p ⇒q, et p ⇔q, sont des formules propositionnelles. 13 / 65 Un peu de formel : d´ eﬁnition du langage propositionnelle Le langage : ensemble de formules propositionnelles L ’ensemble des formules propositionnelles (formules propositionnelles bien form´ ees, propositions) est d´ eﬁni par les r` egles suivantes 1 Si p ∈V alors p est une formule propositionnelle. 2 SI p est une formule propositionnelle alors ¬p est une formule propositionnelle. 3 SI p et q sont des formules propositionnelles alors p ∧q, p ∨q, p ⇒q, et p ⇔q, sont des formules propositionnelles. 4 Les formules propositionnelles sont obtenues uniquement en appliquant les r` egles (1)-(3) un certain nombre de fois. 13 / 65 S´ emantique de la logique propositionnelle 14 / 65 Concept d’interpretations • Rappel : Un symbole propositionnel est soit vrai soit faux (mais pas les deux en mˆ eme temps). 15 / 65 Concept d’interpretations • Rappel : Un symbole propositionnel est soit vrai soit faux (mais pas les deux en mˆ eme temps). • La valeur de v´ erit´ e de chaque symbole propositionnel est CONNUE dans le monde REEL. 15 / 65 Concept d’interpretations • Rappel : Un symbole propositionnel est soit uploads/Philosophie/ logique.pdf