Задание 18 ЕГЭ по информатике 2018

• Условно разделим исходное выражение на части:



• Главное действие (внешняя операция) в исходном выражении — это конъюнкция. Конъюнкция истинна, когда все операнды истинны. Т.е. в задаче обе части 1 и 2 должны быть истинными (т.к. по условию общая формула должна быть истинной).

Рассмотрим часть 1:
• если в 1.1 имеем x > 9, то часть 1 будет истинна независимо от А. Значит, значение числа А влияет на решение только при выполнении условия:
x<=9

(импликация 0 → 0 = 1, 0 → 1 = 1)

• теперь, для того чтобы в части 1, выражение было истинным, надо чтобы часть 1.2 была истинной:
x*x <= A

(импликация 1 → 1 = 1)

• таким образом, получаем:

x <= 9
x2 <= A

при любых x

• так как нам необходимо найти наибольшее возможное А, то, значит, надо ограничить его значения сверху, а данная часть выражения ограничивает только снизу:

возьмем наименьшее натуральное: x=1, тогда A>=1

Рассмотрим часть 2:

• если 2.2 истинно (т.е. y <= 9), то часть 2 будет истинна независимо от А. Значит, значение числа А влияет на решение только при выполнении условия:
y > 9
• теперь, для того чтобы в части 2 выражение было истинным, надо чтобы часть 2.1 была ложной:
y * y > A

(импликация 0 → 0 = 1)

• таким образом, получаем:

y > 9
y2 > A

при любых y

• данная часть выражения ограничивает значения А сверху:

возьмем наименьшее возможное по условию натуральное: y = 10, тогда A < 100

• Получаем, что наибольшее А меньшее 100: А = 99

Результат: 99

✎ Способ 1:
• Произведем замену:

z10 = (x&10 = 0), z3 = (x&3 = 0), A = (x&A = 0)

• Перепишем выражение:

¬A → (z10 → ¬ z3)

• Избавимся от импликации (A → B = ¬ A ∨ B):
• Сначала по правилу преобразования импликации:

¬A → (z10 → ¬ z3) = A + ¬z10 + ¬Z3 

• По Закону де Моргана вынесем отрицание за скобки (¬ (A ∧ B) = ¬ A ∨ ¬ B):

A + ¬z10 + ¬z3 = A + ¬(z10 * z3)

• Вернемся опять к импликации:

A + ¬(z10 * z3) = ¬(z10 * z3) + A = (z10 * z3) → A

• Суть предыдущих действий в том, что нам необходимо прийти к импликации, но, избавившись от отрицания.
• По следующему правилу Z_K * Z_M = Z_{K or M} (К. Поляков) заменим конъюнкцию:

z10 * z3 = z10 or 3

• Выполним поразрядную дизъюнкцию двоичных чисел 10 и 3:

1010 -> 10
0011 -> 3
1011 -> 10 or 3 = 1110

• Получаем:

z11 → A

• Необходимо обеспечить истинность данного выражения при всех x. Это возможно, когда единичные биты A входят в единичные биты числа 11. То есть:

A = 10112 = 1110

✎ Способ 2:

• Введем обозначения:

P = (x&10 = 0), Q = (x&3 = 0), A = (x&A = 0)

• Перепишем выражение:

¬A → (P → ¬Q) 

• Избавимся от импликации:

A + ¬P + ¬Q

• В выражении красным выделена известная часть (ее можно найти). Операция дизъюнкция (логическое сложение) проще находится, когда выражение ложно (=0). Так как результатом дизъюнкции ложь является только в одном случае: 0 + 0 = 0. Поэтому примем выделенную часть за 0.
• Чтобы формула была истинна при любых x, нужно, чтобы ¬P + ¬Q = 0 и при этом A = 1.
• По таблице истинности дизъюнкции имеем:

если ¬P + ¬Q = 0, то P = Q = 1

• Таким образом, необходимо, чтобы P = Q = 1. Подставим в побитовую маску, с учетом введенных обозначений:

P = (x&10 = 0):
3 2 1 0 - номер бита
1 0 1 0 - 10
0 * 0 * - x (маска)
0 0 0 0 - x&10

Q = (x&3 = 0):
3 2 1 0 - номер бита
0 0 1 1 - 3
* * 0 0 - x (маска)
0 0 0 0 - x&3

• Пояснение: чтобы в результате поразрядной конъюнкции получить 0, в тех разрядах, в которых стоит единица, в маске x необходимо поставить 0.

общая маска х:
0 * 0 0

• Сопоставив обе маски, получаем, что в x биты 0, 1 и 3 - нулевые, значит, для x & A они должны быть единичные (так как по заданию требуется найти наибольшее А).

0 * 0 0     общая маска х:
1 0 1 1     x & A = 0

• Переведем результат в десятичную систему:

10112 = 1110

Результат: 11

✎ Способ 1:
• Произведем замену:

z36 = (x&36 = 0), z6 = (x&6 = 0), A = (x&A = 0)

• Перепишем выражение:

¬A → (z36 → ¬ z6)

• Избавимся от импликации (A → B = ¬ A ∨ B):
• Сначала по правилу преобразования импликации:

¬A → (z36 → ¬ z6) = A + ¬z36 + ¬z6 

• По Закону де Моргана вынесем отрицание за скобки (¬ (A ∧ B) = ¬ A ∨ ¬ B):

A + ¬z36 + ¬z6 = A + ¬(z36 * z6)

• Вернемся опять к импликации:

A + ¬(z36 * z6) = ¬(z36 * z6) + A = (z36 * z6) → A

• Суть предыдущих действий в том, что нам необходимо прийти к импликации, но, избавившись от отрицания.
• По следующему правилу Z_K * Z_M = Z_{K or M} (К. Поляков) заменим конъюнкцию:

z36 * z6 = z36 or 6

• Выполним поразрядную дизъюнкцию двоичных чисел 10 и 3:

1001002 -> 36
1102 -> 6
1001102 -> 36 or 6 = 3810

• Получаем:

z38 → A

• Необходимо обеспечить истинность данного выражения при всех x. Это возможно, когда единичные биты A входят в единичные биты числа 38. То есть:

A = 1001102 = 3810

 
✎ Способ 2:

• Так как по заданию формула должна быть тождественно истинна, то перепишем ее так:

x&A ≠ 0 → (x&36 = 0 → x&6 ≠ 0) = 1

• Введем обозначения:

A = (x&A = 0);
P = (x&36 = 0);
Q = (x&6 = 0);

• Перепишем выражение согласно введенным обозначениям:

¬A → (P → ¬Q) = 1

• Избавимся от импликации:

A ∨ (¬P ∨ ¬Q) = 1

• A - наше неизвестное; для части выражения ¬P ∨ ¬Q нам необходимо подобрать такой вариант (равный 0 или 1), при котором единственно возможным значением A была бы единица (1).
• Возьмем (¬P ∨ ¬Q) = 0, тогда А должно быть только единицей (чтобы общее выражение было = 1):

A ∨ (¬P ∨ ¬Q) = 1; 
или 
1 ∨ (0) = 1

• Иными словами, выражение истинно, если при ¬P ∨ ¬Q = 0, A равно единице (1).
• Получаем:

¬P ∨ ¬Q = 0
Отсюда имеем: 
¬P = 0 и ¬Q = 0 

(дизъюнкция равна 0 в единственном случае, когда все операнды равны 0)

• Или запишем другим образом:

Q = 1 и P = 1

• Построим побитовые маски:

100100  : 36
000110  : 6
0**0**  : маска P (x&36 = 0)
***00*  : маска Q (x&6 = 0)

• Сопоставим обе маски и маску x&A = 0:

0**0**  : маска P (x&36 = 0)
***00*  : маска Q (x&6 = 0)
0**00*  : общая маска x
*00**0  : маска для A (x&A = 0)
т.е. в тех битах А, где может получиться единица (звездочки в обеих масках),
 мы поставили нули.

• Так как нам необходимо получить наибольшее A (по заданию), то вместо всех "звездочек" ставим единицы:

100110 = 3810

Результат: 38

• Так как по заданию формула должна быть тождественно истинна, то перепишем ее так:

x&A ≠ 0 → (x&9 = 0 → x&3 ≠ 0) = 1

• Введем обозначения:

A = (x&A = 0);
P = (x&9 = 0);
Q = (x&3 = 0);

• Перепишем выражение согласно введенным обозначениям:

¬A → (P → ¬Q) = 1

• Избавимся от импликации:

A ∨ (¬P ∨ ¬Q) = 1

• A - наше неизвестное; для части выражения ¬P ∨ ¬Q нам необходимо подобрать такой вариант (равный 0 или 1), при котором единственно возможным значением A была бы единица (1).
• Возьмем (¬P ∨ ¬Q) = 0, тогда А должно быть только единицей (чтобы дизъюнкция была = 1):

A ∨ (¬P ∨ ¬Q) = 1; 
или 
1 ∨ (0) = 1

• Иными словами, выражение истинно, если при ¬P ∨ ¬Q = 0, A равно единице (1).
• Получаем:

¬P ∨ ¬Q = 0
Отсюда имеем 
¬P = 0 и ¬Q = 0 
(дизъюнкция равна 0 в единственном случае, когда все операнды равны 0) 
Или запишем другим образом: 
Q = 1 и P = 1

• Построим побитовые маски:

1001  : 9
0011  : 3
0**0  : маска P (x&9 = 0)
**00  : маска Q (x&3 = 0)

• Сопоставим обе маски и получим маску для x&A = 0:

0**0  : маска P (x&9 = 0)
**00  : маска Q (x&3 = 0)
0*00  : общая маска х
*0**  : маска для A (x&A = 0)
т.е. в тех битах, где может получиться единица (звездочки в обеих масках P и Q),
 мы поставили нули.

• Так как нам необходимо получить наибольшее A (по заданию), то вместо всех "звездочек" ставим единицы:

1011 = 1110

Результат: 11

• Так как по заданию формула должна быть тождественно ложна, то перепишем ее так:

x&A = 0 ∧ ¬(x&35 ≠ 0 → x&52 ≠ 0) = 0

• Введем обозначения:

A = (x&A = 0);
P = (x&35 = 0);
Q = (x&52 = 0);

• Перепишем выражение согласно введенным обозначениям:

A  ∧ ¬(¬P  → ¬Q) = 0

• Избавимся от импликации:

A  ∧ ¬(P  ∨ ¬Q) = 0

• Раскроем скобки, иcпользуя закон Де Моргана:

A  ∧ ¬P  ∧ Q = 0

• A - наше неизвестное; для части выражения ¬P ∧ Q нам необходимо подобрать такой вариант (равный 0 или 1), при котором единственно возможным значением A был бы ноль (0).
• Возьмем (¬P ∧ Q) = 1, тогда А должно быть только нулем (чтобы конъюнкция была = 0):

A ∧ ¬P  ∧ Q = 0
или 
0  ∧ 1 = 0

• Иными словами, выражение ложно, если при ¬P ∧ Q = 1, A равно нулю (1).
• Получаем:

¬P  ∧ Q = 1
Отсюда имеем ¬P = 1 и Q = 1 
(конъюнкция равна 1 в единственном случае, когда все операнды равны 1)

• Построим побитовые маски:

100011  : 35
110100  : 52
1***11  : маска ¬P (x&35 ≠ 0)
00*0**  : маска Q (x&52 = 0)

• Вспомним, что А = 0, значит, x&А ≠ 0. Сопоставим обе маски с учетом, что нам необходимо получить
  x&A ≠ 0:

1***11  : маска ¬P (x&35 ≠ 0)
00*0**  : маска Q (x&52 = 0)
00*011  : общая маска
****11  : маска A (x&A ≠ 0)
т.е. в тех битах, где может получиться единица (например, 1-й бит справа может дать в результате 1 (1 и *)),
 мы поставили единицы.

• Таким образом, получаем:

А = 000011 = 310

Результат: 3

• Так как по заданию формула должна быть тождественно ложна, то перепишем ее:

x&56 ≠ 0 ∧ ¬(x&A ≠ 0 ∨ x&32 ≠ 0) = 0

• Введем обозначения:

A = (x&A = 0);
P = (x&56 = 0);
Q = (x&32 = 0);

• Перепишем выражение согласно введенным обозначениям:

¬P ∧ ¬(¬A ∨ ¬Q) = 0

• Раскроем скобки, используя закон Де Моргана:

¬P ∧ A ∧ Q = 0
или
A ∧ ¬P ∧ Q = 0

• A - наше неизвестное; для части выражения ¬P ∧ Q нам необходимо подобрать такой вариант (равный 0 или 1), при котором единственно возможным значением A был бы ноль (0).
• Возьмем (¬P ∧ Q) = 1, тогда А должна быть только нулем (чтобы общая формула была = 0):

A ∧ ¬P ∧ Q = 0
или 
0 ∧ 1 = 0

конъюнкция 0 * 1 = 0

• Иными словами, выражение ложно, если при ¬P ∧ Q = 1, A должно быть равно нулю (1).
• Получаем следующие утверждения:

¬P ∧ Q = 1   Отсюда имеем: 
¬P = 1 и Q = 1 

конъюнкция равна 1 в единственном случае, когда все операнды равны 1
x&A = 0 - ложь т.е.
x&A ≠ 0

• Построим побитовые маски:

111000  : 56
100000  : 32
111***  : маска ¬P (x&56 ≠ 0)
0*****  : маска Q (x&32 = 0)

• Сопоставим обе маски и получим x&A ≠ 0:

111***  : маска ¬P (x&56 ≠ 0)
0*****  : маска Q (x&32 = 0)
011***  : общая маска х
*11***  : маска A (x&A ≠ 0)
т.е. в тех битах, где может получиться единица 
(например, 4-й бит может дать в результате 1 (1 & *)), мы сохранили эти единицы и для A.

• Так как нам необходимо получить наименьшее A (по заданию) при формуле тождественно ложной, то остальные разряды оставим равными 0:

011000 = 2410

Результат: 24

• Упростим выражение, введя обозначения:

A: x ∈ A
P: x ∈ P
Q: x ∈ Q

• Запишем формулу с новыми обозначениями, учитывая, что по условию она должна быть тождественно истинной:

(P → Q) → ¬A = 1

• Избавимся от импликации:

(P → Q) → ¬A = 1        =>
¬(P → Q) ∨ ¬A = 1       =>
¬(¬P ∨ Q) ∨ ¬A = 1   

• Используем закон Де Моргана для последующего преобразования:

¬(¬P ∨ Q) ∨ ¬A = 1    =>
P ∧ ¬Q ∨ ¬A = 1

• А - наше неизвестное, а выделенную часть формулы можно найти. Необходимо поставить А в "вынужденное" значение. Если P ∧ ¬Q = 0, то ¬А может равняться только 1, чтобы формула в результате стала истинной.
• Значит, имеем три случая для ¬А = 1 (или A = 0):

1. A = 0 при P = 0 и Q = 1
2. A = 0 при P = 0 и Q = 0
3. A = 0 при P = 1 и Q = 1

• Соответственно, А = 1 только в одном оставшемся случае:

A = 1 при P = 1 и Q = 0

• Отобразим отрезки на числовой прямой, чтобы найти искомое значение:



часть 1 = часть 3 = часть 5: P = 0 и Q = 0  => A = 0
часть 2: P = 1 и Q = 0  => A = 1
часть 4: P = 0 и Q = 1  => A = 0

• Т.е. A истинно (=1) на промежутке [10;20] (на рис. желтым цветом), имеющему длину 10.

Результат: 10

• Упростим выражение, введя обозначения:

A: x ∈ A
P: x ∈ P
Q: x ∈ Q

• Запишем формулу с новыми обозначениями, учитывая, что по условию она должна быть тождественно истинной:

(P ~ Q) → ¬A = 1

• Избавимся от импликации:

(P ~ Q) → ¬A = 1      =>
¬(P ~ Q) ∨ ¬A = 1

Далее возможно 2 способа решения.
  
✎ 1 способ:

• Избавимся от эквивалентности по правилу преобразования эквивалентности:
(a ~ b) = a * b + ¬a * ¬b

¬(P ~ Q) = ¬((P ∧ Q) ∨ (¬P ∧ ¬Q)) =
= ¬(P ∧ Q) ∧ ¬(¬P ∧ ¬Q) 

• Преобразуем часть данного выражения по закону Де Моргана:

¬(P ∧ Q) ∧ ¬(¬P ∧ ¬Q) =
= ¬(P ∧ Q) ∧ (P ∨ Q) 

• В итоге получим:

¬(P ∧ Q) ∧ (P ∨ Q) ∨ ¬A = 1

• А - наше неизвестное, а выделенную часть выражения можно найти. Необходимо, чтобы А = 1. Значит, предположим, что ¬А = 0, тогда, чтобы общее выражение было истинным (по условию), нужно чтобы ¬(P ∧ Q) ∧ (P ∨ Q) = 1.
• Значит, имеем:

¬(P ∧ Q) ∧ (P ∨ Q) = 1
А = 1

• Отобразим отрезки на числовой прямой, чтобы найти искомое значение:



• Очевидно, что А будет истинно в двух отмеченных на рисунке частях: 2 и 4 (на рис. желтым цветом). Но по условию нам необходимо найти А наибольшей длины, соответственно, выбираем отрезок [12,20], имеющий длину 8.

✎ 2 способ:
После того, как мы избавились от импликации, имеем:

¬(P ~ Q) ∨ ¬A = 1

• А - наше неизвестное, а выделенную часть выражения можно найти. Необходимо, чтобы А = 1. Значит, предположим, что ¬А = 0, тогда ¬(P ~ Q) = 1 (чтобы общее выражение было истинным, как указанно в условии).
• Иными словами ¬(P ~ Q) истинно для всех значений x, при которых P не равно Q (т.е. либо P = 1 и Q = 0, либо P = 0 и Q = 1).
• Это соответствует двум отрезкам (см. рисунок выше, желтым цветом): [3,6] и [12,20]. Но по условию нам необходимо найти А наибольшей длины, соответственно выбираем отрезок [12,20], имеющий длину 8.

Результат: 8

• Упростим выражение, введя обозначения:

A: x ∈ A
P: x ∈ P
Q: x ∈ Q

• Запишем формулу с новыми обозначениями, учитывая, что по условию она должна быть тождественно истинной:

A → ¬(P ~ Q) = 1

• Избавимся от импликации:

A → ¬(P ~ Q) = 1    =>
¬A ∨ ¬(P ~ Q) = 1

• А - наше неизвестное, тогда как выделенную часть формулы можно найти. Введем предположение, что А = 1. Значит, ¬А = 0 (т.е. А = 1), тогда ¬(P ~ Q) = 1 (так как общая формула должна быть истинной по условию).
• Иными словами ¬(P ~ Q) истинно для всех значений x, при которых P не равно Q (т.е. либо P = 1 и Q = 0, либо P = 0 и Q = 1).
• Отобразим отрезки на числовой прямой, чтобы найти искомое значение:



• Получаем, что А соответствует двум отрезкам (см. рисунок, желтым цветом): [11,15] и [21,40]. Но по условию нам необходимо найти А наибольшей длины, соответственно выбираем отрезок [21,40], имеющий длину 19.

Результат: 19

• Упростим выражение, введя обозначения:

A: x ∈ A
P: x ∈ P
Q: x ∈ Q

• Запишем формулу с новыми обозначениями, учитывая, что по условию она должна быть тождественно истинной:

(P → Q) ∨ A = 1

• Избавимся от импликации:

(¬P ∨ Q) ∨ A = 1

• А - наше неизвестное. А должно равняться только 1 в случае, если ¬P ∨ Q = 0 (если ¬P ∨ Q = 1, то А может равняться и 0 и 1, так как имеет место операция логического сложения - ∨)
• Значит, имеем ¬P ∨ Q = 0. Получим следующие три утверждения:

1. А = 1
¬P ∨ Q = 0
дизъюнкция ложна в единственном случае, когда оба операнда ложны:
¬P = 0  
Q = 0
или по-другому:
2. P = 1 
3. Q = 0

• То есть, А истинно (=1) в том случае, если P = 1 и Q = 0
• Отобразим отрезки на числовой прямой, чтобы найти искомое значение:



• Очевидно, что А будет истинно, только в части 2 (на рис.), то есть соответствовать отрезку [3,23], имеющему длину 20.

Результат: 20

• Упростим выражение, введя обозначения:

A: x ∈ A
P: x ∈ P
Q: x ∈ Q

• Запишем формулу с новыми обозначениями, учитывая, что по условию она должна быть тождественно ложной (= 0):

(P → Q) ∧ A = 0

• Избавимся от импликации:

(¬P ∨ Q) ∧ A = 0

• А - наше неизвестное. Необходимо поставить А в вынужденное состояние. Так, если ¬P ∨ Q = 1, тогда A должно быть равно только 0 (чтобы формула в результате была ложной).
• Имеем следующие утверждения для А = 0:

¬P ∨ Q = 1
1. А = 0 при P = 1 и Q = 1
2. А = 0 при P = 0 и Q = 0
3. А = 0 при P = 0 и Q = 1

• То есть для А = 1 имеем единственный оставшийся случай:

А = 1 при P = 1 и Q = 0

• Отобразим отрезки на числовой прямой, чтобы найти искомое значение:



• Рассмотрим отдельно каждую часть числовой прямой:

части 1 = 3 = 5 ¬P ∨ Q : 1 ∨ 0 = 1, значит А = 0
часть 2 ¬P ∨ Q : 1 ∨ 1 = 1, значит А = 0
часть 4 ¬P ∨ Q : 0 ∨ 0 = 0, значит А = 1

• А - истинно только в одном промежутке - [44, 48]. Найдем длину этого отрезка:

48 - 44 = 4

Результат: 4

• Упростим выражение, введя обозначения:

A: x ∈ A
P: x ∈ P
Q: x ∈ Q

• Запишем формулу с новыми обозначениями, учитывая, что по условию она должна быть тождественно ложной (= 0):

(P → Q) ∧ A = 0

• Избавимся от импликации:

(¬P ∨ Q) ∧ A = 0

• А - наше неизвестное. Необходимо найти вынужденное состояние для А. Так, если ¬P ∨ Q = 1, тогда A на этом отрезке вынуждено быть равным 0 (чтобы формула в результате была ложной).
• Значит, примем следующие утверждения:

¬P ∨ Q = 1
1. А = 0 при P = 1 и Q = 1
2. А = 0 при P = 0 и Q = 0
3. А = 0 при P = 0 и Q = 1

• То есть для А = 1 имеем единственный оставшийся случай:

А = 1 при P = 1 и Q = 0

• Отобразим отрезки на числовой прямой, чтобы найти искомое значение:



• Рассмотрим отдельно каждую часть числовой прямой:

1), 3), 5) ¬P ∨ Q : 1 ∨ 0 = 1, значит А = 0
2) ¬P ∨ Q : 0 ∨ 0 = 0, значит А = 1
4) ¬P ∨ Q : 1 ∨ 1 = 1, значит А = 0

• А - истинно только в одном промежутке - [12, 22]. Найдем длину этого отрезка:

22 - 12 = 10

Результат: 10

• Определим основные части выражения, выделив отдельно неизвестную часть - с А, и, так сказать, известную часть, то есть остальную.

    1                 2
(y+3x < A) ∨ (x > 20) ∨ (y > 40)

• Поскольку основными операциями являются операции дизъюнкции (логического сложения) и порядок их выполнения не важен, то последней, внешней, операцией будем выполнять дизъюнкцию слева, т.к. она объединяет неизвестную и известную часть.
• Сначала важно рассмотреть вторую часть выражения, известную, так как от нее будет зависеть значение A. Если вторая часть истинна, то А может быть как = 1, так и = 0. Такой вариант нам не подходит:

(y+3x < A) ∨ (x > 20) ∨ (y > 40)
  1 или 0?                   1               = 1
Не подходит!

• Соответственно, рассмотрим вариант, когда вторая часть ложна, тогда часть выражения с неизвестным А будет обязательно истинной, т.е.:

1. (y+3x < A) = 1
2. (x > 20) ∨ (y > 40) = 0

• Дизъюнкция ложна, когда оба операнда ложны, т.е. из второго пункта имеем:

x <= 20
y <= 40

• Для того, чтобы перекрыть все x и все y, возьмем наибольшие из возможных значений: x = 20, y = 40.
• Выразим А:

А > 3x + y
A > 3*20 + 40
A > 100 

• Поскольку требуется найти наименьшее значение А, то имеем А = 101.

Результат: 101