Методы решения задач на логику в ЕГЭ по информатике

В спецификации контрольных измерительных материалов  для проведения в 2017 году  единого государственного экзамена  по информатике и ИКТ существуют  два задания повышенной и высокой сложности (18,23) связанных со знанием основных понятий и законов математической логики, которые для многих учащихся действительно оказались сложными.

Уровни сложности заданий: Б – базовый; П – повышенный; В – высокий.

Задание 18. Знание основных понятий и законов математической логики

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

1.                задачи  с отрезками 

2.                задачи  с множествами 

3.                задачи  с делителями

4.                задачи  с побитовыми операциями 1) Задачи с отрезками

Пример 1.1.         Задание 18 (демо 2015)

На числовой прямой даны два отрезка: P = [37; 60] и Q = [40; 77].

Укажите наименьшую возможную длину такого отрезка A, что формула

(x  P) → (((x  Q) /\ ¬(x  A)) → ¬(x  P)) истинна при любом значении переменной х, т.е. принимает значение 1 при любом значении переменной х.  Решение

1. Преобразуем формулу:

 P → ((Q /\ ¬ A) → ¬P) = ¬P \/ (¬Q \/ A \/ ¬P) =

= ¬P \/ ¬Q \/ A \/ ¬P = ¬P \/ ¬Q \/ A  

¬P \/ ¬Q \/ A  = 1 

2. Рисуем отрезки: 

Задача может быть сведена к типовой задаче с множествами (задача 1)

A \/ X = 1       X = ¬P \/ ¬Q 

A_min = ¬X      A_min = ¬(¬P \/ ¬Q) = P /\ Q         Ответ: 20

Пример 1.2.         Задание 18 (ТР 2017) На числовой прямой даны два отрезка: P = [10, 34] и Q = [18,40]. 

Отрезок A таков, что формула  ¬(x  A) → ((x  P) → ¬(x  Q)) истинна при любом значении переменной х. Какое наименьшее количество точек, соответствующих нечётным целым числам, может содержать отрезок A?

Решение

1. Преобразуем формулу: ¬ A → (P → ¬Q) = A \/ (P → ¬Q) =

= A \/ (¬P \/ ¬Q) = A \/ ¬P \/ ¬Q  

A \/ ¬P \/ ¬Q  = 1  2. Рисуем отрезки: 

3. Находим решение:  количество точек, соответствующих нечётным целым числам на отрезке [18, 34] (34 – 18)/2 = 16/2 = 8

Ответ: 8

2)  Задачи с множествами

Пример 2.1.         Задание 18 (ТР 2014)

Элементами множества А являются натуральные числа. Известно, что выражение:

(x{2, 4, 6, 8, 10, 12})→(((x{3, 6, 9, 12, 15}) /\ ¬(xA))→ ¬(x{2, 4, 6, 8, 10, 12}))   истинно (т. е. принимает значение 1) при любом значении переменной х.

Определите наименьшее возможное значение суммы элементов множества A.

Решение:

1.     Обозначим:  P = {2, 4, 6, 8, 10, 12}   Q = {3, 6, 9, 12, 15} 

2.     Преобразуем выражение:

P    → ((Q /\ ¬A) → ¬P) = = ¬P \/ (¬(Q /\ ¬A)) \/ ¬P) =

 = ¬P \/ ¬Q \/ A \/ ¬P = ¬P \/ ¬Q \/ A = 1

3.     Приводим к типовой задаче с множествами:

A \/ (¬P \/ ¬Q)  = 1

A _min = ¬(¬P \/ ¬Q)  (см. задача 1) A _min = P /\ Q

Это числа, которые есть и в P, и в Q, а это числа 6 и 12. Их сумма равна 18.

Ответ: 18

Пример 2.2.         Задание 18

Элементами множества А, P и Q являются натуральные числа, причем

P    = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}

Q  = {3, 6, 9, 12, 15, 18, 21, 24, 27, 30}

Известно, что выражение:

((x A) → ¬(x P)) /\ (¬(x Q) → ¬(x A)) истинно (т. е. принимает значение 1) при любом значении переменной х. Определите наибольшее возможное количество элементов множества A.

Решение

Преобразуем выражение

(A → ¬ P) /\ (¬Q → ¬A) = (¬A \/ ¬P) /\ (Q \/ ¬A) =

= ¬A /\ Q \/ ¬A \/ ¬P /\ Q \/ ¬P /\ ¬A  = ¬A /\ (Q \/ 1 \/ ¬P) \/ ¬P /\ Q =

= ¬A \/ ¬P /\ Q = 1

A _max = ¬P /\ Q  (задача 2)

Это числа, которые есть  в Q и нет в P. A _max = {3, 9, 15, 21, 24, 27, 30} Ответ: 7

3)  Задачи с делителями

Пример 3.1. 

Для какого наибольшего натурального числа A выражение

¬ДЕЛ(x, A) → (¬ДЕЛ(x, 21) /\ ¬ДЕЛ(x, 35)) тождественно истинно (принимает значение 1 при любом натуральном значении переменной  x)

Выражение ДЕЛ(n, m) обозначает утверждение «натуральное число n делится без остатка на натуральное число m» Решение:

1.     Обозначим  A = ДЕЛ(x, A),  P = ДЕЛ(x, 21),  Q = ДЕЛ(x, 35)

2.     Преобразуем выражение

¬A → (¬P /\ ¬Q) = A \/ ¬P /\ ¬Q = 1

3.     Приводим к типовой задаче с множествами:

A_min  = ¬(¬P /\ ¬Q)     (задача 1)

A_min  = P \/ Q

P   = {21, 42, 63, 84, …} – множество всех чисел, которые делятся на 21

Q = {35, 70, 105, 140, …} – множество всех чисел, которые делятся на 35 P \/ Q = {21, 35, 42, 63, 70, 84, 105, 140…} – множество чисел, которые делятся на 21 или на 35.

A=ДЕЛ(x, A). Каким должно быть число A, чтобы получить множество P\/Q? A = 3, 5, 7, 14, 15, 21…  НОД (21, 35) = 7. 

 Ответ: 7

Пример 3.2. 

Для какого наименьшего натурального числа A выражение

ДЕЛ(x, A) → (¬ДЕЛ(x, 21) \/ ДЕЛ(x, 35)) тождественно истинно (принимает значение 1 при любом натуральном значении переменной  x)

Выражение ДЕЛ(n, m) обозначает утверждение «натуральное число n делится без остатка на натуральное число m» Решение:

1.     Обозначим  A = ДЕЛ(x, A),  P = ДЕЛ(x, 21),  Q = ДЕЛ(x, 35)

2.     Преобразуем выражение

A → (¬P \/ Q) = ¬A \/ ¬P \/ Q = 1

3.     Приводим к типовой задаче с множествами: A_max  = ¬P \/ Q    (см. задача 2)

P   = {21, 42, 63, 84, …} – множество всех чисел, которые делятся на 21

Q = {35, 70, 105, 140, …} – множество всех чисел, которые делятся на 35 ¬P \/ Q = {35, 70, 105, 140…} – множество всех чисел, которые не делятся на 21 плюс множество чисел, которые делятся на 35. 

A=ДЕЛ(x, A). Каким должно быть A, чтобы получить множество ¬P\/Q? A = 5, 7, 35 …   Ответ: 5

4) Задачи с побитовыми операциями

Пример 4.1.         Задание 18 (демо 2016)

Для какого наименьшего неотрицательного целого числа А формула:

x&25 ≠ 0 → (x&17 = 0 → x&А ≠ 0)

тождественно истинна (т.е. принимает значение 1 при любом неотрицательном целом значении переменной х)? Решение:

1.     Введем обозначения:  P = (x&25 ≠ 0),  _Q = (x&17 = 0),  A = (x&А ≠ 0)

2.     Преобразуем выражение:

P→ (Q → A) = 1, 

P  Q  A = 1

3.     Приводим к типовой задаче с множествами: A_min = (P  Q ) =  P  Q    (задача 1)

4.     Запишем числа 25 и 17 в двоичной системе:

номер бита 4 3 2 1 0

25₁₀ = 1 1 0 0 1₂    x&25 ≠ 0 хотя бы один из битов 4,3,0  должен быть = 1      

17₁₀ = 1 0 0 0 1₂    x&17 = 0  биты  4 и 0 должны быть равны 0  A_min=0 1 0 0 0₂  = 8₁₀      x&А ≠ 0  бит 3 должен быть равен 1 

Как же описать эту операцию?  В числе A нужно обязательно сделать единичными биты, которые равны 1 в числе P и равны 0 в числе Q. Ответ: 8 Пример 4.2. 

Для какого наименьшего неотрицательного целого числа А формула:

x&35 ≠ 0 → (x&31 = 0 → x&А ≠ 0)

тождественно истинна (т.е. принимает значение 1 при любом неотрицательном целом значении переменной х)? Решение

1.     Введем обозначения: P = (x&35 ≠ 0),  _Q = (x&31 = 0),     A = (x&А ≠ 0)

2.     Преобразуем выражение:

P→ (Q → A) = 1

P  Q  A = 1

3.     Приводим к типовой задаче с множествами:

A_min = (P  Q ) = P  Q    (см. задача 1)

4.     Запишем числа 35 и 31 в двоичной системе:

номер бита 5 4 3 2 1 0

35₁₀ = 1 0 0 0 1 1₂    x&35 ≠ 0 хотя бы один из битов 5,1,0 должен быть=1 

31₁₀ = 0 1 1 1 1 1₂    x&31 = 0  биты  4, 3, 2, 1, 0 должны быть равны 0 A_min = 1 0 0 0 0 0₂  = 32₁₀      x&А ≠ 0    бит 5 должен быть равен 1 

В числе A нужно обязательно сделать единичными биты, которые равны 1 в числе P и равны 0 в числе Q. Ответ: 32

Пример 4.3.         Задание 18 (демо 2017)

Для какого наименьшего неотрицательного целого числа А формула x&51 = 0 \/ (x&41 = 0 → x&А ≠ 0)

тождественно истинна (т.е. принимает значение 1 при любом неотрицательном целом значении переменной х)? Решение:

1.     Введем обозначения: Z₅₁= (x&51 = 0), Z₄₁ = (x&41 = 0), A =(x&А ≠ 0)

2.     Преобразуем выражение:

     Z₅₁ + (Z₄₁ → A) = Z₅₁ + Z₄₁ + A = 

= (Z41  A) → Z51 = Z41 or A → Z51  

3.     Запишем числа 51 и 41 в двоичной системе:

номер бита 5 4 3 2 1 0

     51₁₀ = 1 1 0 0 1 1₂

     4110 = 1 0 1 0 0 12                       

      Amin =   1 0 0 1 02  = 1810          

В числе A нужно обязательно сделать единичными биты, которые равны 1 в числе P и равны 0 в числе Q.

Ответ: 18

Задание 23. Анализ уравнений или систем логических уравнений

Решение — битовый вектор

Поскольку все переменные, входящие в решение уравнения или системы уравнений, логические (0 или 1), решение можно рассматривать как цепочку нулей и единиц длиной N. Такие цепочки называют битовыми цепочками, или битовыми векторами. 

При анализе систем логических уравнений удобно не исключать поочередно неизвестные, а рассматривать битовый вектор–решение как целое, как единый объект. Результатом такого анализа будет описание множества векторов-решений, которое позволит подсчитать количество решений. До того, как исследовать возможные решения, систему бывает полезно упростить или использовать замену переменных. 

Вначале мы разберем несколько простых уравнений и систем, а затем перейдем к более сложным, которые использовались в задачах ЕГЭ прошлых лет.

Простые случаи:

Пример 1. 

Найти число решений уравнения 

(х₁ = х₂)  (х₂ = х₃) ...  (х₄ = х₅) = 1.

Решение:

Все “сомножители” имеют форму х_i =х_i+1, они должны быть равны 1. Это значит, что любые два соседних бита должны быть равны. Существует всего две таких цепочки: 000000, 111111. Ответ:  2 

Пример 2. 

Найти число решений уравнения 

 (х₁ = х₂)   (х₂ = х₃) ...  (х₅ = х₆) = 1.

Решение:

Все “сомножители” имеют форму (x_i=x_i+1), они должны быть равны 1. Это значит, что каждые два соседних бита должны быть различны, то есть нули и единицы в битовой цепочке чередуются. Существует всего две таких цепочки: 101010, 010101. Ответ:  2 

Пример 3. 

Найти число решений уравнения 

(х₁ → х₂)  (х₂ → х₃) ...  (х₅ → х₆) = 1.

Решение (вариант 1):

Подобно рассмотренным выше задачам, все импликации: 

(х₁ → х₂), ..., (х₅ → х₆) должны быть истинны. 

Импликация a →b ложна только при a = 1 и b = 0.  Поэтому, если битовый вектор X = х1 х2... х6 — решение данного уравнения, и в нем встретилась единица, то правее нее будут только единицы (сочетание “10” запрещено!). Таким образом, уравнение имеет семь решений:

000000, 000001, 000011, 000111, 001111, 011111, 111111.

Каждое решение определяется тем, в какой позиции первый раз встречается единица: на 1-м, 2-м, ..., 6-м месте или вообще не встречается. Ответ:  7 

Решение (вариант 2):

Такое уравнение может быть записано в виде системы уравнений:

(х₁ → х₂) = 1

(х₂ → х₃) = 1

…

(х₅ → х₆) = 1.

Для первого уравнения (х1→х2)=1 существует 3 решения: 00, 01, 11.

Для системы из двух уравнений: 

(х₁ → х₂) = 1

(х₂ → х₃) = 1 существует 4 решения: 000, 001, 011, 111. Решая систему из 3 уравнений можно увидеть, что добавление в систему еще одного уравнения добавляет еще 1 решение. Таким образом, для такой системы уравнений, в которой  есть n переменных число решений равно n+1.  Ответ:  7 

Пример 4. 

Найти число решений системы уравнений 

(¬ х₁ \/ х₂) = 1

(¬ х₂ \/ х₃) = 1

(¬ х₃ \/ х₄) = 1

…

(¬ х₁₀₂₂ \/ х₁₀₂₃) = 1.

Для такой системы уравнений, в которой  есть n переменных число решений равно n+1.  Ответ:  1024 

Пример 5. 

Найти число решений уравнения 

((х₁  \/  х₂)→ х₃)  ((х₂  \/  х₃)→ х₄) ...  ((х₄  \/  х₅)→ х₆) = 1.

Решение:

Все сомножители имеют форму ((х_i + х_i+1)→ х_i+2), они должны быть равны 1, то есть недопустима импликация 1 → 0. 

Поскольку левая часть импликации — это логическая сумма двух соседних битов, а правая — следующий за ними бит, можно сделать вывод: слева от каждого нулевого бита (начиная с третьего) должны обязательно стоять два нуля. 

Этому условию удовлетворяют цепочки вида: все нули, потом — все единицы: 111111, 011111, 001111, 000111,  000011, 000001, 000000. 

Кроме того, этому уравнению удовлетворяет еще одна цепочка: 101111.  Всего уравнение имеет восемь решений.

Ответ:  8 

Задания из демонстрационных вариантов ЕГЭ

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

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

(x₁  x₂)  (x₂  x₃)  (x₃  x₄) = 1

(y₁  y₂)  (y₂  y₃)  (y₃  y₄) = 1 (z₁  z₂)  (z₂  z₃)  (z₃  z₄) = 1  x₁  y₂  z₃  = 0 где x₁, …, x₄, y₁, …, y₄, z₁, …, z₄, – логические переменные? 

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

Решение (использование свойств битовых цепочек): 1) перепишем систему с более понятными обозначениями:

(x₁  x₂)(x₂  x₃)(x₃  x₄) 1

(y₁  y₂)(y₂  y₃)(y₃  y₄) 1

(z₁  z₂)(z₂  z₃)(z₃  z₄) 1 x₁  y₂  z₃  0

2)    первые 3 уравнения однотипны; рассмотрим первое из них:

(x₁  x₂)(x₂  x₃)(x₃  x₄) 1

3)    рассмотрим решение этого уравнения как битовую цепочку X  x1x2x3x4

4)    все импликации должны быть равны 1, в цепочке X запрещена комбинация 10, поэтому после первой единицы далее следуют только единицы; вот все 5 решений X:

X  =  0000    0001    0011    0111    1111

5)    второе и третье уравнения не зависят от первого и имеют такую же структуру; вот все их решения Y  y₁y₂y₃y₄ и Z  z₁z₂z₃z₄ :

Y  =  0000    0001    0011    0111    1111

Z  =  0000    0001    0011    0111    1111

6)    если бы система состояла бы только из первых трёх уравнений, общее количество решений было бы равно 5 ∙ 5 ∙ 5 = 125 

7)    теперь рассмотрим последнее уравнение, связывающее X, Y и Z: x₁  y₂  z₃  0

8)    таким образом, нужно исключить все решения, где x₁  y₂  z₃ 1

9)    у нас есть одно решение X с x₁ 1, два решения Y с y₂ 1 и три решения Z с z₃ 1; поэтому из 125 нужно отбросить 1 ∙ 2 ∙ 3 = 6 решений; остаётся 125 – 6 = 119 решений Ответ: 119.

Пример 7.

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

(x₁  y₁)  ((x₂  y₂)  (x₁  y₁)) = 1

(x₂  y₂)  ((x₃  y₃)  (x₂  y₂)) = 1 ...

(x₅  y₅)  ((x₆  y₆)  (x₅  y₅)) = 1 x₆  y₆  = 1

где x₁, …, x₇, y₁, …, y₇, – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Решение (использование свойств битовых цепочек):

1)      перепишем систему с более понятными обозначениями:

(x₁  y₁)(x₂  y₂  x₁  y₁) 1

(x₂  y₂)(x₃  y₃  x₂  y₂) 1

                       L                                     

(x₅  y₅)(x₆  y₆  x₅  y₅) 1 x₆  y₆ 1

2)      первые 5 уравнений однотипны, отличаются только сдвигом номеров переменных

3)      будем рассматривать каждое решение как пару битовых цепочек

X  x1x2x3x4x5x6 и Y  y1y2y3y4y5y6

4)      выполним замену переменных z₁  x₁  y₁, z₂  x₂  y₂, K, z₆  x₆  y₆

5)      тогда получаем систему

(z₂  z₁) 1

(z₃  z₂) 1

L

(z₆  z₅) 1 которую можно свернуть в одно уравнение:

(z₂  z₁)(z₃  z₂)K(z₆  z₅) 1

6)      в каждой скобке запрещена комбинация 10, это значит, что в цепочке Z  z₁z₂z₃z₄z₅z₆ запрещена комбинация 01

7)      это значит, что цепочка Z имеет структуру «сначала все единицы, потом все нули», вот все 7 возможных цепочек длиной 6: 111111 111000 000000 111110 110000 111100 100000

8)      теперь нужно перейти к исходным переменным, то есть, к цепочкам

X  x1x2x3x4x5x6 и Y  y1y2y3y4y5y6

9)      пусть z_i  x_i  y_i  0; в исходном уравнении есть ещё ограничение

(xi   y_i ) 1, это та скобка, которую мы «временно забыли», получаем систему

z_i  x_i  y_i  0

                                           

xi  yi 1 первое уравнение означает, что x_i  y_i , второе говорит о том, что, по крайней мере, одно из этих значение равно 1; таких пар две: (0;1) и (1;0)

10)  это означает, что каждый ноль в цепочке Z даёт два решения в исходных переменных

11)  теперь исследуем вариант z_i  x_i  y_i 1; добавляя ограничение

(xi   y_i ) 1, получаем систему

z_i  x_i  y_i 1

                                           

xi  yi 1 первое уравнение означает, что x_i  y_i 1, второе говорит о том, что, по крайней мере, одно из этих значение равно 1; существует только одна такая пара: (1;1)

12)  таким образом, каждый ноль в цепочке Z увеличивает в два раза число решений в исходных переменных, а единицы не меняют количества

13)  например, цепочка Z = 111111 не содержит нулей и даёт только одно решение

14)  цепочка Z = 111110 содержит один ноль и даёт 2¹ = 2 решения

15)  цепочка Z = 111100 содержит два ноля и даёт 2² = 4 решения

16)  общее количество решений системы 2⁰ + 2¹ + 2² +2³ + 2⁴ + 2⁵ +2⁶ = 127. Ответ: 127.

Пример 8  Задание 23 (ТР 2017)

Сколько существует различных наборов значений логических переменных  x₁, x₂, ... x₅, y₁, y₂, ... y₅, которые удовлетворяют всем перечисленным ниже условиям?  

¬ (x₁ /\ y₁) \/ (x₂ /\ y₂) = 1 

¬ (x₂ /\ y₂) \/ (x₃ /\ y₃) = 1 

¬ (x₃ /\ y₃) \/ (x₄ /\ y₄) = 1 

¬ (x₄ /\ y₄) \/ (x₅ /\ y₅) = 1  

В ответе не нужно перечислять все различные наборы значений переменных x₁, x₂, ... x₅, y₁, y₂, ... y₅, при которых выполнена данная система равенств.  В качестве ответа Вам нужно указать количество таких наборов.  

Решение (использование свойств битовых цепочек): 1) Перепишем систему уравнений, используя свойство импликации:

(x₁  y₁)  (x₂  y₂) = 1

(x₂  y₂)  (x₃  y₃) = 1

(x₃  y₃)  (x₄  y₄) = 1

(x₄  y₄)  (x₅  y₅) = 1

2)      Все уравнений системы однотипны, отличаются только сдвигом номеров переменных

3)      будем рассматривать каждое решение как пару битовых цепочек X  x1x2x3x4x5 и Y  y1y2y3y4y5

4)      выполним замену переменных z₁  x₁ y₁, z₂  x₂  y₂, K, z₅  x₅  y₅

5)      тогда получаем систему

(z₂  z₁) 1

(z₃  z₂) 1

L

(z₆  z₅) 1 которую можно свернуть в одно уравнение:

(z₂  z₁)(z₃  z₂)K(z₆  z₅) 1

6)      в каждой скобке запрещена комбинация 10, это значит, что в цепочке Z  z₁z₂z₃z₄z₅z₆ запрещена комбинация 01

7)      это значит, что цепочка Z имеет структуру «сначала все единицы, потом все нули», вот все 6 возможных цепочек длиной 5:

                         11111 11110      11100     11000     10000     00000

8)      теперь нужно перейти к исходным переменным, то есть, к цепочкам

X  x1x2x3x4x5 и Y  y1y2y3y4y5

9)      пусть z_i  x_i  y_i  0; конъюнкция равно нулю в трех случаях.  

Это означает что каждый ноль в цепочке Z даёт три решения в исходных переменных.

10)  теперь исследуем вариант z_i  x_i  y_i 1; конъюнкция равно единице только в одном случае. Это означает, что каждая единица в цепочке Z даёт одно решение в исходных переменных.

11)  таким образом, каждый ноль в цепочке Z увеличивает в три раза число решений в исходных переменных, а единицы не меняют количества

12)  например, цепочка Z = 11111 не содержит нулей и даёт только одно решение

13)  цепочка Z = 11110 содержит один ноль и даёт 3¹ = 3 решения

14)  цепочка Z = 11100 содержит два ноля и даёт 3² = 9 решений и так далее

15)  общее количество решений системы 3⁰ + 3¹ + 3² +3³ + 3⁴ + 3⁵ = 364.

Ответ: 364