Normal Forms
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. We consider an alternate procedure known as the reduction to normal forms.
There are two such forms:
- Disjunctive Normal Form (DNF)
- Conjunctive Normal Form
Disjunctive Normal Form (DNF): If p, q are two statements, then “p or q” is a compound statement, denoted by p ∨ q and referred as the disjunction of p and q. The disjunction of p and q is true whenever at least one of the two statements is true, and it is false only when both p and q are false
| p | q | p ∨ q |
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Example: – if p is “4 is a positive integer” and q is “√5 is a rational number”, then p ∨ q is true as statement p is true, although statement q is false.
Conjunctive Normal Form: If p, q are two statements, then “p and q” is a compound statement, denoted by p ∧ q and referred as the conjunction of p and q. The conjunction of p and q is true only when both p and q are true, otherwise, it is false
| p | q | p ∧ q |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Example: if statement p is “6<7” and statement q is “-3>-4” then the conjunction of p and q is true as both p and q are true statements.