Системы логических уравнений
Задача на подсчет количества решений системы логических уравнений является одним из самых сложных заданий ЕГЭ. Методы решения таких задач лучше изучать на примерах.
Задача: Сколько различных решений имеет система логических уравнений:
\( \begin{cases}x_1 ∨ x_2 = 1\\ x_2 ∨ x_3 = 1\\ … \\ x_9 ∨ x_{10} = 1 \end{cases} \)
Решение: В общем случаем, при небольшом количестве переменных в одном уравнении лучше решать следующим методом, который называется методом отображения:
- Составляем таблицы наборов данных для каждого уравнения
- Выявляем связи между таблицами
- Подсчитываем количество наборов в каждой строке каждой таблицы
- Суммируем количество наборов в таблице, соответсвующей последнему уравнению
Составим таблицу для первого уравнения \( x_1 + x_2 = 1 \). Если подходить к составлению таблицы формально, то надо составить таблицу истинности для выражения в уравнении и вычеркнуть из нее все строки, которые не удовлетворяют уравнению:
| \( x_1 \) | \( x_2 \) | \( x_1 + x_2 \) |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Первая строка, выделенная красным цветом, не удовлетворяет уравнению, потому что значение выражения \( x_1 + x_2 \) ложно, а по уравнению значение должно быть истинным. Поэтому вычеркиваем ее и составляем таблицу наборов данных первого уравнения:
| № | \( x_1 \) | \( x_2 \) | N |
| 1 | 0 | 1 | 1 |
| 2 | 1 | 0 | 1 |
| 3 | 1 | 1 | 1 |
В эту таблицу добавили столбец с номером строки и столбец с количеством наборов. В таблице для первого уравнения для всех строк это количество равно 1.
Для второго уравнения таблица будет такой же, потому что уравнение подобно первому только с другими переменными. Разместим эти таблицы рядом и выявим связи между строками (отобразим):
| Таблица 1 | Таблица 2 | ||||||
| № | \( x_1 \) | \( x_2 \) | N | \( x_2 \) | \( x_3 \) | N | |
| 1 | 0 | 1 | 1 | 0 | 1 | 1 | |
| 2 | 1 | 0 | 1 | 1 | 0 | 2 | |
| 3 | 1 | 1 | 1 | 1 | 1 | 2 | |
В таблицах есть общая переменная \( x_2 \), по ней и будем строить связи. Для первой строки таблицы 2 значение \( x_2 \) ложно, что соответствует строке 2 таблицы 1. Проводим красную линию, а в столбец N таблицы 2 ставим значение количества набора данных таблицы 1 из строки 2.
Для второй строки таблицы 2 для переменной \( x_2 \) соответствуют значения строк 1 и 3 таблицы 1. Проводим зеленую линии, а в столбец N таблицы 2 ставим значение суммы количеств наборов данных таблицы 1 из строк 1 и 3.
Для третьей строки таблицы 2 для переменной \( x_2 \) также соответствуют значения строк 1 и 3 таблицы 1. Проводим синие линии, а в столбец N таблицы 2 ставим значение суммы количеств наборов данных таблицы 1 из строк 1 и 3.
Так как все уравнения подобны, то таблицы наборов и связи между ними будут такие же, поэтому все можно свести к одной таблице только со столбцами, соответствующими количеству наборов данных:
| \( x_1x_2 \) | \( x_2x_3 \) | \( x_3x_4 \) | \( x_4x_5 \) | \( x_5x_6 \) | \( x_6x_7 \) | \( x_7x_8 \) | \( x_8x_9 \) | \( x_9x_{10} \) |
| 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 |
| 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 |
| 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 |
Столбец 1 содержит значения 1. Для каждого следующего столбца заполняем строки по выработанному алгоритму:
Для каждого следующего столбца для строки 1 берем значение из строки 2 предыдущего столбца. Для строк 2 и 3 - сумму значений из строк 1 и 3.
Суммируем последний столбец, соответствующий последнему уравнению: 34 + 55 + 55 = 144. Ответ: система имеет 144 решения - наборов данных.
Задача: Сколько различных решений имеет система логических уравнений:
\( \begin{cases}x_1 ∨ x_2 ∧ x_3= 1\\ x_2 ∨ x_3 ∧ x_4 = 1\\ … \\ x_8 ∨ x_9 ∧ x_{10} = 1 \end{cases} \)
Решение: Составим таблицу наборов данных для первого уравнения \( x_1 + x_2 ⋅ x_3 = 1 \) . Можно это сделать формально как в предыдущем примере, но лучше попробуем заполнить методом рассуждений. Для \( x_1 = 0, x_2 = 0 \) нет решения уравнения, потому что каким бы не было значение переменной \( x_3\), результат будет ложным. Для \( x_1 = 0, x_2 = 1 \) переменная \( x_3\) должна быть истинна, чтобы результат удовлетворял бы уравнению, поэтому заполняем первую строку :
| \( x_1 \) | \( x_2 \) | \( x_3 \) |
| 0 | 1 | 1 |
Для \( x_1 = 1, x_2 = 0 \) переменная \( x_3\) может быть как истинной, так и ложной, поэтому добавляем две строки 1,0,0 и 1,0,1:
| \( x_1 \) | \( x_2 \) | \( x_3 \) |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 0 | 1 |
Для \( x_1 = 1, x_2 = 1 \) переменная \( x_3\) также может быть как истинной, так и ложной, поэтому добавляем еще две строки 1,1,0 и 1,1,1:
| \( x_1 \) | \( x_2 \) | \( x_3 \) |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
| 1 | 1 | 1 |
Для второго уравнения получим таблицу с такими же наборами данных, так как уравнения подобны. Добавим в таблицы столбцы для номера строк, количества наборов и расположим рядом для выявления связей:
| Таблица 1 | Таблица 2 | ||||||||
| № | \( x_1 \) | \( x_2 \) | \( x_3 \) | N | \( x_2 \) | \( x_3 \) | \( x_4 \) | N | |
| 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | |
| 2 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |
| 3 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | |
| 4 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 2 | |
| 5 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | |
Таблицы связаны переменными \( x_2\) и \( x_3\), поэтому для набора значений \( x_2\) и \( x_3\) строки таблицы 2 ищем такие же наборы этих переменных в таблице 1. Вычисляем связи:
\( N_{2-1} = N_{1-3}\)
\( N_{2-2} = N_{1-4}\)
\( N_{2-3} = N_{1-4}\)
\( N_{2-4} = N_{1-1} + N_{1-5}\)
\( N_{2-5} = N_{1-1} + N_{1-5}\)
В индексе для \( N\) первая цифра - номер таблицы, вторая - номер строки.
Все уравнения подобны, поэтому и наборы данных и связи будут одинаковы. Строим таблицу системы только со столбцами количества набора данных:
| № | \( x_1x_2x_3 \) | \( x_2x_3x_4 \) | \( x_3x_4x_5 \) | \( x_4x_5x_6 \) | \( x_5x_6x_7 \) | \( x_6x_7x_8 \) | \( x_7x_8x_9 \) | \( x_8x_9x_{10} \) |
| 1 | 1 | 1 | 1 | 2 | 3 | 4 | 6 | 9 |
| 2 | 1 | 1 | 2 | 3 | 4 | 6 | 9 | 13 |
| 3 | 1 | 1 | 2 | 3 | 4 | 6 | 9 | 13 |
| 4 | 1 | 2 | 3 | 4 | 6 | 9 | 13 | 19 |
| 5 | 1 | 2 | 3 | 4 | 6 | 9 | 13 | 19 |
Суммируем последний столбец: 9 + 13 + 13 + 19 + 19 = 73. Ответ: 73 решения.
Задача: Сколько существует различных наборов значений логических переменных x1, x2,…, x5, y1, y2, …, y5, которые удовлетворяют всем перечисленным ниже условиям?
\( (x_1 ∨ y_1) ≡ ¬(x_2 ∨ y_2) = 1 \)
\( (x_2 ∨ y_2) ≡ ¬(x_3 ∨ y_3) = 1 \)
....
\( (x_8 ∨ y_8) ≡ ¬(x_9 ∨ y_9) = 1 \)
Решение: Преобразуем первое уравнение \( (x_1 + y_1) ≡ \overline{(x_2 + y_2)} = 1 \).
\( (x_1 + y_1) ≡ (\overline{x_2} ⋅ \overline{y_2}) = 1 \).
Заполним таблицу наборов данных этого уравнения методом рассуждений:
Для набора \( x_1 = 0, y_1 = 0 \) первое выражение в скобках будет ложно, поэтому и второе выражение в скобках также должно быть ложно, чтобы условие тождественного равенства этих выражений выполнилось. Второе выражение будет ложно при трех наборах данных: (\( x_2 = 0, y_2 = 1 \) ), (\( x_2 = 1, y_2 = 0 \) ), (\( x_2 = 1, y_2 = 1 \) ). Добавим в таблицу полученные три набора:
| \( x_1 \) | \( y_1 \) | \( x_2 \) | \( y_2 \) |
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 1 |
Для набора \(x_1 = 0, y_1 = 1 \) первое выражение в скобках будет истинно, поэтому и второе выражение должно быть истинно, что может быть только при \( x_2 = 0, y_2 = 0 \) . Для наборов (\(x_1 = 1, y_1 = 0 \) ) и (\( x_1 = 1, y_1 = 1 \) ) также будет выполняться условие тождественности только при наборе \( x_2 = 0, y_2 = 0 \). Добавим в таблицу еще три строки:
| \( x_1 \) | \( y_1 \) | \( x_2 \) | \( y_2 \) |
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 |
Для второго уравнения таблица наборов данных будет с такими же данными, так как уравнения подобны. Расположим таблицы для первого и второго уравнений рядом, добавил столбцы номера строки, количества наборов и выявим связи:
| Таблица 1 | Таблица 2 | ||||||||||
| № | \( x_1 \) | \( y_1 \) | \( x_2 \) | \( y_2 \) | N | \( x_2 \) | \( y_2 \) | \( x_3 \) | \( y_3 \) | N | |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 3 | |
| 2 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 3 | |
| 3 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | |
| 5 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | |
| 6 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | |
В таблицах общими являются столбцы \( x_2\) и \( y_2\), поэтому для строки таблицы 2 ищем в таблице 1 строки с таким же набором \( x_2\) и \( y_2\). По полученным связям составляем выражения для подсчета количества наборов:
\( N_{2-1} = N_{1-4} + N_{1-5} + N_{1-6} \)
\( N_{2-2} = N_{1-4} + N_{1-5} + N_{1-6} \)
\( N_{2-3} = N_{1-4} + N_{1-5} + N_{1-6} \)
\( N_{2-4} = N_{1-1} \)
\( N_{2-5} = N_{1-2} \)
\( N_{2-6} = N_{1-3} \)
В индексах \(N\) первое число номер таблицы, а второе - номер строки. Строим таблицу всех уравнений:
| № | \( x_1y_1x_2y_2 \) | \( x_2y_2x_3y_3 \) | \( x_3y_3x_4y_4 \) | \( x_4y_4x_5y_5 \) | \( x_5y_5x_6y_6 \) | \( x_6y_6x_7y_7 \) | \( x_7y_7x_8y_8 \) | \( x_8y_8x_9y_9 \) |
| 1 | 1 | 3 | 3 | 9 | 9 | 27 | 27 | 81 |
| 2 | 1 | 3 | 3 | 9 | 9 | 27 | 27 | 81 |
| 3 | 1 | 3 | 3 | 9 | 9 | 27 | 27 | 81 |
| 4 | 1 | 1 | 3 | 3 | 9 | 9 | 27 | 27 |
| 5 | 1 | 1 | 3 | 3 | 9 | 9 | 27 | 27 |
| 5 | 1 | 1 | 3 | 3 | 9 | 9 | 27 | 27 |
Суммируем последний столбец: 81 + 81 + 81 + 27 + 27 + 27 = 324. Ответ: 324 набора значений.
Решим эту же задачу другим способом, при котором выявляем связи между парами переменных. Строим таблицу отображения следующим образом:
В столбце соответствующему паре переменных \( x_1y_1 \) записываем в строках все возможные наборы этих переменных. Во втором столбце - все возможные наборы данных для пары переменных \( x_2y_2 \). Устанавливаем связи тем же способом, каким мы заполняли таблицу уравнения в первом варианте решения задачи.
| \( x_1y_1 \) | \( x_2y_2 \) | Подсчет |
| 00 | 00 | 01 + 10 + 11 |
| 01 | 01 | 00 |
| 10 | 10 | 00 |
| 11 | 11 | 00 |
Рассматриваем первое уравнение: \( (x_1 + y_1) ≡ (\overline{x_2} ⋅ \overline{y_2}) = 1 \)
Для набора \( x_1 = 0, y_1 = 0 \) первое выражение в скобках будет ложно, поэтому и второе выражение в скобках также должно быть ложно, чтобы условие тождественного равенства этих выражений выполнилось. Второе выражение будет ложно при трех наборах данных: (\( x_2 = 0, y_2 = 1 \) ), (\( x_2 = 1, y_2 = 0 \) ), (\( x_2 = 1, y_2 = 1 \) ). Проводим линии от строки с набором 00 первого столбца к соответствующим строкам наборов второго столбца.
Для набора \(x_1 = 0, y_1 = 1 \) первое выражение в скобках будет истинно, поэтому и второе выражение должно быть истинно, что может быть только при \( x_2 = 0, y_2 = 0 \) . Проводим линию от строки 01 первого столбца к строке 00 второго столбца. Для наборов (\(x_1 = 1, y_1 = 0 \) ) и (\( x_1 = 1, y_1 = 1 \) ) также будет выполняться условие тождественности только при наборе \( x_2 = 0, y_2 = 0 \). Проводим линии соответствующим образом.
В последнем столбце записываем формулу подсчета, в которой показано из каких наборов состоит количество наборов для пары переменных \( x_2y_2 \).
Строим таблицу со столбцами, соответствующим парам переменных всех уравнений. В этих столбцах будем подсчитывать количество наборов для пар:
| \( x_1y_1 \) | \( x_2y_2 \) | \( x_3y_3 \) | \( x_4y_4 \) | \( x_5y_5 \) | \( x_6y_6 \) | \( x_7y_7 \) | \( x_8y_8 \) | \( x_9y_9 \) | |
| 00 | 1 | 3 | 3 | 9 | 9 | 27 | 27 | 81 | 81 |
| 01 | 1 | 1 | 3 | 3 | 9 | 9 | 27 | 27 | 81 |
| 10 | 1 | 1 | 3 | 3 | 9 | 9 | 27 | 27 | 81 |
| 11 | 1 | 1 | 3 | 3 | 9 | 9 | 27 | 27 | 81 |
Заполняем таблицу по полученным формулам. В первом столбце ставим единицы. Во втором столбце в строку 00 записываем сумму значений строк 01, 10, 11 первого столбца. В строку 01 второго столбца - значение строки 00 первого столбца. В строки 10,11 второго столбца также записываем значение строки 00 первого столбца. В третьем столбце для подсчета используем значения строк предыдущего - второго столбца. Аналогичным образом заполняем и остальные столбцы.
Суммируем последний столбец: 81 + 81 + 81 + 81 = 324. Получили тот же ответ.
Задача: Сколько существует различных наборов значений логических переменных x1, x2,…, x5, y1, y2, …, y5, которые удовлетворяют всем перечисленным ниже условиям?
(x1 → x2) ∧ (x2 → x3) ∧ (x3 → x4) ∧ (x4 → x5) = 1
(y1 → y2) ∧ (y2 →y3) ∧ (y3 → y4) ∧ (y4 → y5) = 1
(¬y1 ∨ x1) ∧ (¬y2 ∨ x2) ∧ (¬y3 ∨ x3) ∧ (¬y4 ∨ x4) ∧ (¬y5 ∨ x5) = 1
Решение: Составим таблицу наборов данных для первого уравнения. Как видно все члены конъюнкции должны быть истинны,чтобы результат был бы истинным, а истинны они могут быть при любом наборе в выражениях в скобках за исключением набора 1 0, то есть для соседних переменных запрещена эта комбинация. Исходя из этого таблица будет выглядеть так:
| x1 | x2 | x3 | x4 | x5 |
| 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 | 1 | 1 | 1 |
Для второго уравнения таблица будет содержать такие же наборы данных. Расположим таблицы рядом. Так как в третьем уравнении переменных 10, то возможных наборов для таблицы - 1024. Метод отображения применить проблематично. Поэтому попробуем рассуждать. Если значения из первой строки таблицы первого уравнения подставить в третье уравнение, то можно заметить, что только один набор из второй таблицы позволит выражению третьего уравнения быть истинным, когда все переменные y1..y5 ложны. Записываем для первой строки количество наборов 1:
| x1 | x2 | x3 | x4 | x5 | y1 | y2 | y3 | y4 | y5 | ||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | ||
| 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | ||
| 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | ||
| 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | ||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Если значения из второй строки таблицы первого уравнения подставить в третье уравнение, то необходимо, чтобы ложны были бы y1…y4, а значение y5 может быть как ложно, так и истинно. Таких наборов 2 - первая и вторая строка таблицы 2. Записываем для второй строки количество наборов 2:
| x1 | x2 | x3 | x4 | x5 | y1 | y2 | y3 | y4 | y5 | ||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 2 | |
| 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | ||
| 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | ||
| 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | ||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Аналогично рассуждая заметим, что для каждой следующей строки количество наборов из второй таблицы удовлетворяющих уравнению 3 увеличивается на 1. Наконец, для набора из последней строки первой таблицы все наборы из второй таблицы будут удовлетворять уравнению 3:
| x1 | x2 | x3 | x4 | x5 | y1 | y2 | y3 | y4 | y5 | ||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 2 | |
| 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 3 | |
| 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 4 | |
| 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 5 | |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 6 |
Просуммируем записанные значения количеств наборов для строк: 1 + 2 + 3 + 4 + 5 + 6 = 20. Ответ: 20
Задача: Сколько существует различных наборов значений логических переменных x1, x2,…, x6, y1, y2, …, y6, z1, z2, …, z6, которые удовлетворяют всем перечисленным ниже условиям?
(x1 → x2) ∧ (x2 → x3) ∧ (x3 → x4) ∧ (x4 → x5) = 1
(y1 → y2) ∧ (y2 →y3) ∧ (y3 → y4) ∧ (y4 → y5) = 1
(z1 → z2) ∧ (z2 → z3) ∧ (z3 → z4) ∧ (z4 → z5) = 1
x5 ∧ y5 ∧ z5 = 0
Решение: Первые три уравнения этой задачи подобны уравнениям предыдущей задачи, поэтому просто скопируем таблицу наборов данных x1…x5:
| x1 | x2 | x3 | x4 | x5 |
| 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 | 1 | 1 | 1 |
Для второго и третьего уравнений таблицы будут с такими же наборами данных, мы их не будем повторять. Составим таблицу наборов данных для уравнения 4. Конъюнкция будет ложна, когда ложна хотя бы одна переменная:
| x5 | y5 | z5 | |
| 0 | 0 | 0 | |
| 0 | 0 | 1 | |
| 0 | 1 | 0 | |
| 0 | 1 | 1 | |
| 1 | 0 | 0 | |
| 1 | 0 | 1 | |
| 1 | 1 | 0 |
В первой строке таблицы значение x5 ложно. Смотрим в таблице для первого уравнения сколько наборов со значением x5 равным 0 - только одно. Аналогично для значения y5 = 0 находится один набор в таблице второго уравнения, а для z5 = 0 - один набор из таблицы третьего уравнения. Перемножаем найденные количества наборов и получаем количество наборов для первой строки (1 ⋅ 1 ⋅ 1 = 1). Для второй строки количество наборов для x5 и y5 уже известно, а для z5 = 1 из таблицы третьего уравнения находим 5 наборов, перемножаем и получаем 5 наборов для второй строки (1 ⋅ 1 ⋅ 5 = 5). Аналогично заполняем количество для остальных строк:
| x5 | y5 | z5 | |
| 0 | 0 | 0 | 1 ⋅ 1 ⋅ 1 = 1 |
| 0 | 0 | 1 | 1 ⋅ 1 ⋅ 5 = 5 |
| 0 | 1 | 0 | 1 ⋅ 5 ⋅ 1 = 5 |
| 0 | 1 | 1 | 1 ⋅ 5 ⋅ 5 = 25 |
| 1 | 0 | 0 | 5 ⋅ 1 ⋅ 1 = 5 |
| 1 | 0 | 1 | 5 ⋅ 1 ⋅ 5 = 25 |
| 1 | 1 | 0 | 5 ⋅ 5 ⋅ 1 = 25 |
Складываем полученные значения: 1 + 5 + 5 + 25 + 5 + 25 + 25 = 91. Ответ: 91.