What is called the truth table of a logical function. The problem of synthesizing logic circuits in a Boolean basis

7. Logical expressions, truth tables of logical expressions.

1.4 Construction of logic circuits

Glossary, definitions of logic

Logical operations and truth tables

Order of logical operations in a complex logical expression

Logical expressions. Each compound statement can be expressed in the form of a formula (logical expression), which includes logical variables, denoting statements, and signs of logical operations, denoting logical functions.

To write a compound statement in the form of a logical expression in a formal language (the language of logical algebra), in the compound statement it is necessary to select simple statements and logical connections between them.

Let us write in the form of a logical expression the compound statement “(2 - 2 = 5 or 2-2 = 4) and (2 2 ≠ 5 or 2-2 ≠ 4)". Let's analyze the compound statement. It contains two simple statements:

A ="2 2 = 5" - false (0),

B = “2 2 = 4 >> - true (1).

Then the compound statement can be written in the following form:

"(A or IN) And (⌐A or (⌐ IN)".

Now you need to write the statement in the form of a logical expression, taking into account the sequence of logical operations. When performing logical operations, the following order of their execution is defined: inversion, conjunction, disjunction. Parentheses can be used to change the specified order:

F = (A v IN) & (⌐ A v ⌐ IN).

The truth or falsity of compound statements can be determined purely formally, guided by the laws of propositional algebra, without referring to the semantic content of the statements.

Let's substitute in logical expression values of logical variables and, using the truth tables of basic logical operations, we obtain the value of the logical function:

F = (AvB)&(⌐ Av⌐ B) = (0v1)&(1v0) = 1 & 1 = 1 .

Truth tables. For each compound statement (logical expression), it is possible to construct a truth table that determines its truth or falsity for all possible combinations of the initial values of simple statements (logical variables).

When constructing truth tables, it is advisable to be guided by a certain sequence of actions.

First, you need to determine the number of rows in the truth table. It is equal to the number of possible combinations of logical variable values included in a logical expression. If the number of logical variables is equal n, That:

number of lines = 2 n .

In our case, the logical function F = (AvB)&(⌐ Av⌐ B) has 2 variables and therefore the number of rows in the truth table must be 4.

Secondly, it is necessary to determine the number of columns in the truth table, which is equal to the number of logical variables plus the number of logical operations.

In our case, the number of variables is two, and the number of logical operations is five, that is, the number of columns of the truth table is seven.

Thirdly, it is necessary to construct a truth table with the specified number of rows and columns, designate the columns and enter into the table possible sets of values of the original logical variables.

Fourth, it is necessary to fill out the truth table by column, performing basic logical operations in the required sequence and in accordance with their truth tables (Table 4.4). We can now determine the value of a Boolean function for any set of Boolean variable values.

Table 4.4. Logic function truth table

F=(AvB)&(⌐ Av⌐ B)

Equivalent logical expressions. Logical expressions for which the last columns of the truth tables coincide are called equivalent. To denote equivalent logical expressions, the “=” sign is used.

Let us prove that logical expressions ⌐A &⌐B And ⌐(AvB) are equivalent. Let's first build a truth table for the logical expression ⌐A &⌐B(Table 4.5).

Table 4.5. Logical Expression Truth Table ⌐A& ⌐B

				⌐A&⌐ IN

Now let's build a truth table for a logical expression ⌐(AvB) (Table 4.6).

Table 4.6. Logical Expression Truth Table ⌐(AvB)

			⌐(AvB)

The values in the last columns of the truth tables are the same, therefore, the logical expressions are equivalent:

⌐A & ⌐B = ⌐(AvB).

And, which will be enough for you to solve complex logical expressions. We will also look at the order in which these logical operations are performed in complex logical expressions and present truth tables for each logical operation. We advise you to use our programs for solving problems in mathematics, and. In addition to a large number of programs for solving problems, the site runs , where you can always ask a question and where you can always be helped with solving problems. Use our services for your health!

Statement is a declarative sentence about which one can definitely say whether it is true or false (true (logical 1), false (logical 0)).

Logical operations- mental actions, the result of which is a change in the content or scope of concepts, as well as the formation of new concepts.

Boolean expression- an oral statement or recording, which, along with constant quantities, necessarily includes variable quantities (objects). Depending on the values of these variables (objects), a logical expression can take one of two possible values: true (logical 1) or false (logical 0).

Complex logical expression- a logical expression consisting of one or more simple logical expressions (or complex logical expressions) connected using logical operations.

1) Logical multiplication or conjunction:

A conjunction is a complex logical expression that is true if and only if both simple expressions are true, in all other cases this folded expression is false.
Designation: F = A & B.

Truth table for conjunction

3) Logical negation or inversion:

Inversion is a complex logical expression, if the original logical expression is true, then the result of negation will be false, and vice versa, if the original logical expression is false, then the result of negation will be true. In other simple words, this operation means that the particle NOT or the word NOT TRUE WHAT is added to the original logical expression.

Truth table for inversion

5) Logical equivalence or equivalence:

Equivalence is a complex logical expression that is true if and only if both simple logical expressions have the same truth.

Truth table for equivalence

A	B	F
1	1	1
1	0	0
0	1	0
0	0	1

1. Inversion;
2. Conjunction;
3. Disjunction;
4. Implication;
5. Equivalence.

Parentheses are used to change the specified order of logical operations.

Task 1 #10050

\((x \wedge y) \vee (x \wedge \overline y) \vee (y\wedge z) \vee (z \wedge x)\)

Make a truth table for it. As an answer, enter the number of tuples \((x,\) \(y,\) \(z),\) for which the function is equal to 1.

1. Let's simplify \((x \wedge y) \vee (x \wedge \overline y).\)

According to the law of distributivity \((y \wedge x) \vee (x \wedge \overline y)\) = \(x \wedge (y \vee \overline y).\)\(y \vee \overline y = 1\) (if \(y = 0,\) then \(\overline y \vee y = 1 \vee 0 = 1,\) if \(y = 1,\) then \(\overline y \vee y = 0 \vee 1 = 1).\) Then \(x \wedge (y \vee \overline y) = x \wedge 1 = x .\)

2. Let's simplify \((y\wedge z) \vee (z \wedge x).\) According to the law of distributivity \((y\wedge z) \vee (z \wedge x) = z \wedge (y \vee x).\)

3. We get: \((x \wedge y) \vee (x \wedge \overline y) \vee (y\wedge z) \vee (z \wedge x) = x \vee z \wedge (y \vee x).\)

4. The truth table contains 8 lines (lines are always \(2^n,\) where \(n\) is the number of variables). In our case there are 3 variables.

5. Fill in the truth table.

\[\begin(array)(|c|c|c|c|c|c|c|) \hline x & y & z & y \vee x & z \wedge (y \vee x) & F = x \vee z \wedge (y \vee x) \\ \hline 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 0 & 0 & 1 & 0 & 0 & 0 \\ \hline 0 & 1 & 0 & 1 & 0 & 0 \\ \hline 0 & 1 & 1 & 1 & 1 & 1 \\ \hline 1 & 0 & 0 & 1 & 0 & 1 \\ \hline 1 & 0 & 1 & 1 & 1 & 1 \\ \hline 1 & 1 & 0 & 1 & 0 & 1 \\ \hline 1 & 1 & 1 & 1 & 1 & 1 \\ \hline \end(array)\]

Since the disjunction \(x \vee z \wedge (y \vee x)\) is true if at least one of the statements included in it is true, then for \(x = 1\) \(F = 1\) for any \(y\) and \(z\) (lines 5-8 in the truth table ).

Consider the case when \(x = 0.\) Then the value of the function will depend on the value of \(z \wedge (y \vee x).\) If \(z \wedge (y \vee x)\) is true, then and \(F\) is true, if false, then \(F\) is false. Consider the case when \(F = 1.\) The conjunction \((z \wedge (y \vee x))\) is true if all the statements included in it are true, that is, \(y \vee x = 1\) and \(z = 1.\) \(x = 0,\) means \(y \vee x = 1,\) when \(y = 1\) (line 4).

If one of the statements included in the conjunction is false, then the entire conjunction is false. If \(x = 0\) and \(y = 0,\) then \(y \vee x = 0.\) Then \(z \wedge (x \vee y) = 0\) for any \(z \) (lines 1-2). Since \(x = 0,\) and the second statement included in the disjunction \((z \wedge (x \vee y)),\) is also false, then the whole function is false. If \(x = 0\) and \(y = 1,\) then \(y \vee x = 1.\) If \(z = 0,\) \(z \wedge (y \vee x) = 0.\) Then \(F = 0\) (line 3). The case when \(z = 1,\) \(y = 1,\) \(x = 0,\) was considered in the previous paragraph.

We have built a truth table. We see that there are 5 sets in it, for which \(F = 1.\) Therefore, the answer is: 5.

Answer: 5

Task 2 #10051

The logical function \(F\) is given by the expression:

\((x \wedge \overline y \wedge z) \vee (x \rightarrow y)\)

Make a truth table for it. As an answer, enter the number of tuples \((x,\) \(y,\) \(z),\) for which the function is equal to 0.

\[\begin(array)(|c|c|c|c|c|c|c|c|c|) \hline x & y & z & \overline y & x\wedge \overline y & x \wedge \overline y \wedge z & \overline x & \overline x \vee y & x \wedge \overline y \wedge z \vee \overline x \vee y \\ \hline 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ \hline 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ \hline 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ \hline 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1\\ \hline 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0\\ \hline 1 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 1\\ \hline 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1\\ \hline 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1\\ \hline \end(array)\]

1. \(x \rightarrow y\) = \(\overline x \vee y.\)

2. Note that for \(y = 1\) \(F = 1,\) since the disjunction is true if at least one expression included in it is true (lines 3-4, 7-8 in the truth table). Similarly for \(\overline x = 1,\) that is, for \(x = 0,\) \(F = 1\) (lines 1-4).

3. For \(x = 1\) and \(y = 0\) \(\overline x \vee y = 0,\) \(x \wedge \overline y = 1.\) For \(z = 1 \) \(x \wedge \overline y \wedge z = 1\) and \(F = 1,\) since one of the expressions is true (line 6), and for \(z = 0\) \(x \wedge \overline y \wedge z = 0\) and \(F = 0,\) since both expressions included in the disjunction are false (line 5).

From the constructed truth table we see that for one set \((x,\) \(y,\) \(z)\) \(F = 0.\)

Answer: 1

Task 3 #10052

The logical function \(F\) is given by the expression:

\((\overline(z \vee \overline y)) \vee (w \wedge (z \equiv y)) \)

Make a truth table for it. As an answer, enter the sum of the values \(z,\) \(y\) and \(w,\) for which \(F = 1.\)

\[\begin(array)(|c|c|c|c|c|c|c|c|c|) \hline w & y & z & \overline y & z \vee \overline y & \overline( z \vee \overline y) & z \equiv y & w \wedge (z \equiv y) & \overline z \vee \overline y \vee w \wedge (z \equiv y) \\ \hline 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ \hline 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ \hline 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ \hline 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ \hline 1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1 \\ \ hline 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ \hline 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ \hline 1 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \\ \hline \end(array)\]

1. \((\overline(z \vee \overline y)) = \overline z \wedge y \)

2. There will be \(2^3 = 8\) rows in the truth table.

3. If \(z = 1\) and \(y = 1,\) \(then (z \equiv y) = 1\) (since equivalence is true if and only if both statements are simultaneously false or true) . \(\overline z \wedge y = 0\) \((0 \wedge 1 = 0).\) If \(w = 1,\) \(w \wedge (z \equiv y) = 1\) \ ((1 \wedge 1 = 1)\) and \(F = 1,\) since the disjunction is true if at least one of the statements included in it is true (line 8 in the truth table). If \(w = 0,\) \(w \wedge (z \equiv y) = 0\) \((0 \wedge 1 = 0)\) and \(F = 0,\) since both statements, those included in the disjunction are false (line 4).

4. Similarly for \(z = 0, y = 0.\) \((z \equiv y) = 1,\) \(\overline z \wedge y = 0\) \((1 \wedge 0 = 0 ).\) Then again the value of the function will depend on \(w.\) For \(w = 1\) \(w \wedge (z \equiv y) = 1,\)\(F = 1,\) since one of the statements included in the disjunction is true (line 5), and for \(w = 0\) \(w \wedge (z \equiv y) = 0,\)\(F = 0,\) since all statements are false (line 1).

5. If \(z = 0\) and \(y = 1,\) then \(\overline z \wedge y = 1\) \((1 \wedge 1 = 1).\) Since \(( z \equiv y) = 0\) (after all, the values \(z\) and \(y\) are different), will be false for any \(w.\) Then, since the value of the variable \(w\) will not influence on the value of the function, with \(z = 0\) and \(y = 1\) \(w\) can be either 0 or 1. \(F = 1,\) since one of the statements included in disjunction, true (lines 3, 7).

6. If \(z = 1\) and \(y = 0,\) then \(\overline z \wedge y = 0 \wedge 0 = 0.\) Since \((z \equiv y) = 0,\) \(w \wedge (z \equiv y) = w \wedge 0\) will be false for any \(w\) (that is, \(w\) can be both 0 and 1). This means that for \(z = 1\) and \(y = 0\) \(F\) will always be false (since both statements included in the disjunction are false, lines 2, 5).

7. \(F = 1\) for the following sets \(z,\) \(y,\) \(w:\) (0, 0, 1), (0, 1, 1), (1, 1 , 1), (0, 1, 0). If we sum the values, we get 7.

Answer: 7

Task 4 #10053

The logical function \(F\) is given by the expression:

\(a \wedge ((\overline(b \wedge c)) \vee (a \wedge \overline b) \vee (\overline c \wedge a)) \)

Make a truth table for it. As an answer, enter the sum of the values \(a,\) \(b\) and \(c,\) for which \(F = 1.\)

\[\begin(array)(|c|c|c|c|) \hline a & b & c & F\\\hline 0 & 0 & 0 & 0 \\ \hline 0 & 0 & 1 & 0 \ \\hline 0 & 1 & 0 & 0 \\ \hline 0 & 1 & 1 & 0 \\ \hline 1 & 0 & 0 & 1 \\ \hline 1 & 0 & 1 & 1 \\ \hline 1 & 1 & 0 & 1 \\ \hline 1 & 1 & 1 & 0 \\ \hline \end(array)\]

1. There are \(2^3 = 8\) rows in the truth table.

2. For \(a = 0\) \(F = 0\) for any values of \(b\) and \(c,\) since the conjunction is true if and only if all the statements included in it are true (lines 1-4 in the truth table).

3. Consider cases when \(a = 1.\) If \(\overline ((b \wedge c)) \vee (a \wedge \overline b) \vee (\overline c \wedge a) = 1,\) then \(F = 1\) (since both statements will be true), otherwise \(F = 0\) (since one statement will be false). According to De Morgan's law \(\overline(b \wedge c) = \overline b \vee \overline c.\) Then, given that \(a = 1,\) \(\overline ((b \wedge c)) \vee (a \wedge \overline b) \vee (\overline c \wedge a) = \overline b \vee \overline c \vee \overline b \vee \overline c = \overline b \vee \overline c.\)

4. If \(\overline b = 0\) and \(\overline c = 0\) (simultaneously, that is, for \(b = 1\) and \(c = 1),\) then \(\overline b \vee \overline c = 0\) and \(F = 0\) (line 8). In other cases \(\overline b \vee \overline c = 1\) and \(F = 1\) (lines 5-7).

5. Sets \((x,\) \(y,\) \(z),\) for which \(F = 1:\) (1, 0, 0), (1, 1, 0), ( 1, 0, 1). The sum of the values is 5.

Answer: 5

Task 5 #10054

The logical function \(F\) is given by the expression:

\(((a \wedge b) \vee (b \wedge c)) \equiv ((d \rightarrow a) \vee (b \wedge \overline c)) \)

Create a truth table. As an answer, enter the sum of the values \(a,\) for which \(F = 0.\)

\[\begin(array)(|c|c|c|c|c|) \hline a & b & c & d & F\\\hline 0 & 0 & 0 & 0 & 0 \\ \hline 0 & 0 & 0 & 1 & 1 \\ \hline 0 & 0 & 1 & 1 & 1 \\ \hline 0 & 1 & 1 & 1 & 0 \\ \hline 1 & 0 & 0 & 0 & 0 \\ \hline 1 & 1 & 0 & 0 & 1 \\ \hline 1 & 1 & 1 & 0 & 1 \\ \hline 1 & 1 & 1 & 1 & 1 \\ \hline 0 & 1 & 0 & 0 & 0 \\ \hline 0 & 0 & 1 & 0 & 0 \\ \hline 1 & 1 & 0 & 1 & 1 \\ \hline 1 & 0 & 1 & 0 & 0 \\ \hline 1 & 0 & 0 & 1 & 0 \\ \hline 0 & 1 & 1 & 0 & 1 \\ \hline 1 & 0 & 1 & 1 & 0 \\ \hline 0 & 1 & 0 & 1 & 0 \\ \hline \end(array)\]

1. According to the law of distributivity \((a \wedge b) \vee (b \wedge c) = b \wedge (a \vee c).\)

2. \(d \rightarrow a = \overline d \vee a.\)

3. \(((a \wedge b) \vee (b \wedge c)) \equiv ((d \rightarrow a) \vee (b \wedge \overline c)) = b \wedge (a \vee c) \equiv (\overline d \vee a \vee (b \wedge \overline c)).\)

4. If \(b = 0,\) then the left side of the function is equal to 0 \((0 \wedge (a \vee c) = 0).\) \(b \wedge \overline c = 0 \wedge \overline c = 0.\) This means that for \(b = 0\) \(c\) can be anything, since it does not affect the value of the function. \(F = 1,\) if \(\overline d \vee a = 0\) (then one of the expressions included in the disjunction will be true). This holds for \(\overline d = 0\) \((d = 1)\) and \(a = 0\) (lines 2, 3). For other \(d\) and \(a\) \(\overline d \vee a = 0,\) means \(F = 0,\) since the equivalence operation is true if and only if both statements are simultaneously true or false (lines 1, 10 in the truth table).

5. If \(b = 1,\) then \(b \wedge (a \vee c) = 1 \wedge (a \vee c) = a \vee c.\) \(b \wedge \overline c = 1 \wedge \overline c = \overline c.\) Then we have that \(a \vee c \equiv \overline d \vee a \vee \overline c.\) If \(a = 1,\) then \(a \vee c = 1\) and \(\overline d \vee a \vee \overline c = 1,\) since the disjunction is true if at least one of the expressions is true (and in both disjunctions there is \(a = 1).\) Then, if \(b = 1\) and \(a = 1,\) \(F = 1\) for any \(c\) and \(d\) (lines 5, 7, 8, 11).

If \(a = 0,\) then \(a \vee c = 0 \vee c = c,\) a \(\overline d \vee a \vee \overline c = \overline d \vee \overline c.\) We have: \(c \equiv (\overline d \vee \overline c).\) For \(c = 1\) \(1 \equiv \overline d.\) For \(d = 1\) \(F = 0,\) since the statements are different (line 4), for \(d = 0 \) \(F = 1,\) since both statements are true (line 14). When \(c = 0\) \(0 \equiv (\overline d \vee 1).\) Since \(\overline d \vee 1\) is a disjunction in which one of the statements is true, then the entire disjunction is true. Then \(0 \equiv 1,\) which is false, means \(F = 0\) for any \(d\) (line 9, 16).

From the constructed table we see that \(F = 0\) for \(a = 0\) (lines 1, 4, 9, 10, 16) and for \(a = 1\) (lines 6, 12, 13, 15). Then the sum of the values is 0 * 5 + 1 * 4 = 4.

Answer: 4

Task 6 #10055

The logical function \(F\) is given by the expression:

\((a \equiv (b \vee \overline c)) \rightarrow (c \wedge (b \vee a)) \)

Create a truth table. As an answer, enter the sum of the values \(c,\) for which \(F = 1.\)

\[\begin(array)(|c|c|c|c|) \hline a & b & c & F\\\hline 0 & 0 & 0 & 1 \\ \hline 0 & 0 & 1 & 0 \ \\hline 0 & 1 & 1 & 1 \\ \hline 0 & 1 & 0 & 1 \\ \hline 1 & 0 & 0 & 0 \\ \hline 1 & 1 & 0 & 0 \\ \hline 1 & 1 & 1 & 1 \\ \hline 1 & 0 & 1 & 1 \\ \hline \end(array)\]

The table has \(2^3 = 8\) rows.

1. An implication is false if and only if true statement false follows. This means \(F = 0,\) if a \(c \wedge (b \vee a) = 0.\) In other cases \(F = 1.\) Let us consider at what values \(a,\) \(b\) and \(c\) \(a \equiv (b \vee \overline c) = 1\)(If \(a \equiv (b \vee \overline c) = 0,\) then \(F = 1\) for any value of \(c \wedge (b \vee a) = 0).\)

If \(a = 0,\) then so that \(a \equiv (b \vee \overline c) = 1,\) necessary \(b \vee \overline c = 0\) (after all, the equivalence operation is true if and only if both statements are true or both are false). For the disjunction \((b \vee \overline c)\) to be false, both statements included in it must be false, that is, \(b = 0\) and \(\overline c = 0\) \(( c = 1).\) For such values \(c \wedge (b \vee a) = 1 \wedge (0 \vee 0) = 0.\) Then \((a \equiv (b \vee \overline c)) \rightarrow (c \wedge (b \vee a)) = 1 \rightarrow 0 = 0,\)\(F = 0.\) This corresponds to row 2 of the truth table.

If \(a = 1,\) then so that \(a \equiv (b \vee \overline c) = 1,\)\(b \vee \overline c = 1.\) This works in several cases. If \(b = 1,\) then \(c\) can be equal to both zero and one, because one of the statements included in the disjunction is already true. When \(c = 1\) \(c \wedge (b \vee a) = 1 \wedge 1 = 1,\) then \(F = 1\) (since \(1 \rightarrow 1 = 1,\) line 7). When \(c = 0\) \(c \wedge (b \vee a) = 0 \wedge 1 = 0,\) that means \(F = 0\) \((1 \rightarrow 0 = 0,\) line 6). If \(b = 0,\) then \(\overline c = 1\) \((c = 0,\) then one of the statements included in the disjunction will be true). In this case \(c \wedge (b \vee a) = 0 \wedge (0 \vee 1) = 0.\)\(F = 0,\) since \(1 \rightarrow 0 = 0\) (line 5).

2. For other values of \(a,\) \(b\) and \(c\) \(F = 1,\) because \(a \equiv (b \vee \overline c) = 0\)(lines 1, 3, 7, 8).

3. From the compiled truth table we see that \(F = 1\) for \(c = 0\) (lines 1, 4) and for \(c = 1\) (lines 3, 7, 8). The sum of the values is 0 * 2 + 1 * 3 = 3.\(2^4 = 16\) rows.

1. Since the conjunction is false if at least one of the statements is false, then for \(d = 0\) \(F = 0\) for any \(a,\) \(b\) and \(c\) (lines 1, 6-10, 12, 14 in the truth table).

2. Consider the case when \(d = 1.\) Then \((a \rightarrow b) \wedge (b \equiv c) \wedge d = (a \rightarrow b) \wedge (b \equiv c) \wedge 1 = (a \rightarrow b) \wedge (b \equiv c).\) When \(b = 1\) \(a \rightarrow b = a \rightarrow 1 = 1\) for any \(a,\) since the implication is false if and only if a false statement follows from a true statement. If \(c = 1,\) then \(b \equiv c = 1,\) since the equivalence operation is true when both expressions are true or both are false, and \(F = 1\) (since all expressions included into conjunction, are true). This corresponds to lines 4 and 5. If \(c = 0,\) then \(b \equiv c = 0,\) \(F = 0,\) since one of the expressions included in the conjunction is false (lines 11 and 16).

For \(b = 0:\) if \(a = 1,\) then \(a \rightarrow b = 1 \rightarrow 0 = 0,\) then one of the expressions included in the conjunction is false, and \(F = 0\) for any \(c\) (lines 13 and 15). If \(a = 0,\) then \(a \rightarrow b = 0 \rightarrow 0 = 1.\) If \(c = 0,\) then \(b \equiv c = 0 \equiv 0 = 1,\)\(F = 1,\) since both expressions included in the conjunction are true (line 2). If \(c = 1,\) then \(b \equiv c = 0 \equiv 1 = 0,\)\(F = 0,\) since one of the expressions included in the conjunction is false (line 3).

Thus, \(F = 1\) for \(d = 1\) (lines 2, 4, 5). The sum of the values of \(d\) is 1 * 3 = 3.

Basic logical operations

Negation (inversion), from the Latin inversio - I turn over:

Corresponds to the particle NOT, the phrase NOT TRUE THAT;

Designation: not A, A, -A;

truth table:

The inverse of a Boolean variable is true if the variable itself is false, and conversely, the inverse is false if the variable is true.

Example: A = (It's snowing outside).

A=(It is not true that it is snowing outside)

A=(It's not snowing outside);

Logical addition (disjunction), from the Latin disjunctio - I distinguish:

Corresponds to the union OR;

Designation: +, or, or, V;

Truth table:

A disjunction is false if and only if both statements are false.

Example: F=(The sun is shining outside or there is a strong wind blowing);

Logical multiplication (conjunction), from the Latin conjunctio - I connect:

Corresponds to the conjunction AND

(in natural language: both A and B, both A and B, A together with B, A, despite B, A, while B);

Designation: H, , &, u, ^, and;

Truth table:

A conjunction is true if and only if both statements are true.

Example: F=(The sun is shining outside and a strong wind is blowing);

Any complex statement can be written using the basic logical operations AND, OR, NOT. Using logical circuits AND, OR, NOT, you can implement a logical function that describes the operation of various computer devices.

2) A truth table is a table that describes a logical function.

In this case, a “logical function” is understood as a function in which the values of the variables (function parameters) and the value of the function itself express logical truth. For example, in two-valued logic they can take the values “true” or “false” (either or).

Tabular assignment of functions is found not only in logic, but for logical functions tables turned out to be especially convenient, and since the beginning of the 20th century this special name has been assigned to them. Truth tables are especially often used in Boolean algebra and similar systems of many-valued logic.

Conjunction is a logical operation, in its application as close as possible to the union “and”. Logical multiplication, sometimes simply “AND”.

Disjunction is a logical operation, in its application as close as possible to the conjunction “or” in the sense of “either this, or that, or both at once.” logical addition, sometimes just “OR”.

Implication is a binary logical connective, in its application close to the conjunctions “if... then...” The implication is written as a premise and consequence; arrows of a different shape and directed in a different direction are also used (the point always points to the consequence).

Equivalence (or equivalence) is a two-place logical operation. Usually indicated by the symbol ≡ or ↔.

A logical expression is a record or oral statement that, along with constants, necessarily includes variable quantities (objects). Depending on the values of these variables, a logical expression can take one of two possible values: TRUE (logical 1) or FALSE (logical 0)

A complex logical expression is a logical expression composed of one or more simple (or complex) logical expressions connected using logical operations.

Logical operations and truth tables

Logical multiplication CONJUNCTION - this new complex expression will be true only if both original simple expressions are true. A conjunction defines the connection of two logical expressions using the conjunction AND.

Logical addition - DISUNCTION - this new complex expression will be true if and only if at least one of the original (simple) expressions is true. Disjunction defines the connection of two logical expressions using the conjunction OR

Logical negation: INVERSION - if the original expression is true, then the result of the negation will be false, and vice versa, if the original expression is false, then the result of the negation will be true/ This operation means that the NOT particle or the word FALSE is added to the original logical expression.

Logical implication: IMPLICATION - connects two simple logical expressions, of which the first is condition (A), and the second (B) is a consequence of this condition. The result of IMPLICATION is FALSE only when condition A is true and consequence B is false. It is denoted by the symbol “therefore” and expressed by the words IF…, THEN…

Logical equivalence: EQUIVALENCE - determines the result of comparing two simple logical expressions A and B. The result of EQUIVALENCE is a new logical expression that will be true if and only if both original expressions are simultaneously true or false. Indicated by the "equivalence" symbol

The order of logical operations in a complex logical expression:

1. inversion

2. conjunction

3. disjunction

4. implication

5. equivalence

Parentheses are used to change the specified order of operations.

Construction of truth tables for complex expressions:

Number of lines = 2n + two lines for the title (n is the number of simple statements)

Number of columns = number of variables + number of logical operations

When constructing a table, it is necessary to take into account all possible combinations of the logical values 0 and 1 of the original expressions. Then - determine the order of actions and draw up a table taking into account the truth tables of basic logical operations.

EXAMPLE: create a truth table for a complex logical expression D = notA & (B+C)

A, B, C are three simple statements, therefore:

number of lines = 23 +2 = 10 (n=3, because there are three input elements A, B, C)

number of columns: 1) A

4) not A is the inversion of A (denoted by E)

5) B + C is the disjunction operation (denoted by F)

6) D = not A & (B+C), i.e. D = E & F is the conjunction operation

A B C E = not A (not 1) F = B+C (2+3) D = E&F (4*5)

When compiling a truth table for a logical expression, you must:

Find out the number of rows in the table (calculated as 2 n, where n is the number of variables).

Find out the number of columns (defined as the number of variables + the number of logical operations).

Establish the sequence of logical operations.

Construct a table, indicating the names of the columns and possible sets of values of the original logical variables.

Complete the truth table by column.

Test case. Construct a truth table for the expression F = (A V B) & (¬A V ¬B).

The number of rows in the table is defined as 2 2 (2 variables) + 1 (table header) = 5.

The number of columns is 2 logical variables (A, B) + 5 logical operations (&, V, ¬, →, ↔).

Let's arrange the order of operations:

(A V B) & (¬A V ¬B).

Let's build a truth table for this logical expression (Table 5).

Table 5 – Truth table for logical expression

Test case. Construct a truth table for the logical expression X V Y & ¬Z.

Number of lines = 2 3 + 1 = 9.

Number of columns = 3 logical variables + 3 logical operations = 6.

Let us indicate the procedure:

Let's draw and fill out Table 6:

Table 6 – Truth table for logical expression

(AvB)&(⌐Av⌐B)

From a logical point of view, electric current either flows or does not flow; whether there is an electrical impulse or not; whether there is electrical voltage or not. Let's consider electrical contact circuits that implement logical operations (circuits 1 – 3). In diagrams 1 – 3, the contacts are designated by the Latin letters A and B.

Scheme 1 – Conjunction Scheme 2 – Disjunction Scheme 3 – Inversion

(automatic key)

Circuit 4 – Conjunctor Circuit 5 – Disjunctor Circuit 6 – Inverter

The circuit in Scheme 1 with a serial connection of contacts corresponds to the logical operation “AND” and is represented by a conjunctor (Scheme 4). The circuit in diagram 2 with a parallel connection of contacts corresponds to the logical operation “OR” and is represented by a disjunctor (diagram 5). The circuit in diagram 3 (electromagnetic relay) corresponds to the logical operation “NOT” and is represented by an inverter (diagram 6).

Exactly like this electronic circuits found their application as a computer element base. The elements that implement basic logical operations are called basic logical elements or valves and they are characterized not by the state of the contacts, but by the presence of signals at the input and output of the element. Their names and symbols are standard and are used in drawing up and describing computer logic circuits.

Logic circuits must be built from the minimum possible number of elements, which, in turn, ensures greater operating speed and increases the reliability of the device.

Rule for constructing logical circuits:

Determine the number of logical variables.

Determine the number of basic logical operations and their order.

For each logical operation, draw the corresponding gate.

Connect the gates in order of performing logical operations.

Test case. Let X = True (1), Y = False (0). Construct a logic diagram for the following logical expression: F = X V Y & X.

1) Two variables –X and Y.

2) Two logical operations: X V Y & X.

3) We build a diagram (Figure 3).

4) Answer: 1 V 0 & 1 = 1.

Figure 3 – Logic diagram for the logical expression F = X V Y & X