Logique propositionnelle

Exemple (semaine dernière)

Trouver F qui a cette table de vérité :

Mise sous forme normale

• Faire la table de vérité :
  • chaque modèle donne un terme de la FND
  • chaque contre-modèle donne une clause de la FNC
  • exponentiel dans le meilleur des cas
• Utiliser la distributivité après avoir poussé les négations aux feuilles (grâce à De Morgan)
  • ¬(a∨b) ≡ (¬a∧¬b)
  • ¬(a∧b) ≡ (¬a∨¬b)
  • a ∧ (b∨c) ≡ (a∧b) ∨ (a∧c)
  • a ∨ (b∧c) ≡ (a∨b) ∧ (a∨c)

Exemple

Mettre ¬(a∨b) ∨ ¬(b∨¬d) en CNF.

Forme Normale Conjonctive

⋀_iC_i

• Entrée par défaut des SAT solvers (outils pour résoudre SAT)
• Format simple et “facile” à traiter algorithmiquement (voir séance 3)
• Naturelle : on modélise le monde comme un ensemble de contraintes
  • Clauses : contraintes les plus simples possibles (voir cours CSP/Contraintes pour langage plus riche)
  • Permet quand même de coder (x∧y∧z) ⇒ (x′∨y′∨z′)
  • (colorRed∨colorGreen∨colorBlue) ∧ (isReptile⇒colorGreen) ∧ ...
• Permet de coder des circuits Booléens en général : la transformation de Tseitin

Transformation de Tseitin

(a∧(b∨c)) ⇒ (¬(a⊕b)∧d)

Transformation de Tseitin II

F une formule Booléenne sur les propositions atomiques X.

On construit G sur les variables X ∪ Z telle que :

• Tout modèle ω de F peut être étendu en un unique modèle ω′ de G.
• Tout modèle ω′ de G vérifie ω′ ⊨ F.
• Marche aussi avec les circuits (formules avec partage).

Les modèles de F et de G sont isomorphes.

Qu’est-ce que la modélisation

1. On modélise un problème qu’on a besoin de résoudre avec une formule propositionnelle.
2. On trouve un modèle (ou pas) de notre formule.
3. On extrait de ce modèle une solution à notre problème.

Il y deux portes. Derrière chacune d’elle se trouve soit un tigre soit de l’or. Voulez-vous tenter votre chance et en ouvrir une ?

• Si la porte 1 mène à de l’or, alors son inscription est vraie et sinon, elle est fausse.
• Si la porte 2 mène à un tigre, alors son inscription est vraie et sinon, elle est fausse.

Sur la porte 1, il est écrit : derrière chacune des portes se cache de l’or.

Sur la porte 2, il est écrit : derrière cette porte se trouve de l’or ou derrière l’autre se trouve un tigre.

Schéma général

1. Bien définir les propositions atomiques qu’on va utiliser et leur sémantique.
2. S’assurer qu’une interprétation de ces propositions atomiques est suffisante pour conclure.
3. Écrire une proposition qui modélise le problème c’est-à-dire dont les modèles permettent de résoudre le problème.
4. Trouver un modèle de la proposition.
5. Conclure!

Choix des propositions atomiques

Exemples possible :

• T₁: il y a un tigre derrière la porte 1, T₂: il y a un tigre derrière la porte 2
• O₁: il y a de l’or derrière la porte 1, O₂: il y a de l’or derrière la porte 2
• V₁: l’inscription de la porte 1 est vraie, V₂: l’inscription de la porte 2 est vraie
• W_TF: il y a un tigre derrière la porte 1 et il y a un tigre derrière la porte 2.

Modélisation du problème I

On va utiliser les propositions T₁, T₂, O₁, O₂, V₁, V₂ pour commencer :

• Il y deux portes. Derrière chacune d’elle se trouve soit un tigre soit de l’or.
  • T₁ ⇔ ¬O₁
  • T₂ ⇔ ¬O₂
• Si la porte 1 mène à de l’or, alors son inscription est vraie et sinon, elle est fausse.
  • V₁ ⇔ O₁
• Si la porte 2 mène à un tigre, alors son inscription est vraie et sinon, elle est fausse.
  • V₂ ⇔ T₂
• Sur la porte 1, il est écrit : derrière chacune des portes se cache de l’or.
  • V₁ ⇔ (O₁∧O₂)
• Sur la porte 2, il est écrit : derrière cette porte se trouve de l’or ou derrière l’autre se trouve un tigre.
  • V₂ ⇔ (O₂∨T₁)

Modélisation du problème II

On a donc un problème équivalent à la formule suivante :

(T₁⇔¬O₁) ∧ (T₂⇔¬O₂) ∧ (V₁⇔O₁) ∧ (V₂⇔T₂) ∧ (V₁⇔(O₁∧O₂)) ∧ (V₂⇔(O₂∨T₁))

Modélisation du problème III

On n’a pas vraiment besoin de tant de propositions atomiques vu qu’elles dépendent toutes de T₁, T₂.

• Il y deux portes. Derrière chacune d’elle se trouve soit un tigre soit de l’or.
  • T₁ ∨ ¬T₁, T₂ ∨ ¬T₂, mais ce sont des formules valides, on n’en a pas besoin.
• Si la porte 1 mène à de l’or, alors son inscription est vraie et sinon, elle est fausse.
• Sur la porte 1, il est écrit : derrière chacune des portes se cache de l’or.
  • ¬T₁ ⇔ (¬T₁∧¬T₂)
• Si la porte 2 mène à un tigre, alors son inscription est vraie et sinon, elle est fausse.
• Sur la porte 2, il est écrit : derrière cette porte se trouve de l’or ou derrière l’autre se trouve un tigre.
  • T₂ ⇔ (¬T₂∨T₁)

On a donc une autre modélisation (¬T₁⇔(¬T₁∧¬T₂)) ∧ (T₂⇔(¬T₂∨T₁))

Sudoku

Remplir la grille avec des nombres de 1 à 9 tel que :

Modélisation du Sudoku

Propositions : c_i, j, k = “la case i, j contient la valeur k” pour 0 ≤ i, j ≤ 8 et 1 ≤ k ≤ 9.

• Chaque case contient un nombre de 1 à 9
  • Pour chaque i, j : c_i, j, 1 ∨ … ∨ c_i, j, 9
  • Exactement un nombre ? c_i, j, k ⇒ ¬c_{i, j, ℓ} pour tout k ≠ ℓ
• Une ligne ne peut contenir deux fois le même nombre
  • Pour chaque i, j, k : c_i, j, k ⇒ ⋀_{j′ ≠ j}¬c_{i, j′, k}
• Une colonne ne peut contenir deux fois le même nombre
  • Pour chaque i, j, k : c_i, j, k ⇒ ⋀_{i′ ≠ i}¬c_{i′, j, k}
• Un carré ne peut contenir deux fois le même nombre
  • Carré autour de i, j: K_i, j = {(⌊i/3⌋ + a, ⌊j/3⌋ + b ∣ 0 ≤ a, b ≤ 2} \ {(i,j)}
  • Pour chaque i, j, k : c_i, j, k ⇒ ⋀_{i′, j′ ∈ Ki, j}¬c_{i′, j, k}
• Case préremplies
  • Si la case i, j est déjà rempli avec le nombre k, on ajoute la clause c_i, j, k pour forcer cette valeur à vrai

Exercice Sudoku