12.3.4. Logical function objects Logical function objects support the operations "logical AND" (returns true if both operands are true - uses the && operator associated with the Type type), "logical OR" (returns true if at least one of the operands is equal to true, –

Logical operations The logical operations include the binary operations and, or and xor, as well as the unary operation not, which have operands of type boolean and return a value of type boolean. These operations follow the standard rules of logic: a and b is true only if a and b are true, a or b is true

Definition 1

Logic function– a function whose variables take one of two values: $1$ or $0$.

Any logical function can be specified using a truth table: the set of all possible arguments is written on the left side of the table, and the corresponding values ​​of the logical function are written on the right side.

Definition 2

Truth table– a table that shows what values ​​a compound expression will take for all possible sets of values ​​of the simple expressions included in it.

Definition 3

Equivalent are called logical expressions whose last columns of truth tables coincide. Equivalence is indicated using the $«=»$ sign.

When compiling a truth table, it is important to consider the following order of logical operations:

Picture 1.

Parentheses take precedence in executing the order of operations.

Algorithm for constructing a truth table of a logical function

Determine the number of lines: number of lines= $2^n + 1$ (for title line), $n$ – number of simple expressions. For example, for functions of two variables there are $2^2 = 4$ combinations of sets of variable values, for functions of three variables there are $2^3 = 8$, etc.

Determine the number of columns: number of columns = number of variables + number of logical operations. When determining the number of logical operations, the order of their execution is also taken into account.

Fill columns with the results of logical operations in a certain sequence, taking into account the truth tables of basic logical operations.

Figure 2.

Example 1

Create a truth table for the logical expression $D=\bar(A) \vee (B \vee C)$.

Solution:

Let's determine the number of lines:

number of lines = $2^3 + 1=9$.

Number of variables – $3$.

1. inverse ($\bar(A)$);
2. disjunction, because it is in parentheses ($B \vee C$);

3. disjunction ($\overline(A)\vee \left(B\vee C\right)$) is the required logical expression.

   Number of columns = $3 + 3=6$.

Let's fill in the table, taking into account the truth tables of logical operations.

Figure 3.

Example 2

Using this logical expression, construct a truth table:

Solution:

Let's determine the number of lines:

The number of simple expressions is $n=3$, which means

number of lines = $2^3 + 1=9$.

Let's determine the number of columns:

Number of variables – $3$.

Number of logical operations and their sequence:

1. negation ($\bar(C)$);
2. disjunction, because it is in parentheses ($A \vee B$);
3. conjunction ($(A\vee B)\bigwedge \overline(C)$);
4. negation, which we denote by $F_1$ ($\overline((A\vee B)\bigwedge \overline(C))$);
5. disjunction ($A \vee C$);
6. conjunction ($(A\vee C)\bigwedge B$);
7. negation, which we denote by $F_2$ ($\overline((A\vee C)\bigwedge B)$);

8. disjunction is the desired logical function ($\overline((A\vee B)\bigwedge \overline(C))\vee \overline((A\vee C)\bigwedge B)$).

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 a false statement follows from a true statement. 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 a 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.

Algebra of logic

Algebra of logic

Algebra of logic(English) algebra of logic) is one of the main branches of mathematical logic, in which algebraic methods are used in logical transformations.

The founder of the algebra of logic is the English mathematician and logician J. Boole (1815-1864), who based his logical teaching on the analogy between algebra and logic. He wrote down any statement using the symbols of the language he developed and received “equations”, the truth or falsity of which could be proven based on certain logical laws, such as the laws of commutativity, distributivity, associativity, etc.

Modern algebra of logic is a branch of mathematical logic and studies logical operations on statements from the point of view of their truth value (true, false). Statements can be true, false, or contain truth and falsehood in different proportions.

Logical statement is any declarative sentence whose content can be unequivocally stated to be true or false.

For example, “3 times 3 equals 9”, “Arkhangelsk is north of Vologda” are true statements, but “Five is less than three”, “Mars is a star” are false.

Obviously, not every sentence can be a logical statement, since it does not always make sense to talk about its falsity or truth. For example, the statement “Computer science is an interesting subject” is vague and requires additional information, and the statement “For a student of grade 10-A Ivanov A.A., computer science is an interesting subject,” depending on the interests of Ivanov A.A., can take on the meaning “true” or "lie".

Except two-valued propositional algebra, in which only two values ​​are accepted - “true” and “false”, there is multivalued propositional algebra. In such algebra, in addition to the values ​​“true” and “false”, such truth values ​​as “probable”, “possible”, “impossible”, etc. are used.

In algebra, logic differs simple(elementary) statements, designated by Latin letters (A, B, C, D, ...), and complex(composite), made up of several simple ones using logical connectives, for example, such as “not”, “and”, “or”, “if and only then”, “if... then”. The truth or falsity of complex statements obtained in this way is determined by the meaning of simple statements.

Let's denote it as A the statement “The algebra of logic is successfully applied in the theory of electrical circuits,” and through IN— “Logic algebra is used in the synthesis of relay circuits.”

Then the compound statement “The algebra of logic is successfully applied in the theory of electrical circuits and in the synthesis of relay circuits” can be briefly written as A and B; here “and” is a logical connective. It is obvious that since elementary statements A and B are true, then the compound statement is true A and B.

Each logical connective is considered as an operation on logical statements and has its own name and designation.

There are only two logical values: true (TRUE) And false (FALSE). This corresponds to the digital representation − 1 And 0 . The results of each logical operation can be written in the form of a table. Such tables are called truth tables.

Basic operations of algebra logic

1. Logical negation, inversion(lat. inversion- inversion) is a logical operation, as a result of which a new statement is obtained from a given statement (for example, A) not A), which is called negation of the original statement, is symbolically indicated by an overbar ($A↖(-)$) or by such conventions as ¬, "not", and reads: “not A”, “A is false”, “it is not true that A”, “negation of A”. For example, “Mars is a planet of the solar system” (statement A); “Mars is not a planet in the solar system” ($A↖(-)$); the statement “10 is a prime number” (statement B) is false; The statement “10 is not a prime number” (statement B) is true.

An operation used on a single quantity is called unary. The table of values ​​for this operation looks like

The statement $A↖(-)$ is false when A is true, and true when A is false.

Geometrically, negation can be represented as follows: if A is a certain set of points, then $A↖(-)$ is the complement of the set A, i.e., all points that do not belong to the set A.

2.Conjunction(lat. conjunctio- connection) - logical multiplication, an operation that requires at least two logical quantities (operands) and connects two or more statements using a connective "And"(For example, "A and B"), which is symbolically denoted by the sign ∧ (A ∧ B) and reads: “A and B.” The following signs are also used to indicate conjunction: A ∙ B; A & B, A and B, and sometimes there is no sign between statements: AB. Example of logical multiplication: “This triangle is isosceles and right-angled.” A given statement can be true only if both conditions are met, otherwise the statement is false.

Statement A ∧ IN true only if both statements are A And IN are true.

Geometrically, the conjunction can be represented as follows: if A, B A ∧ IN there is an intersection of sets A And IN.

3. Disjunction(lat. disjunction- division) - logical addition, an operation connecting two or more statements using a connective "or"(For example, "A or B"), which is symbolically denoted by the sign ∨ (A∨ IN) and reads: "A or B". The following signs are also used to indicate disjunction: A + B; A or B; A | B. An example of logical addition: “The number x is divisible by 3 or 5.” This statement will be true if both conditions or at least one of the conditions are met.

The truth table of the operation has the form

Statement A∨ IN is false only when both statements are A And IN false.

Geometrically, logical addition can be represented as follows: if A, B are some sets of points, then A ∨ IN is a union of sets A And IN, i.e., a figure that combines both a square and a circle.

4. Strictly separative disjunction, addition modulo two- a logical operation that connects two statements using a connective "or", used in an exclusive sense, which is symbolically denoted by the signs ∨ ∨ or ⊕ ( A ∨ ∨ B, A ⊕ IN) and reads: "either A or B". An example of addition modulo two is the statement “This triangle is obtuse or acute.” The statement is true if any one of the conditions is met.

The truth table of the operation has the form

The statement A ⊕ B is true only if the statements A and B have different meanings.

5. Implication(lat. implisito- closely connect) - a logical operation connecting two statements using a connective "if... then" into a complex statement, which is symbolically indicated by the sign → ( A → IN) and reads: “if A, then B”, “A implies B”, “from A follows B”, “A implies B”. The sign ⊃ (A ⊃ B) is also used to denote implication. An example of an implication: “If the resulting quadrilateral is a square, then a circle can be described around it.” This operation connects two simple logical expressions, of which the first is a condition, and the second is a consequence. The result of an operation is false only when the premise is true and the consequence is false. For example, “If 3 * 3 = 9 (A), then the Sun is a planet (B),” the result of the implication A → B is false.

The truth table of the operation has the form

For the operation of implication, the statement is true that anything can follow from a lie, but only truth can follow from truth.

6. Equivalence, double implication, equivalence(lat. aequalis- equal and valentis- having force) - a logical operation that allows from two statements A And IN get a new expression A ≡ B which reads: "A is equivalent to B". The following signs are also used to indicate equivalence: ⇔, ∼. This operation can be expressed by connectives “then and only then”, “necessary and sufficient”, “equivalent”. An example of equivalence is the statement: “A triangle is right-angled if and only if one of the angles is 90 degrees.”

The truth table of the equivalence operation has the form

The equivalence operation is the opposite of addition modulo two and evaluates to true if and only if the values ​​of the variables are the same.

Knowing the meanings of simple statements, it is possible to determine the meanings of complex statements based on truth tables. It is important to know that to represent any function in the algebra of logic, three operations are sufficient: conjunction, disjunction and negation.

The priority of logical operations is as follows: negation ( "Not") has the highest priority, then the conjunction ( "And"), after the conjunction - disjunction ( "or").

With the help of logical variables and logical operations, any logical statement can be formalized, that is, replaced by a logical formula. In this case, the elementary statements that form a compound statement may be absolutely unrelated in meaning, but this does not interfere with determining the truth or falsity of the compound statement. For example, the statement “If five is greater than two ( A), then Tuesday always comes after Monday ( IN)" - implication A→ IN, and the result of the operation in this case is “true”. In logical operations, the meaning of statements is not taken into account, only their truth or falsity is considered.

Consider, for example, the construction of a compound statement from statements A And IN, which would be false if and only if both statements are true. In the truth table for the operation of addition modulo two we find: 1 ⊕ 1 = 0. And the statement could be, for example, like this: “This ball is completely red or completely blue.” Therefore, if the statement A"This ball is completely red" is a truth and a statement IN“This ball is completely blue” is true, then the compound statement is false, because the ball cannot be both red and blue at the same time.

Examples of problem solving

Example 1. For the specified values ​​of X, determine the value of the logical statement ((X > 3) ∨ (X< 3)) → (X < 4) :

1) X = 1; 2) X = 12; 3) X = 3.

Solution. The sequence of operations is as follows: first the comparison operations in parentheses are performed, then the disjunction, and lastly the implication operation is performed. The disjunction operation ∨ is false if and only if both operands are false. The truth table for the implication looks like

From here we get:

1) for X = 1:

((1 > 3) ∨ (1 < 3)) → (1 < 4) = ложь ∨ истина → истина = истина → истина = истина;

2) for X = 12:

((12 > 3) ∨ (12 < 3) → (12 < 4) = истина ∨ ложь → ложь = истина → ложь = ложь;

3) for X = 3:

((3 > 3) ∨ (3 < 3)) → (3<4) = ложь ∨ ложь → истина = ложь → истина = истина.

Example 2. Indicate the set of integer values ​​of X for which the expression ¬((X > 2) → (X > 5)) is true.

Solution. The negation operation is applied to the entire expression ((X > 2) → (X > 5)), therefore, when the expression ¬((X > 2) → (X > 5)) is true, the expression ((X > 2) →(X > 5)) is false. Therefore, it is necessary to determine for which values ​​of X the expression ((X > 2) → (X > 5)) is false. The operation of implication takes on the value “false” only in one case: when a lie follows from truth. And this is only true for X = 3; X = 4; X = 5.

Example 3. For which of the following words is the statement ¬(the first letter is a vowel ∧ the third letter a vowel) ⇔ a string of 4 characters false? 1) assa; 2) kuku; 3) corn; 4) error; 5) strongman.

Solution. Let's consider all the proposed words sequentially:

1) for the word assa we get: ¬(1 ∧ 0) ⇔ 1, 1 ⇔ 1 - the statement is true;

2) for the word kuku we get: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 1 - the statement is true;

3) for the word corn we get: ¬ (0 ∧ 0) ⇔ 0, 1 ⇔ 0 - the statement is false;

4) for the word error we get: ¬ (1 ∧ 1) ⇔ 0, 0 ⇔ 0 - the statement is true;

5) for the word strongman we get: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 0 - the statement is false.

Logical expressions and their transformation

Under logical expression should be understood as a record that can take the logical value “true” or “false”. With this definition, among logical expressions it is necessary to distinguish:

• expressions that use comparison operations (“greater than,” “less than,” “equal to,” “not equal to,” etc.) and take logical values ​​(for example, the expression a > b, where a = 5 and b = 7, equals the value "false");
• direct logical expressions associated with logical quantities and logical operations (for example, A ∨ B ∧ C, where A = true, B = false and C = true).

Boolean expressions can include functions, algebraic operations, comparison operations, and logical operations. In this case, the priority of actions is as follows:

1. calculation of existing functional dependencies;
2. performing algebraic operations (first multiplication and division, then subtraction and addition);
3. performing comparison operations (in random order);
4. performing logical operations (first the negation operations, then the operations of logical multiplication, logical addition, and lastly the operations of implication and equivalence are performed).

A Boolean expression can use parentheses, which change the order in which the operations are performed.

Example. Find the meaning of the expression:

$1 ≤ a ∨ A ∨ sin(π/a - π/b)< 1 ∧ ¬B ∧ ¬(b^a + a^b >a + b ∨ A ∧ B)$ for a = 2, b = 3, A = true, B = false.

Solution. The order of counting values:

1) b a + a b > a + b, after substitution we get: 3 2 + 2 3 > 2 + 3, i.e. 17 > 2 + 3 = true;

2) A ∧ B = true ∧ false = false.

Therefore, the expression in parentheses is (b a + a b > a + b ∨ A ∧ B) = true ∨ false = true;

3) 1≤ a = 1 ≤ 2 = true;

4) sin(π/a - π/b)< 1 = sin(π/2 - π/3) < 1 = истина.

After these calculations we finally get: true ∨ A ∧ true ∧ ¬B ∧ ¬ true.

Now the operations of negation, then logical multiplication and addition must be performed:

5) ¬B = ¬false = true; ¬true = false;

6) A ∧ true ∧ true ∧ false = true ∧ true ∧ true ∧ false = false;

7) true ∨ false = true.

Thus, the result of a logical expression for given values ​​is “true”.

Note. Considering that the original expression is, ultimately, the sum of two terms, and the value of one of them is 1 ≤ a = 1 ≤ 2 = true, without further calculations we can say that the result for the entire expression is also “true”.

Identical transformations of logical expressions

In the algebra of logic, basic laws are followed that allow identical transformations of logical expressions.

Proofs of these statements are made based on the construction of truth tables for the corresponding records.

Equivalent transformations of logical formulas have the same purpose as transformations of formulas in ordinary algebra. They serve to simplify formulas or reduce them to a certain form by using the basic laws of logical algebra. Under simplifying the formula, which does not contain the operations of implication and equivalence, is understood as an equivalent transformation leading to a formula that contains either a smaller number of operations or a smaller number of variables compared to the original one.

Some transformations of logical formulas are similar to transformations of formulas in ordinary algebra (taking the common factor out of brackets, using commutative and combinational laws, etc.), while other transformations are based on properties that the operations of ordinary algebra do not have (using the distributive law for conjunction , laws of absorption, gluing, de Morgan, etc.).

Let's look at some examples of techniques and methods used to simplify logical formulas:

1) X1 ∧ X2 ∨ X1 ∧ X2 ∪ ¬X1 ∧ X2 = X1 ∧ X2 ∨ ¬X1 ∧ X2 = (X1 ∨ ¬X1) ∧ X2 = 1 ∧ X2 = X2 .

To transform here, you can apply the law of idempotence, the distributive law; operation of a variable with inversion and operation with a constant.

2) X1 ∨ X1 ∧ X2 = X1 ∨ (1 ∨ 1 ∧ X2) = X1 ∨ (1 ∨ X2) = X1.

Here, for simplicity, the absorption law is applied.

3) ¬(X1 ∧ X2) ∨ X2 = (¬X1 ∨ ¬X2) ∨ X2 = ¬X1 ∨ ¬X2 ∨ X2 = ¬X1 ∨ 1 = 1 .

When transforming, the de Morgan rule, the operation of a variable with its inversion, and the operation with a constant are applied

Examples of problem solving

Example 1. Find a logical expression equivalent to the expression A ∧ ¬(¬B ∨ C) .

Solution. We apply de Morgan's rule for B and C: ¬(¬B ∨ C) = B ∧ ¬C.

We obtain an expression equivalent to the original one: A ∧ ¬(¬B ∨ C) = A ∧ B ∧ ¬C .

Answer: A ∧ B ∧ ¬C.

Example 2. Indicate the value of the logical variables A, B, C, for which the value of the logical expression (A ∨ B) → (B ∨ ¬C ∨ B) is false.

Solution. The operation of implication is false only if a false statement follows from a true premise. Therefore, for a given expression, the premise A ∨ B must be “true”, and the consequence, i.e., the expression B ∨ ¬C ∨ B, must be “false”.

1) A ∨ B — the result of the disjunction is “true” if at least one of the operands is “true”;

2) B ∨ ¬C ∨ B - the expression is false if all terms have the value “false”, i.e. B is “false”; ¬C is “false”, and therefore the variable C has the value “true”;

3) if we consider the premise and take into account that B is “false”, we obtain that the value of A is “true”.

Answer: A is true, B is false, C is true.

Example 3. What is the largest integer X for which the statement (35

Solution. Let's write down the truth table for the implication operation:

Expression X< (X - 3) ложно при любых положительных значениях X. Следовательно, для того чтобы результатом импликации была «истина», необходимо и достаточно, чтобы выражение 35 < X · X также было ложно. Максимальное целое значение X, для которого 35 < X · X ложно, равно 5.

Answer: X = 5.

Using Boolean Expressions to Describe Geometric Regions

Logical expressions can be used to describe geometric regions. In this case, the task is formulated as follows: write down for a given geometric region a logical expression that takes the value “true” for the values ​​x, y if and only if any point with coordinates (x; y) belongs to the geometric region.

Let's consider the description of a geometric region using a logical expression using examples.

Example 1. An image of a geometric region is specified. Write a logical expression describing the set of points belonging to it.

1) .

Solution. A given geometric region can be represented as a set of the following regions: the first region - D1 - half-plane $(x)/(-1) +(y)/(1) ≤ 1$, the second - D2 - a circle with center at the origin $x ^2 + y^2 ≤ 1$. Their intersection D1 $∩$ D2 represents the desired region.

Result: logical expression $(x)/(-1)+(y)/(1) ≤ 1 ∧ x^2 + y^2 ≤ 1$.

2)

This area can be written as follows: |x| ≤ 1 ∧ y ≤ 0 ∧ y ≥ -1 .

Note. When constructing a logical expression, loose inequalities are used, which means that the boundaries of the figures also belong to the shaded area. If you use strict inequalities, then boundaries will not be taken into account. Boundaries that do not belong to the area are usually shown as dotted lines.

You can solve the inverse problem, namely: draw a region for a given logical expression.

Example 2. Draw and shade the area for which the logical condition y ≥ x ∧ y + x ≥ 0 ∧ y is satisfied< 2 .

Solution. The sought area is the intersection of three half-planes. We construct straight lines on the plane (x, y) y = x; y = -x; y = 2. These are the boundaries of the region, and the last boundary y = 2 does not belong to the region, so we draw it with a dotted line. To satisfy the inequality y ≥ x, the points must be to the left of the line y = x, and the inequality y = -x is satisfied for points that are to the right of the line y = -x. Condition y< 2 выполняется для точек, лежащих ниже прямой y = 2. В результате получим область, которая изображена на рис.:

Using Logic Functions to Describe Electrical Circuits

Logic functions are very useful for describing the operation of electrical circuits. So, for the circuit shown in Fig., where the value of the variable X is the state of the switch (if it is on, the value of X is “true”, and if it is off, the value is “false”), this value of Y is the state of the light bulb (if it is on - the value is “true”, and if not - “false”), the logical function will be written like this: Y = X. The function Y is called conductivity function.

For the circuit shown in Fig., the logical function Y has the form: Y = X1 ∪ X2, since one switch on is enough for the light bulb to light. In the circuit in Fig., in order for the light bulb to light, both switches must be turned on, therefore, the conductivity function has the form: Y = X1 ∧ X2.

For a more complex circuit, the conductivity function will have the form: Y = (X11 ∨ (X12 ∧ X13)) ∧ X2 ∧ (X31 ∨ X32).

The circuit may also contain short-circuit contacts. In this case, the open contact acts as a switch to ensure that the light bulb lights up when the button is released and not pressed. For such circuits, the disconnect switch is described by negation.

The two schemes are called equivalent, if a current passes through one of them then it also passes through the other. Of two equivalent circuits, the simpler circuit is the one whose conductivity function contains a smaller number of elements. The task of finding the simplest circuits among equivalent ones is very important.

Using the apparatus of logic algebra in the design of logic circuits

The mathematics of logical algebra is very useful for describing how computer hardware functions. When processed on a computer, any information is presented in binary form, that is, it is encoded by a certain sequence of 0s and 1s. The processing of binary signals corresponding to 0s and 1s is performed in the computer by logical elements. Logic gates that perform basic logical operations AND, OR, NOT, are presented in Fig.

Symbols for logical elements are standard and are used when drawing up logic circuits of a computer. Using these circuits, you can implement any logical function that describes the operation of a computer.

Technically, a computer logic element is implemented in the form of an electrical circuit, which is a connection of various parts: diodes, transistors, resistors, capacitors. The input of a logic element, which is also called a gate, receives electrical signals of high and low voltage levels, and one output signal is also issued at either a high or low level. These levels correspond to one of the states of the binary system: 1 - 0; TRUTH IS FALSE. Each logical element has its own symbol, which expresses its logical function, but does not indicate what kind of electronic circuit is implemented in it. This makes it easier to write and understand complex logic circuits. The operation of logic circuits is described using truth tables. The symbol in the OR diagram is the sign “1” - from the outdated designation of disjunction as “>=1” (the value of the disjunction is 1 if the sum of the two operands is greater than or equal to 1). The “&” sign in the AND diagram is an abbreviation for the English word and.

Electronic logic circuits are made from logical elements that perform more complex logical operations. A set of logical elements consisting of NOT, OR, AND elements, with the help of which you can build a logical structure of any complexity, is called functionally complete.

Construction of truth tables of logical expressions

For a logical formula you can always write truth table, i.e., present a given logical function in tabular form. In this case, the table should contain all possible combinations of function arguments (formulas) and the corresponding function values ​​(the results of the formula on a given set of values).

A convenient form of recording when finding the values ​​of a function is a table containing, in addition to the values ​​of variables and function values, also the values ​​of intermediate calculations. Let's consider an example of constructing a truth table for the formula $(X1)↖(-) ∧ X2 ∨ (X1 ∨ X2)↖(-) ∨ X1$.

If a function takes the value 1 for all sets of variable values, it is identically true; if for all sets of input values ​​the function takes the value 0, it is identically false; if the set of output values ​​contains both 0 and 1, the function is called feasible. The above example is an example of an identically true function.

Knowing the analytical form of a logical function, you can always go to the tabular form of logical functions. Using a given truth table, you can solve the inverse problem, namely: for a given table, construct an analytical formula for a logical function. There are two forms of constructing the analytical dependence of a logical function based on a table-specified function.

1. Disjunctive normal form (DNF)- the sum of products formed from variables and their negations for false values.

The algorithm for constructing a DNF is as follows:

1. in the truth table, functions select sets of arguments for which the logical forms are equal to 1 (“true”);
2. all selected logical sets are written down as logical products of arguments, sequentially connecting them to each other using the operation of logical sum (disjunction);
3. for arguments that are false, a negation operation is inserted in the constructed record.

Example. Construct a function that determines that the first number is equal to the second using the DNF method. The truth table of the function looks like

Solution. We select sets of argument values ​​in which the function is equal to 1. These are the first and fourth rows of the table (we do not take into account the header row when numbering).

We write down the logical products of the arguments of these sets, combining them with a logical sum: X1 ∧ X2 ∨ X1 ∧ X2.

We write down the negation of the arguments of the selected sets that have a false value (the fourth row of the table; the second set in the formula; the first and second elements): X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ $(X2)↖(-)$.

Answer: F(X1, X2) = X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ $(X2)↖(-)$.

2. Conjunctive normal form (CNF)- the product of sums formed from variables and their negations for true values.

The algorithm for constructing CNF is as follows:

1. in the truth table, sets of arguments are selected for which the logical forms are equal to 0 (“false”);
2. all selected logical sets as logical sums of arguments are written sequentially, connecting them together using the operation of a logical product (conjunction);
3. for arguments that are true, a negation operation is entered in the constructed record.

Examples of problem solving

Example 1. Let's consider the previous example, i.e., construct a function that determines that the first number is equal to the second, using the CNF method. For a given function, its truth table has the form

Solution. We select sets of argument values ​​in which the function is equal to 0. These are the second and third lines (we do not take into account the header line when numbering).

We write down the logical sums of the arguments of these sets, combining them with a logical product: X1 ∨ X2 ∧ X1 ∨ X2.

We write down the negation of the arguments of the selected sets that have a true value (the second row of the table, the first set of the formula, the second element; for the third line, and this is the second set of the formula, the first element): X1 ∨ $(X2)↖(-)$ ∧ $( X1)↖(-)$ ∨ X2.

Thus, a record of the logical function in CNF has been obtained.

Answer: X1 ∨ $(X2)↖(-)$ ∧ $(X1)↖(-)$ ∨ X2.

The function values ​​obtained by the two methods are equivalent. To prove this statement, we use the rules of logic: F(X1, X2) = X1 ∨ $(X2)↖(-)$ ∧ $(X1)↖(-)$ ∨ X2 = X1 ∧ $(X1)↖(-)$ ∨ X1 ∧ X2 ∨ $(X2)↖(-)$ ∧ $(X1)↖(-)$ ∨ $(X2)↖(-)$ ∧ X2 = 0 ∨ X1 ∨ X2 ∨ $(X2)↖(- )$ ∧ $(X1)↖(-)$ ∨ 0 = X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ $(X2)↖(-)$.

Example 2. Construct a logical function for a given truth table:

The required formula: X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ X2 .

It can be simplified: X1 ∧ X2 ∨ $(X1)↖(-)$ ∧ X2 = X2 ∧ (X1 ∨ $(X1)↖(-)$) = X2 ∧ 1 = X2.

Example 3. For the given truth table, construct a logical function using the DNF method.

The required formula: X1 ∧ X2 ∧ X ∨ $(X1)↖(-)$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $(X3)↖(-)$ ∪ X1 ∧ $(X2)↖(-)$ ∧ $ (X3)↖(-)$.

The formula is quite cumbersome and should be simplified:

X1 ∧ X2 ∧ X3 ∨ $(X1)↖(-)$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $(X3)↖(-)$ ∨ X1 ∧ $(X2)↖(-)$ ∧ $(X3) ↖(-)$ = X2 ∧ X3 ∧ (X1 ∨ $(X1)↖(-)$) ∨ X1 ∧ $(X3)↖(-)$ ∧ (X2 ∨ $(X2)↖(-)$) = X2 ∧ X3 ∨ X1 ∧ $(X3)↖(-)$.

Truth tables for solving logical problems

Compiling truth tables is one of the ways to solve logical problems. When using this method of solution, the conditions that the problem contains are recorded using specially compiled tables.

Examples of problem solving

Example 1. Create a truth table for a security device that uses three sensors and is triggered when only two of them are shorted.

Solution. Obviously, the result of the solution will be a table in which the desired function Y(X1, X2, X3) will have the value “true” if any two variables have the value “true”.

Example 2. Make a lesson schedule for the day, taking into account that a computer science lesson can only be the first or second, a mathematics lesson - the first or third, and a physics lesson - the second or third. Is it possible to create a schedule that meets all the requirements? How many scheduling options are there?

Solution. The problem can be easily solved if you create the appropriate table:

The table shows that there are two options for the desired schedule:

1. mathematics, computer science, physics;
2. computer science, physics, mathematics.

Example 3. Three friends came to the sports camp - Peter, Boris and Alexey. Each of them is fond of two sports. It is known that there are six such sports: football, hockey, skiing, swimming, tennis, badminton. It is also known that:

1. Boris is the eldest;
2. a football player younger than a hockey player;
3. playing football and hockey and Peter live in the same house;
4. when a quarrel arises between a skier and a tennis player, Boris reconciles them;
5. Peter can't play tennis or badminton.

What sports does each boy enjoy?

Solution. Let's draw up a table and reflect the conditions of the problem in it, filling in the corresponding cells with the numbers 0 and 1, depending on whether the corresponding statement is false or true.

Since there are six types of sports, it turns out that all the boys are interested in different sports.

From condition 4 it follows that Boris is not interested in skiing or tennis, and from conditions 3 and 5 that Peter does not know how to play football, hockey, tennis and badminton. Consequently, Peter’s favorite sports are skiing and swimming. Let’s put this in the table, and fill the remaining cells of the “Skiing” and “Swimming” columns with zeros.

The table shows that only Alexey can play tennis.

From conditions 1 and 2 it follows that Boris is not a football player. Thus, Alexey plays football. Let's continue filling out the table. Let's enter zeros into the empty cells of the line “Alexey”.

We finally get that Boris is interested in hockey and badminton. The final table will look like this:

Answer: Peter enjoys skiing and swimming, Boris plays hockey and badminton, and Alexey plays football and tennis.

Page 1

Computer science lesson on the topic "Fundamentals of logic, truth tables"

Subject: Howbuild a truth table?

Lesson type: combined:

• 
  knowledge test - oral work;
• 
  new material - lecture;
• 
  consolidation – practical exercises;
• 
  knowledge testing - tasks for independent work.

1. 
   Educational:
   1. 
      Learn to form logical expressions from statements
   2. 
      Introduce the concept of “truth table”
   3. 
      Study the sequence of actions for constructing truth tables
   4. 
      Learn to find the meaning of logical expressions by constructing truth tables
2. 
   Educational:
   1. 
      Develop logical thinking
   2. 
      Develop attention
   3. 
      Develop memory
   4. 
      Develop students' speech
3. 
   Educational:
   1. 
      Develop the ability to listen to teachers and classmates
   2. 
      Cultivate accuracy in notebook keeping
   3. 
      Cultivate discipline

1. 
   Organizational moment (2 min).
2. 
   Repetition of material from the previous lesson + checking homework (oral questioning) (5 min).
3. 
   Explanation of new material (10 min).
4. 
   Physical education minute (1 min).
5. 
   Consolidation
   • 
     case study (5 min);
   • 
     practical exercises (10 min);
   • 
     tasks for independent work (5 min).
6. 
   

• 
  white board;
• 
  handout reference material “Truth Tables”;
• 
  Demonstration of the “Truth Table” presentation.

1. Organizational moment

• 
  Greetings.
• 
  Checking absences from class.
• 
  Announcement of grades for the last lesson.

3 students work using cards:

Match the correct definitions or notations:

1. Logic	1.
2. Statement	2. Logical addition
3. Algebra of logic	3. The science of forms and ways of thinking
4. Logical variable	4. Logical negation
5. Disjunction	5. TRUE and FALSE
6. Inversion	6.
7. Conjunction	7.
8. Implication	8. The Science of Propositional Operations
9. Equivalence	9. A declarative sentence in which something is affirmed or denied, which may be true or false.

1)Examples are written on the board:

1. 
   For logical expressions, formulate compound statements in ordinary language:

B) (X=Y) and (X=Z). (Answer: numbersX, YAndZequal to each other)

2) Give examples of compound statements from school subjects and write them using logical operations: literature, biology, geography, history.

What logical connectives did you use? ( Inversion, disjunction and conjunction)

We saw that logic is quite closely connected with our everyday life, and we also saw that almost any statement can be written in the form of a formula.

Let's remember the basic definitions and concepts:

3. Explanation of new material

From a compound statement, create a formula, replacing simple statements with variables.

Problem: The glass in the classroom was broken. The teacher explains to the director: Kolya or Sasha did it. But Sasha didn’t do this, because at that time he was taking a test for me. Therefore, Kolya did it.

Solution: Let’s formalize this complex statement:

K - Kolya did it; S – Sasha did it.

Statement form:

In the last lesson, we found the value of a compound statement by substituting the original values ​​of the incoming logical variables. And today we will learn that it is possible to construct a truth table that determines the truth or falsity of a logical expression for all possible combinations of the initial values ​​of simple statements (logical variables) and that we can determine the values ​​of the initial logical variables, knowing what result we need.

So, the topic of today's lesson is: “How to build a truth table?”

Have we been using the concept of “truth table” for several lessons in a row? So what is a truth table?

A truth table is a table showing the truth of a complex statement for all possible values ​​of the input variables.

Let's look at our example again

and build a truth table for this compound statement

When constructing truth tables, there is a certain sequence of actions. Let's write it down

1. 
   It is necessary to determine the number of rows in the truth table.

• 
  number of lines = 2 n, where n is the number of logical variables

1. 
   It is necessary to determine the number of columns in the truth table.

• 
  number of columns = number of logical variables + number of logical operations.
• 
  It is necessary to construct a truth table with the specified number of rows and columns, enter the names of the columns of the table in accordance with the sequence of logical operations, taking into account parentheses and priorities (¬, &, V);

1. 
   Populate input variable columns with sets of values
2. 
   Fill out the truth table column by column, performing logical operations in accordance with the established sequence.

TO	WITH
0	0	1	0	0	1
0	1	0	1	0	1
1	0	1	1	1	1
1	1	0	1	0	1

4. Physical education minute

1. 
   Consolidation

• 
  analysis of the example.
• 
  practical exercises.
• 
  assignments for independent work.

A)

A	IN
0	0	0	1
0	1	0	0
1	0	0	0
1	1	1	0

B)

A	IN
0	0	1	0	1
0	1	0	1	0
1	0	1	1	1
1	1	0	1	0

IN)

A	IN	WITH
0	0	0	1	0	0
0	0	1	1	1	1
0	1	0	0	0	0
0	1	1	0	0	0
1	0	0	1	0	1
1	0	1	1	1	1
1	1	0	0	0	1
1	1	1	0	0	1

Assignment for independent work “Who is faster?”

Prepared cards for students, in which they need to fill out the truth table column by column, performing logical operations in accordance with the established sequence.

A	IN	WITH

Answer:

A	IN	WITH
0	0	0	1	0	1	0
0	0	1	0	0	0	1
0	1	0	1	0	1	0
0	1	1	0	0	0	1
1	0	0	1	0	1	0
1	0	1	0	0	0	1
1	1	0	1	1	1	0
1	1	1	0	1	1	0

1. 
   Lesson summary, homework (2 min).

D/Z is not given, since the lesson is paired, children come through the lesson and continue to study the topic “Fundamentals of logic and logical foundations of a computer.”

Page 1