How to bring the formula to the form of CNF?

Question

Java

The task is given to bring the formula to the form of CNF. From the point of view of Boolean algebra, there are no questions, everything is logical and clear, but with bringing this task into the plane of implementation on any PL, questions arise. Google gives the results to the truth tables as a solution, and in the task it is necessary to display the formula reduced to the form of CNF. Maybe someone will throw some solutions. I've been tormenting Google for a week now, but I can't find solutions at least close to the required task.
PS: you do not need to offer Google to help. Thank you! Thank you very much in advance.

Answer 1

Have you learned how to calculate the value of a formula for given values ​​of variables? If yes, you go through all the sets of values ​​(a_1,...,a_n) (there are only 2 ^ n), count the value of the formula for each, and if it turns out 0, add another disjunction to the formula ((x_1 xor a_1) or (x_2 xor a_2) or ... or (x_n xor a_n)).

Answer 2

CNF is built on the truth table by a simple pass through the rows of the table. So the task is reduced to finding the truth table. You can build a truth table in two ways: 1. Bring the formula to a form containing only disjunctions and conjunctions - then simply calculate. 2. Write an analysis of the formula: for example, building a tree according to the formula and then calculating the value of the expression. You can see examples of solving a problem with an arithmetic calculator and change it a little. Was it by chance that there were conditions, what kind of incoming formulas could be? This could simplify the construction

Answer 3

It seems to me that you simply do not understand what CNF is.
Let's say we have a Boolean function f. It depends on n variables x1, x2, ..., xn. Variables can be made 2^n different substitutions. On some substitutions, the function returns 1, on others - 0. We want to encode this somehow with a Boolean formula.
There are two typical ways to do this. The first is to describe all substitutions that yield 1 -- DNF. The second is to describe all substitutions that give 0 -- CNF. We need a second one.
Let's look at KNF. It is a conjunction of disjunctions, like this:
(not x1 or x2) and (x1 or not x2 or x3).
What is written in brackets can be rewritten a little more clearly:
(x1 = 0 or x2 = 1) and (x1 = 1 or x2 = 0 or x3 = 1).
Now, we can use logic, mathematical =), and rewrite again:
(not (x1 = 1 and x2 = 0)) and (not (x1 = 0 and x2 = 1 and x3 = 0)).
What does the last formula say? That the function returns one if the substitution does not contain a pattern (x1 = 1 and x2 = 0) or (x1 = 0 and x2 = 1 and x3 = 0).
In total, we go through all the substitutions for which the function gives 0, write such substitutions into forbidden patterns, and then simply write them into CNF, as I described above.