Контрольные тренировочные задания
(решения)

Часть 1

Задание 18

Решение примера 1

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14&5 = 1110₂&0101₂ = 0100₂ = 4.

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

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

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

Ответ: ___________________________.

Решение.

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

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

x&25 = 0 ∨ x&17 ≠ 0 ∨ x&А ≠ 0

Переведем числа из выражения в двоичную систему счисления

25₁₀ = 11001₂
17₁₀ = 10001₂

Определяем те значения Х, при которых истинно выражение x&25 = 0

25₁₀ 11001
  Х    00??0
  0    00000

Х — 00??0

Определяем те значения Х, при которых истинно выражение x&17 ≠ 0

17₁₀ 10001
  Х    ?????
  0    ?000?

Х — 1????, ????1, 1???1

Следовательно

Х — 01??0

Определим наименьшее А, при котором истинно выражение x&А ≠ 0
Х — 01??0

А₁₀ ?????
 Х   01??0
≠ 0  0???0

Очевидно, что А ≠ 0

Пусть А = 1₂

А₁₀ ????1
 Х   01??0
≠ 0  00000

не подходит, так как не выполняется условие А ≠ 0

Пусть А = 1000₂

А₁₀ 01000
 Х   01??0
≠ 0  01000

подходит, 1000₂ = 8₁₀

Ответ: 8

Возврат на страницу    Решение примеров части 1 задание 18