Normal Forms in Discrete Mathematics for UGC NET Computer Science notes

 Hi Everyone,

Welcome to My blog,

In this post let us understand normal forms in discrete mathematics

Introduction:

• In Discrete Mathematics,we often deal with complex logical expressions.
• A complex logical expression contains more than one logical operator and may include implication and biconditional.
• So these expressions can be converted into standard form using normal Form.

What is Normal form?

Normal form is used to convert complex logical expressions  into a standard form.

Which operators used in Normal form?

Normal form uses AND,OR,NOT operators to represent logical expressions in a standard form.

Definition:

A normal form is a standard way of representing logical expressions using only AND,OR,NOT operators.

Types of  Normal forms:

• Conjunctive Normal Form(CNF)
• Disjunctive Normal Form(DNF)

Conjunctive Normal Form:

  

CNF is obtained by connecting clauses using AND and each clause contains literals connected using OR.

• Literals-single variable
• Clause-literals joined by OR
• CNF-Clauses joined by AND

For example:

(A∨B)∧(¬B∨C)

It is Conjunctive Normal Form

Disjunctive Normal Form

DNF is obtained by connecting clauses using OR and each clause contains literals connected using AND

• Literals-single variable
• Clause-literals joined by AND
• DNF-Clauses joined by OR

For example:

(A∧B)∨(¬B∧C) 

It is Disjunctive Normal Form

Steps to convert into a normal form

Step 1: Remove implication (→) and biconditional (↔)

Replace

P → Q = ¬P ∨ Q

P ↔ Q = (P → Q) ∧ (Q → P)

Step 2: Move NOT (¬) inside using De Morgan’s Laws

¬(A ∧ B) = ¬A ∨ ¬B

¬(A ∨ B) = ¬A ∧ ¬B

¬(¬A) = A

Step 3: Decide the target form

CNF → AND (∧) outside

DNF → OR (∨) outside

Step 4: Apply Distributive Law

For CNF:

A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C)

For DNF:

A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)

Conclusion:

I hope this post helps you to understand normal forms in discrete mathematics in a simple way.