Exploring the Concepts of CNF AND DNF

1-Abdulrahman Al Odaini,

7-Rahul Baviskar,

8-Vedang Bhange,

17-Umesh Gaikwad,

23-Akash Hedau

Index:

1. Definition
2. Significance
3. The Difference
4. How do you calculate DNF and CNF
5. Understanding with Example
6. Converting DNF to CNF
7. Application/Uses of CNF and DNF
8. Conclusion

Introduction to CNF and DNF

CNF and DNF are basically Boolean functions which help in converting any logical expression in the form of conjunction or disjunction. The acronyms itself are quite self-explanatory i.e., conjunctive normal form(CNF) and Disjunctive normal form(DNF).

CNF and DNF are one of the important tools in discrete mathematics used to simplify various complex logical expressions in the case of Implication and negation statements.

CNF and DNF are important applications in the domain such as automated theorem proving and In circuit theory. It has also some vivid applications in designing some of the complicated electric circuits and also in hardware design.

In order to get a complete idea of these Normal forms we should first of all have look into

Definition

Conjunctive normal form (CNF) is an approach to Boolean logic that expresses formulas as conjunctions of clauses with an AND or OR. Each clause connected by a conjunction, or AND, must be either a literal or contain a disjunction, or OR operator.
Example :(P ∨ Q)∧ (P ∨ R)∧(Q ∨ ~S)
Disjunctive normal form (DNF) is an approach to Boolean logic that expresses formulas as Disjunctions of clauses with an OR. Each clause connected by a Disjunction, or OR, must be either a literal or contain a Conjunction, or AND operator.
Example :(P ∧ Q) ∨ (P ∧ R) ∨(Q ∧ ~S)

Some functions can be represented more briefly in DNF whereas others are represented more briefly in CNF, and switching between these representations can involve an exponential increase in size.

We can recall some well-known concepts. The set of variables are represented by Xn = {x1,...,xn}. Literals are variables and negated variables. Terms are conjunctions of literals. Clauses are disjunctions of literals. Terms and clauses don’t contain the same literal twice or a literal and its negative form. Every Boolean function f is represented as a conjunction of clauses,

si=1-∈Ci,--------- (1)

as well as a disjunction of terms,

-si=1∈Ti, --------- (2)

where Ti and Ci are sets of literals. The form 1 is usually referred as CNF and form 2 is referred to as DNF, But it would be historically accurate to call both of them as conjunctive and disjunctive form and use normal only when the set Ci and Ti have n literals on distinct variables. In short it is to ensure that normal forms are unique.

In computer science literature such a distinction isn’t made, we can use CNF and DNF while referring to expression 1 or 2 if there is no restriction imposed on the set “Ci” and “Ti”, and there is no guarantee of uniqueness.

Significance

All conjunction and disjunction of literals are CNF, as they are seen as disjunctions of one-literal clause and conjunction of a single clause, respectively. In disjunctive normal form i.e. DNF, the only propositional connectives can contain AND, OR, and NOT. The not operator is only used as part of a literal, it means it can only antecede a propositional variable or a predicate symbol

The Difference

CNF	DNF
It is converting Expression  to Conjunctive Normal Form	It is converting Expression  to Disjunctive Normal Form
CNF is ∧ of  ∨ , where ∧ is over variables or their negations (literals), an ∨ of literals is also called a clause	DNF is an ∨ of ∧ where ∧ of literals is called a term.

Some Basic Formulae we need to know before calculating CNF & DNF

~(~P)≡ P

~(A ∧ B) ≡ ~A ∨~B (D Morgan Laws)

~(A ∨ B) ≡~A ∧ ~B

A→B ≡ ~A ∨ B

A⇔ B ≡ (A→ B) ∧ (B →A) ≡ (~A ∨ B) ∧ (~B ∨ A)... using above formula

How do you calculate DNF and CNF?

Simply we can write down the truth table, which is quite simple to find, and deduce your CNF and DNF. If you want to find DNF, you need to look at all rows which end with T. When you find these rows, take x,y, and z values from each column. So that, you get (x∧y∧z)∨(x∧¬y∧¬z)∨(¬x∧y∧¬z)∨(¬x∧¬y∧z).

Understanding with Example:

Conjunctive Normal Form(CNF):

To convert a formula in CNF

First open the implications to get the ORs. Then get rid of double negations

Then convert

F ∨ (G ∧ H) to ( F ∨ G) ∧ (F ∧ H) //distributivity

For example:

Disjunctive normal forms (DNF):

A formula which is equivalent to a given formula and which consist of a sum of elementary product is called a disjunctive normal form of given formula

Example:

Conversion to DNF of Above CNF example

(P->Q) → R = => (~P V Q) → R

= => ~(~P V Q) V R

== > (P ∧ ~Q ) V R

Here we can see the above solution has converted into Disjunctive Normal form

Converting DNF to CNF

Application/Uses of CNF and DNF

Conclusion

Conjunctive Normal Form (CNF) and Disjunctive Normal Form(DNF) are two important concepts in logic theory having significant applications in Circuit building and Chip industry. CNF and DNF simplify the complex expressions containing implication and double implications into simple Conjunctive or disjunctive forms.