Section 1.4

Satisfiabilité et validité

Dans cette section, nous allons étudier certaines propriétés des propositions. En particulier, nous allons nous intéresser à la notion de satisfiabilité et de validité. Comme nous allons le découvrir, une proposition est dite satisfiable si elle possible de trouver une interprétation qui la rend vraie, alors qu'une proposition est dite valide si elle est tout le temps vraie, peu importe l'interprétation.

Satisfiabilité

Quand une proposition est vraie étant donné une certaine interprétation, on dit que l'interprétation satisfait la proposition. Par exemple, l'interprétation A = 1, B = 1 satisfait la proposition (non A) ou B.

Quand il existe au moins une interprétation qui satisfait une proposition, on dit de la proposition qu'elle est satisfiable.

♣︎ Exemple

La proposition (non A) ou B est satisfiable. En effet, l'interprétation A = 0, B = 1 satisfait la proposition, de même que l'interprétation A = 1, B = 1 ou encore l'interprétation A = 0, B = 0.

Au contraire, la proposition (non A) et A n'est pas satisfiable. En effet, aucune interprétation ne satisfait cette proposition.

! Remarque

Déterminer si une proposition est satisfiable ou non est une tâche qui peut être difficile. Il existe des algorithmes (des méthodes, des procédures) qui permettent de le faire, mais ils sont généralement très coûteux en temps de calcul dès que la proposition devient relativement grande et complexe.

Une loupe.

En pratique, pour déterminer si une proposition est satisfiable ou non, on cherchera à trouver une interprétation qui satisfait la proposition. Pour trouver une telle interprétation, on essaie généralement à tâtons, en testant toutes les interprétations possibles. On essaie ainsi jusqu'à trouver une interprétation qui satisfait la proposition ou jusqu'à ce que toutes les possibilités soient épuisées.

Parfois, en raisonnant un peu, on arrivera à déduire que, si une interprétation existe, alors elle aura une certaines forme. Par exemple, si on considère la proposition A et p, où A est une variable et p est une proposition quelconque, on peut déduire que si une interprétation existe, alors elle doit être de la forme A = 1, .... En effet, aucune interprétation de la forme A = 0, ... ne peut satisfaire la proposition. De telles observations permettent de grandement réduire le nombre d'interprétations à tester.

★ À essayer

Entrez une proposition dans le champ ci-dessous pour déterminer si elle est satisfiable ou non.

Modèle

On appelle un modèle une interprétation qui satisfait une proposition. Par exemple, l'interprétation A = 1, B = 1 est un modèle de la proposition (non A) ou B. En effet, cette interprétation satisfait la proposition ; la valeur de vérité de la proposition est 1 pour cette interprétation.

Tautologie

Quand une proposition est vraie pour toutes les interprétations possibles, on dit que la proposition est une tautologie. Par exemple, la proposition (non A) ou A est une tautologie. En effet, peu importe l'interprétation, la proposition est vraie. On dit aussi que la proposition est valide.

! Remarque

Déterminer si une proposition est une tautologie ou non est une tâche tout aussi difficile que de déterminer si une proposition est satisfiable. En effet, une proposition p est une tautologie si et seulement si sa négation non p n'est pas satisfiable.

★ À essayer

Entrez une proposition dans le champ ci-dessous pour déterminer si elle est valide ou non.

Contradiction

Quand une proposition est fausse pour toutes les interprétations possibles, on dit que la proposition est une contradiction. Par exemple, la proposition (non A) et A est une contradiction. Peu importe l'interprétation que l'on choisit, la proposition est fausse. On dit parfois aussi que la proposition est insatisfiable.

✎ Auto-évaluation

Une proposition valide est vraie. On appelle ce genre de proposition des .

Une proposition insatisfiable est vraie. On appelle ce genre de proposition des .

On dit d'une proposition qu'elle est satisfiable si elle est .

! À maîtriser

Avant de poursuivre, assurez-vous de pouvoir :

  • Définir ce qu'est une proposition satisfiable et en donner des exemples.
  • Définir ce qu'est une tautologie et en donner des exemples.
  • Définir ce qu'est une contradiction et en donner des exemples.
  • Déterminer, dans des cas simples, si une proposition est satisfiable.
  • Déterminer, dans des cas simples, si une proposition est une tautologie.
  • Déterminer, dans des cas simples, si une proposition est une contradiction.