Programmation logique et fonctionnelle – partie C

Par O. Bailleux, Maître de conférences HDR à l'université de Bourgogne.

La logique propositionnelle

Les activités #.dec (dec pour Découverte) consistent à étudier des présentations explicatives et à traiter tous les exercices de découverte proposés. Si vous ne répondez pas correctement à un exercice de découverte, revenez en arrière pour relire les explications et identifier la cause de votre erreur.

Les activités #.ent (ent pour Entrainement) consistent à traiter des exercices d’entraînement. Vous devez d’abord tenter de traiter ces exercices sans dévoiler d’indice ni regarder la solution. Vous pouvez remonter dans le document pour relire certaines explications ou consulter les solutions des exercices de découverte ou d’entraînement précédemment traités.

Activité de découverte C.dec

Introduction

La logique a pour rôle premier de donner un fondement mathématique aux notions d’énoncés, de raisonnement, de déduction et de preuve.

La logique proportionnelle, que nous abordons dans cette première partie, s’intéresse aux énoncés dont les variables peuvent prendre deux valeurs possibles, vrai ou faux, ne sont pas quantifiées (les formules n’ont pas de quantificateurs tels que $\forall$ et $\exists$), et sont construites à l’aide de connecteurs logiques (et, ou, non etc.).

Il s’agit donc de formules très simples, ayant une puissance d’expression limitée, mais qui permettent déjà de modéliser des problèmes posés dans de nombreux domaines comme par exemple la vérification de circuits électroniques, la conception d’emplois du temps, l’ordonnancement de tâches, l’allocation de ressources, ou encore la gestions de dépendances dans des configurations logicielles.

C.dec1 : Les formules

Les formules de la logique propositionnelle sont constituées des symboles suivants :

  • Les constantes $\top$, appelée symbole vrai et $\bot$, appelé symbole faux.
  • Les variables, que nous représenterons par des lettres minuscules ou des mots, éventuellement avec des indices, comme par exemple $a, b, x_1, x_2$.
  • Les connecteurs $\neg, \vee, \wedge, \to, \leftrightarrow$, appelés respectivement connecteur non, ou, et, implique et équivalent.
  • Les parenthèses $($ et $)$.

On appelle formule complètement parenthésées toute expression pouvant être construite par induction avec les règles suivantes :

  • $\top$et $\bot$ sont des formules.
  • Toute variable est une formule.
  • Si $\Sigma$ est une formule, alors $\neg \Sigma$ est une formule.
  • Si $\Sigma$ et $\Omega$ sont des formules, alors $(\Sigma \vee \Omega)$, $(\Sigma \wedge \Omega)$, $(\Sigma \to \Omega)$ et $(\Sigma \leftrightarrow \Omega)$ sont des formules.

Par exemple, $((\neg(a \vee \neg b) \to b)$ $\wedge$ $(\neg a \vee c))$ est une formule complètement parenthésée.

L’intérêt des formules complètement parenthésées est qu’elles se décomposent d’une manière unique en un arbre syntaxique qui permet d’identifier sans ambiguité chacune des deux sous-formules reliées par chaque connecteur $\neg, \vee, \wedge, \to, \leftrightarrow$ .

plfc1

L’inconvénient est qu’elle contiennent plein de parenthèses qui peuvent nuire à la lisibilité. Les parenthèses les plus extérieures à une formule peuvent êtres supprimées d’emblée. On peut supprimer certaines autres parenthèses en adoptant des conventions syntaxiques d’associativité et de priorité des opérateurs.

L’ordre de priorité des opérateurs est le suivant : $\neg, \wedge, \vee, \to, \leftrightarrow$.

Donc par exemple la formule $b \vee (\neg a \wedge c)$ pourrait aussi s’écrire $b \vee \neg a \wedge c$ en vertu de la priorité de $\wedge$ sur $\vee$, mais on peut laisser certaines parenthèses facultatives pour faciliter la compréhention de la structure de la formule.

Les connecteurs $\vee$ et $\wedge$ sont associatifs à gauche (comme les opérateurs arithmétiques que nous utilisaons dans la vique quotidienne), donc par exemple $a \wedge (\neg b \to a)$ $\wedge$ $\neg c$ $\wedge$ $(a \vee \neg c)$ est équivalent à $((a \wedge (\neg b \to a)) \wedge \neg c)$ $\wedge$ $ (a \vee \neg c)$ tout en étant bien plus lisible.

L’associativité syntaxique des connecteurs $\to$ et $\leftrightarrow$ n’est pas totalement consensuelle dans la littérature. L’associativité à droite est la plus fréquemment rencontrée, mais il et plus sûr de lever toute ambigüité avec des parenthèses dans le cas où plus de deux sous-formules sont successivement reliées par ces opérateurs, comme par exemple dans la formule $a \to (b \to c)$ qui pourrait s’écrire $a \to b \to c$ en vertu de l’associativité à droite du connecteur $\to$, mais avec le risque de se fourvoyer par la suite.

Exercice de découverte C.dec.x1

Mettez toutes les parenthèses dans la formule suivante pour qu’elle soit complètement parenthésée.

$a \vee b \wedge \neg c \vee d$ $\to$ $a \vee b \wedge c$

"Indice"

On commence par parenthéser ce qui est relié par le connecteur le plus prioritaire, c’est à dire $\wedge$.

$a \vee (b \wedge \neg c) \vee d$ $\to$ $a \vee (b \wedge c)$

"Réponse"

On continue avec le $\vee$ en prenant en compte l’associativité à gauche.

$((a \vee (b \wedge \neg c)) \vee d)$ $\to$ $(a \vee (b \wedge c))$

C.dec2 : Notion d’interprétation

Une formule, telle que décrite dans la section précédente, est un objet mathématique purement syntaxique.

Pour modéliser un raisonnement permettant de démontrer qu’une formule est une conséquence logique d’une autre, il faut donner un sens à la notion de valeur de vérité d’une formule et à la notion de conséquence logique. Pour ce faire, il faut introduire deux notions : la valuation et l’interprétation.

Une valuation d’un ensemble $V$ de variables propositionnelle est une fonction de $V$ dans ${0,1}$. Les deux éléments de cet ensemble sont appelés valeurs de vérité. On peut aussi les noter FAUX et VRAI. Les deux notations pourront être utilisées dans la suite de ce document.

Par exemple, on note ${(a,0), (b,1), (c,0)}$ la valuation de l’ensemble de variables ${a, b, c}$ qui attribue la valeur FAUX à $a$, la valeur VRAI à $b$ et la valeur FAUX à $c$.

L’interprétation standard de la logique propositionnelle est une fonction $\text{Val}$ qui à tout couple $(\Sigma,A)$, où $\Sigma$ est une formule et $A$ une valuation des variables de $\Sigma$, associe une valeur de vérité. Il existe d’autres interprétations, telle que l’interprétation intuitioniste, qui sortent du cadre de ce cours. Nous utiliserons donc toujours le mot interprétation dans le sens d’interprétation standard.

L’interprétation d’une formule repose sur le sens donné aux connecteurs $\neg$, $\wedge$, $\vee$, $\to$ et $\leftrightarrow$ par des fonctions pouvant être représentées sous la forme de tables de vérité.

Commençons par le connecteur $\neg$. La sémantique de ce connecteur est définie par la négation Booléenne, c’est à dire la fonction de ${0,1}$ dans ${0,1}$ qui à $0$ associe $1$ et à $1$ associe 0. On notera $\underline{\neg} 0 = 1$ et $\underline{\neg} 1 = 0$.

Voici les tables de vérité définissant les fonctions $\underline{\wedge}$, $\underline{\vee}$, $\underline{\to}$ et $\underline{\leftrightarrow}$ qui donnent un sens aux connecteurs logiques. Les symboles représentant ces fonctions ont été soulignés pour les distinguer des connecteurs correspondants.

$x$ $y$ $ x\underline{\wedge}y$ $ x\underline{\vee}y$ $ x\underline{\to}y$ $ x\underline{\leftrightarrow}y$
0 0 0 0 1 1
0 1 0 1 1 0
1 0 0 1 0 0
1 1 1 1 1 1

En toute rigueur, les variables $x$ et $y$ dans cette table de vérité ne sont pas des variables propositionnelles mais des variables mathématiques pouvant avoir pour valeur 0 ou 1. Les variables propositionnelles sont des objets mathématiques purement syntaxiques.

De même, le symbole $\wedge$ est une brique de construction des formules, alors que $\underline{\wedge}$ désigne la fonction Booléenne qui donne un sens à ce symbole. Ces deux notations désignent des objets mathématiques situés à deux niveaux d’abstraction différents, mais ce n’est pas dramatique si vous avez du mal à les distinguer. Cela ne vous empêchera pas d’atteindre les objectifs pédagogiques de cette partie du cours.

Si vous voulez, par la suite, approfondir votre compréhension de la logique, vous devrez comprendre la distinction entre l’aspect sémantique et l’aspect syntaxique qui est faite ici.

L’interprétation d’un formule pour une valuation $A$ de ses variables est définie de manière inductive par les règles suivantes :

  • L’interprétation d’une variable $v$ est sa valuation : $\text{Val}(v,A) = A(v)$.

  • L’interprétation de $\top$est VRAI et l’interprétation de $\bot$ est FAUX : $\text{Val}(\top,A) = 1$, $\text{Val}(\bot,A) = 0$.

  • L’interprétation d’une formule $\neg \Sigma$ est la négation logique de l’interprétation de $\Sigma$ :

$\text{Val}(\neg \Sigma,A)$ $=$ $\underline{\neg}\text{Val}(\Sigma,A)$

  • L’interprétation d’une formule $(\Sigma_1 \wedge \Sigma_2)$ est définie par :

$\text{Val}(\Sigma_1 \wedge \Sigma_2,A)$ $=$ $\text{Val}(\Sigma_1,A) \underline\wedge \text{Val}(\Sigma_2,A)$

  • L’interprétation d’une formule $(\Sigma_1 \vee \Sigma_2)$ est définie par :

$\text{Val}(\Sigma_1 \vee \Sigma_2,A)$ $=$ $\text{Val}(\Sigma_1,A) \underline\vee \text{Val}(\Sigma_2,A)$

  • L’interprétation d’une formule $(\Sigma_1 \to \Sigma_2)$ est définie par :

$\text{Val}(\Sigma_1 \to \Sigma_2,A)$ $=$ $\text{Val}(\Sigma_1,A) \underline\to \text{Val}(\Sigma_2,A)$

  • L’interprétation d’une formule $(\Sigma_1 \leftrightarrow \Sigma_2)$ est définie par :

$\text{Val}(\Sigma_1 \leftrightarrow \Sigma_2,A)$ $=$ $\text{Val}(\Sigma_1,A) \underline\leftrightarrow \text{Val}(\Sigma_2,A)$

De manière moins formelle, on peut dire que la valeur de vérité attribuée à une formule par l’interprétation standard de la logique propositionnelle est obtenue à partir d’une valuation des variables de cette formule en appliquant les tables de vérité des connecteurs logique. Cette formulation est incomplète (que signifie exactement "appliquer une table de vérité" ?) et manque de rigueur, mais tout le monde comprend le principe après avoir traité quelques exemples.

Voici un exemple. Soit la formule $\Sigma=(a \to b) \vee \neg a$ et la valuation $A = {(a,1),(b,0)}$. Quelle est l’interprétation de $\Sigma$ pour la valuation $A$ ?

La table de vérité du connecteur $\to$ nous indique que $(a\to b)$ s’interprète à 0. Formellement, $\text{Val}(a \to b,I) = 1 \underline\to 0 = 0$.

La table de vérité du connecteur $\neg$ nous indique que $\neg a$ s’interprète à $0$.

La table de vérité du connecteur $\vee$ nous indique que $\Sigma$ s’interprète à $0$.

$\Sigma=\underbrace{ \underset{0}{(a \to b) } \vee \underset{0}{\neg a}} _0$

On a donc $\text{Val}(\Sigma,A) = 0$.

Exercice de découverte C.dec.x2

Soit la formule $\Sigma=(a \to b) \to a$. Donnez les interprétations de $\Sigma$ pour chacune des valuations suivantes :

  1. $A_1 = {(a,1),(b,0)}$
  2. $A_2 = {(a,0),(b,1)}$
"Réponse1"

$\underbrace{\underbrace{(\underset{1}{a} \to \underset{0}{b})} _0 \to \underset{1}{a}} _1$

Formellement, $\text{Val}(\Sigma,A_1) = 1$

"Réponse2"

$\underbrace{\underbrace{(\underset{0}{a} \to \underset{1}{b})} \to \underset{0}{a}} _0$

Formellement, $\text{Val}(\Sigma,A_2) = 0$

C.dec3 : Validité et cohérence

Une formule propositionnelle $\Sigma$ est dite valide si et seulement si elle s’interprète toujours à VRAI quelle que soit la valuation de ses variables. On dit aussi que $\Sigma$ est une tautologie.

Une formule propositionnelle $\Sigma$ est dite cohérente si et seulement s’il existe au moins une valuation de ses variables pour laquelle $\Sigma$ s’interprète à VRAI. On dit aussi que $\Sigma$ est satisfaisable, ou encore satisfiable (mais c’est un anglicisme).

Une formule qui n’est pas cohérente est dite incohérente.

On peut donc classer les formules propositionnelles dans trois catégories :

  • Les formules valides, qui sont "toujours vraies" (dans le sens où elle s’interprètent à VRAI pour toutes les valuations possibles de leurs variables.)
  • Les formules incohérentes, qui sont "toujours fausses".
  • Les formules cohérentes mais pas valides, qui sont "parfois vraies et parfois fausses" (selon la valuation de leurs variables).
Exercice de découverte C.dec.x3

La formule $a \to a$ est-elle une tautologie, est elle cohérente sans être valide, ou est-elle incohérente ?

"Réponse"

D’après la table de vérité du connecteur $\to$, c’est une tautologie.

Exercice de découverte C.dec.x4

La formule $a \to \neg a$ est-elle une tautologie, est elle cohérente sans être valide, ou est-elle incohérente ?

"Réponse"

Elle est cohérente mais pas valide. D’après la table de vérité du connecteur $\to$, ,si $a$ vaut 0 alors $(a \to \neg a)$ s’interprète à 1, mais si $a$ vaut 1 $(a \to \neg a)$ s’interprète à 0.

Exercice de découverte C.dec.x5

La formule $a \wedge \neg a$ est-elle une tautologie, est elle cohérente sans être valide, ou est-elle incohérente ?

"Réponse"

C’est une formule incohérente.

Exercice de découverte C.dec.x6

La formule $(a \wedge b) \vee (\neg a \wedge b)$ est-elle une tautologie, est elle cohérente sans être valide, ou est-elle incohérente ?

"Réponse"

On peut reprendre dans une table de vérité les interprétations des différentes sous-formules pour faciliter le calcul des valeurs de vérité de la formule complète.

$a$ $b$ $a \wedge b$ $\neg a \wedge b$ $(a \wedge b) \vee (\neg a \wedge b)$
0 0 0 0 0
0 1 0 1 1
1 0 0 0 0
1 1 1 0 1

On voit que la formule s’interprète à VRAI pour certaines valuations des variables et à FAUX pour d’autres. C’est donc une formule cohérente, mais pas une tautologie.


Une valuation $A$ pour laquelle une formule $\Sigma$ s’interprète à VRAI est appelée un modèle de $\Sigma$. On dit aussi que $A$ satisfait $\Sigma$. Une valuation $A$ pour laquelle une formule $\Sigma$ s’interprète à FAUX est appelée un contre-modèle de $\Sigma$. On dit aussi que $A$ falsifie $\Sigma$.

Une formule valide, ou tautologie, est donc une formule n’ayant aucun contre-modèle. Une formule incohérente est une formule n’ayant aucun modèle.

Exercice de découverte C.dec.x7

Donnez les modèles de la formule $\neg a \to \neg b$.

"Réponse"

La formule a trois modèles :

  • ${(a,0),(b,0)}$
  • ${(a,1),(b,0)}$
  • ${(a,1),(b,1)}$

C.dec4 : Conséquence logique et équivalence logique

Définition : On dit qu’une formule $\Omega$ est une conséquence logique d’une formule $\Sigma$ si et seulement si tout modèle de $\Sigma$ est un modèle de $\Omega$. On note :

$\Sigma \models \Omega$

plfc2

Attention : le symbole $\models$ n’est pas un connecteur logique. Si $\Sigma$ et $\Omega$ sont des formules propositionnelles, l’expression $\Sigma \models \Omega$ n’est pas une formule propositionnelle, mais une notation mathématique qui exprime une propriété reliant deux formules propositionnelles.

Encore une fois, la nuance tient au fait que les formules sont des objets mathématiques purement syntaxiques, alors que le symbole $\models$ représente une propriété sémantique en rapport avec les interprétations des formules.

Il y a toutefois une propriété qui établit un lien entre le symbole sémantique $\models$ et le connecteur $\to$.

Propriété : Pour toutes formules propositionnelles $\Sigma$ et $\Omega$, $\Sigma \models \Omega$ si et seulement si la formule $\Sigma \to \Omega$ est une tautologie.

Exemple : $a \vee b$ est une conséquence logique de $a \wedge b$, autrement dit, $a \wedge b \models a \vee b$. En effet, toute valuation de $a$ et $b$ qui satisfait $a \wedge b$ (il y en a une seule), satisfait aussi $a \vee b$. De fait, la formule $(a \wedge b)\to(a \vee b)$ est une tautologie.

Exercice de découverte C.dec.x8

L’affirmation $a \to b \models a \vee b$ est elle correcte ?

"Réponse"

On peut répondre à cette question en comparant les tables de vérités des deux formules.

$a$ $b$ $a \to b$ $ a \vee b $
0 0 1 0
0 1 1 1
1 0 0 1
1 1 1 1

La réponse à la question posée est non : $a \vee b$ n’est pas une conséquence logique de $a \to b$ car la valuation représentée par la première ligne de la table de vérité, ${(a,0), (b,0)}$, est un modèle de $a \to b$ mais pas de $a \vee b$.


Définition : On dit que deux formules $\Sigma$ et $\Omega$ sont logiquement équivalentes si et seulement si elles ont les mêmes modèles. On note :

$\Sigma \equiv \Omega$

Propriété : Pour toutes formules propositionnelles $\Sigma$ et $\Omega$, $\Sigma \equiv \Omega$ si et seulement si $\Sigma \models \Omega$ et $\Omega \models \Sigma$.

Propriété : Pour toutes formules propositionnelles $\Sigma$ et $\Omega$, $\Sigma \equiv \Omega$ si et seulement si la formule $\Sigma \leftrightarrow \Omega$ est une tautologie.

Exercice de découverte C.dec.x9

L’affirmation $a \to b$ $\equiv$ $\neg b \to \neg a$ est elle correcte ?

"Réponse"

Avec seulement deux variables, le moyen le plus simple de vérifier si les deux formules sont équivalentes est de comparer leurs tables de vérité.

$a$ $b$ $a \to b$ $ \neg b \to \neg a $
0 0 1 1
0 1 1 1
1 0 0 0
1 1 1 1

Toutes les lignes des 2 tables de vérité sont identiques, donc les deux formules sont logiquement équivalentes.

Certaines propriétés permettent de simplifier des formules contenant des constantes $\top$ et/ou $\bot$ en les remplaçant par des formules équivalentes. Ces propriétés découlent directement des tables de vérité des connecteurs logiques.

  1. $\neg \top \equiv \bot$
  2. $\neg \bot \equiv \top$
  3. $\top \wedge \Sigma \equiv \Sigma \wedge \top \equiv \Sigma$
  4. $\bot \wedge \Sigma \equiv \Sigma \wedge \bot \equiv \bot$
  5. $\top \vee \Sigma \equiv \Sigma \vee \top \equiv \top$
  6. $\bot \vee \Sigma \equiv \Sigma \vee \bot \equiv \Sigma$
  7. $\top \to \Sigma \equiv \Sigma$
  8. $\bot \to \Sigma \equiv \top$
  9. $\Sigma \to \top \equiv \Sigma$
  10. $\Sigma \to \bot \equiv \neg \Sigma $
  11. $\top \leftrightarrow \Sigma \equiv \Sigma \leftrightarrow \top \equiv \Sigma$
  12. $\bot \leftrightarrow \Sigma \equiv \Sigma \leftrightarrow \bot \equiv \neg \Sigma$

C.dec5 : Raisonnement par séparation

Déterminer si une formule est une conséquence logique d’une autre permet d’utiliser la logique propositionnelle pour modéliser un raisonnement. Mais la méthode de comparaison des tables de vérité devient fastidieuse au delà de trois variables, inapplicable "à la main" au de 6 ou 7 variables (pour 7 variables, les tables comportent 128 lignes), et inapplicable avec un ordinateur au delà de quelques dizaines de variables.

On peut parfois aller un peu plus vite en choisissant une variable et en raisonnant séparément sur les interprétations de la formule pour les valuations où cette variable a la valeur 0 et celles où elle a la valeur 1. Dans el premier cas, cela revient à remplacer la variable de séparation par $\bot$ et dans le deuxième cas à la remplacer par $\top$. On peut ensuite appliquer les règles de simplification vues dans la section précédente.

Prenons pour exemple la formule suivante :

$\Sigma = ((a \to b)\wedge(a \to c))$ $\to$ $((\neg a \vee b \vee \neg c) \wedge (\neg a \vee \neg b \vee c))$

Il nous faut choisir une variable de séparation, par exemple la variable $a$. On distingue alors deux cas.

Cas 1 : La variable $a$ est assignée à 0. On s’intéresse uniquement aux valuations qui assignent 0 à $a$. Les valeurs de vérité de la formule $\Sigma$ pour ces valuations sont celles de la formule $\Sigma\vert_{a=\bot}$, c’est à dire la formule dans laquelle on remplace toutes les occurrences de $a$ par la constante propositionnelle $\bot$, qui s’interprète à 0.

$\Sigma\vert_{a=\bot}$ $=$ $((\bot \to b)\wedge(\bot \to c))$ $\to$ $((\top \vee b \vee \neg c) \wedge (\top \vee \neg b \vee c))$

En appliquant les règles de simplification, on obtient :

$\Sigma\vert_{a=\bot}$ $=$ $(\top\wedge \top) \to (\top \wedge \top)$

D’après les tables de vérité des connecteurs $\wedge$ et $\to$, cette formule se simplifie en $\top$ et s’interprète à 1.

Cas 2 : La variable $a$ est assignée à 1. On s’intéresse uniquement aux valuations qui assignent 1 à $a$. Les valeurs de vérité de la formule $\Sigma$ pour ces valuations sont celle de la formule $\Sigma\vert_{a=\top}$, c’est à dire la formule dans laquelle on remplace toutes les occurrences de $a$ par la constante propositionnelle $\top$, qui s’interprète à 1.

$\Sigma\vert_{a=\top}$ $=$ $((\top \to b)\wedge(\top \to c))$ $\to$ $((\bot \vee b \vee \neg c) \wedge (\bot \vee \neg b \vee c))$

La formule se simplifie en :

$\Sigma\vert_{a=\top}$ $=$ $(b \wedge c)$ $\to$ $(( b \vee \neg c) \wedge (\neg b \vee c))$

On peut alors utiliser une nouvelle variable de séparation, par exemple $b$.

Cas 2.1 : $b$ est assignée à 0.

$\Sigma\vert_{a=\top, b=\bot}$ $=$ $(\bot \wedge c)$ $\to$ $(( \bot \vee \neg c) \wedge (\top \vee c))$

$\Sigma\vert_{a=\top, b=\bot}$ $=$ $\bot$ $\to$ $(\neg c \wedge \top) = \top$

Cas 2.2 : $b$ est assignée à 1

$\Sigma\vert_{a=\top, b=\top}$ $=$ $(\top \wedge c)$ $\to$ $(( \top \vee \neg c) \wedge (\bot \vee c))$

$\Sigma\vert_{a=\top, b=\top}$ $=$ $c$ $\to$ $(\top \wedge c) = c \to c = \top$

Pour toutes les valuations possibles des variables, la formule s’interprète à 1. C’est donc un tautologie.

Le raisonnement est résumé par ce schéma :

plfc3

Exercice de découverte C.dec.x10

Utilisez le principe de séparation pour montrer que $\underbrace{(a \wedge b) \to c} _\Sigma$ $;\equiv;$ $\underbrace{a \to (b \to c)} _\Omega$.

"Indice"

On peut raisonner séparément sur les deux formules en utilisant $a$ comme variable de séparation. Les simplifications découlent directement des tables de vérité des connecteurs logiques.

Cas 1 : on remplace $a$ par $\bot$.

$\Sigma\vert_{a=\bot} = \underbrace{(\bot \wedge b)} _{\bot} \to c$

$\Sigma\vert_{a=\bot} = \underbrace{\bot \to c} _{\top}$

$\Sigma\vert_{a=\bot} = \top$

$\Omega\vert_{a=\bot} = \underbrace{\bot \to (b \to c)} _{\top}$

$\Omega\vert_{a=\bot} = \top$.

Donc pour toutes les valuations attribuant 0 à la variable $a$, les deux formules $\Sigma$ et $\Omega$ s’interprètent à VRAI.

Il reste à traiter la cas où $a$ est remplacée par $\top$ pour pouvoir conclure.

"Réponse"

Cas 2 : on remplace $a$ par $\top$.

$\Sigma\vert_{a=\top} = \underset{b}{(\top \wedge b)} \to c$

$\Sigma\vert_{a=\top} = b \to c$

$\Omega\vert_{a=\top} = \underbrace{\top \to (b \to c)}_ {b \to c}$

$\Omega\vert_{a=\top} = b \to c$

Donc pour toutes les valuations attribuant 1 à la variable $a$, les deux formule $\Sigma$ et $\Omega$ s’interprètent comme $b \to c$.

Conclusion : les formules $\Sigma$ et $\Omega$ sont logiquement équivalentes.

C.dec6 : Modélisation

La logique propositionnelle permet de modéliser des problèmes dans lesquels, parmi un nombre fini de scénarios, certains sont autorisés par un énoncé $E$ (exprimé en langage naturel ou en langage mathématique), et certains sont interdits par $E$.

Exemple : Deux bâtiments numérotés $1$ et $2$ doivent être gardés par Anne, Bart et Carl. Chaque personne peut être dans le bâtiment $1$, dans le bâtiment $2$, ou dans aucun des deux. Un scénario représente la situation des trois personnes à un moment donné. Les scénarios autorisés sont ceux dans lesquels il y a au moins une personne dans chaque bâtiment.

On peut modéliser le problème avec 6 variables :

  • $a_1$ et $a_2$ qui sont associées à Anne. Par convention, $a_1 = 1$ signifie qu’Anne est dans le bâtiment 1 et $a_2 = 1$ signifie qu’elle se trouve dans le bâtiment 2. Les deux variable à $0$ indiquent qu’Anne n’est dans aucun bâtiment. Les deux variables à ne peuvent être à $1$ dans les scénarios possibles.
  • $b_1$ et $b_2$ qui sont associées à Bart, avec les mêmes conventions que pour les variables $a_1$ et $a_2$.
  • $c_1$ et $c_2$ qui sont associées à Carl, avec les mêmes conventions que pour les autres variables.

Voici trois exemples de valuations :

  1. $(a_1,1)$, $(a_2,1)$, $(b_1,0)$, $(b_2,1)$, $(c_1,0)$, $(c_2,1)$ représente un scénario impossible dans lequel Anne serait dans les deux bâtiments en même temps.
  2. $(a_1,0)$, $(a_2,0)$, $(b_1,1)$, $(b_2,0)$, $(c_1,0)$, $(c_2,0)$ représente un scénario possible, mais interdit, dans lequel le bâtiment 2 n’est pas surveillé.
  3. $(a_1,0)$, $(a_2,1)$, $(b_1,1)$, $(b_2,0)$, $(c_1,0)$, $(c_2,1)$ représente un scénario autorisé dans lequel Anne et Charlie sont dans le bâtiment 2 et Bart est dans le bâtiment 1.

Le but est de trouver une formule $\Sigma$ qui soit satisfaite par toutes les valuations représentant les scénarios autorisés et falsifiée par toutes les autres valuations.

On peut construire cette formule comme une conjonction de sous-formules vérifiant chacune une partie des propriétés des scénarios autorisés.

  • $\neg (a_1 \wedge a_2)$ vérifie qu’Anne ne peut se trouver en même temps dans les deux bâtiments, c’est à dire que $a_1$ et $a_2$ ne peuvent avoir toutes les deux la valeur $1$. En effet, cette formule est falsifiée si et seulement si les deux variables ont la valeur $1$.
  • $\neg (b_1 \wedge b_2)$ vérifie que Bart ne peut se trouver en même temps dans les deux bâtiments.
  • $\neg (c_1 \wedge c_2)$ vérifie que Charlie ne peut se trouver en même temps dans les deux bâtiments.
  • $a_1 \vee b_1 \vee c_1$ vérifie qu’il y a au moins une personne dans le bâtiment 1.
  • $a_2 \vee b_2 \vee c_2$ vérifie qu’il y a au moins une personne dans le bâtiment 2.

On obtient :

$\Sigma =$ $\neg (a_1 \wedge a_2)$ $\wedge$ $\neg (b_1 \wedge b_2)$ $\wedge$ $\neg (c_1 \wedge c_2)$ $\wedge$ $(a_1 \vee b_1 \vee c_1)$ $\wedge$ $(a_2 \vee b_2 \vee c_2)$

Toute formule logiquement équivalente à celle-ci convient aussi, comme par exemple :

$(\neg a_1 \vee \neg a_2)$ $\wedge$ $(\neg b_1 \vee \neg b_2)$ $\wedge$ $(\neg c_1 \vee \neg c_2)$ $\wedge$ $(a_1 \vee b_1 \vee c_1)$ $\wedge$ $(a_2 \vee b_2 \vee c_2)$

Exercice de découverte C.dec.x11

Vous devez modéliser plusieurs règles applicables à des feux tricolores situés à une carrefour.

plfc4

  1. Une et une seule des ampoules de la rue 1 est allumée (soit la verte, soit la jaune, soit le rouge)
  2. Si le feu de la rue 1 est au vert ou à l’orange, alors celui de la rue 2 est au rouge.

L’état des ampoules des feux du feu de la rue 1 est représenté par les variables $v_1$ pour l’ampoule verte (1 si allumée, 0 sinon), $j_1$ pour l’ampoule jaune, et $r_1$ pour l’ampoule rouge. L’état des ampoules des feux du feu de la rue 2 est représenté par les variables $v_2, j_2, r_2$ avec les mêmes conventions.

"Indice1"

Il existe plusieurs manières de modéliser la première règle. L’une d’elle consiste à partir de sa table de vérité.

$v_1$ $j_1$ $r_1$ Autorisé ?
0 0 0 non
0 0 1 oui
0 1 0 oui
0 1 1 non
1 0 0 oui
1 0 1 non
1 1 0 non
1 1 1 non

Trois valuations correspondent à des scénarios autorisés. On peut construire la formule sous la forme d’une disjonction de trois sous-formules dont chacune est satisfaite uniquement par une des valuations représentant un scénario autorisé.

Par exemple, la sous-formule $\neg v_1 \wedge \neg j_1 \wedge r_1$ s’interprète à 1 si et seulement si les variables $v_1$ et $j_1$ ont la valeur 0 et la variable $r_1$ a la valeur 1.

"Réponse1"

$\Sigma_1$ $=$ $\underbrace{(\neg v_1 \wedge \neg j_1 \wedge r_1)} _{\sigma_1}$ $\vee$ $\underbrace{(\neg v_1 \wedge j_1 \wedge \neg r_1)} _{\sigma_2}$ $\vee$ $\underbrace{(v_1 \wedge \neg j_1 \wedge \neg r_1)} _{\sigma_3}$

La formule $\sigma_1$ est satisfaite par une seule valuation qui correspond au cas où l’ampoule rouge est allumée et les deux autres éteintes. Les formules $\sigma_2$ et $\sigma_3$ sont satisfaites par les valuation correspondant aux deux autres scénarios autorisés. Les modèles de $\Sigma_1$ sont les valuations qui correspondent aux trois scénarios autorisés.

"Indice2"

Pour modéliser la deuxième règle, on pourrait utiliser la même méthode que pour la première. Cette méthode est utilisable lorsque 2, 3, voire 4 variables interviennent dans la formule à modéliser. Mais La manière dont la règle à modéliser est spécifiée permet une approche plus simple et plus rapide. En effet, la formule si … alors peut se modéliser avec une implication.

"Réponse2"

$\Sigma_2 = (v_1 \vee j_1) \to r_2$

Activité d’entraînement C.ent

Cette activité est essentielle. C’est grâce à elle que vous apprendrez vraiment à comprendre et utiliser les notions vues précédemment. Elle se décompose en deux itérations : ent1, ent2. Vous devez réaliser au moins une itération et évaluer votre niveau de réussite.

Si vous avez eu beaucoup de difficulté à traiter les exercices et fait beaucoup d’erreurs, vous devrez traiter à nouveau l’activité de découverte précédente, en laissant passer au moins une nuit, avant de revenir à cette activité d’entraînement en réalisant à nouveau la première l’itération. Vous devez aussi essayer d’identifier les points de blocage et demander à votre enseignant de vous aider à les surmonter.

Si vous avez réussi certains exercices, mais échoué à d’autres, vous devrez d’abord comprendre ce qui vous a conduit à des erreurs et / ou ce qui vous a bloqué. Si vous avez des doutes, des difficultés, essayez de trouver les réponses dans les présentations et explications de l’activité de découverte et demandez toute l’aide nécessaire à votre enseignant. Ensuite, vous devrez réaliser l’itération suivante après au moins une nuit de sommeil et au plus une semaine.

Si vous avez réussi presque tous les exercices et que vos rares erreurs sont dues à l’inattention, vous devriez revenir traiter l’itération suivante après un délai de plusieurs semaines.

Si besoin, après avoir traité la deuxième itération, vous pouvez revenir à la première. Vous pouvez aussi traiter des annales d’évaluations de l’unité d’enseignement.

Itération C.ent1

Exercice d’entrainement C.ent1.1

La formule $a \to ((a \to b) \to (b \to a))$ est elle cohérente ? Est-elle une tautologie ?

"Indice"

La formule comporte seulement deux variables. Dans un tel cas, le moyen le plus simple est de réaliser sa table de vérité.

"Réponse"

$\Sigma = a \to \underbrace{(\underset{\sigma_1}{(a \to b)} \to \underset{\sigma_2}{(b \to a)})}_{\sigma}$

$a$ $b$ $\sigma_1$ $\sigma_2$ $\sigma$ $\Sigma$
0 0 1 1 1 1
0 1 1 0 0 1
1 0 0 1 1 1
1 1 1 1 1 1

On constate que toutes les valuations sont des modèles de $\Sigma$. La formule est donc une tautologie. Elle est donc cohérente.

Exercice d’entrainement C.ent1.2

La formule suivante est elle une tautologie ? Est-elle cohérente ?

$\Sigma$ $=$ $(a \vee \neg b)$ $\wedge$ $(b \vee \neg c)$ $\wedge$ $(c \vee \neg d)$ $\wedge$ $(d \vee \neg e)$ $\wedge$ $(\neg a)$ $\wedge$ $(e)$

"Indice"

Il y a trop de variables pour que la méthode de la table de vérité soit applicable. Il est plus pertinent, dans un tel cas, de raisonner par séparation et déductions.

$\Sigma$ $=$ $\underset{\sigma_1}{(a \vee \neg b)}$ $\wedge$ $\underset{\sigma_2}{(b \vee \neg c)}$ $\wedge$ $\underset{\sigma_3}{(c \vee \neg d)}$ $\wedge$ $\underset{\sigma_4}{(d \vee \neg e)}$ $\wedge$ $\underset{\sigma_5}{(\neg a)}$ $\wedge$ $\underset{\sigma_6}{(e)}$

Pour satisfaire $\Sigma$, il faut satisfaire chacune des sous-formules $\sigma_1$ à $\sigma_6$. Or pour satisfaire $\sigma_5$ il faut assigner la valeur 0 à la variable $a$ et pour satisfaire $\sigma_6$ il faut assigner 1 à la variable $e$. On peut donc déjà affirmer que $\Sigma$ n’est pas une tautologie.

On peut aussi déduire que pour satisfaire $\Sigma$, il faut satisfaire $\Sigma\vert_{a=\bot,e=\top}$. A vous de continuer le raisonnement.

"Réponse"

En remplaçant $a$ par $\bot$ et $e$ par $\bot$, on obtient :

$\Sigma_1$ $=$ $\underset{\sigma_1}{(\bot \vee \neg b)}$ $\wedge$ $\underset{\sigma_2}{(b \vee \neg c)}$ $\wedge$ $\underset{\sigma_3}{(c \vee \neg d)}$ $\wedge$ $\underset{\sigma_4}{(d \vee \bot)}$

Pour satisfaire $\Sigma_1$, il faut assigner $b$ à 0 et $d$ à 1. On peut à nouveau simplifier et ramener le problème à la recherche d’un modèle de la formule :

$\Sigma_2 = \underset{\sigma_2}{(\bot \vee \neg c)} \wedge \underset{\sigma_3}{(c \vee \bot)}$

Or cette formule est incohérente puisqu’elle est falsifiée si on donne à $c$ la valeur 1 et aussi si on lui donne la valeur $0$.

On peut en déduire que la formule initiale $\Sigma$ est incohérente.

Exercice d’entrainement C.ent1.3

Soient les formules suivantes :

  • $\Sigma = (a \wedge \neg b) \vee (\neg a \wedge b)$
  • $\Omega = a \vee b$

Lesquelles de ces trois propositions sont correctes ?

  1. $\Sigma \models \Omega$
  2. $\Omega \models \Sigma$
  3. $\Sigma \equiv \Omega$
"Indice"

La comparaison des tables de vérité des deux formules permet de répondre :

  1. Tout modèle de $\Sigma$ est-il un modèle de $\Omega$ ?
  2. Tout modèle de $\Omega$ est-il un modèle de $\Sigma$ ?
  3. $\Sigma$ et $\Omega$ ont-elles exactement les mêmes modèles ?

"Réponse"

$\Sigma = \underbrace{(a \wedge \neg b)} _{\sigma_1} \vee \underbrace{(\neg a \wedge b)} _{\sigma_2}$

$\Omega = a \vee b$

$a$ $b$ $\Omega$ $\sigma_1$ $\sigma_2$ $\Sigma$
0 0 0 0 0 0
0 1 1 0 1 1
1 0 1 1 0 1
1 1 1 0 0 0

$\Sigma$ et $\Omega$ n’ont pas les mêmes modèles, donc ne sont pas logiquement équivalentes. La proposition 3 est incorrecte. Tous les modèles de $\Sigma$ sont des modèles de $\Omega$, donc $\Sigma \models \Omega$. La proposition 1 est correcte. Un modèle de $\Omega$ ne satisfait pas $\Sigma$, donc la proposition 2 est incorrecte.

Exercice d’entrainement C.ent1.4

Soient les formules suivantes :

  • $\Sigma = (a \vee b) \to c$
  • $\Omega = a \to c$

Lesquelles de ces trois propositions sont correctes ?

  1. $\Sigma \models \Omega$
  2. $\Omega \models \Sigma$
  3. $\Sigma \equiv \Omega$
"Réponse"

Avec trois variables et compte tenu du nombre de propositions à vérifier, la méthode des tables de vérité sera la plus rapide.

$\Sigma = \underset{\sigma}{(a \vee b)} \to c$

$\Omega = a \to c$

$a$ $b$ $c$ $\sigma$ $\Sigma$ $\Omega$
0 0 0 0 1 1
0 0 1 0 1 1
0 1 0 1 0 1
0 1 1 1 1 1
1 0 0 1 0 0
1 0 1 1 1 1
1 1 0 1 0 0
1 1 1 1 1 1

On constate que parmi les trois propositions, la seule correcte est $\Sigma \models \Omega$ (tout modèle de $\Sigma$ est modèle de $\Omega$.

Exercice d’entrainement C.ent1.5

On considère une boule rouge, une bleue, une verte et une urne. Chaque boule peut être soit dans l’urne, soit à l’extérieur. Les situations des boules sont représentées par 3 variables $r, v, b$. Par convention, la variable $r$ a la valeur 1 si la boule rouge est dans l’urne et 0 sinon. Les variables $b$ et $v$ représentent les boules bleue et verte avec la même convention.

Vous devez modéliser chacune des deux propositions suivantes par une formule propositionnelle.

  1. Il y a exactement 2 boules dans l’urne.
  2. Il y a au moins 2 boules dans l’urne.
"Réponse1"

Voici une solution pour la proposition 1.

$(r \wedge v \wedge \neg b)$ $\vee$ $(r \wedge \neg v \wedge b)$ $\vee$ $(\neg r \wedge v \wedge b)$

Il y en a d’autres (toutes logiquement équivalentes). Si vous en avez une, vous pouvez vérifier qu’elle est correcte en comparant sa table de vérité avec celle de la formule ci-dessus. Soyez vigilants car certaines formules peuvent paraître correctes à une personne inexpérimentée alors qu’elles ne le sont pas.

"Réponse2"

Voici une solution pour la proposition 2.

$(r \wedge v) \vee (r \wedge b) \vee ( v \wedge b)$

Pour satisfaire cette formule, il est nécessaire et suffisant qu’au moins une des sous-formules $r \wedge v$, $r \wedge b$ ou $v \wedge b$ soit satisfaite, ce qui suppose qu’au moins deux des variables ait la valeur 1.

Mais des formules syntaxiquement très différentes peuvent être aussi des solutions. Pour vérifier, il faut comparer leurs tables de vérité à celle de la solution proposée.

Exercice d’entrainement C.ent1.6

On considère deux type de pions : les blancs et les noirs, et un damier de 4 cases numérotées comme indiqué sur la figure ci-dessous.

plfc5

On représente les situations (scénarios) du damier avec 8 variables propositionnelles : $b_1, b_2, b_3, b_4$ et $n_1, n_2, n_3, n_4$. Par convention, les valeurs des variables ont le sens suivant :

  • $b_i$ vaut 1 si un pion blanc se trouve sur la case $i$ et vaut 0 dans le cas contraire.
  • $n_i$ vaut 1 si un pion noir se trouve sur la case $i$ et vaut 0 dans le cas contraire.

Donnez les formules permettant de modéliser chacune des propositions suivantes :

  1. Une case ne peut contenir à la fois un pion blanc et un pion noir. (Elle peut être vide ou contenir un pion blanc ou un pion noir.)
  2. Il y a exactement un pion noir sur le damier.
  3. Au moins une des deux diagonales est vide (elle ne contient aucun pion).

Conseil : pour chacune des trois formules, commencez par identifier les variables concernées.

"Réponse1"

Modélisation de la proposition 1 :

$\neg (b_1 \wedge n_1)$ $\wedge$ $\neg (b_2 \wedge n_2)$ $\wedge$ $\neg (b_3 \wedge n_3)$ $\wedge$ $\neg (b_4 \wedge n_4) $

ou encore

$(\neg b_1 \vee \neg n_1)$ $\wedge$ $(\neg b_2 \vee \neg n_2)$ $\wedge(\neg b_3 \vee \neg n_3)$ $\wedge$ $(\neg b_4 \vee \neg n_4)$

ou toute formule logiquement équivalente.

Dans les deux solutions données, chaque sous-formule élimine le scénario dans lequel une des cases contient un pion blanc et un pion noir.

"Réponse2"

Modélisation de la proposition 2 :

$(n_1 \wedge \neg n_2 \wedge \neg n_3 \wedge \neg n_4)$ $\vee$ $(\neg n_1 \wedge n_2 \wedge \neg n_3 \wedge \neg n_4)$ $\vee$ $(\neg n_1 \wedge \neg n_2 \wedge n_3 \wedge \neg n_4)$ $\vee$ $(\neg n_1 \wedge \neg n_2 \wedge \neg n_3 \wedge n_4)$

La première sous-formule est satisfaite si la case 1 contient un pion noir et si les autres cases n’en contiennent pas. Les autres sous formules sont satisfaites par les trois autres configurations autorisées pour les pions noirs. Les pions blancs ne sont pas pris en compte ici car ils ne sont pas concerné par la proposition à modéliser.

Autre solution :

$(n_1 \vee n_2 \vee n_3 \vee n_4)$ $\wedge$ $\neg (n_1 \wedge n_2)$ $\wedge$ $\neg (n_1 \wedge n_3)$ $\wedge$ $\neg (n_1 \wedge n_4)$ $\wedge$ $\neg (n_2 \wedge n_3)$ $\wedge$ $\neg (n_2 \wedge n_4)$ $\wedge$ $\neg (n_3 \wedge n_4)$

La première sous-formule impose qu’il y ait au moins un pion noir dans une case. Chacune des autres interdit que deux cases distinctes contiennent un pion noir.

"Réponse3"

Modélisation de la proposition 3 :

$(\neg b_1 \wedge \neg b_4 \wedge \neg n_1 \wedge \neg n_4)$ $\vee$ $(\neg b_2 \wedge \neg b_3 \wedge \neg n_2 \wedge \neg n_3)$

La première sous-formule est satisfaite si et seulement si la diagonale constituées des cases 1 et 4 ne contient aucun pion. La deuxième sous-formule exprime la même chose pour l’autre diagonale.

Itération C.ent2

Exercice d’entrainement C.ent2.1

La formule suivante est elle une tautologie ? Est-elle cohérente ?

$\neg((a \to b) \wedge (b \to c)) \vee (a \to c)$

"Indice"

Avec trois variables, la méthode de la table de vérité est applicable. On pourra faire apparaitre les valeurs de vérité des sous-formules $\sigma_1$, $\sigma_2$, $\sigma_3$, $\sigma$, $\neg \sigma$.

$\Sigma$ $=$ $\neg\underbrace{(\underset{\sigma_1}{(a \to b)} \wedge \underset{\sigma_2}{(b \to c)})} _{\sigma} \vee \underset{\sigma_3}{(a \to c)}$

"Réponse"

$a$ $b$ $c$ $\sigma_1$ $\sigma_2$ $\sigma$ $\neg \sigma$ $\sigma_3$ $\Sigma$
0 0 0 1 1 1 0 1 1
0 0 1 1 1 1 0 1 1
0 1 0 1 0 0 1 1 1
0 1 1 1 1 1 0 1 1
1 0 0 0 1 0 1 0 1
1 0 1 0 1 0 1 1 1
1 1 0 1 0 0 1 0 1
1 1 1 1 1 1 0 1 1

On constate que $\Sigma$ est une tautologie.

Exercice d’entrainement C.ent2.2

Soient les formules suivantes :

  • $\Sigma = (a \wedge b) \to c$
  • $\Omega = a \to c$

Lesquelles de ces trois propositions sont correctes ?

  1. $\Sigma \models \Omega$
  2. $\Omega \models \Sigma$
  3. $\Sigma \equiv \Omega$
"Réponse"

Avec trois variables et compte tenu du nombre de propositions à vérifier, la méthode des tables de vérité sera la plus rapide.

$\Sigma = \underbrace{(a \wedge b)}_{\sigma} \to c$

$\Omega = a \to c$

$a$ $b$ $c$ $\sigma$ $\Sigma$ $\Omega$
0 0 0 0 1 1
0 0 1 0 1 1
0 1 0 0 1 1
0 1 1 0 1 1
1 0 0 0 1 0
1 0 1 0 1 1
1 1 0 1 0 0
1 1 1 1 1 1

On constate que parmi les trois propositions, la seule correcte est $\Omega \models \Sigma$ (tout modèle de $\Omega$ est modèle de $\Sigma$.

Exercice d’entrainement C.ent2.3

On représente un entier $A$ compris entre 0 et 3 par 2 variables propositionnelles $a_1, a_0$. Les valeurs de ces deux variables représentent la valeur de $A$ en base 2.

$A$ $a_1$ $a_0$
0 0 0
1 0 1
2 1 0
3 1 1

On représente un entier $B$ de manière similaire avec deux variables propositionnelles $b_1, b_0$.

Donnez une formule propositionnelle modélisant la propriété $A \neq B$.

"Réponse"

$\underbrace{(a_0 \wedge \neg b_0) \vee (\neg a_0 \wedge b_0)}_ {\sigma_1}$ $\vee$ $\underbrace{(a_1 \wedge \neg b_1) \vee (\neg a_1 \wedge b_1)}_ {\sigma_2}$

La sous-formule $\sigma_1$ est satisfaite si et seulement si $a_0$ a une valeur différente de $b_0$ (l’une a la valeur 0 et l’autre a la valeur 1). La sous-formule $\sigma_2$ est satisfaite si et seulement si $a_1$ a une valeur différente de $b_1$.

Or $A\neq B$ si et seulement si leurs représentations en base 2 diffèrent par la valeur d’au moins un bit, c’est à dire si $\sigma_1$ ou $\sigma_2$ s’interprète à 1.

Exercice d’entrainement C.ent2.4

Soit un mot binaire de 5 bits. Chaque bit est représenté par une variable propositionnelle. Les variables sont nommées $b_0$ (bit le plus à droite) à $b_4$ (le plus à gauche). Donnez une formule aussi courte que possible qui modélise précisément la proposition suivante : « Le mot ne comporte aucune séquence de deux bits à 1 consécutifs. » Par exemple, 01110 ne vérifie pas la propriété car il comporte au moins une séquence de deux bits à 1 situés l’un après l’autre, alors que 01000 satisfait la propriété à modéliser.

"Indice"

On peut construire la formule comme une conjonction de sous-formules.

$\Sigma = \sigma_0 \wedge \cdots \wedge \sigma_3$

Chaque sous-formule $\sigma_i$ concerne les deux bits représentés par les variables $b_i$ et $b_{i+1}$ et interdit que les deux variables aient la valeur 1.

"Réponse"

$\Sigma$ $=$ $\neg (b_0 \wedge b_1)$ $\wedge$ $\neg (b_1 \wedge b_2)$ $\wedge$ $\neg (b_2 \wedge b_3)$ $\wedge$ $\neg (b_3 \wedge b_4)$

Activité C.top

Cette activité propose des exercices de consolidation qui ne doivent être abordés que par les personnes apprenantes maîtrisant bien la partie A et les parties suivantes disponibles.

Par exemple, si les parties actuellement disponibles sont A et B, vous devez d’abord maîtriser la parie B avant de faire cette activité de consolidation de la partie A.

C.top1

Exercice de consolidation C.top1

On appelle littéral une variable propositionnelle ou la négation d’une variables propositionnelle. Par exemple, $a$ et $\neg a$ sont des littéraux. Pour tout littéral $w$, $\neg \neg w$ se simplifie en $w$.

Soit $L_1 = {x_1, \cdots, x_n}$ et $L_2 = {y_1, \cdots, y_k}$ deux ensembles de littéraux respectant les deux propriétés suivantes :

  1. $\forall w \in L_1, \neg w \notin L_2$
  2. $\forall w \in L_2, \neg w \notin L_1$

En d’autres termes, aucun des deux ensembles ne contient la négation d’un littéral appartenant à l’autre ensemble.

Soit $z$ un littéral n’appartenant ni à $L_1$, ni à $L_2$.

Soient :

  • $p = (x_1 \vee \cdots \vee x_n \vee z)$,
  • $q = (y_1 \vee \cdots \vee y_k \vee \neg z)$,
  • $r = (x_1 \vee \cdots \vee x_n \vee y_1 \vee \cdots \vee y_k)$.

Montrez que $p \wedge q \models r$.

Pour bien visualiser la propriété à démontrer, observons un exemple d’application de cette propriété :

$\underbrace{(a \vee b \vee \neg c)} _{p} \wedge \underbrace{(a \vee \neg d \vee c)} _{q}$ $\models$ $\underbrace{(a \vee b \vee \neg d)} _{r}$

La variable $c$, qui apparait sous forme "négative" dans $p$ et "positive" dans $q$ est appelée variable pivot. Il doit y a voir une et une seule variable pivot pour que la propriété soit applicable. La formule $r$ est appelée résolvante de $p$ et $q$.

L’application directe de la propriété à démontrer donne la résolvante $(a \vee b \vee a \vee \neg d)$ qui se simplifie en $(a \vee b \vee \neg d)$.

"Indice"

Pour montrer la conséquence logique, on peut procéder par séparation en utilisant la variable pivot comme variable de séparation. Il faut monter que tout modèle de $p \wedge q$ dans lequel la variable pivot a la valeur 0 est un modèle de $r$ et que tout modèle de $p \wedge q$ dans lequel la variable pivot a la valeur 1 est un modèle de $r$.

"Solution"

On revient au cas général :

Soient :

  • $p = (x_1 \vee \cdots \vee x_n \vee z)$,
  • $q = (y_1 \vee \cdots \vee y_k \vee \neg z)$,
  • $r = (x_1 \vee \cdots \vee x_n \vee y_1 \vee \cdots \vee y_k)$.

On veux monter que $p \wedge q \models r$.

Soit un modèle $M$ de $p \wedge q$ pour lequel le littéral $z$ vaut 0. D’après la table de vérité du connecteur $\wedge$, $M$ satisfait nécessairement $p$, donc il satisfait au moins un des littéraux $x_1, \cdots, x_n$, donc il satisfait $r$.

Soit un modèle $M$ de $p \wedge q$ pour lequel le littéral $z$ vaut 1. D’après la table de vérité du connecteur $\wedge$, $M$ satisfait nécessairement $q$, donc il satisfait au moins un des littéraux $y_1, \cdots, y_k$, donc il satisfait $r$.

Donc tout modèle de $p \wedge q$ est un modèle de $r$.

Exercice de consolidation C.top2

Cet exercice fait suite à l’exercice précédent et utilise la propriété qui y est démontrée. On appelle clause toute disjonction de littéraux $(w_1 \wedge \cdots \wedge w_n)$. La règle de déduction présentée précédemment est appelée Résolution (avec un grand R). Elle s’applique à deux clauses $p$ et $q$, appelées prémisses, répondant aux conditions suivantes :

  • Une unique variable pivot $u$ apparait sous forme positive $u$ dans une des clauses et négative $\neg u$ dans l’autre.
  • Aucune autre variable que $u$ n’apparait sous forme positive dans une des clause et négative dans l’autre.

Elle permet de déduire une clause conséquence logique des deux prémisses, appelée résolvante, dans la quelles on retrouve les littéraux de $p$ et $q$ à l’exception de ceux basés sur la variable pivot.

Par exemple, la résolvante de $(a \vee b \vee c)$ et de $(b \vee \neg c)$ est la clause $(a \vee b)$.

Incidemment, si une variable $v$ apparait sous forme positive et négative dans une même clause, cette clause est une tautologie qui peut être simplifiée en $\top$, puisqu’elle est nécessairement satisfaite quelle que soit la valeur de vérité de $v$. Par exemple, la clause $(a \vee \neg b \vee \neg a)$ est une tautologie.

D’autre part, dans le cas particulier où les deux prémisses contiennent uniquement la variable pivot, la résolvante est la clause vide, qui est équivalente à $\bot$. Par exemple la résolvante de $(a)$ et $(\neg a)$ est $()$, c’est à dire $\bot$.

Le but de l’exercice est de monter que la formule suivante est incohérente en produisant des résolvantes jusqu’à obtenir la clause vide.

$\Sigma$ $=$ $(a \vee b)$ $\wedge$ $(\neg a \vee b)$ $\wedge$ $(a \vee \neg b)$ $\wedge$ $(\neg a \vee \neg b \vee c)$ $\wedge$ $(\neg a \vee \neg b \vee \neg c)$

Chaque résolvante produite étant une conséquence logique de $\Sigma$, elle peut être utilisée ultérieurement comme prémisse pour réaliser de nouvelles déduction.

Pour information : On dit de toute formule constituée d’une conjonction de clauses (des clauses reliées par des connecteurs $\wedge$ ) qu’elle est sous forme CNF.

La règle de Résolution permet de déterminer, en un nombre fini d’étapes, pour toute formule $\Sigma$ sous forme CNF, si $\Sigma$ est incohérente ou cohérente. Si la clause vide est produite, alors $\Sigma$ est incohérente. Si aucune nouvelle résolvante ne peut être produite et que la clause vide n’a pas été produite, alors $\Sigma$ est cohérente.

"Indice"

On peut numéroter les clauses :

$\Sigma$ $=$ $\underset{q_1}{(a \vee b)}$ $\wedge$ $\underset{q_2}{(\neg a \vee b)}$ $\wedge$ $\underset{q_3}{(a \vee \neg b)}$ $\wedge$ $\underset{q_4}{(\neg a \vee \neg b \vee c)}$ $\wedge$ $\underset{q_5}{(\neg a \vee \neg b \vee \neg c)}$

Une première résolvante peut être produite avec les deux première clauses :

$q_1 \wedge q_2 \models \underset{q_7}{(b)}$

À vous de continuer. Le résultat ne dépend pas de l’ordre dans lequel vous faites les déductions.

"Réponse"

$q_7 \wedge q_3 \models \underset{q_8}{(a)}$

$q_8 \wedge q_4 \models \underset{q_9}{(\neg b \vee c)}$

$q_8 \wedge q_5 \models \underset{q_{10}}{(\neg b \vee \neg c)}$

$q_9 \wedge q_{10} \models \underset{q_{11}}{(\neg b)}$

$q_7 \wedge q_{11} \models \bot$