Побитовая конъюнкция

Обозначим \(x\&25 = 0 \Leftrightarrow Z_{25}, \; x\&17 = 0 \Leftrightarrow Z_{17}, \; x\&A = 0 \Leftrightarrow Z_{A}.\) Перепишем: \(\overline{Z_{25}} \to (Z_{17} \to \overline{Z_{A}}) = 1\) для любых \(x.\)

Воспользуемся тем, что \(a \to b = \overline{a} \vee b, \; \overline{\overline{a}} = a.\) Тогда \(Z_{25} \vee \overline{Z_{17}} \vee \overline{Z_{A}} = 1.\) Теперь воспользуемся тем же в обратную сторону: соберем импликацию. Получим \((Z_{17} \wedge Z_{A}) \to Z_{25} = 1.\)

Помним, что \(Z_{17} \wedge Z_{A} = Z_{17 \; or \; A}.\) Тогда \(Z_{17 \; or\; A} \to Z_{25} = 1.\)

Переведем в двоичную систему счисления известные числа: 17 = 10001, 25 = 11001.

\(\)

r _& 10001;
\(*****\);
\(11001\)

\(\)

Известно, что, чтобы данная импликация была равна 1, на тех местах, где в двоичной записи 25 стоят единички, в двоичной записи \(Z_{17 \; or \; A}\) должны тоже стоять единички.

Мы ищем наименьшее неотрицательное целое число \(A.\) Значит, где вместо звездочек можно ставить нули, — будем ставить. Двигаемся справа налево. На место первой звездочки можно поставить 0 — единичка уже есть в записи числа 17. На втором месте все равно, что ставить, — в записи 25 на этом месте 0. Ставим 0. Аналогично ставим на третье место. Теперь посмотрим на четвертое: в записи 25 — стоит 1, а вот в записи 17 — 0. Значит, на четвертом месте в числе \(A\) должна быть единичка. Аналогично заканчиваем ставить знаки. Никаких лишних разрядов впереди числа добавлять не будем — мы ищем наименьшее.

Итак, получили 1000. Это число в двоичной системе счисления. В десятичной — 8.

Ответ: 8

Введем обозначение: \(x\&a = 0 \Leftrightarrow Z_{a}.\) Тогда данное выражение перепишется в виде \(\overline{Z_{A}} \to (Z_{11} \to \overline{Z_{17}}).\)

Воспользуемся тем, что \(a \to b = \overline{a} \vee b.\) Тогда наше выражение имеет вид \(Z_{A} \vee \overline{Z_{11}} \vee \overline{Z_{17}}.\)

Теперь воспользуемся тем же, только в обратную сторону. Запишем выражение так: \(Z_{11} \wedge Z_{17} \to Z_{A}.\)

Помним, что \(Z_{a} \wedge Z_{b} = Z_{a \; or \; b}.\) Значит, нам нужно найти наибольшее неотрицательное целое \(A\) такое, что \(Z_{11 \; or \; 17} \to Z_{A} = 1.\)

\(Z_{11 \; or \; 17}\) мы можем сразу вычислить. Так как \(11 = 1011_{2}, \; 17 = 10001_{2},\) можем выполнить поразрядное сложение:

\(\)

r 01011;
10001;
\(11011\)

\(\)

Чтобы импликация была истинна, нам нужно, чтобы на тех местах, где справа стоит единица (в двоичной записи числа), слева она стояла тоже.

Таким образом, единица может стоять на тех местах, где она стоит в двоичной записи числа слева — необязательно, но если где-то и стоит, то только там. Но вспомним, что мы ищем максимальное \(A\): значит, мы хотим, чтобы в \(A\) было как можно больше единиц. А так как единицы могут быть только на тех местах, где стоят единицы в \(11011,\) наибольшее возможное \(A,\) — это и есть \(11011_{2} = 27_{10}.\)

Ответ: 27

Введем обозначение: \(x \& a = 0 \Leftrightarrow Z_{a}.\) Тогда выражение имеет вид \((\overline{Z_{17}} \wedge \overline{Z_{57}}) \to (\overline{Z_{A}} \wedge \overline{Z_{17}}).\)

Так как \(a \to b = \overline{a} \vee b,\) \((Z_{17} \vee Z_{57}) \vee (\overline{Z_{A}} \wedge \overline{Z_{17}}).\)

Помним, что \((a \vee b)\wedge(a \vee c) = a \vee b \wedge c.\) Тогда наше выражение имеет вид \((Z_{17} \vee \overline{Z_{17}}) \wedge (Z_{17} \vee \overline{Z_{A}}) \vee Z_{57}.\) Т.к. \(a \vee \overline{a} = 1,\) это то же самое, что \(Z_{17} \vee \overline{Z_{A}} \vee Z_{57}.\)

Воспользуемся тем, что \(a \to b = \overline{a} \vee b.\) Наше выражение тогда имеет вид \(Z_{A} \to (Z_{17} \vee Z_{57}).\)

Знаем, что \(a \to (b \vee c) = a \to b \vee a \to c.\) Тогда получаем \(Z_{A} \to Z_{17} \vee Z_{A} \to Z_{57}.\)

Мы хотим, чтобы данное выражение всегда было равно 1. Для этого нужно, чтобы или \(Z_{A} \to Z_{17} = 1,\) или \(Z_{A} \to Z_{57} = 1.\)

Помним, что импликация истинна, если на тех местах, где в двоичной записи числа справа стоят единицы, стоят единицы и в двоичной записи числа слева, то есть наименьшее неотрицательное целое \(A\) — это и есть число справа, то есть 17 в первом случае и 57 во втором. Мы ищем наименьшее число — то есть нам подходит 17.

Ответ: 17

Введем обозначение: \(x \& a = 0 \Leftrightarrow Z_{a}.\) Тогда выражение имеет вид \((\overline{Z_{29}} \wedge \overline{Z_{18}}) \to (\overline{Z_{A}} \wedge \overline{Z_{29}}).\)

Так как \(a \to b = \overline{a} \vee b,\) \((Z_{29} \vee Z_{18}) \vee (\overline{Z_{A}} \wedge \overline{Z_{29}}).\)

Помним, что \((a \vee b)\wedge(a \vee c) = a \vee b \wedge c.\) Тогда наше выражение имеет вид \((Z_{29} \vee \overline{Z_{29}}) \wedge (Z_{29} \vee \overline{Z_{A}}) \vee Z_{18}.\) Т.к. \(a \vee \overline{a} = 1,\) это то же самое, что \(Z_{29} \vee \overline{Z_{A}} \vee Z_{18}.\)

Воспользуемся тем, что \(a \to b = \overline{a} \vee b.\) Наше выражение тогда имеет вид \(Z_{A} \to (Z_{29} \vee Z_{18}).\)

Знаем, что \(a \to (b \vee c) = a \to b \vee a \to c.\) Тогда получаем \(Z_{A} \to Z_{29} \vee Z_{A} \to Z_{18}.\)

Мы хотим, чтобы данное выражение всегда было равно 1. Для этого нужно, чтобы или \(Z_{A} \to Z_{29} = 1,\) или \(Z_{A} \to Z_{18} = 1.\)

Помним, что импликация истинна, если на тех местах, где в двоичной записи числа справа стоят единицы, стоят единицы и в двоичной записи числа слева, то есть наименьшее неотрицательное целое \(A\) — это и есть число справа, то есть 29 в первом случае и 18 во втором. Мы ищем наименьшее число — то есть нам подходит 18.

Ответ: 18

Введем обозначение: \(x \& a = 0 \Leftrightarrow Z_{A}.\) Тогда наше выражение имеет вид: \((Z_{23} \vee Z_{17}) \to (\overline{Z_{58}} \to Z_{A}).\)

Так как \(a \to b = \overline{a} \vee b,\) получаем \((Z_{23} \vee Z_{17}) \to (Z_{58} \vee Z_{A}).\) Так как \(Z_{23} \vee Z_{17} = Z_{23 \& 17}.\)

\(23 = 10111_{2}, 17 = 10001_{2}.\) Тогда посчитаем \(23 \& 17:\)

\[\begin{array}{r} \,\,10111;\; \\ 10001;\;\\ \hline \;10001\;\;\\ \end{array}\]

\(10001_{2} = 17_{10}.\)

Тогда наше выражение имеет вид \(Z_{17} \to (Z_{58} \vee Z_{A}).\) Это то же самое, что \((Z_{17} \to Z_{58}) \vee (Z_{17} \to Z_{A}).\)

Мы сразу можем определить, истинна ли \(Z_{17} \to Z_{58}.\)

\(\begin{matrix} 17 = 010001\\ 58 = 111010\\ \end{matrix}\)

Нет, не истинна, т.к. на первом месте, например, в двоичной записи 17 стоит 0, а на первом в двоичной записи 58 — 1. Значит, нужно, чтобы истинна была импликация \(Z_{17} \to Z_{A}.\)

Мы ищем наибольшее \(A.\) Чтобы импликация истинна, на тех местах, где в двоичной записи A стоят единицы, стоят единицы и в двоичной записи 17. То есть больше единиц, чем есть в 17, в записи \(A\) быть не может. Тогда наибольшее \(A\) — это и есть само 17.

Ответ: 17

Введем обозначение: \(x \& a = 0 \Leftrightarrow Z_{a}.\) Тогда перепишем выражение: \(((\overline{Z_{17}} \vee \overline{Z_{A}}) \to \overline{Z_{17}}) \vee (\overline{Z_{A}} \wedge Z_{41}))\) (для удобства поставим незначащие скобочки).

Так как \(a \to b = \overline{a} \vee b,\) получим выражение \((Z_{17} \wedge Z_{A}) \vee \overline{Z_{17}} \vee (\overline{Z_{A}} \wedge Z_{41}).\) Воспользуемся тем, что \((a \vee b) \wedge (a \vee c) = a \vee (b \wedge c),\) получая \((\overline{Z_{17}} \vee Z_{17}) \wedge (\overline{Z_{17}} \vee Z_{A}) \vee (\overline{Z_{A}} \wedge Z_{41}) = \overline{Z_{17}} \vee Z_{A} \vee (\overline{Z_{A}} \wedge Z_{41}).\) Теперь воспользуемся этим еще раз, получив \(\overline{Z_{17}} \vee (Z_{A} \vee \overline{Z_{A}}) \wedge (Z_{A} \vee Z_{41}) = \overline{Z_{17}} \vee Z_{A} \vee Z_{41} = Z_{17} \to (Z_{A} \vee Z_{41}) = (Z_{17} \to Z_{A}) \vee (Z_{17} \to Z_{41}).\)

Мы можем сразу посмотреть, верно ли \(Z_{17} \to Z_{41}.\) Напомним, что мы ищем наибольшее целое неотрицательное \(A\) такое, что данное выражение истинно.

\(17 = 010001_{2}\)

\(41 = 101001_{2}.\)

Импликация истинна, если на всех местах, где в двоичной записи 41 стоит единица, стоит единица на том же месте в двоичной записи 17. Это не так. Импликация ложна. Значит, должно быть истинно \(Z_{17} \to Z_{A}.\)

Мы уже сказали, когда истинна импликация. Значит, на других местах, кроме тех, где стоят в двоичной записи числа 17, единицы в двоичной записи \(A\) стоять не могут. Тогда наибольшее подходящее \(A\) — это 17.

Ответ: 17

Введем обозначение: \(x \& a = 0 \Leftrightarrow Z_{a}.\) Тогда данное выражение имеет вид \(((\overline{Z_{24}} \vee \overline{Z_{A}}) \to \overline{Z_{24}}) \vee (\overline{Z_{A}} \wedge Z_{47}).\)

Так как \(a \to b = \overline{a} \vee b,\) выражение имеет вид \(((Z_{24} \wedge Z_{A}) \vee \overline{Z_{24}}) \vee (\overline{Z_{A}} \wedge Z_{47}).\) Теперь воспользуемся тем, что \((a \vee b) \wedge (a \vee c) = a \vee (b \wedge c).\) Получим \(((\overline{Z_{24}} \vee Z_{24}) \wedge (\overline{Z_{24}} \vee Z_{A})) \vee (\overline{Z_{A}} \wedge Z_{47}) = \overline{Z_{24}} \vee Z_{A} \vee (\overline{Z_{A}} \wedge Z_{47}) = \overline{Z_{24}} \vee ((Z_{A} \vee \overline{Z_{A}}) \wedge (Z_{A} \vee Z_{47}) = \overline{Z_{24}} \vee Z_{A} \vee Z_{47} = Z_{24} \to Z_{A} \vee Z_{47} = (Z_{24} \to Z_{A}) \vee (Z_{24} \to Z_{47}).\)

Мы ищем наибольшее \(A\) такое, что данное выражение истинно. Истинно ли \(Z_{24} \to Z_{47}\) мы можем проверить сразу.

\(24 = 011000_{2}\)

\(47 = 101111_{2}\)

Импликация истинна, если на всех местах, где стоят единицы в двоичной записи 47, в двоичной записи 24 также стоят единицы. Но это не так. Импликация ложна. Значит, должна быть истинна импликация \(Z_{24} \to Z_{A}.\) Как мы уже сказали, она истинна, если на месте всех единиц в двоичной записи числа A в двоичной записи числа 24 также стоят единицы. Значит, больше единиц, чем в двоичной записи 24, быть не может. Тогда получается, что наибольшее \(A\) — такое число, в двоичной записи которого единицы стоят там же, где и в двоичной записи 24, и нигде больше. Это и есть 24.

Ответ: 24