Live briefing
Everything about Disjunctive normal form
Standard form of a boolean function
In boolean logic, a disjunctive normal form (DNF) is a normal form of a logical formula consisting of a disjunction of conjunctions; it can also be described as an OR of ANDs, a sum of products, or — in philosophical logic — a cluster concept. The disjunctive normal form and its counterpart, the conjunctive normal form, are the most common standardized ways of representing boolean expressions. They are widely used in various applications such as circuit design or automated theorem proving. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Disjunctive normal formA 5-minute orientation
- Skim a recent paper: Synthesis of Optimal Correction Functions in the Class of Disjunctive Normal FormsInfluential work since 2022
- Pick up a classic book: Discrete and combinatorial mathematicsThe most-reprinted book on the subject
- Read the landmark paper: On the Complexity of Dualization of Monotone Disjunctive Normal FormsCited 320 times
- Go sideways: Conjunctive normal formA closely related topic
- Go sideways: Algebraic normal formA closely related topic
📖 Definitions
Noun The form of a boolean formula that the formula has if the formula is a disjunction of conjunctions of literals, such as “(A and B and C) or (D and E and not F)”.
🏆 Landmark papers (most cited)
On the Complexity of Dualization of Monotone Disjunctive Normal Forms
Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
Finding a short and accurate decision rule in disjunctive normal form by exhaustive search
Local algorithms simplifying the disjunctive normal forms of Boolean functions
Privacy-preserving disjunctive normal form operations on distributed sets
Efficient dualization of (n)-term monotone disjunctive normal forms
On the learnability of disjunctive normal form formulas
Ordered model trees: A normal form for disjunctive deductive databases
🆕 Influential since 2022
Synthesis of Optimal Correction Functions in the Class of Disjunctive Normal Forms
A MODIFIED ALGORITHM FOR MINIMIZING THE DISJUNCTIVE NORMAL FORM
Disjunctive Normal Form Extraction for Interpretable Neural Models in Riesz MV-Algebras
Disjunctive bases: normal forms and model theory for modal logics
Technology independent optimization when implementing sparse systems of disjunctive normal forms of Boolean functions in ASIC
📚 Books worth reading
Discrete and combinatorial mathematicsRalph P. Grimaldi · 1985
Cartesian meditationsEdmund Husserl, Dorion Cairns · 1960
Discrete mathematics for computer scienceGary Haggard · 2006
Mathematical logic for computer scienceChung-wan Lu · 1989
Discrete mathematical structures with applications to computer scienceJean-Paul Tremblay · 1975
Six papers in logic · 1987
Boolean FunctionsWinfrid G. Schneeweiss · 1989
Discrete Mathematics for ComputingPeter Grossman · 1995
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Conjunctive normal form In Boolean algebra, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause…
- Algebraic normal form Algebraic normal form (ANF) is a representation of functions in boolean algebra. Formulas written in ANF are also known as ring sum normal form (RSNF or…
- Horn clause In mathematical logic and logic programming, a Horn clause is a logical formula of a particular rule-like form that gives it useful properties for use…
- First-order logic In mathematics, philosophy, linguistics, and computer science, first-order logic (FOL), also called predicate logic, predicate calculus, or quantificational…
- Logical disjunction In logic, disjunction (also known as logical disjunction, logical or, logical addition, or inclusive disjunction) is a logical connective typically notated…
- Boolean satisfiability problem In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY…
- Logical connective In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is an operator that combines or modifies…
- Propositional logic Propositional logic is a branch of classical logic. It is also called statement logic, sentential calculus, propositional calculus, sentential logic, or…