Section V — Logique formelle, SAT, CSP et preuves

La formule se décompose en quatre clauses : C1 : p ∨ q C2 : ¬p ∨ r C3 : ¬q ∨ r C4 : ¬r Raisonnement par propagation unitaire : 1. Données : C1 ∧ C2 ∧ C3 ∧ C4 2. C4 est une clause unitaire. Elle impose r = Faux. 3. Substitution de r = Faux dans C2 : (¬p ∨ Faux) ≡ ¬p. Donc p = Faux. 4. Substitution de r = Faux dans C3 : (¬q ∨ Faux) ≡ ¬q. Donc q = Faux. 5. Substitution de p = Faux et q = Faux dans C1 : (Faux ∨ Faux) ≡ Faux. 6. Contradiction : C1 requiert (p ∨ q) = Vrai, mais les contraintes de C2, C3 et C4 imposent simultanément p = Faux et q = Faux, ce qui rend C1 toujours Faux. Aucun assignment de vérité ne satisfait l'ensemble des clauses. Résultat : La formule est insatisfaisable.

Données : la formule p → (q ∧ r) Raisonnement : 1. Suppression de l'implication : on applique l'équivalence A → B ≡ ¬A ∨ B. p → (q ∧ r) ≡ ¬p ∨ (q ∧ r) 2. Application de la distributivité de la disjonction sur la conjonction : A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C). ¬p ∨ (q ∧ r) ≡ (¬p ∨ q) ∧ (¬p ∨ r) 3. Vérification de la structure FNC : une forme normale conjonctive est une conjonction de clauses, chaque clause étant une disjonction de littéraux. Le résultat respecte strictement cette définition. Résultat final : (¬p ∨ q) ∧ (¬p ∨ r) Hypothèses : logique propositionnelle classique bivalente.

La formule est valide. Il n'existe aucun contre-modèle. Voici la preuve de validité. 1. Raisonnement sémantique On suppose l'antécédent ((p → q) ∧ (q → r)) vrai. Alors p → q est vrai et q → r est vrai. On veut montrer que p → r est vrai. Cas 1 : p est faux. Par définition, une implication à antécédent faux est vraie, donc p → r est vrai. Cas 2 : p est vrai. Comme p → q est vrai, on en déduit q vrai. Comme q → r est vrai, on en déduit r vrai. Donc p → r est vrai. Dans tous les cas où l'antécédent est vrai, le conséquent est vrai. Si l'antécédent est faux, l'implication globale est vraie par définition. La formule est donc toujours vraie. 2. Table de vérité exhaustive p | q | r | p→q | q→r | A=(p→q)∧(q→r) | p→r | A→(p→r) F | F | F | V | V | V | V | V F | F | V | V | V | V | V | V F | V | F | V | F | F | V | V F | V | V | V | V | V | V | V V | F | F | F | V | F | F | V V | F | V | F | V | F | V | V V | V | F | V | F | F | F | V V | V | V | V | V | V | V | V Chaque ligne de la colonne finale est vraie. Aucun contre-modèle n'existe. La formule est valide (tautologie).

**Résultat RuleCore : 3 solution(s) exacte(s).** 1. X = 1, Y = 3, Z = 2 2. X = 1, Y = 2, Z = 3 3. X = 2, Y = 1, Z = 3 🔒 Calcul par **LANXAS RuleCore** — moteur de contraintes déterministe (brevet FR2604698) : arc-cohérence AC-3 puis recherche exacte. Résultat reproductible : mêmes contraintes → même résultat.

Dans un CSP binaire, ces trois notions correspondent à des niveaux de filtrage croissants, définis par la portée des contraintes vérifiées et la profondeur du raisonnement activé. **1. Consistance de nœud (Node Consistency)** - Définition : Une variable Xi est node-consistante si chaque valeur de son domaine D(Xi) satisfait toutes les contraintes unaires qui lui sont associées. - Portée : Unaire (1 variable). - Complexité : O(n * d^2) ou O(n * d), où n est le nombre de variables et d la taille maximale du domaine. - Effet : Supprime les valeurs incompatibles avec les contraintes locales à une variable avant tout raisonnement global. **2. Consistance d’arc (Arc Consistency)** - Définition : Un CSP binaire est arc-consistant si, pour toute paire de variables (Xi, Xj) reliée par une contrainte Cij, et pour toute valeur a dans D(Xi), il existe au moins une valeur b dans D(Xj) telle que le couple (a, b) satisfait Cij. La propriété doit être vérifiée dans les deux sens (arc (Xi, Xj) et arc (Xj, Xi)). - Portée : Binaire (2 variables). - Complexité : O(e * d^3) avec l'algorithme AC-3, où e est le nombre de contraintes binaires. - Effet : Élimine les valeurs qui ne peuvent former aucune paire valide avec au moins une variable voisine. **3. Consistance de chemin (Path Consistency)** - Définition : Pour toute paire de variables distinctes (Xi, Xj) et toute valeur a dans D(Xi), b dans D(Xj) satisfaisant Cij, et pour toute autre variable Xk, il existe une valeur c dans D(Xk) telle que (a, c) satisfait Cik et (b, c) satisfait Cjk. - Portée : Ternaire/chemin (3 variables via un chemin de longueur 2). - Complexité : O(n^2 * d^3) avec l'algorithme PC-1. - Effet : Élimine les valeurs qui, bien que compatibles localement avec une voisine, ne peuvent pas être étendues simultanément à deux variables voisines sans créer de conflit à distance. **Différences précises et hiérarchie** | Critère | Consistance de nœud | Consistance d’arc | Consistance de chemin | |---|---|---|---| | Portée des contraintes vérifiées | Unaire (1 variable) | Binaire (2 variables) | Ternaire/chemin (3 variables) | | Profondeur du raisonnement | Locale | Immédiate (voisinage direct) | Étendue (voisinage à distance 2) | | Complexité temporelle | O(n * d^2) | O(e * d^3) | O(n^2 * d^3) | | Puissance de filtrage | Faible | Moyenne | Élevée | | Relation d'implication | Impliquée par arc | Impliquée par chemin | Implicite (aucune) | **Relations logiques et implications** - La consistance de chemin implique la consistance d'arc, qui implique la consistance de nœud. Formellement : Consistance de chemin => Consistance d'arc => Consistance de nœud. - L'inverse est faux : un CSP peut être arc-consistant sans être chemin-consistant, et node-consistant sans être arc-consistant. - La consistance de chemin garantit qu'aucun conflit n'apparaîtra lors de la combinaison de deux contraintes binaires adjacentes, réduisant ainsi le besoin de backtracking lors de la recherche de solution. - La consistance d'arc garantit la compatibilité locale immédiate, mais ne prévient pas les conflits à distance (ex. : Xi et Xj compatibles, Xj et Xk compatibles, mais Xi et Xk incompatibles). - La consistance de nœud ne vérifie que la validité intrinsèque des valeurs et ignore totalement les interactions entre variables. **Impact sur la résolution** - Appliquer la consistance de nœud est un prétraitement trivial. - Appliquer la consistance d'arc (AC-3) est le standard pour réduire le domaine avant la recherche. - Appliquer la consistance de chemin est coûteux mais utile pour les CSP à structure très interconnectée ou lorsque l'arc-consistance ne suffit pas à réduire significativement l'espace de recherche. Elle peut transformer un CSP binaire en un CSP équivalent avec moins de contraintes binaires et un espace de recherche plus petit, au prix d'un temps de calcul initial plus élevé.

Le problème de 2-coloration du graphe cycle impair C5 est insatisfaisable. Raisonnement étape par étape : Soit V = {v1, v2, v3, v4, v5} l'ensemble des sommets et E = {(v1,v2), (v2,v3), (v3,v4), (v4,v5), (v5,v1)} l'ensemble des arêtes. Supposons qu'une coloration valide c : V -> {1, 2} existe. Par définition, toute arête (u, v) dans E doit vérifier c(u) != c(v). En partant de v1, on affecte arbitrairement c(v1) = 1. Propagation le long du cycle : 1. Arête (v1, v2) : c(v2) = 2 2. Arête (v2, v3) : c(v3) = 1 3. Arête (v3, v4) : c(v4) = 2 4. Arête (v4, v5) : c(v5) = 1 5. Arête (v5, v1) : impose c(v5) != c(v1), soit 1 != 1. Contradiction détectée. Aucun affectement de couleurs ne satisfait l'ensemble des contraintes. Le problème est donc insatisfaisable. Certificat minimal d'impossibilité : Le certificat est le cycle impair C5 lui-même, noté (v1, v2, v3, v4, v5, v1). Justification de la minimalité : - Tout cycle impair de longueur 2k+1 force une alternance de couleurs c, non-c, c, ..., c sur ses sommets. La dernière arête relie deux sommets de même couleur, rendant la 2-coloration impossible. - La suppression d'une seule arête du graphe transforme C5 en un chemin de longueur 4, qui est biparti et donc 2-colorable. - Par conséquent, C5 est le sous-graphe connexe de taille minimale dont l'existence prouve l'insatisfaisabilité. Il constitue un certificat vérifiable en temps polynomial : il suffit de constater que la longueur du cycle est 5 (impair) et que toute affectation alternée génère une contradiction sur la dernière arête. Résultats finaux : - Satisfaisabilité : Non - Certificat : Cycle impair (v1, v2, v3, v4, v5, v1) de longueur 5 - Vérification : La parité impaire du cycle garantit que c(v1) = c(v5) après alternance, violant la contrainte de l'arête (v5, v1).

Données : l'ensemble de clauses C = {(a ∨ b), (¬a ∨ b), (a ∨ ¬b), (¬a ∨ ¬b)} sur les variables booléennes a et b. Vérification par table de vérité (code Python et sortie) : ```python import itertools print("a|b|C1|C2|C3|C4|SAT") sat = False for a, b in itertools.product([False, True], repeat=2): c1 = a or b c2 = (not a) or b c3 = a or (not b) c4 = (not a) or (not b) s = c1 and c2 and c3 and c4 if s: sat = True print(f"{a}|{b}|{c1}|{c2}|{c3}|{c4}|{s}") print(f"Satisfiable: {sat}") ``` a|b|C1|C2|C3|C4|SAT False|False|False|True|True|True|False False|True|True|True|False|True|False True|False|True|False|True|True|False True|True|True|True|True|False|False Satisfiable: False Analyse logique étape par étape : - C1 ∧ C4 équivaut à (a ∨ b) ∧ (¬a ∨ ¬b), ce qui impose a ≠ b (les variables doivent avoir des valeurs opposées). - C2 ∧ C3 équivaut à (¬a ∨ b) ∧ (a ∨ ¬b), ce qui impose a = b (les variables doivent avoir la même valeur). - Ces deux conditions sont mutuellement exclusives. Aucune affectation de vérité ne peut satisfaire simultanément les quatre clauses. Résultat : l'ensemble de clauses est non satisfiable.

| p | q | p ⊕ q | p ↔ q | ¬(p ↔ q) | (p ⊕ q) ↔ ¬(p ↔ q) | |---|---|-------|-------|----------|---------------------| | V | V | F | V | F | V | | V | F | V | F | V | V | | F | V | V | F | V | V | | F | F | F | V | F | V | **Vérification ligne par ligne :** - Ligne 1 (p=V, q=V) : p⊕q = F. p↔q = V. ¬(p↔q) = F. F ↔ F = V. - Ligne 2 (p=V, q=F) : p⊕q = V. p↔q = F. ¬(p↔q) = V. V ↔ V = V. - Ligne 3 (p=F, q=V) : p⊕q = V. p↔q = F. ¬(p↔q) = V. V ↔ V = V. - Ligne 4 (p=F, q=F) : p⊕q = F. p↔q = V. ¬(p↔q) = F. F ↔ F = V. **Analyse structurelle :** Par définition logique, l'ou exclusif (⊕) et la biconditionnelle classique (↔) sont mutuellement contradictoires : p ⊕ q ≡ ¬(p ↔ q). Les deux operands de la biconditionnelle finale sont donc toujours identiques. Une équivalence de la forme (A ↔ A) est toujours Vraie. **Conclusion :** La formule est une **tautologie** (sa colonne finale est systématiquement Vraie).

L’énoncé est vrai. Voici la démonstration structurée. **1. Cadre et définitions** - Soit $F$ une formule propositionnelle en CNF où chaque clause contient au plus un littéral positif. - Une valuation $v : At \to \{0,1\}$ (avec $0 < 1$) est un modèle de $F$ si $v \models F$. - L’ordre composante par composante est défini par $v \le w \iff \forall p \in At, v(p) \le w(p)$. En identifiant $v$ à l’ensemble de ses atomes vrais $T_v = \{p \mid v(p)=1\}$, cet ordre est équivalent à l’inclusion $\subseteq$. **2. Lemme fondamental : stabilité par intersection** Soient $v_1$ et $v_2$ deux modèles de $F$. On note $v_\cap$ la valuation définie par $v_\cap(p) = \min(v_1(p), v_2(p))$. On montre que $v_\cap \models F$. Il suffit de vérifier chaque type de clause $C$ de $F$ : - Si $C = p$ (fait), $v_1(p)=1$ et $v_2(p)=1$ impliquent $v_\cap(p)=1$. La clause est satisfaite. - Si $C = \neg p_1 \lor \dots \lor \neg p_k$ (clause de but), supposons $v_\cap$ la falsifie. Alors $v_\cap(p_i)=1$ pour tout $i$, ce qui force $v_1(p_i)=1$ et $v_2(p_i)=1$. Ainsi $v_1$ et $v_2$ falsifient $C$, contradiction avec $v_1, v_2 \models F$. - Si $C = \neg p_1 \lor \dots \lor \neg p_k \lor q$ (clause Horn), supposons $v_\cap$ la falsifie. Alors $v_\cap(p_i)=1$ pour tout $i$ et $v_\cap(q)=0$. Les égalités $v_\cap(p_i)=1$ entraînent $v_1(p_i)=1$ et $v_2(p_i)=1$. Comme $v_1, v_2 \models C$, ils doivent rendre $q$ vrai. Donc $v_1(q)=1$ et $v_2(q)=1$, d’où $v_\cap(q)=1$, contradiction. Dans tous les cas, $v_\cap \models F$. L’ensemble des modèles est donc stable par intersection binaire. **3. Existence d’un modèle minimal** Soit $\mathcal{M}$ l’ensemble des modèles de $F$. La satisfaisabilité garantit $\mathcal{M} \neq \emptyset$. Considérons $v_{min}$ définie par $v_{min}(p) = \bigwedge_{v \in \mathcal{M}} v(p)$. Ensemblistement, $T_{v_{min}} = \bigcap_{v \in \mathcal{M}} T_v$. Dans le cadre propositionnel standard, l’ensemble des atomes est fini, donc cette intersection est une intersection finie. Par application répétée du lemme 2, $v_{min} \models F$. Par construction, pour tout $v \in \mathcal{M}$, $T_{v_{min}} \subseteq T_v$, donc $v_{min} \le v$. $v_{min}$ est un modèle minimal. **4. Unicité** Supposons l’existence d’un autre modèle minimal $v'$. Par définition de minimalité, aucun modèle n’est strictement plus petit que $v'$. Or $v_{min}$ est un modèle et $v_{min} \le v'$. De même, $v'$ étant minimal, on a $v' \le v_{min}$. Par antisymétrie de l’ordre $\le$, on obtient $v' = v_{min}$. Le modèle minimal est donc unique. **Conclusion** Toute formule Horn satisfiable possède un unique modèle minimal pour l’ordre composante par composante. La propriété découle directement de la fermeture de l’ensemble des modèles sous l’intersection, caractéristique structurelle des théories Horn.

**Résultat RuleCore : SATISFAISABLE.** Une affectation valide : X = 1, Y = 1. 🔒 Calcul par **LANXAS RuleCore** — moteur de contraintes déterministe (brevet FR2604698) : arc-cohérence AC-3 puis recherche exacte. Résultat reproductible : mêmes contraintes → même résultat.

Soit G=(V,E) une instance du problème 3-COLOR avec |V|=n sommets et |E|=m arêtes. On construit une instance I du CSP fini standard SAT (plus précisément 3-SAT) selon le schéma suivant : 1. Variables Pour chaque sommet v∈V et chaque couleur c∈{1,2,3}, on introduit une variable booléenne x_{v,c}. Ensemble : X={x_{v,c} | v∈V, c∈{1,2,3}}. Taille : 3n. 2. Contraintes (clauses) a) Couverture (au moins une couleur par sommet) : pour tout v∈V, clause C_{v,≥1} = (x_{v,1} ∨ x_{v,2} ∨ x_{v,3}). Nombre : n. b) Exclusivité (au plus une couleur par sommet) : pour tout v∈V et tout couple distinct (c1,c2)∈{1,2,3}^2, clause C_{v,≤1}^{c1,c2} = (¬x_{v,c1} ∨ ¬x_{v,c2}). Nombre : 3n. c) Incompatibilité arête (couleurs différentes) : pour toute arête (u,v)∈E et toute couleur c∈{1,2,3}, clause C_{u,v,≠}^{c} = (¬x_{u,c} ∨ ¬x_{v,c}). Nombre : 3m. 3. Taille et complexité de la transformation Variables : 3n Clauses : n + 3n + 3m = 4n + 3m Longueur maximale d'une clause : 3 Temps de construction : O(n+m) opérations élémentaires (parcours de V et E, génération de clauses). La transformation est donc polynomiale. 4. Correctitude de la réduction → Si G admet un coloriage valide σ:V→{1,2,3}, l'assignation A définie par A(x_{v,c})=vrai ⇔ σ(v)=c satisfait I : • Pour chaque v, exactement une variable x_{v,c} est vraie, donc C_{v,≥1} est vraie et toutes les C_{v,≤1}^{c1,c2} sont vraies. • Pour chaque arête (u,v)∈E, σ(u)≠σ(v), donc pour tout c, au moins un de x_{u,c}, x_{v,c} est faux ; ainsi C_{u,v,≠}^{c} est vraie. ← Si A satisfait I, alors pour chaque v, exactement une variable x_{v,c} est vraie (garanti par C_{v,≥1} et C_{v,≤1}^{c1,c2}). On pose σ(v)=c ⇔ A(x_{v,c})=vrai. Pour toute arête (u,v)∈E et tout c, la clause C_{u,v,≠}^{c} empêche simultanément x_{u,c}=vrai et x_{v,c}=vrai, donc σ(u)≠σ(v). σ est donc un coloriage 3 valide de G. 5. Conclusion La mapping G ↦ (X, Clauses) est une réduction polynomiale explicite de 3-COLOR vers un CSP fini standard (SAT/3-SAT). Elle préserve la satisfaisabilité, s'exécute en O(n+m) temps et produit une instance de taille linéaire en n+m. La même construction peut être vue directement comme un CSP sur domaine D={1,2,3} avec variables V et contraintes C_{u,v}={(a,b)∈D^2 | a≠b} pour (u,v)∈E, ce qui correspond à la formulation CSP canonique du coloriage de graphes.

Ce syllogisme est **invalid**. **Analyse formelle** Il commet la faute de l'**intermédiaire non distribué**. Dans la majeure (« tous les A sont B »), le terme moyen B est attribut et reste non distribué. Dans la mineure (« certains B sont C »), le terme moyen B est sujet d'une proposition particulière et reste également non distribué. Le terme moyen ne recouvre donc jamais la totalité de son extension, ce qui empêche tout lien logique d'être établi entre A et C. **Contre-exemple ensembliste** - A = {1} - B = {1, 2} - C = {2} Vérification des prémisses : - « Tous les A sont B » → vrai (1 ∈ {1, 2}) - « Certains B sont C » → vrai (2 ∈ B ∩ C) Vérification de la conclusion : - « Certains A sont C » → faux (A ∩ C = ∅) Les prémisses sont vraies tandis que la conclusion est fausse. Le raisonnement est donc logiquement invalide.

Non. Cette implication n'est pas valide en logique du premier ordre. Données : - Formule P : \(\forall x \exists y\,R(x,y)\) - Formule Q : \(\exists y \forall x\,R(x,y)\) Raisonnement : L'ordre des quantificateurs modifie la portée et la dépendance des variables. Dans P, le choix de \(y\) peut dépendre de \(x\). Dans Q, il faut un même \(y\) qui satisfait la relation pour tout \(x\), indépendamment de sa valeur. La variable \(y\) dans P est liée localement, tandis que dans Q elle est liée globalement. Contre-exemple formel : - Domaine \(D = \{1, 2\}\) - Relation \(R(x,y) \equiv (x = y)\) - Vérification de P : Pour \(x=1\), on choisit \(y=1\) (vrai). Pour \(x=2\), on choisit \(y=2\) (vrai). Donc P est vraie. - Vérification de Q : Existe-t-il un \(y \in D\) tel que \(x=y\) pour tout \(x \in D\) ? Non, car aucun élément n'est égal simultanément à 1 et à 2. Donc Q est fausse. Résultat final : L'implication \(\forall x \exists y\,R(x,y) \implies \exists y \forall x\,R(x,y)\) est fausse en général. Elle n'est valide que dans des cas particuliers (domaine unitaire, ou relation \(R\) ne dépendant pas de \(x\)), mais ne constitue pas une règle logique universelle.

L’insatisfiabilité de \(F \land \neg F\) est une propriété purement formelle qui découle directement de la sémantique des connecteurs logiques. Elle est indépendante du contenu de \(F\) pour les raisons suivantes : 1. **Définition sémantique des connecteurs** En logique propositionnelle, toute valuation \(v\) attribue à chaque formule une valeur de vérité unique dans \(\{0, 1\}\) (Faux, Vrai). Les connecteurs \(\neg\) (négation) et \(\land\) (conjonction) sont définis par leurs tables de vérité : - \(v(\neg A) = 1 - v(A)\) - \(v(A \land B) = \min(v(A), v(B))\) 2. **Analyse exhaustive par valuation** Pour n'importe quelle formule \(F\), \(v(F)\) ne peut prendre que deux valeurs : - Si \(v(F) = 1\), alors \(v(\neg F) = 0\). On obtient \(v(F \land \neg F) = \min(1, 0) = 0\). - Si \(v(F) = 0\), alors \(v(\neg F) = 1\). On obtient \(v(F \land \neg F) = \min(0, 1) = 0\). Dans les deux cas, la valuation de la formule globale est systématiquement 0 (Faux). 3. **Absence de modèle** Une formule est insatisfiable si et seulement si elle n'admet aucune valuation qui la rende vraie. Ici, quel que soit le nombre d'atomes constituant \(F\), quelle que soit sa profondeur syntaxique ou sa portée sémantique, la structure \(A \land \neg A\) projette obligatoirement sur Faux. Il n'existe donc aucun modèle pour \(F \land \neg F\). 4. **Indépendance vis-à-vis du contenu** Le « contenu » de \(F\) (sa signification, ses termes, sa complexité) intervient uniquement au niveau de la syntaxe. La sémantique des opérateurs agit comme un déterminisme structurel : elle neutralise toute variation de vérité de \(F\) en la combinant avec sa négation. Le principe de non-contradiction n'est pas ici une hypothèse externe, mais la traduction formelle du fait que deux états opposés ne peuvent coexister dans une même valuation. La forme logique impose la contradiction avant même que le contenu ne soit interprété. En résumé, l'insatisfiabilité de \(F \land \neg F\) est garantie par la définition même de \(\neg\) et \(\land\). La valuation de la formule est constamment Faux, indépendamment de toute attribution de vérité possible à ses composants. C'est une propriété inhérente au schéma syntaxique, pas au sens de \(F\).

Le Sudoku 4×4 se formalise comme un triplet (X, D, C) définissant un Problème de Satisfaisabilité de Contraintes (CSP). 1. Variables (X) L'ensemble des variables représente les 16 cellules de la grille. X = { X_{i,j} | i ∈ {1, 2, 3, 4}, j ∈ {1, 2, 3, 4} } où i correspond à l'indice de ligne et j à l'indice de colonne. 2. Domaines (D) Chaque variable doit prendre une valeur appartenant à l'ensemble des symboles autorisés. Pour tout X_{i,j} ∈ X : Dom(X_{i,j}) = {1, 2, 3, 4} 3. Contraintes (C) L'ensemble des contraintes impose que les valeurs soient distinctes (opérateur ≠) selon les règles de la grille. a) Contrainte de ligne Toute ligne doit contenir des valeurs uniques. C_{ligne} = { X_{i,j1} ≠ X_{i,j2} | i ∈ {1, 2, 3, 4}, j1, j2 ∈ {1, 2, 3, 4}, j1 ≠ j2 } b) Contrainte de colonne Toute colonne doit contenir des valeurs uniques. C_{colonne} = { X_{i1,j} ≠ X_{i2,j} | i1, i2 ∈ {1, 2, 3, 4}, j ∈ {1, 2, 3, 4}, i1 ≠ i2 } c) Contrainte de bloc La grille est divisée en quatre blocs de 2×2. Chaque bloc doit contenir des valeurs uniques. On définit l'appartenance à un bloc par la fonction B(i, j) = (⌊(i-1)/2⌋, ⌊(j-1)/2⌋), où ⌊x⌋ désigne la partie entière de x. C_{bloc} = { X_{i1,j1} ≠ X_{i2,j2} | B(i1, j1) = B(i2, j2) et (i1, j1) ≠ (i2, j2) } L'ensemble complet des contraintes est C = C_{ligne} ∪ C_{colonne} ∪ C_{bloc}.

Données : Ensemble des clauses $S = \{(p), (q), (\neg p \lor \neg q), (r)\}$. Raisonnement étape par étape : 1. Recherche d'un sous-ensemble insatisfaisable. Un ensemble de clauses est insatisfaisable s'il n'existe aucune valuation de vérité qui rende toutes ses clauses vraies simultanément. Testons le sous-ensemble $U = \{(p), (q), (\neg p \lor \neg q)\}$. Simplification logique : $(p) \land (q) \land (\neg p \lor \neg q)$ $= (p \land q \land \neg p) \lor (p \land q \land \neg q)$ (distributivité) $= F \lor F$ (car $p \land \neg p \equiv F$ et $q \land \neg q \equiv F$) $= F$ Le sous-ensemble $U$ est donc insatisfaisable. 2. Vérification de la minimalité. Un noyau insatisfiable minimal (MUS) est un sous-ensemble insatisfaisable dont aucun sous-ensemble propre ne l'est. On teste la suppression de chaque clause de $U$ : - Sans $(p)$ : $\{(q), (\neg p \lor \neg q)\}$ est satisfaisable par $p=F, q=T$. - Sans $(q)$ : $\{(p), (\neg p \lor \neg q)\}$ est satisfaisable par $p=T, q=F$. - Sans $(\neg p \lor \neg q)$ : $\{(p), (q)\}$ est satisfaisable par $p=T, q=T$. Tous les sous-ensembles propres sont satisfaisables. $U$ est donc minimal. 3. Analyse de la clause $(r)$. La clause $(r)$ est unitaire et indépendante des variables $p$ et $q$. Aucun sous-ensemble contenant $(r)$ et un sous-ensemble satisfaisable ne devient insatisfaisable. Le seul sous-ensemble insatisfaisable contenant $(r)$ serait $\{(p), (q), (\neg p \lor \neg q), (r)\}$, mais il n'est pas minimal car il contient strictement $U$ comme sous-ensemble insatisfaisable. Résultat : Le noyau insatisfiable minimal unique de l'ensemble est : $\{(p), (q), (\neg p \lor \neg q)\}$

**1. Construction du graphe d’implications** Soit un instance 2-SAT avec n variables booléennes x_1, x_2, ..., x_n et m clauses de la forme (l_1 ∨ l_2), où chaque littéral l_j est soit une variable, soit sa négation. Le graphe d’implications G = (V, E) se construit comme suit : - L’ensemble des sommets V contient les 2n littéraux : V = {x_1, ¬x_1, x_2, ¬x_2, ..., x_n, ¬x_n}. - Pour chaque clause (l_1 ∨ l_2), on ajoute deux arêtes orientées : ¬l_1 → l_2 et ¬l_2 → l_1. Cette traduction repose sur l’équivalence logique (A ∨ B) ≡ (¬A → B) ≡ (¬B → A). - La taille du graphe est |V| = 2n et |E| ≤ 2m. La construction s’effectue en O(n + m). **2. Rôle fondamental du graphe d’implications** Le graphe d’implications transforme un problème logique en un problème de connectivité orientée. Son rôle central est triple : - **Encodage des contraintes** : Chaque clause impose que si son premier littéral est faux, le second doit être vrai, et vice-versa. Les arêtes capturent exactement cette dépendance binaire. - **Transitivité des implications** : Si une arête existe de u vers v, l’affectation de v = True est nécessaire chaque fois que u = True. Par transitivité, l’existence d’un chemin u →* v implique que u = True force v = True. - **Détection des contradictions** : Si un chemin existe de x_i vers ¬x_i ET de ¬x_i vers x_i, alors x_i = True force ¬x_i = True (contradiction), et ¬x_i = True force x_i = True (contradiction). Les deux littéraux appartiennent alors à la même composante fortement connexe (SCC). Cette condition est nécessaire et suffisante pour l’insatisfiabilité. **3. Théorème clé et preuve du rôle des SCC** Théorème : Une instance 2-SAT est insatisfiable si et seulement si, dans G, il existe une variable x_i telle que x_i et ¬x_i appartiennent à la même SCC. Preuve (esquisse) : - (⇒) Si x_i et ¬x_i sont dans la même SCC, un chemin x_i →* ¬x_i et un chemin ¬x_i →* x_i existent. La première chaîne impose x_i = True ⇒ ¬x_i = True, donc x_i = False. La seconde impose ¬x_i = True ⇒ x_i = True, donc x_i = True. Contradiction directe. Aucune affectation ne peut satisfaire l’instance. - (⇐) Si x_i et ¬x_i sont dans des SCC distinctes pour tout i, aucune contradiction de ce type n’existe. On peut alors construire une affectation valide en utilisant l’ordre topologique de la condensation de G (graphe des SCC), comme détaillé ci-dessous. **4. Algorithme de résolution et complexité** Étape 1 – Construction : O(n + m). Étape 2 – Décomposition en SCC : Algorithme de Tarjan ou Kosaraju en O(|V| + |E|) = O(n + m). Étape 3 – Vérification de la contradiction : Pour chaque i de 1 à n, vérifier si SCC[x_i] == SCC[¬x_i]. Coût O(n). Si égalité détectée, retourner INSATISFIABLE. Étape 4 – Affectation satisfaisante (si aucune contradiction) : - Calculer l’ordre topologique inverse des SCC de la condensation de G. - Parcourir les SCC dans cet ordre. Pour chaque SCC, si les littéraux n’ont pas encore d’affectation, assigner False à tous les littéraux de cette SCC, et True à leurs opposés (qui appartiendront à une SCC visitée plus tard dans l’ordre inverse, préservant la cohérence). - Cette phase s’exécute en O(n + m) car elle ne fait qu’un parcours linéaire sur les sommets et arêtes. Complexité totale : O(n + m). Le temps est strictement linéaire par rapport à la taille de l’encodage, donc polynomiale. **5. Conclusion** Le graphe d’implications joue le rôle de médiateur structurel entre la logique propositionnelle et la théorie des graphes. En traduisant chaque clause en deux arêtes orientées, il permet de réduire la satisfiabilité à la détection de cycles contradictoires via les SCC. La décomposition linéaire en SCC, la vérification de l’absence de x_i et ¬x_i dans la même composante, et la construction de l’affectation par ordre topologique inverse garantissent une résolution complète en O(n + m). 2-SAT est donc résoluble en temps polynomial, contrairement au k-SAT pour k ≥ 3 qui reste NP-complet.

Variables : X, Y, Z Domaines : D(X) = {0, 1}, D(Y) = {0, 1}, D(Z) = {0, 1} Contraintes binaires : C1(X,Y) : X ≠ Y, C2(Y,Z) : Y ≠ Z, C3(X,Z) : X ≠ Z Vérification de l'arc-consistance : Pour chaque arc et chaque valeur du domaine source, il existe une valeur compatible dans le domaine cible. - Arc X → Y : si X = 0, Y = 1 satisfait X ≠ Y ; si X = 1, Y = 0 satisfait X ≠ Y. Arc consistant. - Arc Y → X : symétrique, Arc consistant. - Arc Y → Z : si Y = 0, Z = 1 satisfait Y ≠ Z ; si Y = 1, Z = 0 satisfait Y ≠ Z. Arc consistant. - Arc Z → Y : symétrique, Arc consistant. - Arc X → Z : si X = 0, Z = 1 satisfait X ≠ Z ; si X = 1, Z = 0 satisfait X ≠ Z. Arc consistant. - Arc Z → X : symétrique, Arc consistant. Le réseau est donc arc-consistant. Vérification de l'insatisfiabilité globale : On cherche un triplet (x,y,z) ∈ {0,1}^3 vérifiant les trois contraintes. - Cas X = 0. Alors Y = 1 (par C1) et Z = 0 (par C2). Or C3 impose X ≠ Z, donc 0 ≠ 0, contradiction. - Cas X = 1. Alors Y = 0 (par C1) et Z = 1 (par C2). Or C3 impose X ≠ Z, donc 1 ≠ 1, contradiction. Aucune affectation complète ne satisfait l'ensemble des contraintes. Le CSP est globalement insatisfiable. Ce contre-exemple classique montre que l'arc-consistance ne garantit pas l'existence d'une solution globale. Elle élimine uniquement les valeurs incompatibles avec les contraintes binaires locales, sans détecter les conflits d'ordre supérieur (ici de rang 3).

**Principe de propagation ALLDIFFERENT** La propagation globale sur une contrainte ALLDIFFERENT repose sur le théorème de Hall ou sur l'identification des arêtes appartenant à au moins un couplage maximal dans un graphe biparti (variables d'un côté, valeurs de l'autre). Une valeur $v$ dans $D(X_i)$ est éliminée si et seulement si aucune affectation valide (respectant l'unicité des valeurs) ne peut inclure $X_i = v$. **Analyse du problème** - Variables : $X_1, X_2, X_3$ - Domaines initiaux : $D(X_1)=\{1,2\}$, $D(X_2)=\{1,2\}$, $D(X_3)=\{1,2,3\}$ - Union des domaines : $\{1,2,3\}$ (taille 3) - Nombre de variables : 3 Puisque le nombre de variables est égal à la taille de l'union des domaines, toute solution valide doit utiliser exactement les trois valeurs disponibles $\{1,2,3\}$, chacune attribuée une fois. **Application de la propagation** - Pour $X_1$ et $X_2$ : leurs domaines sont identiques $\{1,2\}$. Ils doivent prendre des valeurs distinctes entre elles. Les deux affectations possibles sont $(X_1=1, X_2=2)$ ou $(X_1=2, X_2=1)$. Les deux valeurs 1 et 2 sont donc réalisables pour chacune de ces variables. Aucune propagation ne peut les retirer de $D(X_1)$ ni de $D(X_2)$. - Pour $X_3$ : les valeurs 1 et 2 sont déjà nécessaires pour satisfaire l'unicité entre $X_1$ et $X_2$. Si $X_3$ prenait 1, il resterait une seule valeur disponible (2) pour deux variables ($X_1, X_2$), ce qui viole la contrainte ALLDIFFERENT. De même pour la valeur 2. La seule valeur possible pour $X_3$ est donc 3. **Résultat de la propagation** La propagation élimine les valeurs **1** et **2** du domaine de **$X_3$**. Domaines résiduels après propagation : - $D(X_1) = \{1, 2\}$ - $D(X_2) = \{1, 2\}$ - $D(X_3) = \{3\}$ Les seules valeurs éliminées par la propagation globale sont **1 et 2 de $D(X_3)$**.

Formalisation de l'énoncé initial Énoncé : ∀x ∃!y P(x,y) Définition de l'unicité : ∃!y P(x,y) ≡ ∃y (P(x,y) ∧ ∀z (P(x,z) → z=y)) Énoncé complet : ∀x [ ∃y (P(x,y) ∧ ∀z (P(x,z) → z=y)) ] Dérivation de la négation (étape par étape) 1. Négation du quantificateur universel : ¬∀x A ≡ ∃x ¬A ∃x ¬[ ∃y (P(x,y) ∧ ∀z (P(x,z) → z=y)) ] 2. Négation du quantificateur existentiel : ¬∃y B ≡ ∀y ¬B ∃x ∀y ¬[ P(x,y) ∧ ∀z (P(x,z) → z=y) ] 3. Négation d'une conjonction : ¬(A ∧ B) ≡ ¬A ∨ ¬B ∃x ∀y [ ¬P(x,y) ∨ ¬∀z (P(x,z) → z=y) ] 4. Négation d'un quantificateur universel : ¬∀z C ≡ ∃z ¬C ∃x ∀y [ ¬P(x,y) ∨ ∃z ¬(P(x,z) → z=y) ] 5. Négation d'une implication : ¬(A → B) ≡ A ∧ ¬B ∃x ∀y [ ¬P(x,y) ∨ ∃z (P(x,z) ∧ z≠y) ] Forme canonique simplifiée La structure ∃x ∀y [ ¬P(x,y) ∨ ∃z (P(x,z) ∧ z≠y) ] est logiquement équivalente à la formulation canonique de la négation de l'unicité : ∃x [ (∀y ¬P(x,y)) ∨ (∃y1 ∃y2 (y1≠y2 ∧ P(x,y1) ∧ P(x,y2))) ] Traduction en français « Il existe un x tel que (il n'existe aucun y vérifiant P(x,y)) ou (il existe au moins deux y distincts vérifiant P(x,y)) ». Vérification de validité - Si l'énoncé initial est vrai, chaque x possède exactement un y. - La négation est vraie si et seulement si au moins un x échoue à cette propriété, c'est-à-dire qu'il n'a ni y (cas ∀y ¬P(x,y)) ni deux y ou plus (cas ∃y1 ∃y2 (y1≠y2 ∧ P(x,y1) ∧ P(x,y2))). - Les deux formes dérivées sont équivalentes par les lois de De Morgan et les règles de négation des quantificateurs. Aucun saut logique n'est intervenu. La négation est correcte et complète.

Pour déterminer si \((p\to q)\lor(q\to p)\) est une tautologie, on examine sa valeur de vérité pour toutes les combinaisons possibles de \(p\) et \(q\). Rappelons que l'implication \(A\to B\) est fausse uniquement lorsque \(A\) est vraie et \(B\) est fausse ; dans tous les autres cas, elle est vraie. Tableau de vérité : | p | q | p→q | q→p | (p→q)∨(q→p) | |---|---|-----|-----|-------------| | V | V | V | V | V | | V | F | F | V | V | | F | V | V | F | V | | F | F | V | V | V | Analyse détaillée : - \(p=V, q=V\) : \(p\to q=V\), \(q\to p=V\) → disjonction \(V\). - \(p=V, q=F\) : \(p\to q=F\), \(q\to p=V\) (antécédent faux) → disjonction \(V\). - \(p=F, q=V\) : \(p\to q=V\) (antécédent faux), \(q\to p=F\) → disjonction \(V\). - \(p=F, q=F\) : \(p\to q=V\), \(q\to p=V\) → disjonction \(V\). La formule prend systématiquement la valeur vraie, quelle que soit l'affectation de \(p\) et \(q\). Vérification algébrique : En utilisant la définition \(A\to B \equiv \neg A \lor B\), on obtient : \((p\to q)\lor(q\to p) \equiv (\neg p \lor q)\lor(\neg q \lor p)\) Par associativité et commutativité de \(\lor\) : \(\equiv (\neg p \lor p)\lor(\neg q \lor q)\) \(\neg p \lor p\) est le tiers exclu (toujours vrai), donc \(\text{V}\lor(\neg q \lor q)\) est toujours vrai. La transformation confirme le résultat du tableau. Conclusion : \((p\to q)\lor(q\to p)\) est une tautologie.

La correction et la complétude sont deux propriétés formelles distinctes d’une procédure de preuve, définies par la direction de l’implication logique qu’elles garantissent. Correction ou sûreté : Une procédure est correcte si tout ce qu’elle déclare prouvable l’est effectivement dans le système logique sous-jacent. Autrement dit, elle ne produit jamais de faux positifs. Formellement : si la procédure démontre φ, alors φ est valide (⊢ φ implique ⊨ φ). Complétude : Une procédure est complète si tout énoncé valide dans le système logique peut effectivement être démontré par la procédure. Autrement dit, elle ne produit jamais de faux négatifs. Formellement : si φ est valide (⊨ φ), alors la procédure peut le démontrer (⊢ φ). Différence fondamentale : La correction porte sur la fiabilité des résultats positifs, tandis que la complétude porte sur l’exhaustivité du processus. Une procédure peut être correcte sans être complète, ce qui signifie qu’elle prouve des énoncés vrais mais en rate certains. Elle peut aussi être complète sans être correcte, ce qui la rendrait inutile car elle validerait des énoncés faux. Dans la pratique, les procédures de preuve visent à être les deux, mais la complétude totale est souvent impossible en logique du premier ordre en raison de l’indécidabilité. C’est pourquoi on utilise fréquemment des procédures de réfutation complètes ou des procédures complètes sur des fragments de logique restreints. En résumé : Correction : ⊢ φ implique ⊨ φ, pas de faux positifs Complétude : ⊨ φ implique ⊢ φ, pas de faux négatifs Ces deux propriétés sont indépendantes et doivent être vérifiées séparément pour garantir la fiabilité et l’efficacité d’un système de preuve.

Lorsqu’un solveur annonce UNSAT, l’annonce peut être étayée par des certificats de preuve vérifiables indépendamment. Les types de certificats se classent selon le domaine (SAT propositionnel, SMT, optimisation) et le système de preuve sous-jacent : 1. Certificats de preuve pour le SAT (propositionnel) - Arbres de résolution CDCL : chaque nœud correspond à une clause dérivée par résolution ; la racine est la clause vide. Vérifiable par relecture séquentielle ou par des vérificateurs dédiés. - Format DRAT (Delete, Add, Resolution) : séquence d’opérations sur un ensemble de clauses qui prouve l’insatisfaisabilité tout en préservant la satisfaisabilité à chaque étape. Complexité de vérification polynomiale par rapport à la taille du certificat. - Format LRAT (Lazy Resolution) : extension de DRAT conçue pour les solveurs incrémentaux, permettant une vérification sans reconstruction explicite de l’arbre de résolution ni réexécution complète du solveur. - Preuves par Cutting Planes : utilisées par les solveurs linéaires ou mixtes, basées sur des combinaisons linéaires d’inégalités à coefficients entiers. Vérification par contrôle de l’homogénéité, des coefficients et de la validité des coupes. - Certificats de dualité (MILP/MIP) : pour les solveurs d’optimisation mixte, basés sur le théorème de dualité linéaire et les plans de coupe. La preuve consiste en une solution duale réalisable, une solution primale réalisable ou un gap nul certifié, et la validité de chaque coupe ajoutée. 2. Certificats de preuve pour le SMT (théories combinées) - Arbres de conflit théorie : montrent comment les axiomes d’une théorie (arithmétique linéaire, tableaux, égalité, listes, etc.) entraînent une contradiction. Chaque nœud applique une règle d’inférence ou une transformation de la théorie. - Élimination de Fourier-Motzkin ou méthodes de tableau : pour l’arithmétique linéaire, le certificat est la séquence d’élimination de variables aboutissant à une contradiction de la forme 0 ≤ c avec c < 0. - Preuves de combinaison (cadre Nelson-Oppen) : certificats validant la cohérence des interprétations partagées entre théories disjointes et démontrant leur incompatibilité via un conflit sur les symboles communs. - Formats SMT-LIB : arbres de preuve structurés, souvent accompagnés de transformations de Tseitin ou de réification, vérifiables par des checkers SMT dédiés qui reconstituent l’état des termes et valident les règles de théorie. 3. Principes et outils de vérification indépendante - Vérificateurs standards : drat-trim, verit, smt-rat, cvc5 (mode preuve), sat4j (DRAT/LRAT). Ils lisent le certificat et valident chaque étape sans exécuter le solveur initial ni faire confiance à son binaire. - Complexité : DRAT et LRAT sont vérifiables en temps polynomial. Les preuves par dualité ou Fourier-Motzkin le sont également, mais la taille peut croître exponentiellement dans le pire cas. - Limites pratiques : les certificats peuvent être volumineux (plusieurs Go), la vérification est mémoire intensive, et certains formats incrémentaux nécessitent un état de solveur reconstitué pour la validation. Aucun certificat ne garantit l’absence de bug dans le vérificateur lui-même ; la sécurité repose sur la redondance et l’audit des checkers. La sélection du certificat dépend du solveur (glucose, MiniSAT, Z3, CVC5, Gurobi, etc.) et du format de sortie supporté. Une vérification indépendante repose toujours sur un vérificateur séparé, open source et auditée, qui exécute strictement les règles du système de preuve sous-jacent.

L’assertion est fausse. Élément à vérifier : implication « si chaque sous-ensemble propre d’un ensemble fini de contraintes est satisfiable, alors l’ensemble complet est satisfiable ». Contre-exemple explicite : Soit un ensemble fini de contraintes S = {C1, C2} portant sur une variable réelle x. C1 : x = 0 C2 : x = 1 Sous-ensembles propres de S : {C1} et {C2}. Vérification de la satisfiabilité des sous-ensembles propres : - {C1} admet la solution x = 0. Il est satisfiable. - {C2} admet la solution x = 1. Il est satisfiable. Vérification de la satisfiabilité de l’ensemble complet S : - S = {C1, C2} impose simultanément x = 0 et x = 1. L’intersection des domaines de satisfaction est vide. S est insatisfiable. Conclusion : Chaque sous-ensemble propre est satisfiable, mais l’ensemble complet ne l’est pas. L’implication est donc réfutée. Remarque théorique : La satisfiabilité possède la propriété de monotonicité descendante : si un ensemble de contraintes est satisfiable, tout sous-ensemble l’est également. L’implication inverse n’est pas vraie en général. Un ensemble fini insatisfiable dont tous les sous-ensembles propres sont satisfiables correspond à la définition formelle d’un « sous-ensemble insatisfiable minimal » (MUS) ou d’un conflit. Pour que l’assertion soit vraie, il faudrait ajouter l’hypothèse que la classe de contraintes considérée est close par union (ou qu’elle vérifie la propriété de 2-satisfiabilité), ce qui n’est pas le cas des systèmes de contraintes classiques en programmation par contraintes, en logique propositionnelle ou en optimisation linéaire.

On peut conclure qu'une solution globale existe toujours, sous réserve que le domaine de chaque variable soit non vide. Sur un graphe de contraintes arborescent, la consistance d'arc est équivalente à la consistance globale. En l'absence de cycles, la propagation locale des contraintes entre paires de variables suffit à garantir qu'aucun conflit ne peut apparaître lors de la construction d'une affectation complète. Une recherche avec retour arrière ne rencontrera jamais de blocage et trouvera systématiquement une solution en temps polynomial (linéaire en le nombre de variables). Cette propriété repose sur le théorème fondamental des CSP arborescents : un CSP dont le graphe de contraintes est un arbre et qui est arc-consistant (avec des domaines non vides) est toujours satisfiable. Si l'un des domaines est vide, la solution n'existe pas.