Skip to content
TheChatArchiveThe Chat Archive
gpt-oss-120b· OpenAIHugging Face Arena Expert 5K

Considering the definition of CNF Boolean formulas such that there are 2^3^n formulas…

  1. User

    Considering the definition of CNF Boolean formulas such that there are 2^3^n formulas (inclusion/exclusion of literals/clauses), how many satisfiable formulas of 2 variables are there? List a reasonable amount.

  2. Assistant

    How many 2‑variable CNF formulas are satisfiable?

    For a set of (n) Boolean variables a CNF formula is a set of clauses, and each clause is a disjunction of literals.
    For each variable we have three possibilities inside a clause

    • the variable appears positively,
    • the variable appears negatively,
    • the variable does not appear.

    Hence there are (3^{n}) different possible clauses.
    A CNF formula is any subset of those clauses, so the total number of CNF formulas over (n) variables is

    [ 2^{,3^{n}} . ]


    The case (n=2)

    Number of possible clauses

    [ 3^{2}=9 ]

    clausedescription
    (;) (empty)always false
    (x)
    (\neg x)
    (y)
    (\neg y)
    (x\lor y)
    (x\lor \neg y)
    (\neg x\lor y)
    (\neg x\lor \neg y)

    Number of possible CNF formulas

    [ 2^{9}=512 . ]


    Counting the satisfiable ones

    Let the two variables be (x) and (y).
    There are four assignments:

    assignmentfalsified clauses (the only clauses that are false under the assignment)
    (x=0,;y=0)({;\emptyset,;x,;y,;x\lor y;})
    (x=0,;y=1)({;\emptyset,;x,;\neg y,;x\lor\neg y;})
    (x=1,;y=0)({;\emptyset,;\neg x,;y,;\neg x\lor y;})
    (x=1,;y=1)({;\emptyset,;\neg x,;\neg y,;\neg x\lor\neg y;})

    A CNF formula is satisfied by an assignment iff none of the clauses it contains belongs to the falsified‑clause set of that assignment.

    • For a single assignment the number of formulas it satisfies is

      [ 2^{9-4}=2^{5}=32 . ]

    • Using inclusion–exclusion over the four assignments we obtain

    [ \begin{aligned} |\text{satisfiable}| &= \sum_{a}|S_a| -!!\sum_{a<b}|S_a\cap S_b| +!!\sum_{a<b<c}|S_a\cap S_b\cap S_c|

    • |S_{00}\cap S_{01}\cap S_{10}\cap S_{11}| \[4pt] &=4\cdot 32
    • (8+8+4+4+8+8) \ &\qquad + (2+2+2+2)
    • 1 \[4pt] &=128-40+8-1 \[4pt] &=95 . \end{aligned} ]

    Hence exactly 95 of the 512 possible CNF formulas over two variables are satisfiable.
    The remaining 417 formulas are unsatisfiable (they contain the empty clause, contradictory unit clauses, or a combination of clauses that forces a contradiction).


    A “reasonable” list of satisfiable formulas

    Below are some representative satisfiable CNF formulas.
    (Every formula is written as a set of its clauses; the empty set of clauses, ∅, denotes the trivially true formula.)

    #CNF formula (set of clauses)Reason it is satisfiable
    1({})No clause → always true
    2({x})Satisfied by any assignment with (x=1)
    3({\neg x})Satisfied by any assignment with (x=0)
    4({y})Satisfied by any assignment with (y=1)
    5({\neg y})Satisfied by any assignment with (y=0)
    6({x,;y})Satisfied by the assignment (x=1,;y=1)
    7({x,;\neg y})Satisfied by (x=1,;y=0)
    8({\neg x,;y})Satisfied by (x=0,;y=1)
    9({\neg x,;\neg y})Satisfied by (x=0,;y=0)
    10({x\lor y})False only on (x=0,y=0); any other assignment works
    11({x\lor\neg y})False only on (x=0,y=1)
    12({\neg x\lor y})False only on (x=1,y=0)
    13({\neg x\lor\neg y})False only on (x=1,y=1)
    14({x,;x\lor y})The unit clause forces (x=1); then the second clause is automatically true
    15({x,;\neg x\lor y})Forces (x=1) and then (y) can be either value
    16({y,;x\lor y})Forces (y=1)
    17({x\lor y,;\neg x\lor\neg y})Satisfied by assignments ((1,0)) and ((0,1))
    18({x\lor\neg y,;\neg x\lor y})Satisfied by ((1,1)) and ((0,0))
    19({x\lor y,;x\lor\neg y,;\neg x\lor y})Satisfied by ((1,0)) and ((1,1))
    20({x,;\neg x\lor\neg y})Forces (x=1); the second clause then forces (y=0) – the assignment ((1,0)) works
    ………

    The list can be continued; any CNF that does not contain

    • the empty clause (which is always false), or
    • both a unit clause (x) and its complement (\neg x) (or similarly for (y)),

    will be among the 95 satisfiable formulas.

    If you need the complete enumeration, it can be generated automatically (e.g., by a short script that iterates over the (2^{9}=512) subsets and checks satisfiability). The count, however, is 95.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.