Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
Топ:
Определение места расположения распределительного центра: Фирма реализует продукцию на рынках сбыта и имеет постоянных поставщиков в разных регионах. Увеличение объема продаж...
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Интересное:
Мероприятия для защиты от морозного пучения грунтов: Инженерная защита от морозного (криогенного) пучения грунтов необходима для легких малоэтажных зданий и других сооружений...
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Дисциплины:
2018-01-29 | 662 |
5.00
из
|
Заказать работу |
|
|
Для решения этих задач удобно применять метод, предложенный А.В. Здвижковой (г. Армавир) и обоснованный автором[2]. Введём обозначения
Это означает, что если истинно , то это равносильно тому, что истинно . Для сокращения записи вместо будем писать просто .
Пусть в двоичной записи числа K бит с номером i, обозначаемый как ki, равен 1. Если при этом для некоторого x выполнено условие , то соответствующий i -й бит в двоичной записи числа x равен нулю, так как должно выполняться условие .
Для преобразования выражений полезно следующее свойство:
где «or» означает поразрядную дизъюнкцию между двумя натуральными числами. Для доказательства предположим, что в двоичной записи числа K биты с номерами i 1, i 2, …, iq равны 1, а остальные равны 0; а в двоичной записи числа M биты с номерами j 1, j 2, …, jp равны 1, а остальные равны 0. Истинность выражения в левой части означает, что все биты числа x, входящие во множества BK = { i 1, i 2, …, iq } и BM = { j 1, j 2, …, jp } одновременно равны нулю. Поэтому любая комбинация битов из этих множеств тоже равна нулю. Это справедливо, в том числе, и для множества, которое представляет собой объединение множеств BK и BM, то есть, для множества единичных битов числа K or M.
Самый важный результат можно сформулировать так:
Условие истинно для любых натуральных значений x тогда и только тогда, когда все единичные биты двоичной записи числа M входят во множество единичных битов двоичной записи числа K.
Доказательство. Пусть в двоичной записи числа K биты с номерами i 1, i 2, …, iq равны 1, а остальные равны 0. Пусть также истинно для некоторого x, это значит, что в числе x биты с теми же номерами – нулевые. Если все единичные биты двоичной записи числа M входят во множество BK = { i 1, i 2, …, iq }, то истинно и высказывание , а следовательно – высказывание (1 ® 1 = 1). Если же хотя бы один бит двоичной записи числа M не входит во множество BK (пусть это будет бит с номером j), то для тех х, у которых все биты из множества BK нулевые, а бит j равен 1, выполняется , но не выполняется , так что высказывание ложно.
|
Для упрощения выражений полезен следующий результат:
Условие при любых натуральных K, M и N ложно для некоторых натуральных значений x.
Идея доказательства состоит в том, чтобы представить импликацию в виде произведения двух импликаций:
.
Вторая импликация в правой части ложна хотя бы для некоторых x, поскольку из того, что некоторые биты числа x равны нулю (выполняется ) совершенно не следует, что какие-то другие (или те же самые) биты того же числа ненулевые (выполняется ). Строгое доказательство дано в статье, ссылка на которую приведена в сноске на предыдущей странице.
Метод, предложенный А.В. Здвижковой заключается в следующем:
1) упростить заданное выражение, сведя его к импликации, в которой нет инверсий
2) применить полученные выше результаты для нахождения всех подходящих значений неизвестного числа a, включая минимальное и максимальное значения.
Этот же метод можно применить и в том случае, когда результат поразрядной операции «И» сравнивается не с нулём, а с другими числами. Например, рассмотрим выражение R = (x &125= 5). Переведём числа в двоичную систему:
6 5 4 3 2 1 0
125 = 11111012
5 = 1012.
Истинность R означает, что
1) биты числа x с номерами 3, 4, 5 и 6 равны 0;
2) биты числа x с номерами 0 и 2 равны 1.
С учётом введённых выше обозначений можно записать эквивалентное условие:
R = (x &125= 5) Û .
Применяя операцию «НЕ» к этому выражению, получаем
= (x &125¹ 5) Û Û .
В общем виде для чисел b и c, таких, что множество единичных битов числа c входит во множество единичных битов числа b, имеем
R = (x & b = c) Û
= (x & b ¹ c) Û .
где c 1, c 2, …, cq – степени числа 2, которые соответствуют единичным битам числа c. Например, для
c = 5 = 1012 имеем c 1 = 22 = 4, c 2 = 20 = 1.
|
Пример задания:
Р-25. Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число a, такое что выражение
(x &125¹ 1) Ú ((x & 34 = 2) ® (x & a = 0))
|
|
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!