Определите наименьшее натуральное число a такое что выражение

Ещё пример задания:

Р-22. Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число A, такое что выражение

(X & 49  0)  ((X & 33 = 0)  (X & A  0))

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

Решение (1 способ):

P = (X & 49  0), Q = (X & 33 = 0), A=(X & A  0)

перепишем исходное выражение и преобразуем его, используя свойство импликации и закон де Моргана:

P  (Q  A) = + (Q  A) =

таким образом, нужно выбрать минимальное A, такое что при выполнении условийPиQавтоматически выполняется и условиеA

теперь попробуем понять, что означают условия типа X & 49 = 0иX & 49  0; побитовая конъюнкция (операция «И») применяется к соответствующим битам чиселXи49, где 49 выполняет роль маски;

запишем числа в двоичной системе; учитывая, что 49 = 32 + 16 + 1 = 2 5 + 2 4 + 2 0 , в двоичном коде числа 49 будут равны 1 (установлены) только биты с номерами 0, 4 и 5:

номер бита 5 4 3 2 1 0

49 = 110001

X = abcdef

X & 49 = ab000f

после выполнения побитовой операции «И» остаются только те биты числа X, для которых соответствующие биты маски равны 1, остальные (соответствующие нулевым битам маски) обнуляются; поэтому

условие X & 49  0означает, что среди битов <5, 4, 0>числаXесть ненулевой

условие X & 49 = 0означает, что биты <5, 4, 0>числаXнулевые

итак, условие Pобозначает, что среди битов <5, 4, 0>числаXесть ненулевой

поскольку Q = (X & 33 = 0) и 33 = 32 + 1 = 2 5 + 2 0 , условиеQозначает, что биты 5 и 0 – нулевые

что же следует из выполнения PиQодновременно? только то, что бит 4 в числеX– ненулевой; поэтому для выполнения условияA=(X & A  0) этот бит в числеAтоже должен быть ненулевой

минимальное натуральное число, у которого 4 бит ненулевой – это 10000₂= 16 = 2 4 .

Решение (2 способ, Н.Г. Неуймина, г. Екатеринбург):

P = (X & 49  0), Q = (X & 33 = 0), A=(X & A  0)

перепишем исходное выражение и преобразуем его, используя свойство импликации :

P  (Q  A) = + (Q  A) =

чтобы формула была тождественно истинной для любых Хнеобходимо, чтобы при было А=1

имеем тогда и только тогда, когда ;

посмотрим, какими свойствами должен обладать Xдля того, чтобы было

если , то есть, (X & 33 = 0), имеем

номер бита 5 4 3 2 1 0

X = 0bcde0

33 = 100001

X & 33 = 000000

это значит, что биты <5, 0>– нулевые

если одновременно , то есть, (X & 49  0), имеем

номер бита 5 4 3 2 1 0

X = 0bcde0

49 = 110001

X & 49 = 0b0000

это значит, что бит 4 в X– обязательно ненулевой

из 6 и 7 делаем вывод, что для выполнения условия A=(X & A  0) = 1необходимо, чтобы, по крайней мере, бит 4 числаAбыл ненулевым (так как биты <3,2,1>вXмогут быть нулевые!)

поскольку нужно найти наименьшее подходящее A, получаем ответ 2 4 = 16

Решение (3 способ, А.В. Лаздин, НИУ ИТМО):

если X & 49 = 0, то исходное выражение истинно, независимо от значения числа А; значит, значение числа А влияет на решение задачи только при выполнении условия:

тогда исходное выражение может быть представлено в виде:

1  ((X & 33 = 0)  (X & A  0)) (2)

Для того чтобы это выражение было истинным, необходимо, чтобы выражение

(X & 33 = 0)  (X & A  0)

было истинным, при этом, если X & 33  0, то это выражение истинно независимо от значения числаА(импликация из 0 в 1).

следовательно, значение числа Авлияет на принимаемое исходным выражением значение только при одновременном соблюдении двух условий:

1. X & 49  0

2. X & 33 = 0

исходное выражение принимает следующий вид:

1  (1  (X & A  0)) (3)

для того чтобы это выражение приняло значение 1, необходимо, чтобы выполнилось третье условие:

3. X & A  0.

49₁₀ = 110001₂

33₁₀= 100001₂

X 010000

условия 1 и 2 выполняются, если пятый бит числа Х равен 1.

значит условие № 3 выполняется, если пятый бит числа Аравен 1

число Аминимально, если младшие разряды этого числа равны 0

Решение (4 способ, М.В. Кузнецова ):

P = (X & 49  0), Q = (X & 33  0), A=(X & A  0)

Перепишем исходное выражение и преобразуем его, используя свойство импликации :

Чтобы формула была тождественно истинной для любых Хнеобходимо, чтобы при былоА=1, т.е .

Значит,A =1 тогда и только тогда, когда .

Запишем двоичное представление чисел 49 и 33, на их основе составим маски возможных значений числа х, таких, что . В маске «1» — соответствуетвозможномуположению 1, «0» —обязательномуположению 0 в двоичной записи числах.

Поразрядная конъюнкция задачи 3

Давайте разберем поразрядную конъюнкцию. Это задача, которая несколько лет была на ЕГЭ и на всех СтатГрадах, и она как-то исторически вызывает неприятные эмоции у учеников. На самом деле, ничего сложного.

Что такое поразрядная конъюнкция? Это перевод чисел в двоичную систему, а потом разряд с разрядом умножаем. Например, 7 х 4. 7 перевожу в двоичную систему – 1 1 1. 4 перевожу в двоичную систему – 1 0 0. И умножаю разряд с разрядом – 111 х 100=100.

Читать:

Err connection aborted как исправить ошибку

Давайте порешаем задачи.

«Введем выражение М & К, обозначающие поразрядную конъюнкцию М и К (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число А, такое, что выражение

Начнем с короткого обозначения. Выражение Х х 56 =0 обозначим как Х₅₆, в коротком виде. Первое уравнение принимает вид . Нам нужно найти наименьшее натуральное А.

Избавляемся от импликации. Формулу напоминать не буду, наверное, ее уже все знают наизусть.

Теперь мой любимый прием – известная часть пусть будет нулем (0), тогда искомая часть обязана быть единицей (1)

На какой-то момент я забываю про предметную область, я занимаюсь преобразованием до системы.

С нулем работать не очень приятно, поэтому сделаю отрицание и будет единица.

На что мне надо умножить 48, чтобы получились одни нули?

У X должны быть в первом разряде нули, чтобы обнулить единицы у 48, а остальное не важно

И те же самые X я должна умножить на 56 и не получить ноль. Чтобы не получить ноль, мне нужно здесь поставить единицу, чтобы она зацепила единицу от 56

Дальше может стоять что угодно. Все такие X являются решением этого уравнения.

Второе уравнение говорит, что все такие X (001…) нужно умножить на А и не получить ноль.

На первой и второй позиции у А может стоять что угодно. Три последние позиции тоже без разницы. Нужно поймать единственную единицу.

Если у А будет здесь единица, я умножу А и Х и ноль не получу. Вот такое А должно быть.
Нужно найти наименьшее. Тогда остальные пусть будут нули.

А это значит 8 в десятичной системе.

Благодарим за то, что пользуйтесь нашими статьями. Информация на странице «Поразрядная конъюнкция задачи 3» подготовлена нашими авторами специально, чтобы помочь вам в освоении предмета и подготовке к ЕГЭ и ОГЭ. Чтобы успешно сдать нужные и поступить в высшее учебное заведение или техникум нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий. Также вы можете воспользоваться другими статьями из данного раздела.