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


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

Обо­зна­чим через 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. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поэтому в правой части единичными битами независимо друг от друга могут быть (а могут не быть) только нулевой, второй и четвертый биты (как обычно, считая справа налево, начиная с нуля). Поскольку искомое A — наименьшее неотрицательное целое число, в его записи нет единичных битов.

Тем самым, наименьшее А = 0000002 = 010.