Question

Converting cnf to gnf in bollean algebra

Answer 1

Step 1

Find all the cases that makes the function to be false. In our case we can just find all the truth of that formula:

x⊕y⊕z⊕ax⊕y⊕z⊕a

I will write it down from left to write, from xx - aa, 1 for true 0 for false.

0 0 0 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0

Those will be the false cases for the main formula.

Step 2

Now to get the CNF all what you have to do is to write them down with not. Because all the laterals connected with or signs, if we didn't wrote it down it will be true. So this is the CNF for that expression.

(¬x∨¬y∨¬z∨a)(¬x∨¬y∨¬z∨a)

(¬x∨¬y∨z∨¬a)(¬x∨¬y∨z∨¬a)

(¬x∨y∨¬z∨¬a)(¬x∨y∨¬z∨¬a)

(¬x∨y∨z∨a)(¬x∨y∨z∨a)

(x∨¬y∨¬z∨¬a)(x∨¬y∨¬z∨¬a)

(x∨¬y∨z∨a)(x∨¬y∨z∨a)

(x∨y∨z∨¬a)(x∨y∨z∨¬a)

In general this trick will work if all the variables appear in all the clauses