ITN-logo
Сеть творческих учителей
Войти
Присоединяйтесь к Сети творческих учителей и станьте частью мирового сообщества педагогов, готовых учить и учиться, готовых применять лучшие методики преподавания с использованием ИКТ, делиться своим опытом, творить и экспериментировать.

При поддержке

Все веб-узлы корпорации Майкрософт

О портале
Сообщества и форумы
Методическая копилка
Конкурсы***, ВиЭкс-М
Для новичков...
Полезные ссылки


Статистика портала
Материалов в библиотеках документов 34 540
(+2)
Зарегистрированных пользователей 149 013
(+46)
Тем/сообщений в форумах 50 469 / 590 219
(+5 / +132)
В скобках указаны обновления за последние 7 дней.
ЕГЭ по информатике: сложные вопросы
Подготовка к успешной сдаче ЕГЭ по информатике

<< перейти на страницу сообщества Сообщество творческих учителей информатики

<< перейти на страницу творческой группы ЕГЭ по информатике: сложные вопросы

Форум
Раздел: ЕГЭ по информатике: сложные вопросы

Лобова Нина Ивановна
06.05.2017 11:12:41
Лобова Нина Ивановна
Нужна помощь
Ответить

re: >re: >Какому наименьшему положительному числу может быть равно A,
re: > чтобы выражение
re: > (x & 213≠1)или((x & 42=2)→(x & A=0)
re: > было верно для любого неотрицательного x?
re: > В ответе число 2.

 

К сожалению, это неверный ответ, и решение неверное. Контрпример: при x = 3 выражение ложно.

Обозначим через Zb логическое выражение (x & b = 0). Если множество единичных битов числа c входит во множество единичных битов числа b, то (x & b = с) = Zb-c * not Zc. Аналогично можно показать, что (x & b != с) = not Zb-c + Zc.

В нашем примере получаем:
(x & 213 != 1) = not Z212 + Z1.
(x & 42 != 2) = not Z40 + Z2.

Преобразуем исходное выражение, раскрывая импликацию:
(x & 213 ≠ 1) or (x & 42 != 2) or (x & A = 0) = 1
Вводим Z-выражения:
not Z212 + Z1 + not Z40 + Z2 + Za = 1

Теперь избавляемся от инверсий, переходя к импликации:
not (Z212*Z40) + Z1 + Z2 + Za = 1
(Z212*Z40) -> (Z1 + Z2 + Za) = 1

Так как
Z212*Z40 = Z212 or 40 = Z252,
получаем
Z252 -> (Z1 + Z2 + Za) = 1

Далее учтем, что в двоичной записи числа 252 = 111111002 биты 0 и 1 равны 0, поэтому
Z252 -> Z1 = 0 и Z252 -> Z2 = 0
(это значит, что найдутся такие x, при которых эти выражения ложны).

Таким образом, получили эквивалентное уравнение:
Z252 -> Za = 1
Минимальное положительное значение a, при котором оно истинно для любых x, равно 22 = 4. Это и есть ответ.

Соответствующую теорию можно посмотреть здесь: http://kpolyakov.spb.ru/download/bitwise2.pdf

Огромное спасибо Константин Юрьевич, теперь все понятно.


« нить сообщений
Напишите нам. Запрос на размещение рекламы Свяжитесь с нами Майкрософт для образования Условия
использования
Товарные знаки Конфиденциальность Правила поведения
Любая републикация материалов, опубликованных на портале, в соответствии со ст.1270 ГК РФ допускается только после согласования с их авторами.
Хостинг на Parking.ru | Разработка сайта: Metric.ru | CMS: Optimizer.NET | Контент: Участники портала