The logical function f is given by the expression z. The logical function F is given by the expression
Let's first define what we have in the problem:
- a logical function F defined 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 values of x, y, z from the table into the expression, the result should coincide with the one given in the table (see explanation below).
- The variables x, y, z and the three columns that correspond to them. Moreover, in this problem we do not know which column corresponds to which variable. That is, in the column Variable. 1 can be either x, y or z.
- We are asked to determine which column corresponds to which variable.
Let's look at an example.
Solution
- 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 contains two constructions with a conjunction, connected by a disjunction. As is known, most often the disjunction is true (for this it is enough that one of the terms is true).
- Let's then look carefully at the lines where the expression F is false.
- The first line is not interesting to us, since it does not determine where what is (all values are the same).
- Let us then consider the penultimate line, it contains most of 1, but the result is 0.
- Can z be in the third column? No, because in this case there will be 1s 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. 1.
- Knowing that z is in the first column, consider the third row. Can x be in the second column? Let's 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 must be 0.
- Hence, x cannot be Per. 2.
- Hence, x is Variable. 3.
- Therefore, by the method of elimination, y is Variable. 2.
- Thus, the answer is as follows: zyx (z - Variable 1, y - Variable 2, x - Variable 3).
Based on: demo versions of the Unified State Exam in computer science for 2015, on the textbook by Lyudmila Leonidovna Bosova
In the previous part 1, we discussed with you the logical operations Disjunction and Conjunction, all that remains for us is to analyze inversion and move on to solving the Unified State Exam task.
Inversion
Inversion — logical operation, which corresponds to each statement with a new statement, the meaning of which is opposite to the original one.
The following characters are used to write inversion: NOT, `¯`, ` ¬ `
The inversion is determined by the following truth table:
Inversion is otherwise called logical negation.
Any complex statement can be written in the form logical expression— expressions containing logical variables, logical operator signs and parentheses. Logical operations in a logical expression are performed in the following order: inversion, conjunction, disjunction. You can change the order of operations using parentheses.
Logical operations have the following priority: inversion, conjunction, disjunction.
And so, before us is task No. 2 from the Unified State Exam in computer science 2015
Alexandra was filling out the truth table for the expression F. She only managed to fill out a small fragment of the table:
x1 x2 x3 x4 x5 x6 x7 x8 F 0 1 0 1 0 1 1 1 1 What expression can F be?
What makes solving the problem much easier is that in each version of the complex expression F there is only one logical operation: multiplication or addition. In case of multiplication /\ if at least one variable is equal to zero, then the value of the entire expression F must also be equal to zero. And in the case of addition V, if at least one variable is equal to one, then the value of the entire expression F must be equal to 1.
The data that is in the table for each of the 8 variables of the expression F is quite enough for us to solve.
Let's check expression number 1:
- ? /\ 1 /\ ? /\ ? /\ ? /\ ? /\ ? /\ 0 )
- from the second line of the table x1=1, x4=0 we see that F is possible and can be equal to = 1 if all other variables are equal to 1 (1 /\ ? /\ ? /\ 1 /\ ? /\ ? /\ ? /\ ? )
- according to the third line of the table x4=1, x8=1 we see that F=0 (? /\ ? /\ ? /\ 0 /\ ? /\ ? /\ ? /\ 0 ), and in the table we have F=1, and this means that expression number one is for us DEFINITELY NOT SUITABLE.
Let's check expression number 2:
- from the first line of the table x2=0, x8=1 we see that F is possible and can be equal to = 0 if all other variables are equal to 0 (? V 0 V ? V ? V ? V ? V ? V 0 )
- from the second line of the table x1=1, x4=0 we see that F = 1 ( 1 V ? V ? V 1 V ? V ? V ? V ? )
- according to the third line of the table x4=1, x8=1 we see that F is possible and can be equal to = 1 if at least one of the remaining variables is equal to 1 ( ?
V ?
V ?
V 0
V ?
V ?
V ?
V 0
)
Let's check expression number 3:
- from the first line of the table x2=0, x8=1 we see that F=0 (? /\ 0 /\ ? /\ ? /\ ? /\ ? /\ ? /\ 1 )
- from the second line of the table x1=1, x4=0 we see that F =0 (0 /\ ? /\ ? /\ 0 /\ ? /\ ? /\ ? /\ ? ), and in the table we have F=1, and this means that expression number three gives us DEFINITELY NOT SUITABLE.
Let's check expression number 4:
- from the first line of the table x2=0, x8=1 we see that F=1 ( ? V 1 V ? V ? V ? V ? V ? V 0 ), and in the table we have F=0, and this means that expression number four gives us DEFINITELY NOT SUITABLE.
When solving a task on the unified state exam, you need to do exactly the same thing: discard those options that are definitely not suitable based on the data in the table. The remaining possible option (as in our case, option number 2) will be the correct answer.
Logic function F is 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 function's truth table F each of the variables corresponds w, x, y, z.
Write the letters in your answer w, x, y, z in the order they come
their corresponding columns (first – the letter corresponding to the first
column; then – the letter corresponding to the second column, etc.) Letters
In your answer, write in a row, no separators between letters.
no need.
Demo version of the Unified State Examination USE 2017 – task No. 2
Solution:
A conjunction (logical multiplication) is true if and only if all statements are true. Therefore the variable X 1 .
Variable ¬y must match the column in which all values are equal 0 .
A 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.
Thus, the variable ¬z w corresponds to the column with variable 4 (column 4).
Answer: zyxw
Demo version of the Unified State Examination USE 2016 – task No. 2
Logic function F is given by the expression (¬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 their corresponding columns appear (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; there is no 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 the variable x. In the answer you need to write: yx.
Solution:
1. Let's write it down for this expression in simpler notation:
¬z*x + x*y = x*(¬z + y)
2. Conjunction (logical multiplication) is true if and only if all statements are true. Therefore, so that the function ( F) was equal to one ( 1 ), it is necessary that each factor be equal to one (1 ). Thus, when 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. 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. Thus, the variable ¬z corresponds to column with variable 1 (1 column), variable y
Answer: zyx
KIM Unified State Examination Unified State Exam 2016 (early period)– task No. 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 their corresponding columns 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 There is no need to put it between letters.
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 when at least one of (x*y*¬z), (x*y*z), (x*¬y*¬z) equals 1. 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.
Thus, the variable X corresponds to the column with variable 2 (column 2).
Let y- variable 1, z- prem.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 indicates one of the following: logical 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). Which expression matches 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
Solution:
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 the 3rd line)
4) X ∨ Y ∧ ¬Z (corresponds 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
Given a fragment of the truth table of the expression F. 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
Solution:
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 the 3rd line)
3) (A ∧ B) → C = (1 ∧ 0) → 0 = 0 → 0 = 1 (does not match on 2nd line)
4) (A ∨ B) → C (corresponds 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
A logical expression is given that depends on 6 logical 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
Solution:
False expression only in 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
There are 2 6 =64 options in total, 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 |
Which expression matches 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
Solution:
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 (corresponds 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
Solution:
1) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7 ∧ ¬x8 = x1 . ¬x2. 0 . ... = 0 (does not match on 1st line)
2) ¬x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ x8 (corresponds to F)
3) ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ ¬x6 ∧ ¬x7 ∧ ¬x8 = … ¬x7 ∧ ¬x8 = … ¬1 ∧ ¬x8 = … 0 ∧ ¬x8 = 0 (does not match on 1- th 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
Given is a fragment of the truth table for the expression F:
| 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 |
Find the minimum possible number of different rows in the complete truth table of this expression in which the value x5 matches F.
Solution:
Minimum possible number of distinct rows in which x5 matches F = 4
Answer: 4
Given is a fragment of the truth table for the expression F:
| 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 |
Find the maximum possible number of distinct rows in the complete truth table of this expression in which the value x6 does not coincide with F.
Solution:
Maximum possible number = 2 8 = 256
The maximum possible number of different rows in which the value x6 does not match F = 256 – 5 = 251
Answer: 251
Given is a fragment of the truth table for the expression F:
| 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 |
Find the maximum possible number of different rows of the complete truth table of this expression in which the value ¬x5 ∨ x1 coincides with F.
Solution:
1+0=1 – does not match F
0+0=0 – does not match F
0+0=0 – does not match F
0+1=1 – coincides with 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 value column. What is the minimum possible number of ones in the value column of the truth table of the expression A ∨ B?
Solution:
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 value column. What is the maximum possible number of ones in the value column of the truth table of the expression A ∨ B?
Solution:
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 value column. What is the minimum possible number of zeros in the value column of the truth table of the expression A ∧ B?
Solution:
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 value column. What is the maximum possible number of zeros in the value column of the truth table of the expression A ∧ B?
Solution:
Answer: 256
The Boolean expressions A and B each depend on the same set of 5 variables. There are no matching rows in the truth tables of both expressions. How many ones will be contained in the value column of the truth table of the expression A ∧ B?
Solution:
There are no matching rows in the truth tables of both expressions.
Answer: 0
The Boolean expressions A and B each depend on the same set of 6 variables. There are no matching rows in the truth tables of both expressions. How many ones will be contained in the value column of the truth table of the expression A ∨ B?
Solution:
Answer: 64
Each of the Boolean 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?
Solution:
A=1,B=0 => ¬0 ∨ 0 = 0 + 0 = 0
Answer: 128
Each of the Boolean expressions F and G contains 7 variables. There are exactly 8 identical rows in the truth tables of the expressions F and G, and exactly 5 of them have a 1 in the value column. How many rows of the truth table for the expression F ∨ G contain a 1 in the value column?
Solution:
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 a 0 in the value column.
Answer: 125
The logical function F is given by the expression (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 their corresponding columns appear.
Solution:
(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 the expression (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 when 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 their corresponding columns appear.
Solution:
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
Demo Unified State Exam option 2019 – task No. 2
Misha filled out the truth table of the function (¬x /\ ¬y) \/ (y≡z) \/ ¬w, but only managed to fill out a fragment of three different lines, without even indicating which column of the table corresponds to each of the variables w, x ,
y, z.
Determine which table column each variable w, x, y, z corresponds to.
In your answer, write the letters w, x, y, z in the order in which their corresponding columns appear (first the letter corresponding to the first column; then the letter corresponding to the second column, etc.). Letters
In your answer, write in a row; there is no need to put any separators between the letters.
Example. If the function were given by the expression ¬x \/ y, depending on two variables, and the table fragment would look like
then the first column would correspond to the variable y, and the second column would correspond to the variable x. The answer should have been written yx.
(¬x ¬y)+(y≡z)+¬w=0
w=1 w must be true; w - last
y and z must be different, so before the latter, it is x. the first two are y and z or z and y.
y and x cannot be false at the same time. The first is z.
Answer: zyxw
Demonstration version of the Unified State Exam 2018 – task No. 2
The logical function F is 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 is false. Determine which column of the truth table of function F corresponds to each of the variables w, x, y, z
In your answer, write the letters w, x, y, z in the order in which their corresponding columns 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, There is no need to put any separators between 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 is true.
Then the first column would correspond to the variable y, and the second column would correspond to the variable x. The answer should have been written: yx.
Answer: xzwy
Logic function F is 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 function's truth table F each of the variables corresponds w, x, y, z.
Write the letters in your answer w, x, y, z in the order they come
their corresponding columns (first – the letter corresponding to the first
column; then – the letter corresponding to the second column, etc.) Letters
In your answer, write in a row, no separators between letters.
no need.
Demonstration version of the Unified State Exam 2017 - task No. 2
Solution:
A conjunction (logical multiplication) is true if and only if all statements are true. Therefore the variable X 1 .
Variable ¬y must match the column in which all values are equal 0 .
A 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.
Thus, the variable ¬z w corresponds to the column with variable 4 (column 4).
Answer: zyxw
Demonstration version of the Unified State Exam 2016 - task No. 2
Logic function F is given by the expression (¬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 their corresponding columns appear (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; there is no 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 the variable x. In the answer you need to write: yx.
Solution:
1. Let's write the given expression in simpler notation:
¬z*x + x*y = x*(¬z + y)
2. Conjunction (logical multiplication) is true if and only if all statements are true. Therefore, so that the function ( F) was equal to one ( 1 ), each factor must be equal to one ( 1 ). Thus, when 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. 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. Thus, the variable ¬z corresponds to column with variable 1 (1 column), variable y
Answer: zyx
KIM Unified State Exam 2016 (early period)– task No. 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 their corresponding columns 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 There is no need to put it between letters.
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 when at least one of (x*y*¬z), (x*y*z), (x*¬y*¬z) equals 1. 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.
Thus, the variable X corresponds to the column with variable 2 (column 2).
Let y- variable 1, z- prem.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 logical 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). Which expression matches 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
Solution:
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 the 3rd line)
4) X ∨ Y ∧ ¬Z (corresponds 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
Given a fragment of the truth table of the expression F. 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
Solution:
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 the 3rd line)
3) (A ∧ B) → C = (1 ∧ 0) → 0 = 0 → 0 = 1 (does not match on 2nd line)
4) (A ∨ B) → C (corresponds 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
A logical expression is given that depends on 6 logical 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
Solution:
False expression only in 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
There are 2 6 =64 options in total, 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 |
Which expression matches 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
Solution:
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 (corresponds 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
Solution:
1) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7 ∧ ¬x8 = x1 . ¬x2. 0 . ... = 0 (does not match on 1st line)
2) ¬x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ x8 (corresponds to F)
3) ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ ¬x6 ∧ ¬x7 ∧ ¬x8 = … ¬x7 ∧ ¬x8 = … ¬1 ∧ ¬x8 = … 0 ∧ ¬x8 = 0 (does not match on 1- th 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
Given is a fragment of the truth table for the expression F:
| 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 |
Find the minimum possible number of different rows in the complete truth table of this expression in which the value x5 matches F.
Solution:
Minimum possible number of distinct rows in which x5 matches F = 4
Answer: 4
Given is a fragment of the truth table for the expression F:
| 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 |
Find the maximum possible number of distinct rows in the complete truth table of this expression in which the value x6 does not coincide with F.
Solution:
Maximum possible number = 2 8 = 256
The maximum possible number of different rows in which the value x6 does not match F = 256 - 5 = 251
Answer: 251
Given is a fragment of the truth table for the expression F:
| 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 |
Find the maximum possible number of different rows of the complete truth table of this expression in which the value ¬x5 ∨ x1 coincides with F.
Solution:
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 value column. What is the minimum possible number of ones in the value column of the truth table of the expression A ∨ B?
Solution:
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 value column. What is the maximum possible number of ones in the value column of the truth table of the expression A ∨ B?
Solution:
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 value column. What is the minimum possible number of zeros in the value column of the truth table of the expression A ∧ B?
Solution:
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 value column. What is the maximum possible number of zeros in the value column of the truth table of the expression A ∧ B?
Solution:
Answer: 256
The Boolean expressions A and B each depend on the same set of 5 variables. There are no matching rows in the truth tables of both expressions. How many ones will be contained in the value column of the truth table of the expression A ∧ B?
Solution:
There are no matching rows in the truth tables of both expressions.
Answer: 0
The Boolean expressions A and B each depend on the same set of 6 variables. There are no matching rows in the truth tables of both expressions. How many ones will be contained in the value column of the truth table of the expression A ∨ B?
Solution:
(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 the expression (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.
| ? | ? | ? | F | |
| 0 | 0 | 0 | 1 | |
| 0 | 0 | 1 | 1 | |
| 0 | 1 | 0 | 0 | |
| 0 | 1 | 1 | 0 | |
| 1 | 0 | 0 | 0 | |
| 1 | 0 | 1 | 1 | |
| 1 | 1 | 0 | 1 | ¬a. b0 |
| 1 | 1 | 1 |
Based on the fact that when 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 their corresponding columns appear.
Solution:
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
