Право. Битовые операции в задачах ким егэ по информатике. Часть II
 Скачать 266.08 Kb.
|
|
19.02.2017 Битовые операции в задачах КИМ ЕГЭ по информатике. Часть II К.Ю. Поляков, д.т.н., учитель информатики ГБОУ СОШ № 163, г. Санкт-Петербург В данной статье рассматриваются задачи следующего типа (впервые эти задачи поя- вились в КИМ на ЕГЭ 2015 года): Введёмвыражение M & K, обозначающее поразрядную конъюнкцию M и K (логиче- ское «И» между соответствующими битами двоичной записи). 1. Определите наименьшее натуральное число a, такое что выражение (x & α = 0 ) → ((x & 29 = 0) → (x &43≠ 0)) тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной x)? 2. Определите наибольшее натуральное число a, такое что выражение (x & α ≠ 0 ) → ((x & 29 = 0) → (x &43≠ 0)) тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной x)? Предлагается и обосновывается новый подход к решению таких задач, основанный на идее А.В. Здвижковой (г. Армавир). Обозначения Через K Z обозначим множество чисел, которые в результате поразрядной конъюнк- ции с числом K дают 0: } 0 & : { = = K x x K Z Соответственно, числа, которые в результате поразрядной конъюнкции с числом K дают ненулевое значение, составляют множество K Z : } 0 & : { ≠ = K x x K Z Введём утверждения ) ( ) ( K K x x Z Z ∈ = , ) ( ) ( K K x x Z Z ∈ = Для сокращения записи будем вместо ) (x Z K и ) (x Z K писать соответственно K Z и K Z . Нашей целью будет поиск чисел a, при которых некоторое логическое выражение, зависящее от a, истинно для любых натуральных значений x. Будет обозначать через A выражение ) (x Z a Два свойства импликации Сначала докажем два свойства импликации, которые будут нам нужны далее 1 Свойство 1. Следующее равенство тождественно истинно: ) ( ) ( ) ( C A B A C B A → + → = + → 1 Автору не удалось обнаружить их в известной литературе, хотя они легко доказываются. К.Ю. Поляков, 2016 2 Доказательство. Представим левую и правую часть равенства через операции ИЛИ и НЕ: C B A C B A + + = + → ) ( C B A C A B A C A B A + + = + + + = → + → ) ( ) ( В обоих случаях получили одинаковые выражения, что и требовалось доказать. Свойство 2. Следующее равенство тождественно истинно: ) ( ) ( ) ( C A B A C B A → ⋅ → = ⋅ → Доказательство. Представим левую и правую часть равенства через операции ИЛИ и НЕ: C B A C B A ⋅ + = ⋅ → ) ( C B A C A B A C A B A ⋅ + = + ⋅ + = → ⋅ → ) ( ) ( ) ( ) ( При упрощении второго выражения использован распределительный закон. В результате в обоих случаях получили одинаковые выражения, что и требовалось доказать. Математическое обоснование метода В этом разделе мы докажем несколько утверждений, на которых основан предлагаемый метод решения. Утверждение 1. Пусть логическое выражение K Z истинно для некоторого нату- рального числа x. Тогда все биты двоичной записи числа x, соответствующие еди- ничным битам двоичной записи числа K, нулевые. Доказательство. Пусть k i – i-ый бит числа K (находящийся в i-м разряде его двоич- ной записи) – равен 1. По условию для числа x истинно логическое выражение ) 0 & ( ) ( = = K x x Z K Тогда в результате конъюнкции с соответствующим i-м битом двоичной записи числа x, который обозначим как x i , получаем 0 & = i i k x . Поскольку по условию k i = 1, это возмож- но только при 0 = i x , что и требовалось доказать. Утверждение 2. Логическоевыражение M K Z Z → истинно для всех x тогда и только тогда, когда множество единичных битов двоичной записи числа M входит во мно- жество единичных битов двоичной записи числа K. Доказательство. Пусть множество единичных битов числа M: } ,..., , { 2 1 q M m m m B = входит во множество единичных битов числа K: } ,..., , { 2 1 p K k k k B = и пусть для некоторого x выполняется условие K Z . Это значит, что все биты числа x с но- мерами p k k k ,..., , 2 1 равны 0. Поскольку любой единичный бит числа M входит в это мно- жество, истинно также и условие M Z Предположим обратное: условие M K Z Z → истинно для всех x. Пусть при этом один из единичных битов числа M, скажем, бит с номером m 1 , не входит во множество K B . Это К.Ю. Поляков, 2016 3 значит, что для любого числа x, в котором все биты из множества K B равны 0, а бит m 1 равен 1, высказывание K Z будет истинно, а M Z – ложно, так что высказывание M K Z Z → истинно не для всех x. Получили противоречие, что и доказывает вторую часть утвержде- ния. Утверждение 3. Для любого натурального x справедливо равенство: M K M K Z Z Z or ) ( = ⋅ , где or обозначает поразрядную дизъюнкцию между двоичной записью чисел K и M. Доказательство. Обозначим множества единичных битов чисел K и M через } ,..., , { 2 1 p K k k k B = , } ,..., , { 2 1 q M m m m B = Пусть одновременно истинны логические выражения K Z и M Z . Тогда логическое выра- жение N Z истинно для всех N, у которых множество единичных битов } ,..., , { 2 1 w N n n n B = таково, что каждый из них входит во множество K B или во множество M B . В частности, одно из таких чисел – это M K N or = Напротив, пусть M K N or = . При этом все единичные биты двоичной записи чисел K и M входят во множество N B . Из утверждения 2 следует, что одновременно истинны выражения K Z и M Z , то есть истинно M K Z Z ⋅ . Утверждение доказано. Утверждение 4. При любых натуральных числах K и M существуют значения x, при которых логическоевыражение M K Z Z → ложно. Доказательство. Рассмотрим отдельно два случая. 1) Множество единичных битов числа M, } ,..., , { 2 1 q M m m m B = , входит во множество единичных битов числа K, } ,..., , { 2 1 p K k k k B = . Если при этом истинно K Z , то все биты чис- ла x из множества K B равны нулю. Среди этих битов не может быть ненулевых. Поэтому высказывание M K Z Z → ложно для всех x, для которых истинно K Z 2) Множество M B содержит биты, не входящие во множество K B . При этом выска- зывание M K Z Z → ложно для всех x, для которых истинно K Z и, кроме того, все биты, входящие во множество M B , равны нулю. Утверждение 5. При любых натуральных числах K и M существуют значения x, при которых логическоевыражение N M K Z Z Z ⋅ → ложно. Доказательство. Применим доказанное выше свойство 2 импликации: ) ( ) ( N K M K N M K Z Z Z Z Z Z Z → ⋅ → = ⋅ → В силу утверждения 4 второй сомножитель, N K Z Z → , равен нулю хотя бы для некоторых x, что доказывает утверждение. Утверждение 6. Пусть выражение N K Z Z → истинно при любом натуральном x. То- гда выражение ) ( N K Z A Z + → истинно для всех x при любом выборе a. К.Ю. Поляков, 2016 4 Доказательство. Применим доказанное выше свойство 1 импликации: ) ( ) ( ) ( N K K N K Z Z A Z Z A Z → + → = + → Так как второе слагаемое истинно при любых x, результат не зависит от первого слагаемо- го, то есть от выбора a. Утверждение 7. Пусть выражение N K Z Z → ложно при некотором натуральном x. Тогда выражение ) ( N K Z A Z + → истинно для всех x при условии, что 1 = → A Z K Доказательство. Применим доказанное выше свойство 1 импликации: ) ( ) ( ) ( N K K N K Z Z A Z Z A Z → + → = + → Если первое слагаемое истинно при любых x, то и левая часть равенства тоже истинна. Что и требовалось доказать. Утверждение 8. Пусть выражение M K Z Z + истинно при некотором натуральном x. Тогда истинно выражение M K Z & Доказательство. Обозначим множества единичных битов чисел K и M через } ,..., , { 2 1 p K k k k B = , } ,..., , { 2 1 q M m m m B = Пусть для некоторого x истинно одно из логических выражений, K Z или M Z . Истинность K Z означает, что в числе x биты с номерами p k k k ,..., , 2 1 – нулевые, истинность M Z озна- чает, что в числе x биты с номерами q m m m ,..., , 2 1 – нулевые. В любом случае биты числа x, номера которых входят в оба множества, и в } ,..., , { 2 1 p K k k k B = , и в } ,..., , { 2 1 q M m m m B = , – нулевые. Соответствующее число можно получить как результат поразрядной операции «И» между числами K и M. Утверждение доказано. Необходимо отметить, что обратное высказывание неверно: если M K Z & истинно, то это совершенно не означает, что истинно M K Z Z + . Контрпример: пусть при K = 3 и M = 5 истинно выражение 1 5 & 3 & Z Z Z M K = = , то есть бит 0 числа x равен нулю. Этому условию соответствует любое чётное число, например, x = 6, в котором биты 1 и 2 равны 1, то есть 0 ) 6 ( ) 6 ( 3 = = Z Z K и 0 ) 6 ( ) 6 ( 5 = = Z Z M Утверждение 9. Минимальное натуральное число a, при котором истинновыраже- ние ) ( M K Z Z A + → , равно ) , min( M K Доказательство. Согласно Свойству 1, представим выражение в виде ) ( ) ( ) ( M K M K Z A Z A Z Z A → + → = + → Как следует из Утверждения 2, при A = K или A = M это выражение равно 1 при всех x, так как, по крайней мере, одно из слагаемых равно 1. Таким образом, при ) , min( M K a = ут- верждение верно. Докажем, что нет меньшего подходящего a, используя метод «от противного»: пусть существует такое a, меньшее, чем ) , min( M K , при котором 1 ) ( = + → M K Z Z A для всех натуральных x. Поскольку a < K, двоичная запись числа K содержит единичные биты, которых нет в двоичной записи числа a (обозначим это множество битов через 0 K B ). Поэтому для всех К.Ю. Поляков, 2016 5 чисел x, у которых все единичные биты числа a также равны 1, но ещё есть единичные би- ты из множества 0 K B , получаем 0 0 1 = → = → K Z A Аналогично двоичная запись числа M содержит единичные биты, которых нет в двоичной записи числа a (обозначим это множество через 0 M B ). Поэтому для всех чисел x, у которых все единичные биты числа a также равны 1, но ещё есть единичные биты из множества 0 M B , получаем 0 0 1 = → = → M Z A . Таким образом, для всех чисел, в двоичной записи которых все единичные биты числа a равны 0, но есть ещё единичные биты, вхо- дящие во множества 0 K B и 0 M B , оба слагаемых равны 0, так что все выражение ложно. Что и требовалось доказать. Утверждение 10. Пусть 0 = → M K Z Z . Тогда 1 ) ( = + → M K Z A Z тогда и только то- гда, когда 1 = → A Z K Доказательство. Согласно Свойству 1, представим выражение в виде ) ( ) ( ) ( M K K M K Z Z A Z Z A Z → + → = + → Во-первых, если 1 = → A Z K , то сразу 1 ) ( = + → M K Z A Z Чтобы доказать обратное, рассмотрим слагаемое M K Z Z → . Обозначим через K B множество единичных битов двоичной записи числа K,а через 0 M B – множество единич- ных битов в двоичной записи числа M, которые равны 0 в двоичной записи числа K. Выражение M K Z Z → ложно для всех x, в двоичной записи которых все биты из множества K B равны 0, а среди битов из множества 0 M B есть единичные. Если для этих значения x истинно выражение ) ( M K Z A Z + → , то это значит, что для них 1 = → A Z K Поскольку в двоичной записи всех таких x все биты из множества K B равны нулю, то 1 = → A Z K для всех натуральных x, что и требовалось доказать. Утверждение 11. 1 ) ( = + → M K Z A Z тогда и только тогда, когда 1 = → A Z M K or Доказательство. Согласно Свойству 1, представим выражение в виде ) ( ) ( ) ( M K K M K Z Z A Z Z A Z → + → = + → Рассмотрим слагаемое M K Z Z → . Обозначим через K B множество единичных битов двоичной записи числа K,а через M B – множество единичных битов в двоичной записи числа M. Как следует из доказательства Утверждения 4, выражение M K Z Z → ложно для всех x, в двоичной записи которых все биты из множеств K B и M B равны 0. Таким обра- зом, выражение M K Z Z → ложно тогда, когда истинно M K Z or , и истинно тогда, когда ис- тинно M K Z or . Поэтому можно выполнить замену M K Z Z → на M K Z or : A Z A Z Z A Z Z Z A Z Z A Z M K M K K M K K M K K M K → = → ⋅ = + + = + → = + → or or or or ) ( ) ( ) ( Поскольку в силу Утверждения 3 имеем M K M K K Z Z Z or or = ⋅ , получаем A Z Z A Z M K M K → = + → or ) ( К.Ю. Поляков, 2016 6 Утверждение 12. Пусть 0 = → L K Z Z . Тогда 1 ) ( = ⋅ + → M L K Z Z A Z тогда и только тогда, когда 1 = → A Z K Доказательство. Представим выражение в виде ) ( ) ( ) ( M L K K M L K Z Z Z A Z Z Z A Z ⋅ → + → = ⋅ + → Во-первых, если 1 = → A Z K , то сразу 1 ) ( = ⋅ + → M L K Z Z A Z Чтобы доказать обратное, рассмотрим второе слагаемое, преобразуя его согласно Свойству 2: ) ( ) ( ) ( M K L K M L K Z Z Z Z Z Z Z → ⋅ → = ⋅ → Предположим, что для некоторого a выражение A Z K → ложно при некоторых x, но 1 ) ( = ⋅ + → M L K Z Z A Z для всех x. Поскольку A Z K → ложно при некоторых x, двоичная запись числа a содержит единичные биты, которые равны 0 в двоичной записи числа K. Так как по условию двоичная запись числа L содержит единичные биты, которые равны 0 в двоичной записи числа K, то для значений x, в двоичной записи которых эти «лишние» биты равны 1, имеем 0 = → L K Z Z , так что всё выражение равно 0. Получили противоре- чие. Следовательно, 1 = → A Z K Утверждение 13. Пусть 1 = → L K Z Z . Тогда 1 ) ( = ⋅ + → M L K Z Z A Z тогда и только тогда, когда 1 = → A Z M K or Доказательство. Используя доказанные выше утверждения, преобразуем выраже- ние: M K L K K M K L K K M L K K M L K Z Z Z A Z Z Z Z Z A Z Z Z Z A Z Z Z A Z or ⋅ → + → = → ⋅ → + → = = ⋅ → + → = ⋅ + → ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( Поскольку по условию множество единичных битов двоичной записи числа L явля- ется подмножеством множества единичных битов числа K, то 1 = → L K Z Z для всех x. По- этому выражение далее преобразуется так же, как и при доказательстве Утверждения 11: 1 1 1 1 ) ( = → = + ⋅ = + + = + → A Z A Z Z Z A Z Z A Z M K M K K M K K M K K or or or or что и требовалось доказать. Общий метод решения Идея метода решения, предложенная А.В. Здвижковой, состоит в следующем: 1) упростить логическое выражение так, чтобы свести его к импликации и избавиться от всех инверсий; 2) применить утверждения 3-7 с целью свести задачу к форме, в которой можно исполь- зовать утверждение 2. Упрощение может привести к нескольким разным формам выражения, например, К.Ю. Поляков, 2016 7 1) N K Z A Z → ⋅ ) ( 2) A Z K → 3) ) ( N K Z A Z + → 4) ) ( N K Z A Z ⋅ → В первом случае a K K Z A Z or = ⋅ , так что с помощью числа a можно добавить в левую часть единичные биты числа N, которых нет во множестве единичных битов числа K. Во втором случае согласно утверждению 2 число a должно быть выбрано так, чтобы все его единичные биты входили во множество единичных битов числа K. В третьем случае с помощью утверждений 6 и 7 можно либо свести задачу ко второ- му случаю, либо придти к выводу от том, что число a можно выбрать произвольно. В четвёртом случае решение не всегда существует: с помощью числа a можно доба- вить в правую часть единичные биты, но нельзя их убрать. Поэтому если множество еди- ничных битов числа N не является подмножеством единичных битов числа K, задача не имеет решения (при любом выборе a выражение будет ложно при некоторых значениях x). Примеры Пример 1 . Определите наименьшее натуральное число a, такое что выражение (x & 53 ≠ 0) → ((x & 41 = 0) → (x & a ≠ 0)) тождественно истинно. Решение. Используя обозначения, приведенные в начале статьи, запишем выражение в виде ) ( 41 53 A Z Z → → . Упрощаем выражение, раскрывая импликации по формуле B A B A + = → : A Z Z A Z Z A Z Z + + = → + = → → 41 53 41 53 41 53 ) ( ) ( Теперь избавляемся от инверсий, применяя закон де Моргана и переходя к импликации: 53 41 53 41 41 53 ) ( ) ( Z A Z Z A Z A Z Z → ⋅ = + ⋅ = + + Применяем утверждение 3: 53 or 41 53 41 ) ( Z Z Z A Z a → = → ⋅ Таким образом, с помощью числа a мы должны добавить в левую часть недостающие би- ты – те, которые есть в двоичной записи числа 53, но отсутствуют в двоичной записи чис- ла 41: разряды 5 4 3 2 1 0 41 = 101001 53 = 110101 Биты, которые обязательно должны быть в числе a – это биты в разрядах 4 и 2 (выделены фоном), поэтому минимальное значение числа a min = 2 4 + 2 2 = 20. Можно выбрать и любое другое значение a, в двоичной записи которого эти биты равны 1. Пример 2 . Определите наибольшее натуральное число a, такое что выражение (x & a ≠ 0) → ((x & 20 = 0) → (x &5≠ 0)) К.Ю. Поляков, 2016 8 тождественно истинно. Решение. Используя обозначения, приведенные в начале статьи, запишем выражение в виде ) ( 5 20 Z Z A → → . Упрощаем выражение, раскрывая импликации по формуле B A B A + = → : 5 20 5 20 5 20 ) ( ) ( Z Z A Z Z A Z Z A + + = → + = → → Теперь избавляемся от инверсий, применяя закон де Моргана и переходя к импликации: A Z Z A Z Z Z Z A → ⋅ = + ⋅ = + + ) ( ) ( 5 20 5 20 5 20 Согласно утверждению 3, 5 or 20 5 20 Z Z Z = ⋅ . Вычисляем разряды 4 3 2 1 0 20 = 10100 5 = 00101 20 or 5 = 10101 = 21 Таким образом, получили 1 21 = → A Z . Согласно утверждению 2, все единичные биты числа а должны присутствовать в числе 21. Поэтому максимальное значение a max = 21. Кроме того, можно взять и другие значения a, которые не содержат в двоичной записи других единичных битов, кроме 4-го, 2-го и 0-го (это 1, 4, 5, 16, 17 и 20). Пример 3 . Определите наибольшее натуральное число a, такое что выражение (x & a ≠ 0) → ((x & 12 = 0) → (x &21= 0)) тождественно истинно. Решение. Используя обозначения, приведенные в начале статьи, запишем выражение в виде ) ( 21 12 Z Z A → → . Упрощаем выражение, раскрывая импликации по формуле B A B A + = → : 21 12 21 12 21 12 ) ( ) ( Z Z A Z Z A Z Z A + + = → + = → → Теперь избавляемся от инверсий, переходя к импликации: ) ( 21 12 21 12 Z A Z Z Z A + → = + + Согласно свойству 1 импликации, ) ( ) ( ) ( 21 12 12 21 12 Z Z A Z Z A Z → + → = + → . Двоичная за- пись числа 21 = 10101 2 содержит единичные биты, которые не входят во множество еди- ничных битов числа 12 = 1100 2 . Поэтому по утверждению 7 задача сводится к обеспече- нию условия 1 12 = → A Z Согласно утверждению 2, все единичные биты числа a должны присутствовать в числе 12. Поэтому максимальное значение a max = 12. Кроме того, можно взять и другие значения a, которые не содержат в двоичной записи других единичных битов, кроме 3-го и 2-го (это 4, 8 и 12). Пример 4 . Определите наименьшее натуральное число a, такое что выражение ( (x &28 ≠ 0) ∨ (x & 45 ≠ 0)) → ((x & 48 = 0) → (x & a ≠ 0)) тождественно истинно. Решение. Используя обозначения, приведенные в начале статьи, запишем выражение в виде ) ( ) ( 48 45 28 A Z Z Z → → + . Упрощаем выражение, раскрывая импликации: К.Ю. Поляков, 2016 9 A Z Z Z A Z Z Z A Z Z Z + + ⋅ = → + + = → → + 48 45 28 48 45 28 48 45 28 ) ( ) ( ) ( Теперь избавляемся от инверсий, используя закон де Моргана и переходя к импликации: ) ( ) ( 45 28 48 45 28 48 48 45 28 Z Z A Z Z Z A Z A Z Z Z ⋅ → ⋅ = ⋅ + ⋅ = + + ⋅ Упрощаем выражение в правой части, используя утверждение 3: 45 or 28 45 28 Z Z Z = ⋅ . Вычис- ляем: разряды 5 4 3 2 1 0 28 = 011100 45 = 101101 28 or 45 = 111101 = 61 Нам нужно обеспечить истинность выражения 61 48 ) ( Z A Z → ⋅ при всех x. Согласно утвер- ждению 2 для этого необходимо, чтобы множество битов числа 61 входило во множество битов числа 48 or a, то есть с помощью a мы можем добавить недостающие биты: разряды 5 4 3 2 1 0 48 = 110000 61 = 111101 Биты, которые обязательно должны быть в числе a – это биты в разрядах 3, 2 и 0 (выделе- ны фоном), поэтому минимальное значение числа a min = 2 3 + 2 2 + 2 0 = 13. Можно выбрать и любое другое значение a, в двоичной записи которого эти биты равны 1. Пример 5 . (А.Г. Гильдин). Определите наибольшее натуральное число a, такое что выражение (x &19= 0) ∧ (x & 38 ≠ 0) ∨ ((x & 43 = 0) → ((x & a = 0) ∧ (x & 43 = 0))) тождественно истинно. Решение. Используя обозначения, приведенные в начале статьи, запишем выражение в виде )) ( ( 43 43 38 19 Z A Z Z Z ⋅ → + ⋅ . Упрощаем выражение, приводя его к импликации: )) ( ) (( 38 19 43 43 Z Z Z A Z ⋅ + ⋅ → Согласно свойству 1 импликации, ) ( ) ( )) ( ) (( 38 19 43 43 43 38 19 43 43 Z Z Z Z A Z Z Z Z A Z ⋅ → + ⋅ → = ⋅ + ⋅ → По утверждению 12, второе слагаемое в правой части можно отбросить, поэтому остается обеспечить истинность выражения 43 43 Z A Z ⋅ → В силу утверждений 3 и 2, множество единичных битов числа a or 43 должно вхо- дить во множество единичных битов числа 43. Поэтому число a может содержать единич- ные биты только в тех разрядах, где они есть в двоичной записи числа 43. Таким образом, a max = 43. Кроме этого, можно использовать и другие значения a, все единичные биты ко- торых входят во множество единичных битов числа 43: это 1, 2, 3, 8, 9, 10, 11, 32, 33, 34, 35, 40, 41, 42 и 43. Пример 6 . (М.В. Кузнецова). Определите наибольшее натуральное число a, такое что выражение (( (x &13 ≠ 0) ∨ (x & a ≠ 0)) → (x & 13 ≠ 0) ∨ ((x & a ≠ 0) ∧ (x & 39 = 0)) К.Ю. Поляков, 2016 10 тождественно истинно. Решение. Используя обозначения, приведенные в начале статьи, запишем выражение в виде 39 13 13 ) ) (( Z A Z A Z ⋅ + → + . Упрощаем выражение, раскрывая импликацию: 39 13 13 39 13 13 39 13 13 ) ) (( Z A Z A Z Z A Z A Z Z A Z A Z ⋅ + + ⋅ = ⋅ + + + = ⋅ + → + Применяем распределительный закон 13 13 13 13 13 13 ) ( ) ( Z A Z A Z Z Z A Z + = + ⋅ + = + ⋅ Получаем 39 13 39 13 13 Z A Z A Z A Z A Z ⋅ + + = ⋅ + + ⋅ Используем распределительный закон ещё раз 39 39 39 ) ( ) ( Z A Z A A A Z A A + = + ⋅ + = ⋅ + так что выражение сводится к 39 13 Z Z A + + . Теперь избавляемся от инверсий, переходя к импликации: ) ( 39 13 39 13 Z A Z Z Z A + → = + + По свойству 1 импликации имеем ) ( ) ( ) ( 39 13 13 39 13 Z Z A Z Z A Z → + → = + → Поскольку число 39 = 100111 2 содержит единичные биты, которых нет в числе 13 = 1101 2 , второе слагаемое, 39 13 Z Z → , равно 0 (ложно для каких-то x), поэтому остается обеспечить только равенство 1 13 = → A Z . В силу утверждения 2, для этого требуется, чтобы двоичная запись числа a имела единичные биты только там, где есть единичные биты в числе 13. Поэтому a max = 13. Кроме того, условие выполнено при выборе a = 1, 4, 5, 8, 9, 12 и 13. Количество этих решений несложно подсчитать. Число 13 содержит m = 3 ненулевых бита, в числе a каж- дый из них может быть равен 0 или 1. Поэтому общее количество возможных комбинаций равно 2 m . Учитывая, что нас интересуют только натуральные числа, нельзя выбрать все эти биты нулевыми, поэтому один вариант исключается. Итог: количество решений на множестве натуральных чисел равно 2 m –1. Отметим, что если в этой задаче вместо чисел 13 и 39 взять, например, числа 53 и 21, то выражение истинно при любом выборе a (см. утверждение 6). Это связано с тем, что все единичные биты числа 21 = 10101 2 входят во множество единичных битов числа 53 = 110101 2 Пример 7 . Определите наибольшее натуральное число a, такое что выражение ((x &46= 0) ∨ (x & 18 = 0)) → ((x & 115 ≠ 0) → (x & a = 0))) тождественно истинно. Решение. Используя обозначения, приведенные в начале статьи, запишем выражение в виде ) ( ) ( 115 18 46 A Z Z Z → → + . Упрощаем выражение, раскрыв вторую импликацию и из- бавившись от инверсий: ) ( ) ( 115 18 46 A Z Z Z + → + Преобразуем левую часть согласно Утверждению 8: К.Ю. Поляков, 2016 11 2 18 & 46 18 46 Z Z Z Z = ⇒ + и получаем таким образом (с помощью свойства 1 импликации) ) ( ) ( ) ( 2 115 2 115 2 A Z Z Z A Z Z → + → = + → Первая импликация в сумме равна 0, так как двоичная запись числа 115 содержит единич- ные биты, которых нет в двоичной записи числа 2. Поэтому требуется обеспечить истин- ность второй импликации, A Z → 2 . Для этого множество единичных битов числа a долж- но входить во множество единичных битов числа 2 (а это единственный бит в 1-м разря- де). Поэтому единственное натуральное число a, удовлетворяющее условию – это 2. Пример 8 . Определите наименьшее натуральное число a, такое что выражение ((x &23 ≠ 0) ∧ (x & 45 ≠ 0)) → ((x & a ≠ 0) ∧ (x & 23 ≠ 0)) тождественно истинно. Решение. Используя обозначения, приведенные в начале статьи, запишем выражение в виде ) ( ) ( 23 45 23 Z A Z Z ⋅ → ⋅ . Упрощаем выражение, раскрывая импликацию и избавляясь от инверсий: = + + ⋅ + = ⋅ + + = ⋅ + ⋅ 45 23 23 23 23 45 23 23 45 23 ) ( ) ( Z Z Z A Z Z A Z Z Z A Z Z ) ( 45 23 45 23 Z Z A Z A Z + → = + + = Преобразуем левую часть согласно Свойству 1 импликации: ) ( ) ( ) ( 45 23 45 23 Z A Z A Z Z A → + → = + → Таким образом, нужно обеспечить выполнение для всех x одного из условий: 1 23 = → Z A или 1 45 = → Z A Первое из них верно при минимальном значении 23, второе – при минимальном значении 45. Поэтому в качестве ответа выбираем наименьшее из двух – 23. У этой задачи возможно интересное продолжение – давайте найдем все решения, меньшие 100 . Сначала найдём все решения уравнения 1 23 = → Z A . Учитывая, что разряды 6 5 4 3 2 1 0 23 = 0010111 биты 0, 1, 2 и 4 нужно обязательно сохранить. К ним можно добавить бит 3 (получается 23+8=31), бит 5 (23+32=55), биты 4 и 5 (23+32+8=63), бит 6 (23+64=87), биты 6 и 3 (23+64+8=95), остальные подходящие значения больше 100. Теперь найдём все решения уравнения 1 45 = → Z A . Запишем 45 в двоичной системе счисления: разряды 6 5 4 3 2 1 0 45 = 0101101 Рассуждая аналогично, добавляем биты 1 (45+2=47), 4 (45+16=61), 4 и 1 (45+16+2=63), остальные значения получаются больше 100. В итоге получается такой список всех возможных значений a, меньших 100: 23, 31, 45, 47, 55, 61, 63, 87, 95. К.Ю. Поляков, 2016 12 Литература 1. К.Ю. Поляков, Множества и логика в задачах ЕГЭ // Информатика, № 10, 2015, с. 38-42. 2. К.Ю. Поляков, Битовые операции в задачах КИМ ЕГЭ по информатике. Электрон- ный ресурс [URL: http://kpolyakov.spb.ru/download/bitwise.pdf ] Дата обращения: 06.11.2016. |