Системы логических уравнений

Задача на подсчет количества решений системы логических уравнений является одним из самых сложных заданий ЕГЭ. Методы решения таких задач лучше изучать на примерах.

Задача: Сколько различных решений имеет система логических уравнений:

\( \begin{cases}x_1 ∨ x_2 = 1\\ x_2 ∨ x_3 = 1\\    ...   \\ x_9 ∨ x_{10} = 1 \end{cases} \) 

Решение: В общем случаем, при небольшом количестве переменных в одном уравнении лучше решать следующим методом, который называется методом отображения:

  1. Составляем таблицы наборов данных для каждого уравнения
  2. Выявляем связи между таблицами
  3. Подсчитываем количество наборов в каждой строке каждой таблице
  4. Суммируем количество наборов в таблице, соответсвующей последнему уравнению

Составим таблицу для первого уравнения \( 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.

 

Задачи для самостоятельного решения