# DNF

A propositional formula is a DNF formula^{}, meaning Disjunctive Normal Form^{}, if it is a disjunction^{} of conjunctions^{} of literals^{} (a literal is a propositional variable or its negation^{}). Hence, a DNF is a formula of the form: ${K}_{1}\vee {K}_{2}\vee \mathrm{\dots}\vee {K}_{n}$, where each ${K}_{i}$ is of the form ${l}_{i1}\wedge {l}_{i2}\wedge \mathrm{\dots}\wedge {l}_{im}$ for literals ${l}_{ij}$ and some $m$ which can vary for each ${K}_{i}$.

Example: $(x\wedge y\wedge \mathrm{\neg}z)\vee (y\wedge \mathrm{\neg}w\wedge \mathrm{\neg}u)\vee (x\wedge v)$.

Title | DNF |
---|---|

Canonical name | DNF |

Date of creation | 2013-03-22 14:14:08 |

Last modified on | 2013-03-22 14:14:08 |

Owner | rspuzio (6075) |

Last modified by | rspuzio (6075) |

Numerical id | 4 |

Author | rspuzio (6075) |

Entry type | Definition |

Classification | msc 03B05 |

Synonym | disjunctive normal form |

Related topic | CNF |

Related topic | AtomicFormula |