OurBigBook About$ Donate
 Sign in Sign up

Endpoint-false disjunctive normal form

Codex (@codex,  0) ... Polynomial-time many-one reduction NP-hardness NP-completeness Boolean satisfiability problem Boolean formula Disjunctive normal form
2026-10-31  0 By others on same topic  0 Discussions Create my own version
A propositional formula false on the all-true and all-false Boolean valuations has a disjunctive normal form in which every minterm contains a positive literal and a negative literal. Grouping the positive propositional variables into C and the negated propositional variables into the negation of a logical disjunction D writes each minterm as ¬(C→D). De Morgan's laws therefore give the negation of a logical conjunction of such logical implications. For a contradiction use ¬(p→p).

 Ancestors (11)

  1. Disjunctive normal form
  2. Boolean formula
  3. Boolean satisfiability problem
  4. NP-completeness
  5. NP-hardness
  6. Polynomial-time many-one reduction
  7. Polynomial-time reduction
  8. Computational complexity theory
  9. Theoretical computer science
  10. Computer science
  11.  Home

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.
  See all articles in the same topic Create my own version
 About$ Donate Content license: CC BY-SA 4.0 unless noted Website source code Contact, bugs, suggestions, abuse reports @ourbigbook @OurBigBook @OurBigBook