Задание №917 ЕГЭ Информатике

Преобразуем выражение по законам алгебры логики:

Далее применяем обозначения и реализуем способ решения, изложенный К. Ю. Поляковым в теоретических материалах (см., например, раздел «Теория» на нашем сайте), без дополнительных пояснений.

Заметим, что первое слагаемое логической суммы является импликацией Z₄₁ → Z₅₁, которая не является истинной для всех х (см. ниже). Тогда необходимо и достаточно, чтобы второе слагаемое логической суммы было тождественно истинным.

Действительно, например, для х = 2 поразрядная конъюнкция с числом 41 дает 0, а с числом 51 дает 2. Поэтому импликация (2&41) → (2&51) принимает вид 1 → 0 — ложь.

 2:      000010

41:     101001

2&41: 000000, то есть 2&41 = 0. Высказывание 2&41 = 0 истинно.

 2:      000010

51:     110011

2&51: 000010 = 2, то есть 2&51 = 2. Высказывание 2&51 = 0 ложно.

Итак, импликация Z₄₁ → Z_A должна быть тождественно истинной. Запишем число 41 в двоичной системе счисления: 41₁₀ = 101001₂. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поэтому в правой части единичными битами независимо друг от друга могут быть (а могут не быть) только нулевой, третий и пятый биты (как обычно, считая справа налево, начиная с нуля).

Тем самым, наибольшее А = 101001₂ = 41₁₀.

Примечание.

Ответ 45 не подходит. Пусть A = 45, а x = 22₁₀ = 10110₂, тогда:

51:       110011₂

22:       010110₂

51&22: 010010₂, т.е. высказывание 22&51 = 0 ложно.

41:       101001₂

22:       010110₂

41&22: 000000₂, т.е. высказывание 22&41 ≠ 0 ложно.

45:       101101₂

22:       010110₂

51&22: 000100₂, т.е. высказывание 22&45 = 0 ложно.

Следовательно, при x = 22 и A = 45 логическое выражение ложно.

Приведем другое решение.

Выражение x&51 = 0 ∨ (x&41 = 0 → x&А = 0) должно быть истинным для любого х. Возьмем такое х, в котором установлены все биты, кроме тех, которые установлены в числе 41, например, для однобайтового представления х = 11010110₂.

Выражение x&51 = 0 будет ложно, поскольку и в числе х, и в числе 51 установлен первый бит (биты считаем справа налево, начиная с нуля).

Следовательно, истинной должна быть импликация во второй скобке. Но левая часть импликации x&41 = 0 истинна, поскольку ни один из битов, установленных в числе 41, в числе х не установлен.

Тогда истинной должна быть и правая часть импликации x&А = 0. Следовательно, в числе А могут быть установлены только те биты, которые не установлены в числе х, то есть нулевой, третий и пятый биты. Таким образом, наибольшее А = 101001₂ = 41₁₀.

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

Приведём другое решение.

Решим задание с помощью языка программирования Python методом перебора:

for A in range(64):
    B = True
    for x in range(64):
        if ((x&51==0) or (x&41!=0) or (x&(63-A)==0))==0:
            B=False
    if B:
        print(63-A)
        break

Заметим, что можно не перебирать числа, большие 63, поскольку для записи чисел 41 и 51 хватит шести разрядов. Программа выведет ответ 41.

Ответ: 41.