The conjunctive normal form is a way of expressing a formula in the
The conjunctive normal form states that a formula is in CNF if it is a conjunction of one or more than one clause, where each clause is a disjunction of literals. In other words, it is a product of sums where
Consider the first formula,
Remove the conditional symbol as per the rules explained in the first step:
Remove the double negation as mentioned in the second step:
Apply the De Morgans law that opens a negation as a whole:
Remove the double negation similar to the step we did before:
Apply the De Morgans law again:
Remove the double negation again:
Apply the distributive property over disjunction, which will lead to two clauses:
This is the final conjunction form of the formula. This is in the product of sums form.
Let's take another formula:
Remove all the occurrences of the conditional symbols:
Apply the distributive property over conjunction:
Apply the same property:
By the rules of disjunction,
Using the identity property for conjunction,
Finally, using the distributive property over conjunction:
Hence, the final conjunctive form.
Note: Both the final forms have a conjunctive symbol between the clauses, while a disjunctive symbol is used in the clauses.
Free Resources