In task 23, you need to count the number of solutions to a system of logical equations. The most obvious way is to make a list of all possible values of all variables, substitute the values into the system according to the list and check if there is a contradiction. If not, then add 1 solution to the answer.
This method is very time consuming. Another option is to make a tree of all possible values of all variables. Now you need to substitute the values of the variables not in the entire system, but in turn in each equation. So, after substituting all combinations of x1 and x2 into the first equation, pairs of values that, when substituting, give a contradiction, are excluded, automatically excluding the branch of combinations further in the tree, after which they do not need to be substituted. The number of non-excluded leaves in the tree will be the answer to the problem.
At the same height in the tree there are several identical values of pairs of variables (for example, in this tree there are 3 pairs of variables such that x3=1 and x4=0). In order not to substitute them several times, you must first make a separate tree for each equation, substitute the values of the variables there and exclude unnecessary pairs. Then, when compiling the main tree, it will only be necessary to transfer the result from the auxiliary trees to the main one. If the equations in the system are of the same type, that is, they differ only in variables (as in the example), then it is not necessary to draw a tree for each, since these trees will be identical.
The display method is the fastest and less voluminous way of solving many systems of logical equations. In it, instead of the main tree of possible values of all variables, a table of the number of possible values of all variables is built. In the tree, from all the same values of one variable, there are identical branches of the values of the following variables. In order not to redraw identical branches, you can "splice" them into one, at the same time, so that the number of solutions remains correct, we add to each vertex k - a coefficient equal to the number of "spliced" variables. In this case, the excluded variables do not need to be spliced, since they do not affect the answer. Table is "spliced" a tree containing the obtained coefficients in the cells.
When solving by the display method, the tree is not drawn, a table is immediately built, the coefficients of which are calculated using ""spliced" auxiliary trees" (hereinafter referred to as arrows). The value in the cell is equal to the sum of the values in the cells from which the arrow comes. Accordingly, in the first column, the value in the cells is equal to one. The sum of the values of the last column is the number of solutions of the system.
How to solve systems of logical equations using the mapping method?
1. Make arrows for different equations
2. Fill the table with arrows
3. Calculate the number of solutions of the system