Boolean functions can be expressed in Disjunctive normal form (DNF) or Conjunctive normal form (CNF). Can anyone explain why these forms are useful?
Boolean function, what is the purpose of DNF and CNF?
7k Views Asked by Max_Salah At
2
There are 2 best solutions below
Related Questions in BOOLEAN-LOGIC
- how do we represent the expression x+y'+z' in into one which can be represented using only NANDs (i.e. negations of products)
- LC-3 Assembly OR operation
- I am new to Boolean Algebra, and i need advice
- How do I modify this .hdl chip to fulfill the question's requirements? (boolean logic / nand2tetris)
- How the logical operators works in java?
- My TempArray always has the wrong values and therefore doesnt evaluate properly and I am confused why
- How do I get this code to accommodate any given number by only using boolean logic (no conditionals/ functions)
- Trouble with boolean logic in if (else) statements
- How to make an alert show up when the page won't load AND it's been 7 seconds
- Derive conditions for each variable assignment from pseudocode
- Problems with Drag and Drop system in Unity
- How to output a 5 bit number from a ripple-carry adder/subtractor into a 5 bit decoder to account for overflow in Verilog?
- Most optimal way of running intensive math calculations on a GPU
- What language uses `and` and `or` keywords to mean "do this thing without affecting the result"?
- Change boolean in ajax in ASP.NET MVC
Related Questions in BOOLEAN-EXPRESSION
- QueryDSL BooleanExpression exclude data if the field is null
- Evaluating logical expressions recognized by ANTLR using the System.Linq.Expressions namespace
- What is the most elegant way of checking if multiple objects exist, in Node.js?
- I am new to Boolean Algebra, and i need advice
- How is this (xy)' + (yz) simplified into this (x’+y’)+z in boolean algebra?
- Octave: Boolean AND returns wrong number
- How do I get this code to accommodate any given number by only using boolean logic (no conditionals/ functions)
- Retrieve data based on boolean logic
- Can reification predicates from CLP(FD) be used to check equality of logic expressions?
- Trouble with boolean logic in if (else) statements
- designing a circuit with 3 3-bit inputs and 4 1-bit outputs
- Yacc : Boolean and Arithmetic expression grammars conflict
- Confusion with Boolean Expressions in C / < and > are reversed?
- What is a good way to verify if arguments of a function are numbers
- Reduce if/else-if on a bunch of partially overlapping conditions
Related Questions in CONJUNCTIVE-NORMAL-FORM
- How can I simplify a conjunction of disjunctions (CNF) statement if I can introduce extra variables?
- The way Sat4j actually solves CNF clauses
- How can I simplify the following CNF
- Dimacs cnf expression not satisfiable, why?
- Creating random CNF formulas prolog
- Generating DIMACS CNF file using bc2cnf is missing AND
- Algorithm implementation to convert propositional formula into conjunctive normal form in JavaScript?
- Is an empty clause within another empty clause is equivalent to an empty clause ?(In CNF form)
- How to get the span of a conjunct in spacy?
- How are objective functions represented in SAT solvers?
- Which of the following is TRUE about formulae in Conjunctive Normal Form?
- Print all solutions of the N-Queens problem using a SAT solver
- How to using CNFs to describe addition
- Converting first-order logic to CNF without exponential blowup
- Why a Boolean Logic Statement Needs to be in Conjunctive Normal Form (CNF)
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
Popular # Hahtags
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
CNF is useful because this form directly describes the Boolean SAT problem, which while NP-complete, has many incomplete and heuristic exponential time solvers. CNF has been further standardized into a file format called the "DIMACS CNF file format", from which most solvers can operate on. Thus for example, the chip industry can verify their circuit designs by converting to DIMACS CNF, and feeding in to any of the solvers available. The Tseitin Transformation can convert circuits to an equisatisfiable CNF.
DNF is not as useful practically, but converting a formula to DNF means one can see a list of possible assignments that would satisfy the formula. Unfortunately, converting a formula to DNF in general, is hard, and can lead to exponential blow up (very large DNF), which is evident, because there can be exponentially number of satisfying assignments to a formula.
While CNF can be succinct compared with DNF, it is sometimes hard to reason with, because it can lose structure when converted from a circuit for example, and so another succinct form would be useful. The and-inverter graph data structure was designed for this purpose; it can more closely model the structure of circuits, and is thus much easier to reason with in some types of formulas. However there are not many solvers that operate on it.
Other forms include: