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

Лада Есакова, преподаватель информатики и математики, автор книги "Информатика. Полный курс подготовки к ЕГЭ".

Добрый день!

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

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

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

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

(X & 56 ≠0)→((X & 48=0)→(X & A ≠0)).»

Начнем с короткого обозначения. Выражение Х х 56 =0 обозначим как Х₅₆, в коротком виде. Первое уравнение принимает вид $\bar{X}_{56}\rightarrow (X_{48}\rightarrow \bar{X}_{A})=1$ . Нам нужно найти наименьшее натуральное А.

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

$X_{56}\vee \bar{X}_{48}\vee \bar{X}_{A}=1$

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

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

$\left\{\begin{matrix}X_{56}\vee \bar{X}_{48}=0\\\bar{X}_{A}=1\end{matrix}\right.$

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

$\left\{\begin{matrix}\bar{X}_{56}\wedge {X}_{48}=1\\\bar{X}_{A}=1\end{matrix}\right.$

$\begin{matrix}48 & 1 & 1 & 0 & 0 & 0 & 0\\56 & 1 & 1 & 1 & 0 & 0 & 0\end{matrix}$

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

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

$\begin{matrix}48 & 1 & 1 & 0 & 0 & 0 & 0\\ 56 & 1 & 1 & 1 & 0 & 0 & 0\\X & 0 & 0 & - & - & - & -\end{matrix}$

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

$\begin{matrix}48 & 1 & 1 & 0 & 0 & 0 & 0\\ 56 & 1 & 1 & 1 & 0 & 0 & 0\\X & 0 & 0 & 1 & - & - & -\end{matrix}$

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

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

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

$\begin{matrix}48 & 1 & 1 & 0 & 0 & 0 & 0\\ 56 & 1 & 1 & 1 & 0 & 0 & 0\\X & 0 & 0 & 1 & - & - & -\\A & - & - & 1 & - & - & -\end{matrix}$

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

$\begin{matrix}48 & 1 & 1 & 0 & 0 & 0 & 0\\ 56 & 1 & 1 & 1 & 0 & 0 & 0\\X & 0 & 0 & 1 & - & - & -\\A & - & - & 1 & 0 & 0 & 0\end{matrix}$

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

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

Публикация обновлена: 08.03.2023

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

Это полезно