Математика ЕГЭ
Русский язык ЕГЭ
Математика 5-7
Математика ОГЭ
Информатика
Физика
Обществознание
Кликните, чтобы открыть меню

15. Алгебра высказываний

1. Вспоминай формулы по каждой теме
2. Решай новые задачи каждый день
3. Вдумчиво разбирай решения

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

Задание 1 #12755

Обозначим через \(m\&n\) поразрядную конъюнкцию неотрицательных целых чисел \(m\) и \(n.\) Так, например, \(14\&5 = 11102\&01012 = 0100_2 = 4.\)

Для какого наименьшего неотрицательного целого числа \(A\) формула \((x\&25 \neq 0) \to ((x\&17 = 0) \to (x\&A \neq 0))\) тождественно истинна (т.е. принимает значение \(1\) при любом неотрицательном целом значении переменной \(x\))?

Обозначим \(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

Задание 2 #12756

Обозначим через \(m\&n\) поразрядную конъюнкцию неотрицательных целых чисел \(m\) и \(n.\) Так, например, \(14\&5 = 11102\&01012 = 0100_2 = 4.\)

Для какого наименьшего неотрицательного целого числа \(A\) формула \(((x\&47 \neq 0) \vee (x\&24 \neq 0)) \to ((x\&29 = 0) \to (x\&A \neq 0))\) тождественно истинна (т.е. принимает значение \(1\) при любом неотрицательном целом значении переменной \(x\))?

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

Используя, что \(a \to b = \overline{a} \vee b,\) получим: \(Z_{47} \wedge Z_{24} \vee \overline{Z_{29}} \vee \overline{Z_{A}}.\)

Теперь снова воспользуемся этим правилом, только в обратную сторону. Получим \(Z_{A} \wedge Z_{29} \to Z_{47} \wedge Z_{24}.\)

Так как \(Z_{a} \wedge Z_{b} = Z_{a \; or \; b},\) наше выражение имеет вид \(Z_{A \; or \; 29} \to Z_{47 \; or \; 24}.\)

Правую часть можем сразу вычислить, поразрядно сложив в двоичной системе счисления. Это

\[\begin{array}{r} \,\,101111;\; \\ 011000;\;\\ \hline 111111\;\;\\ \end{array}\]

Теперь рассмотрим левую часть. Знаем, что, чтобы импликация была истинной, нам нужно, чтобы на всех местах, где в двоичной записи правого выражения стоит \(1,\) единица стояла и в записи выражения слева. \(29 = 11101_{2}.\) Для удобства запишем в столбик \(A\) (пока не знаем, чему равно) и \(29,\) а под чертой — \(Z_{47 \; or \; 24}.\)

\(\)

r \(*****\)
11101
111111

\(\)

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

Таким образом, на месте второго с конца бита числа \(A\) должна стоять \(1\) — а на остальных местах неважно, что: благодаря 29 на этих местах и так будут стоять 1.

Так как мы ищем наименьшее неотрицательное целое \(A,\) на тех местах, на каких можем, мы хотим ставить \(0.\) Значит, \(A\) имеет вид \(10_{2} = 2_{10}.\)

Ответ: 2

Задание 3 #12757

Обозначим через \(m\&n\) поразрядную конъюнкцию неотрицательных целых чисел \(m\) и \(n.\) Так, например, \(14\&5 = 11102\&01012 = 0100_2 = 4.\)

Для какого наибольшего неотрицательного целого числа \(A\) формула \((x\&A \neq 0) \to ((x\&11 = 0) \to (x\&17 \neq 0))\) тождественно истинна (т.е. принимает значение \(1\) при любом неотрицательном целом значении переменной \(x\))?

Введем обозначение: \(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

Задание 4 #12758

Обозначим через \(m\&n\) поразрядную конъюнкцию неотрицательных целых чисел \(m\) и \(n.\) Так, например, \(14\&5 = 11102\&01012 = 0100_2 = 4.\)

Для какого наименьшего неотрицательного целого числа \(A\) формула \(((x\&17 \neq 0) \wedge (x\&57 \neq 0)) \to ((x\&A \neq 0) \wedge (x\&17 \neq 0))\) тождественно истинна (т.е. принимает значение \(1\) при любом неотрицательном целом значении переменной \(x\))?

Введем обозначение: \(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

Задание 5 #12759

Обозначим через \(m\&n\) поразрядную конъюнкцию неотрицательных целых чисел \(m\) и \(n.\) Так, например, \(14\&5 = 11102\&01012 = 0100_2 = 4.\)

Для какого наименьшего неотрицательного целого числа \(A\) формула \(((x\&29 \neq 0) \wedge (x\&18 \neq 0)) \to ((x\&A \neq 0) \wedge (x\&29 \neq 0))\) тождественно истинна (т.е. принимает значение \(1\) при любом неотрицательном целом значении переменной \(x\))?

Введем обозначение: \(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

Задание 6 #12760

Обозначим через \(m\&n\) поразрядную конъюнкцию неотрицательных целых чисел \(m\) и \(n.\) Так, например, \(14\&5 = 11102\&01012 = 0100_2 = 4.\)

Для какого наибольшего неотрицательного целого числа \(A\) формула \(((x\&23 = 0) \vee (x\&17 = 0)) \to ((x\&58 \neq 0) \to (x\&A = 0))\) тождественно истинна (т.е. принимает значение \(1\) при любом неотрицательном целом значении переменной \(x\))?

Введем обозначение: \(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

Задание 7 #12761

Обозначим через \(m\&n\) поразрядную конъюнкцию неотрицательных целых чисел \(m\) и \(n.\) Так, например, \(14\&5 = 11102\&01012 = 0100_2 = 4.\)

Для какого наибольшего неотрицательного целого числа \(A\) формула \(((x\&17 \neq 0) \vee (x\&A \neq 0)) \to (x\&17 \neq 0) \vee ((x\&A \neq 0) \wedge (x\&41 = 0))\) тождественно истинна (т.е. принимает значение \(1\) при любом неотрицательном целом значении переменной \(x\))?

Введем обозначение: \(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