Tautology of 3-DNF formulas and unsatisfiability of 3-CNF formulas
Lax564036.ThreeDnfTautology · concepts/Lax564036/ThreeDnfTautology.lean · lax-564036
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
Over the vocabulary of CNF instances, an instance has width at most three when no clause has four distinct literal occurrences. It is a yes-instance of 3-DNF-TAUT when it has width at most three and, read as a formula in disjunctive normal form, is a tautology; it is a yes-instance of 3-UNSAT when it has width at most three and, read as a formula in conjunctive normal form, is unsatisfiable. Each problem is the decision problem of the structures isomorphic to such an instance. The width bound is part of both problems, so 3-UNSAT is not the complement of 3SAT, which wide instances also satisfy.
Concept map
Lean source view on GitHub
| 1 | import Mathlib.ModelTheory.Semantics |
| 2 | import Lax904597.Problems |
| 3 | import Lax485149.Problems |
| 4 | import Lax904597.Sat |
| 5 | import Lax799700.ThreeSat |
| 6 | import Lax564036.Tautology |
| 7 | |
| 8 | /-! |
| 9 | --- |
| 10 | title: Tautology of 3-DNF formulas and unsatisfiability of 3-CNF formulas |
| 11 | type: definition |
| 12 | --- |
| 13 | Over the vocabulary of CNF instances, an instance has width at most three |
| 14 | when no clause has four distinct literal occurrences. It is a yes-instance |
| 15 | of 3-DNF-TAUT when it has width at most three and, read as a formula in |
| 16 | disjunctive normal form, is a tautology; it is a yes-instance of 3-UNSAT |
| 17 | when it has width at most three and, read as a formula in conjunctive normal |
| 18 | form, is unsatisfiable. Each problem is the decision problem of the |
| 19 | structures isomorphic to such an instance. The width bound is part of both |
| 20 | problems, so 3-UNSAT is not the complement of 3SAT, which wide instances |
| 21 | also satisfy. |
| 22 | -/ |
| 23 | |
| 24 | namespace Lax564036.ThreeDnfTautology |
| 25 | |
| 26 | open Lax904597.Problems Lax485149.Problems |
| 27 | |
| 28 | open Lax799700.ThreeSat Lax564036.Tautology Lax904597.Sat |
| 29 | |
| 30 | open FirstOrder |
| 31 | |
| 32 | open Language Structure |
| 33 | |
| 34 | section Problems |
| 35 | |
| 36 | variable (A : Type) [sat.Structure A] |
| 37 | |
| 38 | /-- An instance, read as a formula in disjunctive normal form, |
| 39 | is a yes-instance of 3-DNF-TAUT if every term has at most three literal |
| 40 | occurrences and every truth assignment satisfies all the literals of some |
| 41 | term. -/ |
| 42 | def ThreeDnfTautology : Prop := |
| 43 | WidthAtMostThree A ∧ Tautology A |
| 44 | |
| 45 | /-- An instance, read as a formula in conjunctive normal form, |
| 46 | is a yes-instance of 3-UNSAT if every clause has at most three literal |
| 47 | occurrences and no truth assignment satisfies the formula. This is the |
| 48 | CNF-side reading of `ThreeDnfTautology`; it is *not* the complement of 3SAT, |
| 49 | which also holds of wide instances. -/ |
| 50 | def ThreeUnsatisfiable : Prop := |
| 51 | WidthAtMostThree A ∧ ¬Satisfiable A |
| 52 | |
| 53 | end Problems |
| 54 | |
| 55 | /-- 3-DNF-TAUT: is the instance a DNF tautology of width at most three? -/ |
| 56 | def ThreeDnfTAUT : DecisionProblem sat := |
| 57 | DecisionProblem.ofPred fun A _ => ThreeDnfTautology A |
| 58 | |
| 59 | /-- 3-UNSAT: is the instance an unsatisfiable CNF formula of width at most |
| 60 | three? -/ |
| 61 | def ThreeUNSAT : DecisionProblem sat := |
| 62 | DecisionProblem.ofPred fun A _ => ThreeUnsatisfiable A |
| 63 | |
| 64 | end Lax564036.ThreeDnfTautology |
| 65 |
Used by
Lax564036.AlternatingMachineCompleteLax564036.AlternatingMachineInvarianceLax564036.CoNPClosureLax564036.DPClosureLax564036.DPInclusionsLax564036.HierarchyDualityLax564036.HierarchyInclusionsLax564036.PolynomialTimeInHierarchyLax564036.QbfCompleteLax564036.QuantifiedBooleanFormulasInvarianceLax564036.SatUnsatDPCompleteLax564036.SatUnsatInvarianceLax564036.TautCoNPCompleteLax564036.TautologyInvarianceLax564036.ThreeDnfTautCoNPCompleteLax564036.ThreeDnfTautologyInvariance
From Mathlib
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments