Conjunctive normal form(CNF) and Disjunctive normal form(DNF) from Truth Table, Explained!

Finding DNF(Disjunctive Normal Form) and CNF(Conjunctive Normal Form) from a given truth table is a very easy task. If you don’t know, just Google, you will find tons of web pages explaining the method. But have you ever thought about the reasons for following those steps.

When I was learning about these forms, that was a problem for me. I could understand the reasons. I will give you an abstract idea about what is happening.

This method is about finding a logical( or boolean in boolean algebra) expression using a truth table. I will explain the method using an example from here.

This is the truth table.

First, let’s consider DNF.

In this case, usually what you have to do is you look at the rows that ends with T and when you find those rows, take the x and y from each respective column. Thus you get,

Here is the explanation. Actually what you are doing here is you write a logical expression that become True for 1,4,6 and 7 lines and False for other lines. If you consider the first elementary product of the answer (DNF is a sum of elementary products) you can see it becomes true when x,y,z take row by values, and these x,y,z values can’t make any other elementary product True since every row has discrete x,y,z values. (Since we are taking product of x,y,z values, only the values in the first row make that elementary product true).

Same thing happens with the second elementary product. Now x stays as x since it gets the value True. But y and z values should face not operation since you want the True values for the elementary product to become true. Likewise you write elementary products that only get the value True for their related rows in the table. But if you checked carefully, you will see none of other rows can make at least one of these elementary product true. Since that, when you get the sum of these elementary products, you will get a result that become True only for 1,4,6 and 7 lines ; which means you have a logical expression for the given Truth table, but in the Disjunctive Normal Form.

Now let’s move on to the CNF,

In this case, I’m going to write a logical expression that becomes False only for values of 2,3,5 and 8 rows of the truth table. Since you have to make a expression False connect some compound prepositions eg. (~x∨~y∨z), you should use conjunction (∧) to connect them, since if you use disjunction (∨) , whole expression will become True when a single compound preposition became True.

When you are building compound prepositions for expression, you can select either disjunction or conjunction. Look at the above paragraph again, I highlighted the word ‘only’. I wanted to emphasize you that the expression should become True for 1,4,6,7 rows. For this, you should use disjunction to connect prepositions in the compound preposition. (If you looked carefully, I will see at least one preposition in from all the compound preposition become true for values 1,4,6 and 7 rows. Finally you will get this for the above truth table.

There is another way that you can use to write the CNF. Do this as an exercise.

• Replace all the True values with False values and all the False values with True values in the last column.
• Write the DNF for the moderated truth table.

Now you have a logical expression that gives opposite value for every row. (Please remember, this expression is not equal to the expression you got from DNF above, since you selected 1,4,6 and 7 rows)

• Since you get the opposite value for  every single row, take the negation (~, not) of the whole expression.
• Simplify the expression using De Morgan’s laws.
• You will end up with the CNF of the truth table.

Here is something interesting you can prove using the same concept (Not the way we used in the exercise) that we used to form the CNF.

Prove that any complex number can be written as the next term of the sequence 2,4,6,8.

Write your answer in the comment section

I hope you learned something from this article. ✌

– Praveen Dinelka