Побитовая конъюнкция (страница 2)
Обозначим через \(m\&n\) поразрядную конъюнкцию неотрицательных целых чисел \(m\) и \(n\).
Так, например, \(14\&5 = 1110_2\&0101_2 = 0100_2 = 4\).
Для какого наименьшего целого числа \(А\) формула
\[x\&17=0 \rightarrow (x\&33 \neq 0 \rightarrow x\&A \neq 0)\]
тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной \(x\))?
Преобразуем выражение к виду \(Z_{17}Z_A \rightarrow Z_{33}\) с помощью законов де Моргана:
\[(x\&17\neq0) \vee (x\&33=0) \vee (x\&A\neq0)\] \[(x\&17\neq0) \vee (x\&A\neq0) \vee (x\&33=0)\] \[(x\&17=0 \wedge x\&A=0) \rightarrow (x\&33=0)\]
Для того, чтобы выражение вида \(Z_{17}Z_A \rightarrow Z_{33}\) являлось истинным, единичные биты, стоящие в правой части, должны являться единичными битами левой.
Запишем числа 17 и 33 в двоичной системе счисления:
\(33_{10}=100001_2\) – правая часть
\(17_{10}=010001_2\) – левая часть
Значит, \(A\) обязательно должно содержать в себе единицу в пятом разряде. Так как ищем наименьшее \(A\), наш ответ \(100000_2=32_{10}\).
Обозначим через \(m\&n\) поразрядную конъюнкцию неотрицательных целых чисел \(m\) и \(n\).
Так, например, \(14\&5 = 1110_2\&0101_2 = 0100_2 = 4\).
Для какого наименьшего целого числа \(А\) формула
\[x\&15=0 \rightarrow (x\&29\neq0 \rightarrow x\&A\neq0)\]
тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной \(x\))?
Преобразуем выражение к виду \(Z_{17}Z_A \rightarrow Z_{33}\) с помощью законов де Моргана:
\[(x\&15\neq0) \vee (x\&29=0) \vee (x\&A\neq0)\] \[(x\&15\neq0) \vee (x\&A\neq0) \vee (x\&29=0)\] \[(x\&15=0 \wedge x\&A=0) \rightarrow (x\&29=0)\]
Для того, чтобы выражение вида \(Z_{15}Z_A \rightarrow Z_{29}\) являлось истинным, единичные биты, стоящие в правой части, должны являться единичными битами левой.
Запишем числа 15 и 29 в двоичной системе счисления:
\(29_{10}=11101_2\) – правая часть
\(15_{10}=01111_2\) – левая часть
Значит, \(A\) обязательно должно содержать в себе единицу в четвертом разряде. Так как ищем наименьшее \(A\), наш ответ \(10000_2=16_{10}\).
Обозначим через \(m\&n\) поразрядную конъюнкцию неотрицательных целых чисел \(m\) и \(n\).
Так, например, \(14\&5 = 1110_2\&0101_2 = 0100_2 = 4\).
Для какого наибольшего целого числа \(А\) формула
\[x\&A\neq0 \rightarrow (x\&14=0 \rightarrow x\&3\neq0)\]
тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной \(x\))?
Преобразуем выражение к виду \(Z_{14}Z_3 \rightarrow Z_A\) с помощью законов де Моргана:
\[(x\&A=0) \vee (x\&14\neq0) \vee (x\&3\neq0)\] \[(x\&14=0 \wedge x\&3=0) \rightarrow (x\&A=0)\]
Для того, чтобы выражение вида \(Z_{14}Z_3 \rightarrow Z_{A}\) являлось истинным, единичные биты, стоящие в правой части, должны являться единичными битами левой.
Запишем числа 14 и 3 в двоичной системе счисления:
\(14_{10}=1110_2\)
\(9_{10}=0011_2\)
Значит, \(A\) обязательно должно содержать в себе единицу во всех азрядах. Так как ищем наибольшее \(A\), наш ответ \(1111_2=15_{10}\).
Обозначим через \(m\&n\) поразрядную конъюнкцию неотрицательных целых чисел \(m\) и \(n\). Так, например, \(14\&5 = 1110_2 \& 0101_2 = 0100_2 = 4\).
Для какого наименьшего неотрицательного целого числа A формула
\[((x\&47 \neq 0) \vee (x\&24 \neq 0)) \rightarrow ((x\&29 = 0) \rightarrow (x\&A \neq 0))\]
тождественно истинна (т.е. принимает значение 1 при любом неотрицательном целом значении переменной \(x\))?
Запишем в виде системы, чего хотят враги:
\[\begin{cases} \left[ \begin{gathered} x\&47 \neq 0 \\ x\&24 \neq 0 \\ \end{gathered} \right. \\ x\&29 = 0 \\ x\&A = 0 \\ \end{cases}\]
Рассмотрим условие \(x\&29 = 0\), при этом \(29_{10} = 11101\). Значит, враги будут выбирать такие иксы: \(...000*0_2\), где многоточие означает любую последовательность цифр, а звёздочка - любую цифру.
Обратимся к совокупности: \(47_{10} = 101111_2, 24_{10} = 11000\). Заметим, что враги не смогут выбрать такой \(x\), который подходил бы и под первое рассмотренное нами условие, и под условие \(x\&24 \neq 0\). Значит, его можно отбросить.
Тогда, иксы, которые выбирают враги, имеют следующий вид: \(...100010_2\), при этом единички могут быть как и на обоих местах, так и только на одном из двух.
Друзья хотят, чтобы \(x\&A \neq 0\). Значит, \(A = 100010_2\). Заметим, что мы не можем выбрать \(A = 10_2\), потому что враги могут выбрать \(x = 100000_2\) и поломать нашу систему. Аналогично с \(A = 100000\).
Следовательно, ответ 34.
Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, \(14\&5=1110_2\&0101_2=0100_2=4.\) Для какого наименьшего целого числа А формула
\(x\&A\neq 0\rightarrow (x\&10=0\rightarrow x\&5\neq 0)\)
тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной x)?
Преобразуем выражение к виду \(Z_{10}Z_5\rightarrow Z_A\) с помощью законов де Моргана:
\((x\&A=0)\lor (x\&10\neq 0)\lor (x\&5\neq 0)\)
\((x\&10=0 \ \land \ x\&5=0)\rightarrow (x\&A=0)\)
Заметим, что если А=0, то последнее выражение всегда 0, а следовательно последняя скобка всегда 0, то есть выражение имеет вид:
\(X\rightarrow1\), а это всегда истинно.
Нам нужно минимальное неотрицательное целое число А, значит наш ответ 0.
