Conjunctive Normal Form

Conjunctive Normal Form

In Boolean logic, a formula is in conjunctive normal form (CNF) if it is a conjunction of clauses, where a clause is a disjunction of literals. As a normal form, it is useful in automated theorem proving. It is similar to the product of sums form used in circuit theory.

All conjunctions of literals and all disjunctions of literals are in CNF, as they can be seen as conjunctions of one-literal clauses and conjunctions of a single clause, respectively. As in the disjunctive normal form (DNF), the only propositional connectives a formula in CNF can contain are and, or, and not. The not operator can only be used as part of a literal, which means that it can only precede a propositional variable.

Read more about Conjunctive Normal Form:  Examples and Counterexamples, Conversion Into CNF, First-order Logic, Computational Complexity, Converting From First-order Logic

Famous quotes containing the words normal and/or form:

    “Nothing is poetical if plain daylight is not poetical; and no monster should amaze us if the normal man does not amaze.”
    —Gilbert Keith Chesterton (1874–1936)

    “The form of act or thought mattered nothing. The hymns of David, the plays of Shakespeare, the metaphysics of Descartes, the crimes of Borgia, the virtues of Antonine, the atheism of yesterday and the materialism of to-day, were all emanation of divine thought, doing their appointed work. It was the duty of the church to deal with them all, not as though they existed through a power hostile to the deity, but as instruments of the deity to work out his unrevealed ends.”
    —Henry Brooks Adams (1838–1918)