The algorithm for constructing truth tables of logical expressions

Today in this paper we will consider in detail the question of constructing truth tables of logical expressions. Schoolchildren who pass a unified state exam in computer science often encounter this problem. In fact, the so-called Boolean algebra is not complicated if you know the necessary laws, operations and rules for constructing truth tables. Today we will deal with these issues.

Boolean Algebra

The logic algebra is based on simple logical expressions that are interconnected by operations, while creating complex expressions. It should be noted that 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 logic algebra is based on several fairly simple axioms:

• associativity;
• commutativity;
• absorption;
• distributivity;
• complementarity.

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

Table compilation rules

The construction of truth tables of logical expressions helps to solve many logical problems and find a solution to complex cumbersome examples. It is worth noting that there are some rules for their preparation.

In order to correctly compile 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 a simple formula: A = 2 to the power of n. A is the number of rows in the compiled truth table, n is the number of variables that enter a complex logical expression.

Example: a complex expression contains three variables (A, B and C), which means that the two must be raised to the third power. In the compiled truth table, we will have eight rows. Add one line for the column headings.

Next, we turn to our expression and determine the order of the actions to be performed. It is better for yourself 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 the number of variables in your expression to fill in possible combinations of variables.

Next, fill in the header of our table. Below you see an example of this.

Now move on to filling 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 completing all of the above items, you can proceed to the calculation and filling in the remaining cells of the resulting table.

Example

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

1. Counting variables: 2. Number of rows: 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 out the table.

As a rule, the task sounds like this: “how many combinations satisfy the condition F = 0” or “in which combinations F = 1”. The answer to the first question is 1, to the second - 00, 01, 11.

Read the assignment given to you carefully. 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.

Task

Building a truth table can help find the answer to a difficult logical problem. You can follow the process of compiling an expression and a truth table according to the condition of a logical task in this section of the article.

Four values ​​of the number A are given: 1) 7, 2) 6, 3) 5, 4) 4. For which of them is the statement “inversion (A less than 6) + (A less than 5)” false?

Our first column will be filled with the values ​​7, 6, 5, 4 necessarily in this sequence. In the next column, we must answer the question: "Is less than 6?" We fill the third column in the same way, only now we answer the question: "Is it less than 5?"

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

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