СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости


Задания
Версия для печати и копирования в MS Word
Задание 18 № 13695

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.

Так, например, 14&5 = 11102&01012 = 01002 = 4.

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

 

x&51 = 0 ∨ (x&41 = 0 → x&А = 0)

 

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

Решение.

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

 

Х + (Y → Z) = Х + (¬Y + Z) = Х + Z + ¬Y = Y → (X + Z) = (Y → X) + (Y → Z).

 

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

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

Действительно, например, для х = 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 ложно.

 

Итак, импликация Z41 → ZA должна быть тождественно истинной. Запишем число 41 в двоичной системе счисления: 4110 = 1010012. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поэтому в правой части единичными битами независимо друг от друга могут быть (а могут не быть) только первый, второй и четвертый биты (как обычно, считая справа налево, начиная с нуля).

Тем самым, наибольшее А = 1010012 = 4110.

 

Примечание.

Ответ 45 не подходит. Пусть A = 45, а x = 2210 = 101102, тогда:

 

51:       1100112

22:       0101102

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

 

41:       1010012

22:       0101102

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

 

45:       1011012

22:       0101102

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

 

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

 

Ответ: 41.

Источник: РЕШУ ЕГЭ