Scribd
Upload
7 views2 pages

Understanding Disjunctive Normal Form (DNF)

The document discusses disjunctive normal form (DNF), which is a way to represent logical formulas using conjunctions and disjunctions. DNF involves representing a formula as the disjunction of conjunctive clauses, where each variable appears only once in each clause. The document provides the definition of DNF and examples of generating DNF and formulas that are not in DNF.

Uploaded by

Aditi Jindal
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views2 pages

Understanding Disjunctive Normal Form (DNF)

The document discusses disjunctive normal form (DNF), which is a way to represent logical formulas using conjunctions and disjunctions. DNF involves representing a formula as the disjunction of conjunctive clauses, where each variable appears only once in each clause. The document provides the definition of DNF and examples of generating DNF and formulas that are not in DNF.

Uploaded by

Aditi Jindal
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

DNF

The problem of finding whether a given statement is tautology or


contradiction or satisfiable in a finite number of steps is called the
Decision Problem.
For Decision Problem, construction of truth table may not be practical
always.
For decision problems CNF and DNF forms are considered.

DNF
A logical formula is said to be in disjunctive normal form if it is a
disjunction of conjunctions with every variable and its negation is present
once in each conjunction.
A formula which is equivalent to a given formula that consists of a sum of
elementary products is called a disjunctive normal form of given formula.
Disjunctive normal form (DNF) is the normalization of a logical formula in
Boolean mathematics.
Similar to conjunctive normal form, the propositional operators in
disjunctive normal form are same: 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.
A formula is considered as in full disjunctive normal form if all the
variables involved are represented only once in every clause.
Any unique Boolean function can be represented by only one and a unique
full disjunctive normal form.
Ways of generating DNF for logical formulas:
• Truth table method
• Truth trees
• a table of logical equivalences

Examples of DNF
Following examples are not in DNF

You might also like