Algorithm for constructing truth tables of logical expressions

Today in this paper, the construction of truth tables of logical expressions will be considered in detail. With this problem, there are often schoolchildren who pass a unified state exam in computer science. In fact, the so-called Boolean algebra is not complicated if one knows the necessary laws, operations, and rules for constructing truth tables. We will address these issues today.

Boolean algebra

The logic algebra is based on simple logical expressions that are linked together by operations, creating complex expressions. It should be noted that the Boolean algebra contains two binary operations: multiplication and addition (conjunction and disjunction, respectively); One unary is inversion. All simple expressions (elements of a complex logical expression) take one of two values: "1" or "0", "true" or "false", "+" or "-", respectively.

The algebra of logic is based on a few fairly simple axioms:

• Associativity;
• Commutativity;
• Absorption;
• Distributivity;
• Additionality.

If you know these laws and the order of execution of functions, the construction of truth tables of logical expressions will not cause any difficulties. Recall that operations must be performed in strict sequence: denial, multiplication, addition, consequence, equivalence, only then go to the operations of the Schiffer bar or the Pirs arrow. By the way, for the last two functions there is no rule of priority, execute them in the order in which they are located.

Rules for compiling a table

Building truth tables of logical expressions helps to solve many logical problems and find solutions to complex cumbersome examples. It is worth noting that there are some rules for their compilation.

In order to correctly create a logical table, you must first determine the number of rows. How to do it? Count the number of variables that make up the complex expression, and use the simple formula: A = 2 to the power of n. A is the number of rows in the truth table being compiled, n is the number of variables that enter the complex logical expression.

Example: a complex expression contains three variables (A, B, and C), so the deuce must be raised to the third power. In the compiled truth table we will have eight lines. Add one line for the title of the columns.

Next, we turn to our expression and determine the order of the actions to be performed. It's better to mark the order with a pencil (one, two, and so on).

The next step is to count the number of operations. The resulting number is the number of columns in our table. Be sure to add as many columns as there are variables in your expression, to populate possible combinations of variables.

Then fill out the header of our table. Below you see an example of this.

Now go on to fill out the possible combinations. For two variables they will be the following: 00, 01, 10, 11. For three variables: 000, 001, 010, 011, 100, 101, 110, 111.

After all the above points are fulfilled, you can proceed to calculate and fill the remaining cells of the resulting table.

Example

Now we consider an example of constructing a truth table of a logical expression: inversion A + B * A.

1. Counting variables: 2. Number of lines: 4 + 1 = 5.
2. The order of the actions: the first inversion, the second conjunction, the third disjunction.
3. Number of columns: 3 + 2 = 5.
4. We begin to draw and fill the table.

As a rule, the task sounds like this: "how many combinations satisfy the condition F = 0" or "in what combinations F = 1". On the first question the answer is 1, on the second - 00, 01, 11.

Carefully read the assignment that you are given. You can correctly solve the problem, but make a mistake in writing the answer. Once again, we draw your attention to the order of the actions:

• negation;
• multiplication;
• addition.

A task

Building a truth table can help to find the answer to a difficult logical problem. To trace the process of compiling an expression and a truth table by the condition of a logical task, you can in this section of the article.

Given four values of the number A: 1) 7, 2) 6, 3) 5, 4) 4. For which of them is the saying "inversion (A less than 6) + (A less than 5)" is false?

Our first column will be filled with the values 7, 6, 5, 4 in this sequence. In the next column, we must answer the question: "And less than 6?" The third column is filled in the same way, only now we answer the question: "And less than 5?"

Determine the sequence of operations. We remember that denial takes precedence over disjunction. Hence, we fill the next column with values that correspond to the condition not (A is less than 6). The fourth will answer the main question of our task. Below you can see an example of filling a table.

Please note that we have answer numbers, the false expression will be at A = 5, this is the third answer.