Логические уравнения (23 задание)
Логика – наиболее сложная часть ЕГЭ. В предыдущей статье уже были рассмотрены логические задачи (№18 кодификатора ЕГЭ). По многочисленным просьбам сделать новый разбор задания повышенной сложности, была написана эта статья, которая поможет во всем разобраться.
Задания из 23 номера можно разделить на 3 большие группы:
1. Системы логических уравнений, содержащие однотипные уравнения;
2. Логические уравнения;
3. Системы логических уравнений, содержащие неоднотипные уравнения.
1. Системы логических уравнений, содержащие однотипные уравнения.
1.1. Сколько существует различных наборов значений логических переменных x1, х2, х3, х4, х5, х6, которые удовлетворяют всем перечисленным ниже условиям?
(x1 —> х2) —> (х3—> х4) = 1
(х3 —> х4) —> (х5 —> х6) = 1
В ответе не нужно перечислять все различные наборы значений переменных x1, х2, х3, х4, х5, х6, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Пусть (x1 —> х2) = a, (х3 —> х4) = b, (х5 —> х6) = c
Построим таблицу истинности. Импликация истина при всех значениях логических переменных, кроме случая, когда из истины следует ложь:
|
a |
b |
c |
|
0 |
0 |
0 |
|
0 |
0 |
1 |
|
0 |
1 |
1 |
|
1 |
1 |
1 |
Истинность импликации достигается в трех случаях, а ложь – в одном. Значит, количество возможных вариантов:
1 * 1 * 1 = 1 для первой строки таблицы
1 * 1 * 3 = 3 для второй строки таблицы
1 * 3 * 3 = 9 для третьей строки таблицы
3 * 3 * 3 = 27 для четвертой строки таблицы
Следовательно, количество всех возможных вариантов равно сумме 1 + 3 + 9+ 27 = 40.
Ответ: 40
1.2. Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, которые удовлетворяют всем перечисленным ниже условиям?
(x1≡x2) —> (x2≡x3) = 1
(x2≡x3) —> (x3≡x4) = 1
(x3≡x4) —> (x4≡x5) = 1
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, x5 при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Отметим, что в данном случае переменные зависимы.
Данное уравнение истинно при следующих значениях переменных:
|
№ строки |
x1≡x2 |
x2≡x3 |
x3≡x4 |
x4≡x5 |
|
1 |
0 |
0 |
0 |
0 |
|
2 |
0 |
0 |
0 |
1 |
|
3 |
0 |
0 |
1 |
1 |
|
4 |
0 |
1 |
1 |
1 |
|
5 |
1 |
1 |
1 |
1 |
Таким образом, есть пять наборов тождеств, при которых данное уравнение принимает значения истинности.
Теперь рассмотрим, при каких значениях переменных данное уравнение принимает значение истинности для каждой строки из верхней таблицы.
|
№ строки |
x1 |
x2 |
x3 |
x4 |
x5 |
|
1 |
0 |
1 |
0 |
1 |
0 |
|
1 |
0 |
1 |
0 |
1 |
|
|
2 |
0 |
1 |
0 |
1 |
0 |
|
1 |
0 |
1 |
0 |
1 |
|
|
3 |
0 |
1 |
0 |
1 |
0 |
|
1 |
0 |
1 |
0 |
1 |
|
|
4 |
0 |
1 |
0 |
1 |
0 |
|
1 |
0 |
1 |
0 |
1 |
|
|
5 |
0 |
1 |
0 |
1 |
1 |
|
1 |
0 |
1 |
0 |
0 |
Количество наборов равно количеству строк — 10.
Ответ: 10
Источник: Основная волна. ЕГЭ-2018 по информатике 30.05.2013. Дальний Восток. Вариант 1
1.3. Сколько существует различных наборов значений логических переменных x1, x2, ... x8, которые удовлетворяют всем перечисленным ниже условиям?
((x1 ≡ x2) ∨ (x3 ≡ x4)) ∧ (¬(x1 ≡ x2) ∨ ¬(x3 ≡ x4)) = 1
((x3 ≡ x4) ∨ (x5 ≡ x6)) ∧ (¬(x3 ≡ x4) ∨ ¬(x5 ≡ x6)) = 1
((x5 ≡ x6) ∨ (x7 ≡ x8)) ∧ (¬(x5 ≡ x6) ∨ ¬(x7 ≡ x8)) = 1
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, … x8 при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Пусть (x1 ≡ x2) = а, (x3 ≡ x4) = b, (x5 ≡ x6) = c, (x7 ≡ x8) = d. Тогда:
*(a | b) & (¬a | ¬b) = 1
(b | c) & (¬b | ¬c) =1
(c | d) & (¬c | ¬d) =1
Рассмотрим уравнение *. По законам де Моргана ¬a | ¬b = ¬(a&b). Рассмотрим для него таблицу истинности:
|
a |
b |
a | b |
a&b |
¬(a&b) |
* |
|
0 |
0 |
0 |
0 |
1 |
0 |
|
0 |
1 |
1 |
0 |
1 |
1 |
|
1 |
0 |
1 |
0 |
1 |
1 |
|
1 |
1 |
1 |
1 |
0 |
0 |
Заметим закономерность. Истинность достигается при a ≠ b.
Следовательно, получаем систему:
a ≠ b
b ≠ c
c ≠ d
|
№ строки |
a |
b |
c |
d |
|
1 |
0 |
1 |
0 |
1 |
|
2 |
1 |
0 |
1 |
0 |
Производим обратную замену для тождеств:
|
№ строки |
x1 ≡ x2 |
x3 ≡ x4 |
x5 ≡ x6 |
x7 ≡ x8 |
|
1 |
0 |
1 |
0 |
1 |
|
2 |
1 |
0 |
1 |
0 |
Рассмотрим, в скольких случаях выполняется 1 строка: эквивалентность принимает значение 0 в 2 случаях, 1 – также в 2. Т.е. 2 * 2 * 2 * 2 = 16.
Аналогично вторая строка. Количество различных наборов = 16. Сумма = 32.
Ответ: 32
Источник: Основная волна. ЕГЭ-2018 по информатике 30.05.2013. Центр. Вариант 1
1.4. Сколько существует различных наборов значений логических переменных x1, x2, ... x10, которые удовлетворяют всем перечисленным ниже условиям?
*¬(x1 ≡ x2) ∧ (x1 ∨ x3) ∧ (¬x1∨ ¬x3) = 0
¬(x2 ≡ x3) ∧ (x2∨ x4) ∧ (¬x2∨ ¬x4) = 0
...
¬(x8 ≡ x9) ∧ (x8 ∨ x10) ∧ (¬x8∨ ¬x10) = 0
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, … x10 при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Составим таблицу истинности для первого уравнения системы:
|
x1 |
x2 |
x3 |
(x1 ≡ x2) |
¬(x1 ≡ x2) |
(x1 ∨ x3) |
¬x1 |
¬x3 |
(¬x1∨¬x3) |
* |
|
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
|
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
|
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
|
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
|
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
|
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
|
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
|
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
Проанализируем таблицу, строки четвертую и пятую. Можно заметить, что данное уравнение не ложно при выполнении следующих условий:
x1 ≠ x2
x2 ≡ x3
Перейдем к следующей строке системы логических уравнений:
¬(x2 ≡ x3) ∧ (x2∨ x4) ∧ (¬x2∨ ¬x4) = 0
По аналогии при выполнении следующих условий:
x2 ≠ x3
x3 ≡ x4
Не будет достигнут требуемый результат. Воспользуемся предыдущей таблицей, только в этот раз будем рассматривать x1 = x2, x2 = x3, x3 = x4. Условие прошли лишь две строки: 2 и 7. Аналогичная картина будет наблюдаться у всех следующих уравнений системы (еще 6) вплоть до последнего. Итоговое количество решений = 6*2 + 8 = 20.
Ответ: 20
2. Логические уравнения
2.1 Сколько различных решений имеет уравнение A ∧ ¬B ∧ C ∧ (D ∨ ¬D) = 0, где A, B, C, D — логические переменные?
В ответе не нужно перечислять все различные наборы значений A, B, C, D, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
Рассмотрим варианты, когда данное уравнение будет принимать значение «истина». Получаем 2 системы уравнений:
A = 1
B = 0
C = 1
D = 0
A = 1
B = 0
C = 1
D = 1
Таким образом, всего 2 набора переменных.
А всего количество возможных наборов = 2^4 = 16. Т.е. ложь будет в оставшихся 14 случаях.
Ответ: 14
2.2. Составьте таблицу истинности для логической функции
*X = (А ↔ B) ∨ ¬(A → (B ∨ C))
в которой столбец значений аргумента А представляет собой двоичную запись числа 15, столбец значений аргумента В — числа 32, столбец значений аргумента С — числа 12. Число в столбце записывается сверху вниз от старшего разряда к младшему(включая нулевой набор). Переведите полученную двоичную запись значений функции X в десятичную систему счисления.
Переведем числа в двоичную систему счисления:
15 = 1111
32 = 100000
12 = 1100
Добавим необходимые нули. Сначала, чтобы уравнять количество разрядов, а потом еще один для того, чтобы учесть условие «нулевой набор»:
15 = 111100
32 = 100000
12 = 110000
Запишем, как требуется в таблицу:
|
A |
B |
C |
(А ↔ B) |
(B ∨ C) |
A→ (B ∨ C) |
¬(A → (B ∨ C)) |
X |
|
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
|
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
|
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
|
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
|
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
|
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
Теперь запишем это число снизу вверх, как то требуется и переведем в десятичное:
101111 = 47
Ответ: 47
2.3. Каково наибольшее целое число X, при котором истинно высказывание
(2 < X·(X+1)) → (4 > X*X+3*X)
Рассмотрим систему неравенств, когда импликация ложна:
X·(X+1) > 2
X*X+3*X ≥ 4
Решим первое уравнение:
x ∈ (-∞; -2);(1; +∞)
Решим второе уравнение:
x ∈ (-∞; 4];[1; +∞)
Для решения подходят все значения, принадлежащие обоим промежуткам. Проанализировав числовую прямую, определяем, что максимальное значение стремится к 1. 1 целое число, меньшее 1 – это 0.
Ответ: 0
2.4. Известно, что для целых чисел X, Y и Z истинно высказывание
(Z < X ∨ Z < Y) ∧ ¬(Z+1 < X) ∧ ¬(Z+1 < Y)
Чему равно Z, если X=12 и Y=27?
Конъюнкция истинна, когда истинно каждое из выражений:
(Z < X ∨ Z < Y) = 1
¬(Z+1 < X) = 1
¬(Z+1 < Y) = 1
Подставим значения X и Y в данные выражения:
Z < 12 ∨ Z < 27 = 1
Z ≥ 11 = 1
Z ≥ 26 = 1
Всем условиям удовлетворяет лишь одно число – 26.
Ответ: 26
3. Системы логических уравнений, содержащие неоднотипные уравнения
Источник: Яндекс. Тренировочная работа ЕГЭ по информатике. Вариант 1
3.1. Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют всем перечисленным ниже условиям?
(x1 → x2) ∧ (x2 → x3) ∧ (x3 → x4) ∧ (x4 → x5 ) = 1
(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) ∧ (y4 → y5 ) = 1
*x1 ∨ y1 = 1
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Рассмотрим *. Для достижения истинности у дизъюнкции, необходимо, чтобы хотя бы одна из логических переменных имела значение «истина». Таким образом, имеем три возможных варианта:
1) x1 = 1
y1 = 0
2) x1 = 0
y1 = 1
3) x1 = 1
y1 = 1
Обратимся к первой системе. Если x1 = 1, то для того, чтобы серия импликаций была истиной, необходимо, чтобы x2, x3, x4, x5 = 1. Таким, образом, лишь один набор переменных для x.
Для y составим таблицу истинности:
|
y1 |
y2 |
y3 |
y4 |
y5 |
|
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
1 |
|
0 |
0 |
0 |
1 |
1 |
|
0 |
0 |
1 |
1 |
1 |
|
0 |
1 |
1 |
1 |
1 |
Следовательно, для 1 системы существует 1*5=5 наборов.
Аналогично для 2 – 5 наборов.
Рассмотрим 3 систему.
Если x1 = 1, то из предыдущего рассуждения получаем x2, x3, x4, x5 = 1.
Если y1 = 1, то также получаем y2, y3, y4, y5 = 1.
Итого 1 набор.
Теперь просуммируем количество всех возможных наборов переменных: 5+5+1 = 11.
Ответ: 11
3.2. Сколько существует различных наборов значений логических переменных x1, ..., x4, y1, ..., y4, z1,..., z4, которые удовлетворяют всем перечисленным ниже условиям?
(x1 → x2) ∧ (x2 → x3) ∧ (x3 → x4) = 1
(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1
(z1 → z2) ∧ (z2→ z3) ∧ (z3 → z4) = 1
*(x4 | y4) ∧ z4 = 0
В ответе не нужно перечислять все различные наборы значений переменных x1, ..., x4, y1, ..., y4, z1, ..., z4, при которых выполнена данная система равенств.
В качестве ответа Вам нужно указать количество таких наборов.
Из условия * очевидно, что хотя бы одна из логических переменных (x4 | y4) или z4 должна принимать значение «ложь». Возможны 5 наборов:
|
№ набора |
x4 |
y4 |
z4 |
|
1 |
0 |
0 |
0 |
|
2 |
0 |
0 |
1 |
|
3 |
0 |
1 |
0 |
|
4 |
1 |
0 |
0 |
|
5 |
1 |
1 |
0 |
Составим таблицу истинности для x:
|
x1 |
x2 |
x3 |
x4 |
|
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
1 |
|
0 |
0 |
1 |
1 |
|
0 |
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
Аналогичная таблица будет для y и z.
Посмотрим, сколько возможных комбинаций есть для первого набора (x4 = 0, y4 = 0, z4 = 0). 1 * 1 * 1 = 1.
Для второго набора (x4 = 0, y4 = 0, z4 = 1). 1 * 1 * 4 = 4.
Для третьего (x4 = 0, y4 = 1, z4 = 0). 1 * 4 * 1 = 4.
Для четвертого набора (x4 = 1, y4 = 0, z4 = 0). 4 * 1 * 1 = 4.
Тогда как для пятого набора (x4 = 1, y4 = 1, z4 = 0). 4 * 4 * 1 = 16.
Суммируем количество всех комбинаций: 1 + 4 + 4 + 4 + 16 = 29.
Ответ: 29
3.3. Сколько существует различных наборов значений логических переменных x1, x2, … x3, y1, y2, … y3, которые удовлетворяют всем перечисленным ниже условиям:
(¬(x1 ≡ y1) –> ¬(x2 ≡ y2))∧(x1 –> x2)∧(y1–> y2) = 1
(¬(x2 ≡ y2) –> ¬(x3 ≡ y3))∧(x2 –> x3)∧(y2–> y3) = 1
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, … x3, y1, y2, … y3, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Конъюнкция истинна, когда значение «истина» принимает каждое из её логических выражений:
*¬(x1 ≡ y1) –> ¬(x2 ≡ y2)) = 1
x1 –> x2 =1
y1–> y2 = 1
Напишем таблицу истинности для 4 переменных:
|
x1 |
x2 |
y1 |
y2 |
x1 –> x2 |
y1–> y2 |
x1 ≡ y1 |
¬(x1 ≡ y1) |
x2 ≡ y2 |
¬(x2 ≡ y2) |
–> |
* |
|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
|
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
|
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
|
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
|
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
|
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
|
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
|
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
|
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
|
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
|
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
|
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
|
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
|
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
|
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
Получаем 7 наборов переменных.
В следующем уравнении также встречаются переменные x2 и y2. Проанализируем, какие значения этих переменных привели к решению:
x2 = 0
y2 = 0
x2 = 0
y2 = 1
x2 = 1
y2 = 0
x2 = 1
y2 = 1
Чтобы второе уравнение системы принимало значение «истина», необходимо, чтобы новые наборы переменных были такими же. Мысленно составим таблицу истинности для второго уравнения системы и определим, что в результате получаем только три набора переменных. Следовательно, суммарное количество наборов равно 7 + 3 = 10
Ответ: 10
Вывод
Конечно же, необходима практика, чтобы научиться как следует решать эти задания. Внимательно составленные таблицы истинности – гарант успеха на ЕГЭ.
