# conjunctive normal form

conjunctive normal form
The form of a boolean formula that the formula has if the formula is a conjunction of disjunctions of literals, such as "(A or B or C) and (D or E or not F)".

Wikipedia foundation.

### Look at other dictionaries:

• 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 …   Wikipedia

• Normal form — may refer to: Normal form (abstract rewriting) Normal form (databases) Normal form (game theory) Normal form (mathematics) In formal language theory: Beta normal form Chomsky normal form Greibach normal form Kuroda normal form Normal form… …   Wikipedia

• normal form — A well formed formula of the propositional calculus is in conjunctive normal form when it is of the form A & B &…where each of A, B…is a formula consisting of a disjunction of atomic propositions or negations of atomic propositions (e.g. p ∨q ∨ ¬ …   Philosophy dictionary

• Disjunctive normal form — In boolean logic, a disjunctive normal form (DNF) is a standardization (or normalization) of a logical formula which is a disjunction of conjunctive clauses. As a normal form, it is useful in automated theorem proving. A logical formula is… …   Wikipedia

• Clausal normal form — The clausal normal form (or clause normal form, conjunctive normal form, CNF) of a logical formula is used in logic programming and many theorem proving systems. A formula in clause normal form is a set of clauses, interpreted as a conjunction. A …   Wikipedia

• Negation normal form — A logical formula is in negation normal form if negation occurs only immediately above elementary propositions, and { } are the only allowed Boolean connectives. In classical logic each formula can be brought into this form by replacing… …   Wikipedia

• Algebraic normal form — In Boolean logic, the algebraic normal form (ANF) is a method of standardizing and normalizing logical formulas. As a normal form, it can be used in automated theorem proving (ATP), but is more commonly used in the design of cryptographic random… …   Wikipedia

• Skolem normal form — A formula of first order logic is in Skolem normal form (named after Thoralf Skolem) if it is in conjunctive prenex normal form with only universal first order quantifiers. Every first order formula can be converted into Skolem normal form while… …   Wikipedia

• Conjunctive query — In database theory, a conjunctive query is a restricted form of first order queries. A large part of queries issued on relational databases can be written as conjunctive queries, and large parts of other first order queries can be written as… …   Wikipedia

• Canonical form (Boolean algebra) — In Boolean algebra, any Boolean function can be expressed in a canonical form using the dual concepts of minterms and maxterms. Minterms are called products because they are the logical AND of a set of variables, and maxterms are called sums… …   Wikipedia