Разбор 18 задания ЕГЭ 2016 года по информатике из демоверсии. Это задание на знание основных понятий и законов математической логики (уметь вычислять логическое значение сложного высказывания по известным значениям элементарных высказываний). Это задание повышенного уровня сложности. Примерное время выполнения задания 3 минуты.
Задание 18:
Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14&5 = 11102&01012 = 01002 = 4.
Для какого наименьшего неотрицательного целого числа А формула
x&25 ≠ 0 → (x&17 = 0 → x&А ≠ 0)
тождественно истинна (т.е. принимает значение 1 при любом неотрицательном целом значении переменной х)?
Ответ: ________
Разбор 18 задания ЕГЭ 2016:
Преобразуем исходное выражение
x&25 ≠ 0 → (x&17 = 0 → x&А ≠ 0)
¬(x&25 ≠ 0) ∨ (¬(x&17 = 0) ∨ x&А ≠ 0)
x&25 = 0 ∨ x&17 ≠ 0 ∨ x&А ≠ 0
Переведем числа из выражения в двоичную систему счисления
2510 = 110012
1710 = 100012
Определяем те значения Х, при которых истинно выражение x&25 = 0
2510 11001
Х 00??0
0 00000
Х — 00??0
Определяем те значения Х, при которых истинно выражение x&17 ≠ 0
1710 10001
Х ?????
0 ?000?
Х — 1????, ????1, 1???1
Следовательно
Х — 01??0
Определим наименьшее А, при котором истинно выражение x&А ≠ 0
Х — 01??0
А10 ?????
Х 01??0
≠ 0 0???0
Очевидно, что А ≠ 0
Пусть А = 12
А10 ????1
Х 01??0
≠ 0 00000
не подходит, так как не выполняется условие А ≠ 0
Пусть А = 10002
А10 01000
Х 01??0
≠ 0 01000
подходит, 10002 = 810
Ответ: 8