Sémantique logique - IMAGINEimagine.enpc.fr/~marletr/LaBRI/teaching/FormLing/slides/... · Notion...

Cours de formalismes linguistiquesCours de formalismes linguistiquesMaster 1 — 2005-2006Master 1 — 2005-2006

Sémantique logiqueSémantique logique

Renaud Marlet

LaBRI / INRIA

http://www.labri.fr/~marlet/teaching

màj : 07/02/2006

Formaliser le sensFormaliser le sens

Le sens :– concept abstrait– souvent défini en fonction de lui-même– généralement donné en langue naturelle

Parcours sémasiologique de l'interprétant [rappel]– se détacher des signes (de la langue)

Pour manipuler le sens :– besoin de concret

– représentation du sens → objet d'un langage formel

Formalismes sémantiquesFormalismes sémantiques

● Graphes sémantiques– cf. Théorie Sens-Texte [I. Mel'čuk]

● Formules logiques– Exemple

● Tout homme est mortel● Pour tout x, si x est un homme, alors x est mortel● ∀x (homme(x) ⇒ mortel(x))

La logique du sensLa logique du sens

Dans la suite de ce cours :– sémantique donnée par une formule logique

Avantages :– langage formel, syntaxe simple, non ambiguë– relation entre l'interprétation en valeurs de vérité et

une représentation du monde homme(Socrate) est vrai ssi Socrate est un homme

– possibilité de raisonner sur un énoncé Si « ∀x (homme(x) ⇒ mortel(x)) » et « homme(Socrate) »

on peut en déduire « mortel(Socrate) »

Quelques rappels de logiqueQuelques rappels de logique

● valeur booléenne : p ∈ {vrai, faux}● négation : ¬p → non p (ou p est faux)● implication : p ⇒ q → si p, alors q● conjonction : p ∧ q → p et q● disjonction : p ∨ q → p ou q● quantification

– universelle : ∀x P(x) → pour tout x, P(x)

– existentielle : ∃x P(x) → il existe x tel que P(x)

Valeurs (et tables) de véritéValeurs (et tables) de vérité

Définition des opérateurs booléens

p qV V F V V VV F F F F VF V V V F VF F V V F F

¬p p ⇒ q p ∧ q p ∨ q

ExerciceExercice(premier lien avec la langue)(premier lien avec la langue)

Exemple : p = il dort ; q = il dîne ; r(x) = x dort● négation : ¬p = ...?● implication : p ⇒ q = ...?● conjonction : p ∧ q = ...?● disjonction : p ∨ q = ...?● quantification universelle :

∀x r(x) = ...?● quantification existentielle :

∃x r(x) = ...?

ExerciceExercice(premier lien avec la langue)(premier lien avec la langue)

Exemple : p = il dort ; q = il dîne ; r(x) = x dort● négation : ¬p = il ne dort pas● implication : p ⇒ q = s'il dort, alors il dîne● conjonction : p ∧ q = il dort et il dîne● disjonction : p ∨ q = il dort ou il dîne● quantification universelle :

∀x r(x) = pour tout x, x dort (ç.-à-d., tout dort)

● quantification existentielle : ∃x r(x) = il existe un x qui dort (qqchose/qq'un dort)

Signification ordinaire : attention!Signification ordinaire : attention!Énumérez les cas de figureÉnumérez les cas de figure

Exemple : p = il dort ; q = il dîne● implication : p ⇒ q = s'il dort, alors il dîne

– ou bien ...?– ou bien ...?

● disjonction non exclusive : p ∨ q = il dort ou il dîne

– ou bien ...?– ou bien ...?– ou bien ...?

Signification ordinaire : attention!Signification ordinaire : attention!

Exemple : p = il dort ; q = il dîne● implication : p ⇒ q = s'il dort, alors il dîne

– ou bien il dort et il dîne aussi– ou bien il ne dort pas, et on se fiche de savoir s'il dîne

● disjonction inclusive : p ∨ q = il dort ou il dîne

– ou bien il dort et il ne dîne pas– ou bien il dîne et il ne dort pas– ou bien il dort et il dîne

● disjonction exclusive : tu veux du thé ou du café ?

Quelques lois algébriquesQuelques lois algébriques

¬¬p = p [en logique classique]

¬(p ∨ q) = (¬p) ∧ (¬q) [loi de Morgan]

¬(p ∧ q) = (¬p) ∨ (¬q) [loi de Morgan]

p ⇒ q = (¬p) ∨ q [définition]

p ⇒ q = ¬q ⇒ ¬p [contraposée]

p ∨ q = q ∨ p [commutativité]

p ∧ q = q ∧ p [commutativité]

(p ∨ q) ∨ r = p ∨ (q ∨ r) = p ∨ q ∨ r [associativité]

(p ∧ q) ∧ r = p ∧ (q ∧ r) = p ∧ q ∧ r [associativité]

p ∨ (q ∧ r) = (p ∨ q) ∧ (p ∨ r) [distributivité]

p ∧ (q ∨ r) = (p ∧ q) ∨ (p ∧ r) [distributivité]

Exercice : démontrer ces loisExercice : démontrer ces loisComment faire ?Comment faire ?

¬¬p = p [en logique classique]

¬(p ∨ q) = (¬p) ∧ (¬q) [loi de Morgan]

¬(p ∧ q) = (¬p) ∨ (¬q) [loi de Morgan]

p ⇒ q = (¬p) ∨ q [définition]

¬(p ⇒ q) = ¬q ⇒ ¬p [contraposée]

p ∨ q = q ∨ p [commutativité]

p ∧ q = q ∧ p [commutativité]

(p ∨ q) ∨ r = p ∨ (q ∨ r) = p ∨ q ∨ r [associativité]

(p ∧ q) ∧ r = p ∧ (q ∧ r) = p ∧ q ∧ r [associativité]

p ∨ (q ∧ r) = (p ∨ q) ∧ (p ∨ r) [distributivité]

p ∧ (q ∨ r) = (p ∧ q) ∨ (p ∧ r) [distributivité]

Méthode 1 : construction des Méthode 1 : construction des tables de véritétables de vérité

Ex. démontrer : ¬(p ∨ q) = (¬p) ∧ (¬q)

1. Construire les deux expressions logiques à comparer dans une table de vérité

2. Comparer les colonnes correspondantes

p qV V V F F F FV F V F F V FF V V F V F FF F F V V V V

p ∨ q ¬(p ∨ q) ¬p ¬q (¬p) ∧ (¬q)

Méthode 2 : Méthode 2 : raisonnement (calcul) algébrique raisonnement (calcul) algébrique

● Utiliser les définitions et les lois déjà connues pour en démontrer de nouvelles

● Ex. démontrer : p ⇒ q = (¬q) ⇒ (¬p)

(¬q) ⇒ (¬p)

= (¬(¬q)) ∨ (¬p) [définition de ⇒]

= q ∨ (¬p) [double négation]

= (¬p) ∨ q [commutativité de ∨]

= p ⇒ q [définition de ⇒]

ExerciceExercice

Démontrez : (p ∧ q) ⇒ r = p ⇒ (q ⇒ r)

– En construisant une table de vérité– Par calcul/raisonnement algébrique

ExerciceExercice

p q rV V V V V V VV V F V F F FV F V F V V VV F F F V V VF V V F V V VF V F F V F VF F V F V V VF F F F V V V

p ∧ q (p ∧ q) ⇒ r q ⇒ r p ⇒ (q ⇒ r)

ExerciceExercice

(p ∧ q) ⇒ r = (¬(p ∧ q)) ∨ r [définition de ⇒]

= ((¬p) ∨ (¬q)) ∨ r [loi de Morgan]

= (¬p) ∨ ((¬q) ∨ r) [associativité de ∨]

= (¬p) ∨ (q ⇒ r) [définition de ⇒]

= p ⇒ (q ⇒ r) [définition de ⇒]

Choix de la méthodeChoix de la méthode

Quelle est la meilleure méthode ?– tables de vérité– calcul/raisonnement algébrique

Choix de la méthodeChoix de la méthode

Quelle est la meilleure méthode ?– tables de vérité– calcul/raisonnement algébrique

Ça dépend :– beaucoup de calculs → fastidieux, risque d'erreur

– peu de variables

→ tables de vérité OK

– beaucoup de variables

→ calcul algébrique indispensable

Précédence des opérateursPrécédence des opérateursQuestion :Question :

En arithmétique, 2 + 3 × 4 signifie en fait

2 + (3 × 4) ?

(2 + 3) × 4 ?

Pourquoi n'écrit-on pas les parenthèses ?

Précédence des opérateurs (1)Précédence des opérateurs (1)

En arithmétique2 + 3 × 4 signifie 2 + (3 × 4) et non (2 + 3) × 4

De mêmep ∧ q ⇒ r signifie (p ∧ q) ⇒ r et non p ∧ (q ⇒ r)

p ∨ q ⇒ r signifie (p ∨ q) ⇒ r et non p ∨ (q ⇒ r)

p ⇒ q ∧ r signifie p ⇒ (q ∧ r) et non (p ⇒ q) ∧ r

p ⇒ q ∨ r signifie p ⇒ (q ∨ r) et non (p ⇒ q) ∨ r

p ⇒ q ⇒ r signifie p ⇒ (q ⇒ r) et non (p ⇒ q) ⇒ r

¬p ∧ q signifie (¬p) ∧ q et non ¬(p ∧ q)

¬p ∨ q signifie (¬p) ∨ q et non ¬(p ∨ q)

¬p ⇒ q signifie (¬p) ⇒ q et non ¬(p ⇒ q)

Précédence des opérateurs (2)Précédence des opérateurs (2)

p ∧ q ⇒ r signifie (p ∧ q) ⇒ r et non p ∧ (q ⇒ r)

p ∨ q ⇒ r signifie (p ∨ q) ⇒ r et non p ∨ (q ⇒ r)

p ⇒ q ∧ r signifie p ⇒ (q ∧ r) et non (p ⇒ q) ∧ r

p ⇒ q ∨ r signifie p ⇒ (q ∨ r) et non (p ⇒ q) ∨ r

p ⇒ q ⇒ r signifie p ⇒ (q ⇒ r) et non (p ⇒ q) ⇒ r

¬p ∧ q signifie (¬p) ∧ q et non ¬(p ∧ q)

¬p ∨ q signifie (¬p) ∨ q et non ¬(p ∨ q)

¬p ⇒ q signifie (¬p) ⇒ q et non ¬(p ⇒ q)

Pour s'en souvenir : « accrocher » dans l'ordre(1) ¬(2) ∧ et ∨(3) ⇒ (en commençant par la droite)

Exercice :Exercice :Retrouvez les parenthèsesRetrouvez les parenthèses

● ¬ p ∨ q ⇒ r

● ¬ p ⇒ q ∧ r

● p ∨ ¬ q ⇒ r ∧ ¬ t ∧ u

● p ∧ (¬ q ⇒ r) ⇒ ¬ t ⇒ ¬ u ∨ v

Exercice :Exercice :Retrouvez les parenthèsesRetrouvez les parenthèses

● ¬ p ∨ q ⇒ r

((¬p) ∨ q) ⇒ r

● ¬ p ⇒ q ∧ r

(¬p) ⇒ (q ∧ r)

● p ∨ ¬ q ⇒ r ∧ ¬ t ∧ u

(p ∨ (¬q)) ⇒ (r ∧ (¬t) ∧ u)

● p ∧ (¬ q ⇒ r) ⇒ ¬ t ⇒ ¬ u ∨ v

(p ∧ (¬q ⇒ r)) ⇒ ( (¬t) ⇒ ((¬u) ∨ v) )

Précédence des opérateursPrécédence des opérateursAmbiguïtésAmbiguïtés

Où sont les parenthèses ?– p ∨ q ∧ r

– ∀x p ⇒ q

– ∃x p ∧ q

Où sont les parenthèses ?– p ∨ q ∧ r → (p ∨ q) ∧ r ou p ∨ (q ∧ r) ?

– ∀x p ⇒ q → (∀x p) ⇒ q ou ∀x (p ⇒ q) ?

– ∃x p ∧ q → (∃x p) ∧ q ou ∃x (p ∧ q) ?

Où sont les parenthèses ?– p ∨ q ∧ r → (p ∨ q) ∧ r ou p ∨ (q ∧ r) ?

– ∀x p ⇒ q → (∀x p) ⇒ q ou ∀x (p ⇒ q) ?

– ∃x p ∧ q → (∃x p) ∧ q ou ∃x (p ∧ q) ?

C'est ambigu

→ toujours mettre des parenthèses (rien d'implicite)

[On verra plus loin pour les quantificateurs]

Quelques lois algébriques :Quelques lois algébriques :quantificateursquantificateurs

¬ (∀x P(x)) = ∃x ¬P(x) [en logique classique]

¬ (∃x P(x)) = ∀x ¬P(x) [en logique classique]

∀x ∀y P(x,y) = ∀y ∀x P(x,y) [commutativité]

∃x ∃y P(x,y) = ∃y ∃x P(x,y) [commutativité]

∀x ∃y P(x,y) ≠ ∃y ∀x P(x,y) [ ATTENTION ! ]– Exemple : ∀x ∃y x < y ≠ ∃y ∀x x < y

∀x (P(x) ⇒ ∀y Q(x,y)) = ∀x ∀y (P(x) ⇒ Q(x,y)) [et idem pour ∧, ∨]

∀x (P(x) ⇒ ∃y Q(x,y)) = ∀x ∃y (P(x) ⇒ Q(x,y)) [et idem pour ∧, ∨]

∃x (P(x) ⇒ ∀y Q(x,y)) = ∃x ∀y (P(x) ⇒ Q(x,y)) [et idem pour ∧, ∨]

∃x (P(x) ⇒ ∃y Q(x,y)) = ∃x ∃y (P(x) ⇒ Q(x,y)) [et idem pour ∧, ∨]

Notion de proposition (1)Notion de proposition (1)

● Considérez :– J'étais à Paris l'année dernière– L'année dernière j'étais à Paris– L'année dernière, à Paris, j'y étais– C'est à Paris que j'étais l'année dernière– C'est l'année dernière que j'étais à Paris

● En quoi ces phrases diffèrent-elles ?● En quoi ces phrases se ressemblent-elles ?

d'après « Penser la logique » (G. Hottois)

– J'étais à Paris l'année dernière– L'année dernière j'étais à Paris– L'année dernière, à Paris, j'y étais– C'est à Paris que j'étais l'année dernière– C'est l'année dernière que j'étais à Paris

Une même proposition logique, sous diverses formes phrastiques (abstraction de l'intention communicative)

Mais qu'est-ce qu'une proposition exactement ?– Ce n'est pas clair ☹ : le sens ? le fait décrit ? l'idée ?

la pensée ? le contenu objectif d'information ?

Dans ce cours : proposition = phrase à qui l'on peut donner une valeur de vérité (vrai ou faux).– phrase déclarative, descriptive, empirique– qui dit quelque chose au sujet de la réalité– dont l'affirmation est (théoriquement) vérifiable

Ce n'est pas :– une prière, une interrogation, un commandement,

un souhait

ExerciceExerciceQuelles sont les propositions ?Quelles sont les propositions ?

Rappel : proposition = phrase à qui l'on peut donner une valeur de vérité.

(1) Les petits pois sont rouges.

(2) Comme vous avez de grandes dents !

(3) Quelle heure est-il ?

(4) Passe-moi le sel.

(5) Il cria : « rendez-vous, vous êtes cernés »

(6) Il croyait que le père Noël était déjà passé.

(7) Ou bien vous êtes avec nous, ou bien vous êtes contre nous.

ExerciceExerciceQuelles sont les propositions ?Quelles sont les propositions ?

Rappel : proposition = phrase à qui l'on peut donner une valeur de vérité.

(1) Les petits pois sont rouges.

(2) Comme vous avez de grandes dents !

(3) Quelle heure est-il ?

(4) Passe-moi le sel.

(5) Il cria : « rendez-vous, vous êtes cernés »

(6) Il croyait que le père Noël était déjà passé.

(7) Ou bien vous êtes avec nous, ou bien vous êtes contre nous.

Variantes sans incidence logiqueVariantes sans incidence logique

Exemples :– Il y a du soleil mais il fait froid– Bien qu'il y ait du soleil, il fait froid– Il y a du soleil et pourtant il fait froid

Variantes grammaticales, stylistiques, ou psychologiques de la conjonction :– Il y a du soleil et il fait froid

Modélisation :– il_y_a_du_soleil ∧ il_fait_froid

Sens et valeurs de vérité (1)Sens et valeurs de vérité (1)

Considérez les phrases suivantes :– La baleine est un mammifère et Noël est en décembre– 2+2=5 ou Bruxelles est la capitale de la Belgique– Si 2+2=5 alors Paris est la capitale de la Belgique

● Quel est leur sens ?● Quelle est leur valeur logique ?

Sens et valeur de vérité (1)Sens et valeur de vérité (1)

– La baleine est un mammifère et Noël est en décembre– 2+2=5 ou Bruxelles est la capitale de la Belgique– Si 2+2=5 alors Paris est la capitale de la Belgique

Paradoxe (?) :– Sémantiquement absurde, mais valeur de vérité = vrai

☛ Distinguer valeur linguistique et valeur logique

Ces valeurs peuvent toutefois se rejoindre :– S'il y avait en Irak des armes de destruction massive,

alors je suis le pape

Fonction de véritéFonction de vérité

Définition : une proposition complexe est une fonction de vérité ssi sa valeur de vérité dépend des propositions simples qui la composent

Ex. Il fait beau et il fait chaud● p = il fait beau● q = il fait chaud● r = p et q

– r est une fonction de vérité : sa valeur logique dépend de la valeur logique de p et q

– Bernard croit que le tetrapturus est un cétacé

Analyse● q = le tetrapturus est un cétacé● p = Bernard croit que q

– p peut être vrai ou faux, indépendamment de q– Donc p n'est pas une fonction de q, ce n'est pas

une fonction de vérité : sa valeur de vérité ne dépend pas des propositions simples qui la composent

[cf. notion de proposition intentionnelle]

La gauche a perdu les élections parce qu'elle était divisée

Analyse● p = la gauche a perdu les élections● q = la gauche était divisée● r = p parce que q

– Si p est vrai et q vrai, alors r est-il vrai ?

La gauche a perdu les élections parce qu'elle était divisée

Analyse● p = la gauche a perdu les élections● q = la gauche était divisée● r = p parce que q

– Si p est vrai et q vrai, alors r est-il vrai ?– Non, il est possible qu'il n'y ait pas de liaison de cause à

effet entre p et q– « parce que » n'exprime pas un connecteur logique

mais une liaison causale de nature empirique ; ce n'est pas une fonction de vérité

– La gauche était divisée et elle a perdu les élections

Analyse● p = la gauche était divisée● q = la gauche a perdu les élections● r = p et q

– Est-ce que r est une fonction de vérité ?

– La gauche était divisée et elle a perdu les élections

Analyse● p = la gauche était divisée● q = la gauche a perdu les élections● r = p et q

– Est-ce que r est une fonction de vérité ?– Si « et » a un sens causal : non– Si « et » est une simple conjonction : oui

Il y a d'autres facteurs que la valeur de vérité des propositions simples enchâssées. Illustration :– proposition vraie : la pollution est plus grande dans

les villes [→vrai] parce que le trafic est plus intense[→vrai]

– proposition fausse : la couche d'ozone est crevée [→vrai] parce que les satellites tournent autour de la terre [→vrai]

– sujet à controverse : si la gauche n'était pas divisée [conditionnel irréel → toujours faux], elle aurait gagné les élections

À retenir (1)À retenir (1)

● Logique linguistique et mathématique– Termes logiques dans la langue ≠ termes logiques

en mathématique (ex. ou exclusif ou non)● Manipulation d'expressions logiques

– lois– tables de vérité– raisonnement algébrique– précédence et ambiguïté

À retenir (2)À retenir (2)

● Propositions– Tous les énoncés ne sont pas des propositions– Inversement : il existe des variantes grammaticales,

stylistiques, psychologiques (...), sans incidence sur la proposition logique associée

● Distinguer la valeur linguistique (y compris les cas d'absurdité) et la valeur logique

● Fonction de vérité– Tout n'est pas simplement compositionnel

Poussons un peu la formalisationPoussons un peu la formalisation

La logique du premier ordre ...

Sémantique logique - IMAGINEimagine.enpc.fr/~marletr/LaBRI/teaching/FormLing/slides/... · Notion...

Documents

PRESENTATION DU PROJET ET PROPOSITION … · La concertation tout au long du projet ... Tirage du câble sur l’estran depuis ... Une logique complémentaire de viabilité technique

Cours LOGIQUE ET RAISONNEMENTS PROF 1BAC · Prof/ATMANI NAJIB Année Scolaire 2018-2019 Semestre1 2 2-2) L’opérateur logique « ou » La proposition « P ou Q » est vraie si l’une

Proposition de correction Proposition de correction

© Ecole Nationale Supérieure d’Informatique et d’Analyse Des Systèmes Introduction à la Logique (Logique I) 1ère Année Introduction à la Logique (Logique

La proposition principale et la proposition subordonnée ... · La proposition principale et la proposition subordonnée relative Nom : ..... 1) Souliane : - - en bleu la proposition

Analyse des Besoins (Spécifications) - IMAGINEimagine.enpc.fr/~marletr/LaBRI/teaching/GenLog/slides/GenLog... · Génie logiciel – Définition des ... Position dans le cycle de

ANNEXE 3 : GUIDE POUR PREPARER LA PROPOSITION DE …coraf.org/mdtf/wp-content/uploads/2015/09/ISHpropositioncorafpisci... · climat de type guinéen, ... Le cadre logique et les directives

APPRENDRE A APPRENDRE - ac-rouen.frcircsaintvalery.spip.ac-rouen.fr/IMG/pdf/diaporama-theorie-proposition-im.pdfL’intelligence logique-mathématique capacité à raisonner, à compter

logique propositionnelle, 1 1cm Logique séance 2mikael.cozic.free.fr/logique-avancee-1112/logique-avancee-1112-LP1 … · la LP I la logique propositionnelle (LP) traite exclusivement

Génie Logiciel - IMAGINEimagine.enpc.fr/~marletr/LaBRI/teaching/.../GenLogGestionProjet.pdf · Génie logiciel – Gestion de projet © 2005-2007 Renaud Marlet 3 Objectif de ce cours

Logique Intuitionniste - quirin.science · Proposition 1.1 Il existe deux irrationnels aet btels que ab soit rationnel. Démonstration. On part du fait que 2 est rationnel, et que

Cas d'étude : Puissance 4 Définition des besoinsimagine.enpc.fr/~marletr/LaBRI/teaching/GenLog/slides/GenLogP4... · joueur, à tour de rôle, doit insérer un pion dans l'une des

Logique, vocabulaire ensembliste et raisonnementblazere.ece1.free.fr/2017_2018/Cours/Chapitre2.pdf · 2.2. CONNECTEURS LOGIQUES On retiendra que : 1. Pour montrer qu’une proposition

I la logique La Logique des Pr´edicats - Homepage de … · INFO-F-302, Cours d’Informatique Fondamentale Logique pour l’Informatique La Logique des Pr´edicats Introduction

Logique combinatoire - depannezvous.com · appel cette logique la logique combinatoire. {Exemple d’application:Un pont roulant utilise principalement les notions de logique combinatoire

Introduction à la logique : logique propositionnelle

Mathématiques appliquées à l’informatique 3 – Logique ...bliaudet.free.fr/IMG/pdf/Maths-03-Logique.pdf · LOGIQUE DES PREDICATS 43 1 : Logique des prédicat (logique d’ordre

La matrice cadre logique (MCL) et l’approche cadre logique

Logique du premier ordre (Logique de prédicats)

Rudiments de logique propositionnelle3Formelogique,niveaud’analyse 4 ou qui ne comporte pas de négation. Une proposition complexe (ou moléculaire), à l’inverse, est composée