(dernière modification : )

Logique du premier ordre : grammaire, sémantique et validité

La syntaxe

La syntaxe de LPO(M) se compose des symboles suivants :

Il est possible d’écrire de manière syntaxiquement correcte sans les parenthèses (invention des Polonais), mais nous utiliserons toujours les parenthèses.

La grammaire

Une formule bien formée atomique est composée d’un symbole de propriété, un prédicat, suivie d’une variable ou d’un symbole de constante.

Exemples (avec ou sans les parenthèses, c’est équivalent) :

Px, Pa, Qy, Qb, Pb
P(x), P(a), Q(y), P(b)

La grammaire : les formules bien formées

Les règles sont récursives :

  1. Une formule bien formée atomique est une formule bien formée.
  2. Si A et B (non des prédicats, mais des formules) sont des formules bien formées, alors ¬A, (A ∧ B), (A ∨ B), (A ⊃ B), (A ≡ B) sont aussi des formules bien formées.
  3. Si A est une formule bien formée et x est une variable, alors (∀x)A et (∃x)A sont aussi des formules bien formées.
  4. Toute formule bien formée est construite par un nombre fini d’applications des règles de 1 à 3.

Exemples :

Px ∧ Qb

(∀x)Px ⊃ Pb

(∃x)(Px ∨ Qx)

(∃x)(Px ∨ Qx)

(∀x)(Px ⊃ (∃y(Qx ∧ Qy))

(∀x)(∃y)((Px ∧ Py) ⊃ Qx)

La portée d’un quantificateur

La portée d’un quantificateur désigne la partie de la formule qui est capturée par un quantificateur donné.

Exemples :

(∀x)(Px ⊃ Qx)
    ^--------^

(∀x)(Px) ⊃ Qx
^------^

(∀x)(Px ⊃ (∃y)(By ∧ Qx))
           ^-----------^  ∃
^-----------------------^ ∀

Variables liées et variables libres

Une variable est liée si elle est dans la portée d’un quantificateur et qu’elle est alphabétiquement identique à la variable qui suit le quantificateur.

Une variable est libre si elle n’est pas liée.

Exemples :

(∀y)(Px ⊃ Qy)

x : libre
y : lié

(∃x)Qx ∧ (Ay)Py

x : lié
y : lié

(∀x)Qx ∧ (∃x)Px

x : lié
y : lié

(∀x)(∃y)((Px ∨ Qy) ⊃ (∃z) ¬Qz)

x : lié
y : lié
z : lié

Formules bien formées closes

Une formule bien formée est close si toutes ses variables sont liées, c’est-à-dire qu’elle ne contient aucune occurrence d’une variable libre.

Une formule bien formée est ouverte si elle n’est pas close, donc si elle contient au moins une occurrence d’une variable libre.

Exemples :

Les formules suivantes sont closes :

(∀x)Px

x : lié

(∀x)(Px ⊃ Qx)

x : lié

Les formules suivantes sont ouvertes :

(∀x)Px ∧ Qy

y: libre

(∀x)(Px ⊃ Qy)

y : libre

La sémantique de la LPO(M)

En logique propositionnelle LP, la sémantique nous est donnée par les tables de vérité. C’est une logique binaire : c’est vrai ou c’est faux.

Les propositions atomiques sont vraies ou fausses et, ensuite, on détermine la valeur de vérité des propositions complexes à l’aide des tables de vérité.

Pour la LPO(M), nous devons introduire une étape préliminaire.

Avant de pouvoir attribuer une valeur de vérité aux formules, il faut savoir à quoi réfèrent les symboles de constantes et quel est le sens des symboles de propriétés.

Notre sémantique repose sur une certaine représentation du monde.

Ce dernier est composé d’objets dont certains peuvent être nommés directement ou indirectement.

Ces objets ont des propriétés et il existe des relations entre eux (c’est là que réside la richesse).

Une proposition de LPO peut être vraie selon une interprétation donnée et fausse selon une autre interprétation.

Interprétation d’une proposition de LPO

Un domaine d’interprétation :

Tableau de Janeth Fish
The Red Vase and the Yellow Tulips par Janet Fish

Première interprétation :

Deuxième interprétation :

Schéma : ensembles à partir du tableau de Janet Fish

Soit la formule :

(∀x)(Px ⊃ Rx)

Première interprétation : toutes les pommes sont rouges.

Deuxième interprétation : tous les plats sont rouges.

Représentation abstraite d’un domaine d’interprétation

Nous fixons un domaine, qui est simplement un ensemble d’objets.

Une propriété de ces objets est représentée par extension : c’est l’ensemble des objets qui possèdent cette propriété.

Les relations entre les propriétés sont représentées par les relations spatiales entre les ensembles ainsi dénotés.

Exemples :

Tous les H sont des M :

(∀x)(Hx ⊃ Mx)

Schéma : tous les M sont des H

Certains H sont des M :

(∃x)(Hx ∧ Mx)

Schéma : certains H sont des M

Aucun H n’est un M :

¬(∃x)(Hx ∧ Mx)
≡
(∀x)(Hx ⊃ ¬Mx)

Schéma : aucun H n’est un M

La sémantique de la LPO(M)

Notre sémantique doit considérer, en quelque sorte, tous les domaines possibles, tous les objets possibles dans ces domaines, toutes les propriétés possibles de ces objets et toutes les relations possibles de ces objets!

La méthode des arbres et la déduction naturelle apportent quelque chose à cette infinité d’interprétations possibles permise par la sémantique : ce sont des moyens finis qui nous permettent « d’embrasser » cette infinité.

La logique est indépendante de l’existence d’objets spécifiques, de propriétés spécifiques et de relations spécifiques…

Définition

Définition : une interprétation ou un modèle pour la LPO(M) est donnée par :

  1. Un univers de discours ou un domaine D, c’est-à-dire un ensemble non vide d’objets;
  2. Pour chaque symbole de constante, un objet de ce domaine D;
  3. Pour chaque symbole de propriété, un sous-ensemble de D, c’est-à-dire l’ensemble des objets de D qui ont la propriété en question.

La vérité d’une formule de la forme Px

Exemple d’un domaine

Les énoncés suivants sont vrais :

Les énoncés suivants sont faux :

Dans chacun de ces cas, j’assigne un objet à la variable x dans le domaine D.

La valeur de vérité de l’énoncé dépend de cette assignation de valeur à x.

La vérité des formules quantifiées

Exemple d’un domaine, deux sous-ensembles

Quelle est la valeur de vérité des formules suivantes?

Une proposition de la forme (∀x)Ax est vraie dans un domaine D si et seulement si la formule Ax est vraie lorsque la variable x est remplacée par tous les objets du domaine D.

Une proposition de la forme (∃x)Ax est vraie dans un domaine D si et seulement si il existe un objet de D tel que la formule Ax est vraie lorsque la variable est remplacée par cet objet.

Reprenons la proposition :

(∀x)Px ∨ (∃x)¬Px

Cette proposition ne peut pas être fausse!

En effet, soit D un domaine donné (arbitraire). Quelle que soit l’assignation de valeur donnée à x, si ce n’est pas le cas que tous es objets du domaine ont la propriété P, c’est parce qu’il y a un objet a qui n’a pas la propriété P, en d’autres mots, il existe un objet x tel que Px est fausse.

Inversement, s’il n’existe pas un objet x tel que Px est fausse, c’est que tous les objets du domaine D ont la propriété P.

La notion de validité en LPO(M)

Définitions :

  1. Une proposition est logiquement valide (tautologie) si et seulement si elle est vraie pour toute interprétation dans tous les domaines (non vides).
    La seule différence avec la définition d’argument valide, c’est la notion d’interprétation dans les domaines (mais c’est la même définition, formulée en termes de domaines).
  2. Une proposition B est une conséquence logique des propositions A1, …, An, si et seulement si pour tout domaine et toute interprétation pour lesquels A1, …, An sont vraies, alors B l’est également. (C’est la notion formelle de la validité d’argument.)

Notation :

A1, …, An ⊨ B

⊨ est un symbole sémantique (et non pas seulement syntaxique).

Méthode des arbres et la LPO(M)

Nous n’avons pas les tables de vérité, mais nous avons les arbres.

Comment déterminer si une proposition de LPO(M) est logiquement valide?

Comment déterminer si une proposition est une conséquence logique d’un ensemble de prémisses en LPO(M), en d’autres mots si un argument est formellement valide?

Nous pouvons adapter la méthode des arbres à la LPO(M).

La méthode des arbres pour la LPO(M) permet de :

  1. Déterminer si une proposition de LPO(M) est vraie dans une interprétation (ce ne sera pas demandé à l’examen);
  2. Déterminer si une proposions de LPO(M) est logiquement valide (une tautologie);
  3. Déterminer si une proposition donnée est une conséquence logique d’autres propositions, c’est-à-dire si nous avons affaire à un argument formellement valide de LPO(M);
  4. De construire une interprétation qui rend vraies les propositions au sommet d’un arbre.

Les règles pour la logique propositionnelle s’appliquent telles quelles.

Nous avons besoin de quatre nouvelles règles : deux pour le quantificateur universel, son affirmation et sa négation, et deux pour le quantificateur existentiel, son affirmation et sa négation.

Règle du quantificateur universel

Règle du quantificateur universel

Mise en garde

Avant de conclure qu’une branche d’un arbre décrit un modèle, il faut vérifier que les quantificateurs universels ont été instanciés pour tous les termes qui apparaissent sur cette branche.

… d’où le truc mnémotechnique : inscrire l’astérisque (*) à côté d’une formule quantifiée universellement. Cette formule quantifiée est tout le temps active; on peut toujours l’instancier à nouveau.

Exemple 1

Déterminez si la proposition suivante est logiquement valide :

⊨ Pa ⊃ ¬(∀x)¬Px

L’arbre :

Arbre de l’exemple 1

L’arbre est fermé. La proposition est donc logiquement valide.

Négation du quantificateur universel

Règle de la négation du quantificateur universel

Exemple 2 : les mammifères mortels

Soit l’argument suivant :

1. Tous les êtres humains sont des mammifères.  
2. Tous les mammifères sont mortels.  
------
C. Tous les êtres humains sont mortels

Dictionnaire :

Traduction :

1. (∀x)(Hx ⊃ Mx)
2. (∀x)(Mx ⊃ Nx)
------
C. (∀x)(Hx ⊃ Nx)

L’argument est-il valide?

L’arbre :

Arbre exemple 2

Les branches de l’arbre sont toutes fermées. L’argument est donc valide.

Règle du quantificateur existentiel

Règle du quantificateur existentiel

Mise en garde

Avant de conclure qu’une branche d’un arbre décrit un modèle de l’énoncé, il faut s’assurer que tous les quantificateurs existentiels apparaissent sur cette branche ont été instanciés.

Exemple 3

Arbre exemple 3

Le contre-exemple

Contre-exemple du domaine, exemple 3