Разбор задачи B15 (демо ЕГЭ 2013)
(x1 → x2) /\ (x2 → x3) /\ (x3 → x4) = 1
(¬y1 \/ y2) /\ (¬y2 \/ y3) /\ (¬y3 \/ y4) = 1
(y1 → x1) /\ (y2 → x2) /\ (y3 → x3) /\ (y4 → x4) = 1
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, y1, y2 y3, y4, при которых выполнена данная система равенств.
В качестве ответа Вам нужно указать количество таких наборов.
Преобразуем систему уравнений к виду:
(x1 → x2) /\ (x2 → x3) /\ (x3 → x4) = 1 (1)
(y1 → y2) /\ (y2 → y3) /\ (y3 → y4) = 1 (2)
(y1 → x1) /\ (y2 → x2) /\ (y3 → x3) /\ (y4 → x4) = 1 (3)
Розовым выделено уравнение, которое было преобразовано. ¬y1 \/ y2=y1 → y2. Аналогично и для остальных частей данного уравнения.
Решим уравнение (1).
1 способ
Уравнение (1) содержит импликации (→), связанные конъюнкцией (/\). Соответственно, чтобы уравнение было истинно, все входящие импликации должны быть истинны:
x1 → x2=1,
x2 → x3=1,
x3 → x4=1.
Таблица истинности для импликации на примере x1 → x2:
| x1 | x2 | x1→x2 |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Розовым выделена комбинация, когда импликация ложна. Видно, что в ней идут подряд "1" и "0". Выпишем комбинации для x1x2x3x4, в которых не встречается подряд "1" и "0", чтобы импликации x1 → x2, x2 → x3, x3 → x4 не были равны 0-ю.
| x1 |
x2 |
x3 |
x4 |
|---|---|---|---|
| 0 |
0 |
0 |
0 |
| 0 |
0 |
0 |
1 |
| 0 |
0 |
1 |
1 |
| 0 |
1 |
1 |
1 |
| 1 |
1 |
1 |
1 |
Получили 5 комбинаций.
2 способ
Решим методом от противного. Рассмотрим случаи, когда уравнение (x1 → x2) /\ (x2 → x3) /\ (x3 → x4)=0.
Импликация ложна, когда посылка истинна, а следствие ложно. Таблица истинности приведена выше:
Исходя из этого определим случаи, когда импликация ложна.
Если x1 → x2=0:
| x1 | x2 | x3 | x4 |
|---|---|---|---|
| 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 |
x1=1, x2=0,
x3 и x4 - 0 или 1, поэтому они дают 22=4 комбинации.
Если x2 → x3=0:
| x1 | x2 | x3 | x4 |
|---|---|---|---|
| 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 |
x2=1, x3=0,
x1 и x4 - 0 или 1, поэтому они дают 4 комбинации.
Если x3 → x4=0:
| x1 | x2 | x3 | x4 |
|---|---|---|---|
| 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 |
x3=1, x4=0,
x1 и x2 - 0 или 1, поэтому они дают 4 комбинации.
Получили 4*3=12 комбинаций.
Также нужно учеть повторные комбинации. В данном случае повторная комбинация одна: 1010. В таблицах выше такая комбинация выделена синей рамкой. Она встретилась 2 раза, поэтому общее число комбинаций с учетом повторов:
12−1=11.
Мы решали уравнение методом от противного. Теперь перейдем к исходному уравнению.
Общее число комбинаций при 4-х переменных: 24=16. 16-11=5 комбинаций.
Перейдем к уравнению (2):
(y1 → y2) /\ (y2 → y3) /\ (y3 → y4) = 1.
Это уравнение содержит переменные y1, y2, y3, y4, которые не связаны с уравнением (1). Уравнения (1) и (2) независимы друг от друга. Но вид уравнения (2) аналогичен виду уравнения (1), которое мы решили выше. Поэтому получаем 5 комбинаций.
| y1 |
y2 |
y3 |
y4 |
|---|---|---|---|
| 0 |
0 |
0 |
0 |
| 0 |
0 |
0 |
1 |
| 0 |
0 |
1 |
1 |
| 0 |
1 |
1 |
1 |
| 1 |
1 |
1 |
1 |
Добавим к системе уравнение (3):
(y1 → x1) /\ (y2 → x2) /\ (y3 → x3) /\ (y4 → x4) = 1
Выпишем рядом решения уравнений (1) и (2)
| y1 | y2 | y3 | y4 | | x1 |
x2 |
x3 |
x4 |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
0 |
0 |
0 |
|
| 0 | 0 | 0 | 1 | 0 |
0 |
0 |
1 |
|
| 0 | 0 | 1 | 1 | 0 |
0 |
1 |
1 |
|
| 0 | 1 | 1 | 1 | 0 |
1 |
1 |
1 |
|
| 1 | 1 | 1 | 1 | 1 |
1 |
1 |
1 |
Будем решать систему уравнений методом от противного. Уравнение (3) равно 0-ю.
y1 → x1=0:
y1=1, x1=0
| y1 |
y2 |
y3 |
y4 |
x1 |
x2 |
x3 |
x4 |
|
|---|---|---|---|---|---|---|---|---|
| 0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
| 0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
|
| 0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
| 0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
|
| 1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Получили 4 комбинации.
y2 → x2=0:
y2=1, x2=0. Строку 1111 (y1y2y3y4) не берем во избежания повторов.
| y1 |
y2 |
y3 |
y4 |
x1 |
x2 |
x3 |
x4 |
|
|---|---|---|---|---|---|---|---|---|
| 0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
| 0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
|
| 0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
| 0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
|
| 1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Получили 3 комбинации.
y3 → x3=0
y3=1, x3=0. Строки 1111, 0111 (y1y2y3y4) не берем во избежания повторов.
| y1 |
y2 |
y3 |
y4 |
x1 |
x2 |
x3 |
x4 |
|
|---|---|---|---|---|---|---|---|---|
| 0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
| 0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
|
| 0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
| 0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
|
| 1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Получили 2-е комбинации.
y4 → x4=0
y4=1, x4=0. Строки 1111, 0111, 0011 (y1y2y3y4) не берем во избежания повторов.
| y1 |
y2 |
y3 |
y4 |
x1 |
x2 |
x3 |
x4 |
|
|---|---|---|---|---|---|---|---|---|
| 0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
| 0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
|
| 0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
| 0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
|
| 1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Получили 1-у комбинацию.
Всего комбинаций: 4+3+2+1=10.
Мы решали систему уравнений методом от противного. Теперь перейдем к исходной системе.
Общее число комбинаций: 5*5=25. Уравнения (1) и (2) дают по 5 независимых комбинаций.
25-10=15 комбинаций.