2. Таблица истинности логической функции
Логическая функция F задаётся выражением x /\ ¬y /\ (¬z \/ w).
На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F истинна.
Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут
соответствующие им столбцы (сначала – буква, соответствующая первому
столбцу; затем – буква, соответствующая второму столбцу, и т.д.) Буквы
в ответе пишите подряд, никаких разделителей между буквами ставить
не нужно.
Демонстрационный вариант Единый государственный экзамен ЕГЭ 2017 г. – задание№2
Решение:
Конъюнкция (логическое умножение) истинна тогда и только тогда, когда истинны все высказывания. Следовательно переменной х должен соответствовать тот столбец, в котором все значения равны 1.
Переменной ¬y должен соответствовать тот столбец, в котором все значения равны 0.
Дизъюнкция (логическое сложение) двух высказываний истинна тогда и только тогда, когда истинно хотя бы одно высказывание.
Дизъюнкция ¬z \/ y в данной строке будет истинна только если z=0, w=1.
Таким образом, переменной ¬z соответствует столбец с переменной 1 (1 столбец), переменной w соответствует столбец с переменной 4 (4 столбец).
Ответ: zyxw
Демонстрационный вариант Единый государственный экзамен ЕГЭ 2016 г. – задание№2
Логическая функция F задаётся выражением (¬z)/\x \/ x/\y. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z.
В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала – буква, соответствующая 1-му столбцу; затем – буква, соответствующая 2-му столбцу; затем – буква, соответствующая 3-му столбцу). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и таблица истинности:
Тогда 1-му столбцу соответствует переменная y, а 2-му столбцу
соответствует переменная x. В ответе нужно написать: yx.
Ответ:
Решение:
1. Запишем заданное выражение в более простых обозначениях:
¬z*x + x*y = x*(¬z + y)
2. Конъюнкция (логическое умножение) истинна тогда и только тогда, когда истинны все высказывания. Следовательно, чтобы функция (F) была равна единице (1), нужно, чтобы каждый множитель был равен единице (1). Таким образом, при F = 1, переменной х должен соответствовать тот столбец, в котором все значения равны 1.
3. Рассмотрим (¬z + y), при F = 1 данное выражение также равно 1(см. пункт 2).
4. Дизъюнкция (логическое сложение) двух высказываний истинна тогда и только тогда, когда истинно хотя бы одно высказывание.
Дизъюнкция ¬z \/ y в данной строке будет истинна только если
- z = 0; y = 0 или y = 1;
- z = 1; y = 1
5. Таким образом, переменной ¬z соответствует столбец с переменной 1 (1 столбец), переменной y соответствует столбец с переменной 2 (2 столбец).
Ответ: zyx
КИМ Единый государственный экзамен ЕГЭ 2016 (досрочный период) – задание№2
Логическая функция F задаётся выражением
(x /\ y /\¬z) \/ (x /\ y /\ z) \/ (x /\¬y /\¬z).
На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F истинна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z.
В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала – буква, соответствующая первому столбцу; затем – буква, соответствующая второму столбцу, и т.д.) Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Решение:
Запишем заданное выражение в более простых обозначениях:
(x*y*¬z) + (x*y*z) + (x*¬y*¬z)=1
Это выражение истинно тогда, когда хотя бы один из (x*y*¬z) , (x*y*z) , (x*¬y*¬z) равняется 1. Конъюнкция (логическое умножение) истинна тогда и только тогда, когда истинны все высказывания.
Хотя бы одна из этих дизъюнкции x*y*¬z; x*y*z; x*¬y*¬z будет истинна только если х=1.
Таким образом, переменной х соответствует столбец с переменной 2 (2 столбец).
Пусть y- перем.1, z- прем.3. Тогда, в первом случае x*¬y*¬z будет истинна, во втором случае x*y*¬z , а в третьем x*y*z.
Ответ: yxz
Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F (см. таблицу справа). Какое выражение соответствует 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
Решение:
1) X ∧ Y ∧ Z = 1.0.1 = 0 (не соответствует на 2-й строке)
2) ¬X ∨ Y ∨¬Z = ¬0 ∨ 0 ∨ ¬0 = 1+0+1 = 1 (не соответствует на 1-й строке)
3) X ∧ Y ∨ Z = 0.1+0 = 0 (не соответствует на 3-й строке)
4) X ∨ Y ∧ ¬Z (соответствует 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
Ответ: 4
Дан фрагмент таблицы истинности выражения F. Какое выражение соответствует 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
Решение:
1) (A → ¬B) ∨ C = (1 → ¬0) ∨ 0 = (1 → 1) + 0 = 1 + 0 = 1 (не соответствует на 2-й строке)
2) (¬A ∨ B) ∧ C = (¬1 ∨ 0) ∧ 1 = (0+0).1 = 0 (не соответствует на 3-й строке)
3) (A ∧ B) → C = (1 ∧ 0) → 0 = 0 → 0 = 1 (не соответствует на 2-й строке)
4) (A ∨ B) → C (соответствует F)
(A ∨ B) → C = (0 ∨ 1) → 1 = 1
(A ∨ B) → C = (1 ∨ 0) → 0 = 0
(A ∨ B) → C = (1 ∨ 0) → 1 = 1
Ответ: 4
Дано логическое выражение, зависящее от 6 логических переменных:
X1 ∨ ¬X2 ∨ X3 ∨ ¬X4 ∨ X5 ∨ X6
Сколько существует различных наборов значений переменных, при которых выражение истинно?
1) 1 2) 2 3) 63 4) 64
Решение:
Ложное выражение только в 1 случае: 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
Всего вариантов 26=64, значит истинных
64-1 = 63
Ответ: 63
Дан фрагмент таблицы истинности выражения F.
| 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 |
Какое выражение соответствует 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
Решение:
1) x1 ∨ x2 ∨ ¬x3 ∨ x4 ∨ ¬x5 ∨ x6 ∨ ¬x7 = 0 + 1 + … = 1 (не соответствует на 1-й строке)
2) x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ x7 = 0 + 0 + 0 + 0 + 0 + 1 + 0 = 1 (не соответствует на 1-й строке)
3) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ ¬x6 ∧ x7 = 1.0. …= 0 (не соответствует на 2-й строке)
4) x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7 (соответствует F)
x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7 = 0. … = 0
x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7 = 1.1.1.1.1.1.1 = 1
x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7 = 0. … = 0
Ответ: 4
Дан фрагмент таблицы истинности для выражения F:
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | F |
| 0 | 1 | 1 | ||||||
| 1 | 0 | 1 | 0 | |||||
| 1 | 0 | 1 |
Каким выражением может быть F?
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
Решение:
1) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7 ∧ ¬x8 = x1 . ¬x2 . 0 . … = 0 (не соответствует на 1-й строке)
2) ¬x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ x8 (соответствует F)
3) ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ ¬x6 ∧ ¬x7 ∧ ¬x8 = … ¬x7 ∧ ¬x8 = … ¬1 ∧ ¬x8 = … 0 ∧ ¬x8 = 0 (не соответствует на 1-й строке)
4) ¬x1 ∨ ¬x2 ∨ ¬x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ ¬x8 = ¬x1 ∨ ¬x2 ∨ ¬x3 … = ¬1 ∨ ¬x2 ∨ ¬0 .. = 1 (не соответствует на 2-й строке)
Ответ: 2
Дан фрагмент таблицы истинности для выражения 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 |
Укажите минимально возможное число различных строк полной таблицы истинности этого выражения, в которых значение x5 совпадает с F.
Решение:
Минимально возможное число различных строк, в которых значение x5 совпадает с F = 4
Ответ: 4
Дан фрагмент таблицы истинности для выражения 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 |
Укажите максимально возможное число различных строк полной таблицы истинности этого выражения, в которых значение x6 не совпадает с F.
Решение:
Максимально возможное число = 28 = 256
Максимально возможное число различных строк, в которых значение x6 не совпадает с F = 256 – 5 = 251
Ответ: 251
Дан фрагмент таблицы истинности для выражения 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 |
Укажите максимально возможное число различных строк полной таблицы истинности этого выражения, в которых значение ¬x5 ∨ x1 совпадает с F.
Решение:
¬x5 ∨ x1
1+0=1 – не совпадает с F
0+0=0 – не совпадает с F
0+0=0 – не совпадает с F
0+1=1 – совпадает с F
1+0=1 – совпадает с F
27 = 128 – 3 = 125
Ответ: 125
Каждое логическое выражение A и B зависит от одного и того же набора из 6 переменных. В таблицах истинности каждого из этих выражений в столбце значений стоит ровно по 4 единицы. Каково минимально возможное число единиц в столбце значений таблицы истинности выражения A ∨ B?
Решение:
4&4 = 4
Ответ: 4
Каждое логическое выражение A и B зависит от одного и того же набора из 7 переменных. В таблицах истинности каждого из этих выражений в столбце значений стоит ровно по 4 единицы. Каково максимально возможное число единиц в столбце значений таблицы истинности выражения A ∨ B?
Решение:
4+4 = 8
Ответ: 8
Каждое логическое выражение A и B зависит от одного и того же набора из 8 переменных. В таблицах истинности каждого из этих выражений в столбце значений стоит ровно по 5 единиц. Каково минимально возможное число нулей в столбце значений таблицы истинности выражения A ∧ B?
Решение:
28 = 256 – 5 = 251
Ответ: 251
Каждое логическое выражение A и B зависит от одного и того же набора из 8 переменных. В таблицах истинности каждого из этих выражений в столбце значений стоит ровно по 6 единиц. Каково максимально возможное число нулей в столбце значений таблицы истинности выражения A ∧ B?
Решение:
28 = 256
Ответ: 256
Каждое из логических выражений A и B зависит от одного и того же набора из 5 переменных. В таблицах истинности обоих выражений нет ни одной совпадающей строки. Сколько единиц будет содержаться в столбце значений таблицы истинности выражения A ∧ B?
Решение:
В таблицах истинности обоих выражений нет ни одной совпадающей строки.
1.0 = 0
0.1 = 0
Ответ: 0
Каждое из логических выражений A и B зависит от одного и того же набора из 6 переменных. В таблицах истинности обоих выражений нет ни одной совпадающей строки. Сколько единиц будет содержаться в столбце значений таблицы истинности выражения A ∨ B?
Решение:
26 = 64
Ответ: 64
Каждое из логических выражений A и B зависит от одного и того же набора из 7 переменных. В таблицах истинности обоих выражений нет ни одной совпадающей строки. Каково максимально возможное число нулей в столбце значений таблицы истинности выражения ¬A ∨ B?
Решение:
¬A ∨ B
A=1,B=0 => ¬0 ∨ 0 = 0 + 0 = 0
27 = 128
Ответ: 128
Каждое из логических выражений F и G содержит 7 переменных. В таблицах истинности выражений F и G есть ровно 8 одинаковых строк, причем ровно в 5 из них в столбце значений стоит 1. Сколько строк таблицы истинности для выражения F ∨ G содержит 1 в столбце значений?
Решение:
Есть ровно 8 одинаковых строк, причем ровно в 5 из них в столбце значений стоит 1.
Это означает, что ровно в 3 из них в столбце значений стоит 0.
27 = 128
128 – 3 = 125
Ответ: 125
Логическая функция F задаётся выражением (a ∧ ¬c) ∨ (¬b ∧ ¬c). Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных 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 |
В ответе напишите буквы a, b, c в том порядке, в котором идут соответствующие им столбцы.
Решение:
(a . ¬c) + (¬b . ¬c)
Когда с равно 1, F равна нулю так что последний столбец c.
Xтобы определить первый и второй столбцы, мы можем использовать значения из 3-го ряда.
0, 1,C=0, F=0
(a . 1) + (¬b . 1) = 0
a=0, b=1.
Ответ: abc
Логическая функция F задаётся выражением (a ∧ c)∨ (¬a ∧ (b ∨ ¬c)). Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных 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 |
| 1 | 1 | 1 | 1 |
В ответе напишите буквы a, b, c в том порядке, в котором идут соответствующие им столбцы.
Решение:
(a ∧ c) ∨ (¬a ∧ (b ∨ ¬c))
(a ∧ c) ∨ ¬a ∧ b ∨ ¬a ∧ ¬c
a.c + ¬a.¬c + ¬a. b
a.c + ¬a.¬c
| a | c | F | ||
| 0 | 0 | 1 | ||
| 0 | 1 | 0 | ¬a. b | b |
| 1 | 0 | 0 | ¬a. b | 0 |
| 1 | 1 | 1 |
Исходя из того, что при a=0 и c=0, то F=0, и данных из второй строки, мы можем сделать вывод, что в третьем стоблце располагается b.
Ответ: cab
Логическая функция F задаётся выражением x ∧ (¬y ∧ z ∧ ¬w ∨ y ∧ ¬z). На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F истинна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.
| ? | ? | ? | ? | F |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы.
Решение:
x ∧ (¬y ∧ z ∧ ¬w ∨ y ∧ ¬z)
x . (¬y . z . ¬w . y . ¬z)
Исходя из того, что при x=0, то F=0, мы можем сделать вывод, что во втором столбце располагается x.
Ответ: wxzy