Analysis of the 2nd assignment of the USE 2017 in computer science from the demo project. This is a basic level task. Estimated time to complete the task is 3 minutes.
Checked content elements: the ability to build truth tables and logic circuits. Content elements tested on the exam: statements, logical operations, quantifiers, truth of the statement.
Task 2:
Boolean function F given by the expression x /\¬ y /\ (¬ z \/ w).
The figure shows a fragment of the truth table of the function F, containing all F true.
Determine which column of the truth table of the function F corresponds to each of the variables w, x, y, z.
Write the letters in your answer. w, x, y, z in the order in which the columns corresponding to them go (first - the letter corresponding to the first column; then - the letter corresponding to the second column, etc.) Write the letters in the answer in a row, you do not need to put any separators between the letters.
Example. If the function were given by the expression ¬ x \/ y depending on two variables: x and y, and a fragment of its truth table was given, containing all sets of arguments for which the function F true.
Then the first column would correspond to the variable y, and the second column is a variable x. The answer should have been: yx.
Answer: ________
x /\¬ y /\ (¬ z \/ w)
A conjunction (logical multiplication) is true if and only if all statements are true. Hence the variable X 1 .
So the variable x corresponds to the column with variable 3.
variable ¬y must match the column in which the value is 0 .
The disjunction (logical addition) of two statements is true if and only if at least one statement is true.
Disjunction ¬z \/w in this line will be true only if z=0, w=1.
So the variable ¬z matches column with variable 1 (1 column), variable w corresponds to the column with variable 4 (column 4).
№1
(x /\ y/\z/\¬w)\/ (x /\ y/\¬z/\¬w)\/ (x /\¬y/\¬z/\¬w).
Decision
x /\ y/\z/\¬w – x=1, y=1, z=1, w=0;
x /\ y/\¬z/\¬w – x=1, y=1, z=0, w=0;
x /\¬y/\¬z/\¬w – x=1, y=0, z=0, w=0.
As a result, we get 6 units.
Answer:
6.
№2 The logical function F is given by the expression
(¬x /\ y/\¬z/\w)\/ (x /\ y/\z/\¬w)\/ (x /\¬ y/\¬z/\w).
Stepan wrote down all sets of variables for which this expression is true. How many units did Stepan write? In the answer, write down only an integer - the number of units.
Example. Let an expression x → y be given depending on two variables x and y. This expression is true for three sets: (0, 0), (0, 1) and (1, 1). Stepan wrote 3 units.
Decision similar to solution.
№3 The logical function F is given by the expression
(x /\ ¬y/\z/\w)\/ (x /\ y/\¬z/\w)\/ (¬x /\ y/\ z/\w).
Stepan wrote down all sets of variables for which this expression is true. How many units did Stepan write? In the answer, write down only an integer - the number of units.
Example. Let an expression x → y be given depending on two variables x and y. This expression is true for three sets: (0, 0), (0, 1) and (1, 1). Stepan wrote 3 units.
Decision similar to solution.
№4 The logical function F is given by the expression
(¬x /\ ¬y/\z/\w)\/ (¬x /\ ¬y/\¬z/\w)\/ (¬x /\ y/\ z/\¬w).
Stepan wrote down all sets of variables for which this expression is true. How many units did Stepan write? In the answer, write down only an integer - the number of units.
Example. Let an expression x → y be given depending on two variables x and y. This expression is true for three sets: (0, 0), (0, 1) and (1, 1). Stepan wrote 3 units.
Decision similar to solution.
№5 The logical function F is given by the expression
(¬x /\ y/\¬z/\¬w)\/ (x /\ ¬y/\¬z/\¬w)\/ (¬x /\ ¬y/\ z/\¬w).
Stepan wrote down all sets of variables for which this expression is true. How many units did Stepan write? In the answer, write down only an integer - the number of units.
Example. Let an expression x → y be given depending on two variables x and y. This expression is true for three sets: (0, 0), (0, 1) and (1, 1). Stepan wrote 3 units.
Decision similar to solution.
№6 The logical function F is given by the expression
(x /\ y/\¬w)\/ (x /\¬y/\¬z/\¬w).
Stepan wrote down all sets of variables for which this expression is true. How many units did Stepan write? In the answer, write down only an integer - the number of units.
Example. Let an expression x → y be given depending on two variables x and y. This expression is true for three sets: (0, 0), (0, 1) and (1, 1). Stepan wrote 3 units.
Decision
The logical function F is true if at least one expression in the parentheses is true. Since all the variables in them are connected by a conjunction, then each member must be true. Let us write down the true sets for each disjunction.
x /\ y/\¬w – (x=1, y=1, z=1, w=0) and (x=1, y=1, z=0, w=0);
x /\¬y/\¬z/\¬w – x=1, y=1, z=0, w=0.
As a result, we get 6 units.
№7 The logical function F is given by the expression
(x /\ y/\z/\¬w)\/ (x /\¬z/\¬w).
Stepan wrote down all sets of variables for which this expression is true. How many units did Stepan write? In the answer, write down only an integer - the number of units.
Example. Let an expression x → y be given depending on two variables x and y. This expression is true for three sets: (0, 0), (0, 1) and (1, 1). Stepan wrote 3 units.
Decision similar to solution.
№8 The logical function F is given by the expression
(¬x /\ ¬y/\z/\w)\/ (x /\z/\w).
Stepan wrote down all sets of variables for which this expression is true. How many units did Stepan write? In the answer, write down only an integer - the number of units.
Example. Let an expression x → y be given depending on two variables x and y. This expression is true for three sets: (0, 0), (0, 1) and (1, 1). Stepan wrote 3 units.
Decision similar to solution.
№9 The logical function F is given by the expression
(y /\ ¬z /\ ¬w) \/ (¬x /\ ¬y/\¬z/\w).
Stepan wrote down all sets of variables for which this expression is true. How many units did Stepan write? In the answer, write down only an integer - the number of units.
Example. Let an expression x → y be given depending on two variables x and y. This expression is true for three sets: (0, 0), (0, 1) and (1, 1). Stepan wrote 3 units.
Decision similar to solution.
№10 The logical function F is given by the expression
(x /\ y /\ ¬z) \/ (¬x /\ ¬y/\¬z).
Stepan wrote down all sets of variables for which this expression is true. How many units did Stepan write? In the answer, write down only an integer - the number of units.
Example. Let an expression x → y be given depending on two variables x and y. This expression is true for three sets: (0, 0), (0, 1) and (1, 1). Stepan wrote 3 units.
Decision similar to solution.
№11 The logical function F is given by the expression
¬((¬w/\x) → (y /\ z)) \/ ¬((x /\¬ y)→ (¬z\/¬w)).
Stepan wrote down all sets of variables for which this expression is true. How many units did Stepan write? In the answer, write down only an integer - the number of units.
Example. Let an expression x → y be given depending on two variables x and y. This expression is true for three sets: (0, 0), (0, 1) and (1, 1). Stepan wrote 3 units.
Decision
¬((¬w/\x) → (y /\ z)) – (x=1, y=1, z=0, w=0) and (x=1, y=0, z=1, w =0);
¬((x /\¬y)→ (¬z\/¬w)) – (x=1, y=0, z=1, w=1).
As a result, we get 5 units.
№12 The logical function F is given by the expression
¬((¬x\/¬y) → (z \/ w)) \/ ¬((x \/ y)→ (z\/¬w)).
Stepan wrote down all sets of variables for which this expression is true. How many units did Stepan write? In the answer, write down only an integer - the number of units.
Example. Let an expression x → y be given depending on two variables x and y. This expression is true for three sets: (0, 0), (0, 1) and (1, 1). Stepan wrote 3 units.
Decision
The logical function F is true if at least one expression in the parentheses is true. Since all the variables in them are implication, then the condition of its falsity gives the truth of the brackets. Following the example, we write out the true sets for each parenthesis.
¬((¬x\/¬y) → (z \/ w)) – (x=1, y=0, z=0, w=0) and (x=0, y=1, z=0, w=0);
¬((x /\¬y)→ (¬z\/¬w)) – (x=1, y=0, z=0, w=0).
As a result, we get 3 units.
№13 The logical function F is given by the expression
¬(¬(x\/y) → (¬z\/ w)) \/ ¬(¬(x /\ y)→ (z\/¬w)).
Stepan wrote down all sets of variables for which this expression is true. How many units did Stepan write? In the answer, write down only an integer - the number of units.
Example. Let an expression x → y be given depending on two variables x and y. This expression is true for three sets: (0, 0), (0, 1) and (1, 1). Stepan wrote 3 units.
Decision
The logical function F is true if at least one expression in the parentheses is true. Since all the variables in them are implication, then the condition of its falsity gives the truth of the brackets. Following the example, we write out the true sets for each parenthesis.
¬(¬(x\/y) → (¬z\/ w)) – (x=0, y=0, z=1, w=0);
¬(¬(x /\ y)→ (z\/¬w)) – (x=1, y=0, z=0, w=1), (x=0, y=1, z=0, w=1) and
(x=0, y=0, z=0, w=1).
As a result, we get 6 units.
Boolean function F given by the expression x/\ ¬y/\ (¬z\/ w).
The figure shows a fragment of the truth table of the function F, containing all sets of arguments for which the function F true.
Determine which column of the truth table of the function F corresponds to each of the variables w, x, y, z.
Write the letters in your answer. w, x, y, z in the order they go
columns corresponding to them (first - the letter corresponding to the first
column then - the letter corresponding to the second column, etc.) Letters
in the answer, write in a row, put no separators between letters
not necessary.
Demo version of the Unified State Examination of the Unified State Examination of 2017 - task No. 2
Decision:
A conjunction (logical multiplication) is true if and only if all statements are true. Hence the variable X 1 .
variable ¬y must match the column in which all values are equal 0 .
The disjunction (logical addition) of two statements is true if and only if at least one statement is true.
Disjunction ¬z \/ y z=0, w=1.
So the variable ¬z w corresponds to the column with variable 4 (column 4).
Answer: zyxw
Demo version of the Unified State Examination of the Unified State Examination of 2016 - task No. 2
Boolean function F given by (¬z)/\x \/ x/\y. Determine which column of the truth table of the function F corresponds to each of the variables x, y, z.
In your answer, write the letters x, y, z in the order in which the columns corresponding to them go (first - the letter corresponding to the 1st column; then - the letter corresponding to the 2nd column; then - the letter corresponding to the 3rd column) . Write the letters in the answer in a row, you do not need to put any separators between the letters.
Example. Let an expression x → y be given, depending on two variables x and y, and a truth table:
Then the 1st column corresponds to the variable y, and the 2nd column
corresponds to x. In the answer you need to write: yx.
Decision:
1. Write for given expression in simpler notation:
¬z*x + x*y = x*(¬z + y)
2. A conjunction (logical multiplication) is true if and only if all statements are true. Therefore, in order for the function ( F) was equal to one ( 1 ), it is necessary that each multiplier be equal to one ( 1 ). Thus, at F=1, variable X must match the column in which all values are equal 1 .
3. Consider (¬z + y), at F=1 this expression is also equal to 1 (see point 2).
4. A disjunction (logical addition) of two statements is true if and only if at least one statement is true.
Disjunction ¬z \/ y in this line will be true only if
- z = 0; y=0 or y=1;
- z = 1; y=1
5. Variable way ¬z matches column with variable 1 (1 column), variable y
Answer: zyx
KIM Unified State Exam USE 2016 (early period)- task number 2
The logical function F is given by the expression
(x /\ y /\¬z) \/ (x /\ y /\ z) \/ (x /\¬y /\¬z).
The figure shows a fragment of the truth table of the function F, containing all sets of arguments for which the function F is true. Determine which column of the truth table of the function F corresponds to each of the variables x, y, z.
In your answer, write the letters x, y, z in the order in which the columns corresponding to them appear (first - the letter corresponding to the first column; then - the letter corresponding to the second column, etc.) Write the letters in the answer in a row, no separators between letters is not necessary.
R Solution:
Let's write the given expression in simpler notation:
(x*y*¬z) + (x*y*z) + (x*¬y*¬z)=1
This expression is true if at least one of (x*y*¬z) , (x*y*z) , (x*¬y*¬z) is equal to 1. The conjunction (logical multiplication) is true if and only if when all statements are true.
At least one of these disjunctions x*y*¬z; x*y*z; x*¬y*¬z will be true only if x=1.
So the variable X corresponds to the column with variable 2 (column 2).
Let be y- var.1, z- premium 3. Then, in the first case x*¬y*¬z will be true in the second case x*y*¬z, and in the third x*y*z.
Answer: yxz
The symbol F denotes one of the following boolean expressions from three arguments: X, Y, Z. A fragment of the truth table of the expression F is given (see the table on the right). What expression corresponds to F?
| X | Y | Z | F |
| 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
1) X ∧ Y ∧ Z 2) ¬X ∨ Y ∨¬Z 3) X ∧ Y ∨ Z 4) X ∨ Y ∧ ¬Z
Decision:
1) X ∧ Y ∧ Z = 1.0.1 = 0 (does not match on 2nd line)
2) ¬X ∨ Y ∨¬Z = ¬0 ∨ 0 ∨ ¬0 = 1+0+1 = 1 (does not match on the 1st line)
3) X ∧ Y ∨ Z = 0.1+0 = 0 (does not match on line 3)
4) X ∨ Y ∧ ¬Z (corresponding to F)
X ∨ Y ∧ ¬Z = 0 ∨ 0 ∧ ¬0 = 0+0.1 = 0
X ∨ Y ∧ ¬Z = 1 ∨ 0 ∧ ¬1 = 1+0.0 = 1
X ∨ Y ∧ ¬Z = 0 ∨ 1 ∧ ¬0 = 0+1.1 = 1
Answer: 4
A fragment of the truth table of the expression F is given. Which expression corresponds to F?
| A | B | C | F |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
1) (A → ¬B) ∨ C 2) (¬A ∨ B) ∧ C 3) (A ∧ B) → C 4) (A ∨ B) → C
Decision:
1) (A → ¬B) ∨ C = (1 → ¬0) ∨ 0 = (1 → 1) + 0 = 1 + 0 = 1 (does not match on 2nd line)
2) (¬A ∨ B) ∧ C = (¬1 ∨ 0) ∧ 1 = (0+0).1 = 0 (does not match on line 3)
3) (A ∧ B) → C = (1 ∧ 0) → 0 = 0 → 0 = 1 (does not match on 2nd line)
4) (A ∨ B) → C (corresponding to F)
(A ∨ B) → C = (0 ∨ 1) → 1 = 1
(A ∨ B) → C = (1 ∨ 0) → 0 = 0
(A ∨ B) → C = (1 ∨ 0) → 1 = 1
Answer: 4
Given a boolean expression that depends on 6 boolean variables:
X1 ∨ ¬X2 ∨ X3 ∨ ¬X4 ∨ X5 ∨ X6
How many different sets of variable values are there for which the expression is true?
1) 1 2) 2 3) 63 4) 64
Decision:
False expression in only 1 case: X1=0, X2=1, X3=0, X4=1, X5=0, X6=0
X1 ∨ ¬X2 ∨ X3 ∨ ¬X4 ∨ X5 ∨ X6 = 0 ∨ ¬1 ∨ 0 ∨ ¬1 ∨ 0 ∨ 0 = 0
Total options 2 6 \u003d 64, which means true
Answer: 63
A fragment of the truth table of the expression F is given.
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | F |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
What expression corresponds to F?
1) x1 ∨ x2 ∨ ¬x3 ∨ x4 ∨ ¬x5 ∨ x6 ∨ ¬x7
2) x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ x7
3) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ ¬x6 ∧ x7
4) x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7
Decision:
1) x1 ∨ x2 ∨ ¬x3 ∨ x4 ∨ ¬x5 ∨ x6 ∨ ¬x7 = 0 + 1 + … = 1 (does not match on the 1st line)
2) x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ x7 = 0 + 0 + 0 + 0 + 0 + 1 + 0 = 1 (does not match on the 1st line)
3) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ ¬x6 ∧ x7 = 1.0. …= 0 (does not match on 2nd line)
4) x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7 (corresponding to F)
x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7 = 1.1.1.1.1.1.1 = 1
x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7 = 0. … = 0
Answer: 4
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | F |
| 0 | 1 | 1 | ||||||
| 1 | 0 | 1 | 0 | |||||
| 1 | 0 | 1 |
What expression can F be?
1) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7 ∧ ¬x8
2) ¬x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ x8
3) ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ ¬x6 ∧ ¬x7 ∧ ¬x8
4) ¬x1 ∨ ¬x2 ∨ ¬x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ ¬x8
Decision:
1) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7 ∧ ¬x8 = x1 . x2 . 0 . … = 0 (does not match on the 1st line)
2) ¬x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ x8 (corresponding to F)
3) ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ ¬x6 ∧ ¬x7 ∧ ¬x8 = … ¬x7 ∧ ¬x8 = … ¬1 ∧ ¬x8 = … 0 ∧ ¬x8 = 0 (does not correspond to 1- line)
4) ¬x1 ∨ ¬x2 ∨ ¬x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ ¬x8 = ¬x1 ∨ ¬x2 ∨ ¬x3 … = ¬1 ∨ ¬x2 ∨ ¬0 .. = 1 (not matches on the 2nd line)
Answer: 2
A fragment of the truth table for the expression F is given:
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | F |
| 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 | 1 | 0 | 1 |
Indicate the minimum possible number of different rows of the complete truth table of this expression, in which the value x5 is the same as F.
Decision:
Minimum possible number of distinct rows where x5 is the same as F = 4
Answer: 4
A fragment of the truth table for the expression F is given:
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | F |
| 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 |
| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 |
Indicate the maximum possible number of different rows of the complete truth table of this expression in which the value x6 does not match F.
Decision:
Maximum possible number = 2 8 = 256
Maximum possible number of distinct rows where x6 does not match F = 256 - 5 = 251
Answer: 251
A fragment of the truth table for the expression F is given:
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | F |
| 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 | 1 | 0 | 1 |
Indicate the maximum possible number of different rows of the complete truth table of this expression in which the value ¬x5 ∨ x1 is the same as F.
Decision:
1+0=1 - does not match F
0+0=0 - does not match F
0+0=0 - does not match F
0+1=1 - same as F
1+0=1 - same as F
2 7 = 128 – 3 = 125
Answer: 125
Each boolean expression A and B depends on the same set of 6 variables. In the truth tables, each of these expressions has exactly 4 units in the column of values. What is the minimum possible number of ones in the value column of the truth table of the expression A ∨ B?
Decision:
Answer: 4
Each boolean expression A and B depends on the same set of 7 variables. In the truth tables, each of these expressions has exactly 4 units in the column of values. What is the maximum possible number of ones in the value column of the truth table of the expression A ∨ B?
Decision:
Answer: 8
Each boolean expression A and B depends on the same set of 8 variables. In the truth tables, each of these expressions has exactly 5 units in the column of values. What is the minimum possible number of zeros in the value column of the truth table of the expression A ∧ B?
Decision:
2 8 = 256 – 5 = 251
Answer: 251
Each boolean expression A and B depends on the same set of 8 variables. In the truth tables, each of these expressions has exactly 6 units in the column of values. What is the maximum possible number of zeros in the value column of the truth table of the expression A ∧ B?
Decision:
Answer: 256
Each of the boolean expressions A and B depends on the same set of 5 variables. There are no matching rows in the truth tables of both expressions. How many units will be contained in the value column of the truth table of the expression A ∧ B?
Decision:
There are no matching rows in the truth tables of both expressions.
Answer: 0
Each of the logical expressions A and B depends on the same set of 6 variables. There are no matching rows in the truth tables of both expressions. How many units will be contained in the value column of the truth table of the expression A ∨ B?
Decision:
Answer: 64
Each of the logical expressions A and B depends on the same set of 7 variables. There are no matching rows in the truth tables of both expressions. What is the maximum possible number of zeros in the value column of the truth table of the expression ¬A ∨ B?
Decision:
A=1,B=0 => ¬0 ∨ 0 = 0 + 0 = 0
Answer: 128
Each of the logical expressions F and G contains 7 variables. There are exactly 8 identical rows in the truth tables of expressions F and G, and exactly 5 of them have 1 in the value column. How many rows of the truth table for the expression F ∨ G contain 1 in the value column?
Decision:
There are exactly 8 identical rows, and exactly 5 of them have a 1 in the value column.
This means that exactly 3 of them have 0 in the value column.
Answer: 125
The logical function F is given by (a ∧ ¬c) ∨ (¬b ∧ ¬c). Determine which column of the truth table of the function F corresponds to each of the variables a, b, c.
| ? | ? | ? | F |
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
In your answer, write the letters a, b, c in the order in which the corresponding columns appear.
Decision:
(a . ¬c) + (¬b . ¬c)
When c is 1, F is zero so the last column is c.
To determine the first and second columns, we can use the values from the 3rd row.
(a . 1) + (¬b . 1) = 0
Answer: abc
The logical function F is given by (a ∧ c)∨ (¬a ∧ (b ∨ ¬c)). Determine which column of the truth table of the function F corresponds to each of the variables a, b, c.
Based on the fact that with a=0 and c=0, then F=0, and the data from the second row, we can conclude that the third column contains b.
Answer: cab
The logical function F is given by x ∧ (¬y ∧ z ∧ ¬w ∨ y ∧ ¬z). The figure shows a fragment of the truth table of the function F, containing all sets of arguments for which the function F is true. Determine which column of the truth table of the function F corresponds to each of the variables x, y, z, w.
| ? | ? | ? | ? | F |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
In your answer, write the letters x, y, z, w in the order in which the corresponding columns appear.
Decision:
x ∧ (¬y ∧ z ∧ ¬w ∨ y ∧ ¬z)
x . (¬y . z . ¬w . y . ¬z)
Based on the fact that at x=0, then F=0, we can conclude that the second column contains x.
Answer: wxzy
Let's first define what we have in the task:
- logical function F given by some expression. The elements of the truth table of this function are also presented in the problem in the form of a table. Thus, when substituting specific x, y, z values from the table into the expression, the result must match the one given in the table (see explanation below).
- Variables x, y, z and three columns that correspond to them. At the same time, in this problem we do not know which column corresponds to which variable. That is, in the column Variable. 1 can be either x or y or z.
- We are asked just to determine which column corresponds to which variable.
Consider an example.
Decision
- Let's return now to the solution. Let's take a closer look at the formula: \((\neg z) \wedge x \vee x\wedge y\)
- It has two constructions with a conjunction connected by a disjunction. As you know, most often the disjunction is true (for this it is enough that one of the terms is true).
- Let's then carefully consider the lines where the expression F is false.
- The first line is of no interest to us, since it does not determine where what is (all values \u200b\u200bare the same).
- Consider then the penultimate line, it has the most 1, but the result is 0.
- Can z be in the third column? No, since in this case there will be 1 everywhere in the formula, and, therefore, the result will be equal to 1, but according to the truth table, the value of F in this row is 0. Therefore, z cannot be Variable. 3.
- Similarly, for the previous line, we have that z cannot be Variable. 2.
- Hence, z is Variable. one.
- Knowing that z is in the first column, consider the third row. Can x be in the second column? Substitute the values:
\((\neg z) \wedge x \vee x\wedge y = \\ = (\neg 0) \wedge 1 \vee 1\wedge 0 = \\ = 1 \wedge 1 \vee 0 = \\ = 1 \vee 0 = 1\) - However, according to the truth table, the result should be 0.
- Hence, x cannot be var. 2.
- Hence, x is Variable. 3.
- Therefore, according to the elimination method, y is Variable. 2.
- So the answer is: zyx (z - Variable 1, y - Variable 2, x - Variable 3).
Job directory.
Number of programs with a mandatory stage
Take the test for these tasks
Back to job catalog
Version for printing and copying in MS Word
Executor A16 converts the number written on the screen.
The performer has three teams that are assigned numbers:
1. Add 1
2. Add 2
3. Multiply by 2
The first of them increases the number on the screen by 1, the second increases it by 2, the third multiplies it by 2.
The program for the A16 performer is a sequence of commands.
How many programs are there that convert the original number 3 into the number 12 and at the same time the trajectory of the program's calculations contains the number 10?
The trajectory of the program's computations is the sequence of results of the execution of all program commands. For example, for program 132, with the initial number 7, the trajectory will consist of the numbers 8, 16, 18.
Decision.
The desired number of programs is equal to the product of the number of programs that receive the number 10 from the number 3 by the number of programs that receive the number 12 from the number 10.
Let R(n) be the number of programs that convert the number 3 to the number n, and P(n) be the number of programs that convert the number 10 to the number n.
For all n > 5, the following relations are true:
1. If n is not divisible by 2, then R(n) = R(n - 1) + R(n - 2), since there are two ways to get n - by adding one or adding two. Similarly P(n) = P(n - 1) + P(n - 2)
2. If n is divisible by 2 then R(n) = R(n - 1) + R(n - 2) + R(n / 2). Similarly P(n) = P(n - 1) + P(n - 2) + P(n / 2)
Sequentially calculate the values of R(n):
R(5) = R(4) + R(3) = 1 + 1 = 2
R(6) = R(5) + R(4) + R(3) = 2 + 1 + 1 = 4
R(7) = R(6) + R(5) = 4 + 2 = 6
R(8) = R(7) + R(6) + R(4) = 6 + 4 + 1 = 11
R(9) = R(8) + R(7) = 11 + 6 = 17
R(10) = R(9) + R(8) + R(5) = 17 + 11 + 2 = 30
Now we calculate the values of P(n):
P(11) = P(10) = 1
P(12) = P(11) + P(10) = 2
Thus, the number of programs that satisfy the condition of the problem is 30 2 = 60.
Answer: 60.
Answer: 60
Source: Demo version of the USE-2017 in informatics.
1. Add 1
2. Add 3
How many programs are there for which, with the initial number 1, the result is the number 17 and the calculation trajectory contains the number 9? The trajectory of the program's computations is the sequence of results of the execution of all program commands. For example, for program 121, with the initial number 7, the trajectory will consist of the numbers 8, 11, 12.
Decision.
We use the dynamic programming method. create an array dp, where dp[i] is the number of ways to get the number i using such commands.
Dynamic base:
Transition formula:
dp[i]=dp + dp
This does not take into account the values for numbers greater than 9, which can be obtained from numbers less than 9 (thus skipping the trajectory 9):
Answer: 169.
Answer: 169
Source: Training work on INFORMATICS Grade 11 November 29, 2016 Option IN10203
Artist May17 converts the number on the screen.
The performer has two teams that are assigned numbers:
1. Add 1
2. Add 3
The first command increases the number on the screen by 1, the second increases it by 3. The program for the May17 performer is a sequence of commands.
How many programs are there for which, with the initial number 1, the result is the number 15 and the calculation trajectory contains the number 8? The trajectory of program computations is the sequence of results of execution of all program commands. For example, for program 121, with the initial number 7, the trajectory will consist of the numbers 8, 11, 12.
Decision.
We use the dynamic programming method. Let's create an array dp, where dp[i] is the number of ways to get the number i using such commands.
Dynamic base:
Transition formula:
dp[i]=dp + dp
But this does not take into account such numbers that are greater than 8, but we can get to them from a value less than 8. Next, the values \u200b\u200bin dp from 1 to 15 will be given: 1 1 1 2 3 4 6 9 9 9 18 27 36 54 81 .
