Tautology of 3-DNF formulas and unsatisfiability of 3-CNF formulas

Lax564036.ThreeDnfTautology · concepts/Lax564036/ThreeDnfTautology.lean · lax-564036

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural 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
    12 concepts; 16 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Lean source view on GitHub

    1import Mathlib.ModelTheory.Semantics
    2import Lax904597.Problems
    3import Lax485149.Problems
    4import Lax904597.Sat
    5import Lax799700.ThreeSat
    6import Lax564036.Tautology
    7
    8/-!
    9---
    10title: Tautology of 3-DNF formulas and unsatisfiability of 3-CNF formulas
    11type: definition
    12---
    13Over the vocabulary of CNF instances, an instance has width at most three
    14when no clause has four distinct literal occurrences. It is a yes-instance
    15of 3-DNF-TAUT when it has width at most three and, read as a formula in
    16disjunctive normal form, is a tautology; it is a yes-instance of 3-UNSAT
    17when it has width at most three and, read as a formula in conjunctive normal
    18form, is unsatisfiable. Each problem is the decision problem of the
    19structures isomorphic to such an instance. The width bound is part of both
    20problems, so 3-UNSAT is not the complement of 3SAT, which wide instances
    21also satisfy.
    22-/
    23
    24namespace Lax564036.ThreeDnfTautology
    25
    26open Lax904597.Problems Lax485149.Problems
    27
    28open Lax799700.ThreeSat Lax564036.Tautology Lax904597.Sat
    29
    30open FirstOrder
    31
    32open Language Structure
    33
    34section Problems
    35
    36variable (A : Type) [sat.Structure A]
    37
    38/-- An instance, read as a formula in disjunctive normal form,
    39is a yes-instance of 3-DNF-TAUT if every term has at most three literal
    40occurrences and every truth assignment satisfies all the literals of some
    41term. -/
    42def ThreeDnfTautology : Prop :=
    43 WidthAtMostThree A ∧ Tautology A
    44
    45/-- An instance, read as a formula in conjunctive normal form,
    46is a yes-instance of 3-UNSAT if every clause has at most three literal
    47occurrences and no truth assignment satisfies the formula. This is the
    48CNF-side reading of `ThreeDnfTautology`; it is *not* the complement of 3SAT,
    49which also holds of wide instances. -/
    50def ThreeUnsatisfiable : Prop :=
    51 WidthAtMostThree A ∧ ¬Satisfiable A
    52
    53end Problems
    54
    55/-- 3-DNF-TAUT: is the instance a DNF tautology of width at most three? -/
    56def 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
    60three? -/
    61def ThreeUNSAT : DecisionProblem sat :=
    62 DecisionProblem.ofPred fun A _ => ThreeUnsatisfiable A
    63
    64end Lax564036.ThreeDnfTautology
    65

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…