Побитовая конъюнкция —Каталог задач по ЕГЭ - Информатика

Тема 15. Преобразование логических выражений

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

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела преобразование логических выражений

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#39302

Обозначим через $m&n$ поразрядную конъюнкцию неотрицательных целых чисел $m$ и $n$ .

Так, например, $14&5 = 11102&01012 = 01002 = 4$ .

Для какого наименьшего натурального числа $A$ формула

((x&35 ⁄= 0)∨ (x &23 ⁄= 0)) → ((x&26 ⁄= 0)∨ (x&A = 0))

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

Показать ответ и решение

Решение 1 (руками) Враги хотят, чтобы выражение было ложно, такое возможно при выполнении следующих условий:

$x&26 = 0$ , $x&A ⁄= 0$ , $X &35 ⁄= 0$ ИЛИ $X &23 ⁄= 0$ .

Переведем числа в двоичную систему счисления:

$26 = 110102$

$23 = 101112$

$35 = 1000112$

Рассмотрим два случая:

1) $x &26 = 0$ , $x&A ⁄= 0$ , $x&35 ⁄= 0$

Чтобы $x &26 = 0$ , врагам нужен $x$ вида $∗...∗00 ∗0∗$ , * — 0 или 1.

Чтобы $x &26 = 0$ и $x&35 ⁄= 0$ , врагам нужен $x$ вида $∗ ...∗ 00∗01$ , * — 0 или 1.

Чтобы $x &A ⁄= 0$ , на место * враги поставят 1, то есть будут брать $x = 1...100101$ , на месте ... — 1.

2) $x &26 = 0$ , $x&A ⁄= 0$ , $x&23 ⁄= 0$

Чтобы $x &26 = 0$ , врагам нужен $x$ вида $∗...∗00 ∗0∗$ , * — 0 или 1.

Чтобы $x &26 = 0$ и $x&23 ⁄= 0$ , врагам нужен $x$ вида $∗ ...∗ 00 0-$ , * — 0 или 1, а на месте одного из _ стоит 1.

Чтобы $x &A ⁄= 0$ , на место * враги поставят 1, то есть будут брать $x = 1...100101$ , на месте ... — 1.

Врагам достаточно, чтобы выполнялся 1 или 2 случай, но в обоих случаях они берут один и тот же $x$ .

Цель друзей — найти такой $A$ , чтобы $x&A = 0$ , то есть их цель - обнулить все единицы выбранного врагами $x$ , а оставшиеся разряды им нужно занять так, чтобы число $A$ было минимальным, но натуральным (больше 0).

Тогда $A = 0...0000102 = 2$ .

Решение 2 (прогой)

def f(x, a):
    return ((x & 35 != 0) or (x & 23 != 0)) <= ((x & 26 != 0) or (x & a == 0))


for a in range(1, 300):
    p = True
    for x in range(0, 300):
        if f(x, a) == False:
            p = False
            break
    if p == True:
        print(a)
        break

Ответ: 2

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#33874

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

Для какого наименьшего целого числа $A$ формула

(x & 105 = 0) → ((x & 58 ⁄= 0) → (x & A ⁄= 0))

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

Показать ответ и решение

for A in range(1000):
    p = True
    for x in range(1000):
        f = (x & 105 == 0) <= ((x & 58 != 0) <= (x & A != 0))
        if f == False:
            p = False
            break
    if p == True:
        print(A)
        break

Ответ: 18

Ошибка.
Попробуйте повторить позже

Задача 3#33873

Для какого наименьшего целого числа $A$ формула

(x & 85 = 0) → (x & 54 ⁄= 0 → x & A ⁄= 0)

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

Показать ответ и решение

def f(a):
    # если отрцание формулы возвращает истину,
    # то сама формула возвращает ложь
    for x in range(1000):
        if not((x & 85 == 0) <= ((x & 54 != 0) <= (x & a != 0))):
            return False
    return True

for a in range(1000):
    if f(a):
        print(a)
        break

Ответ: 34

Ошибка.
Попробуйте повторить позже

Задача 4#29716

Обозначим через $m&n$ поразрядную конъюнкцию неотрицательных целых чисел $m$ и $n$ .

Так, например, $14&5 = 11102&01012 = 01002 = 4$ .

Для какого наименьшего неотрицательного целого числа $A$ формула

((x&35 ⁄= 0)∨ (x &23 ⁄= 0)) → ((x&26 = 0)∨ (x&A ⁄= 0))

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

Показать ответ и решение

def f(x, a):
    return ((x & 35 != 0) or (x & 23 != 0)) <= ((x & 26 == 0) or (x & a != 0))


for a in range(0, 300):
    p = True
    for x in range(0, 300):
        if f(x, a) == False:
            p = False
            break
    if p == True:
        print(a)
        break

Ответ: 26

Ошибка.
Попробуйте повторить позже

Задача 5#29715

Обозначим через $m&n$ поразрядную конъюнкцию неотрицательных целых чисел $m$ и $n$ .

Так, например, $14&5 = 11102&01012 = 01002 = 4$ .

Для какого наибольшего целого числа $A$ формула

¬(x&A ⁄= 0) ∨¬ (x&122 = 0)∨ (x&144 ⁄= 0)

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

Показать ответ и решение

Решение 1

Преобразуем выражение к виду $Z122Z144 → ZA$ с помощью законов де Моргана:

(x&A = 0) ∨(x&122 ⁄= 0)∨ (x &144 ⁄= 0)

((x &122 = 0) ∧(x&144 = 0)) → (x&A = 0)

Для того, чтобы выражение вида $Z122Z144 → ZA$ являлось истинным, единичные биты, стоящие в правой части, должны являться единичными битами левой.

Запишем числа 122 и 144 в двоичной системе счисления:

$12210 = 011110102$

$144 = 10010000 10 2$

Враги будут брать такие $x$ , которые дают 0 в побитовой конъюнкции с числами $122$ и $144$ , и увеличить число незначащих единиц, чтобы $x &A ⁄= 0$ .

Тогда враги возьмут $x = 1...100000101$ , на месте ... — 1.

Тогда друзья берут такое $A$ , чтобы $x&A = 0$ , и делают его максимальным:

$A = 00...0111110102$ , то есть $A = 250$ .

Решение 2

def f(a):
    for x in range(1, 10000):
        if not((x & a == 0) or (x & 122 != 0) or (x & 144 != 0)):
            return False
    return True

for a in range(1, 1000):
    if f(a):
        print(a)

Ответ: 250

Ошибка.
Попробуйте повторить позже

Задача 6#29714

Обозначим через $m&n$ поразрядную конъюнкцию неотрицательных целых чисел $m$ и $n$ .

Так, например, $14&5 = 11102&01012 = 01002 = 4$ .

Для какого наибольшего целого числа $A$ формула

--------- (x&A ⁄= 0)∨ (x&74 = 0 → x&65 ⁄= 0)

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

Показать ответ и решение

Решение 1 (руками)

Враги хотят, чтобы все выражение было ложно, тогда условия для врагов:

$x&A ⁄= 0$ , $x&74 = 0$ , $x &65 = 0$ .

$74 = 10010102$

$65 = 10000012$

Чтобы $x &74 = 0$ , $x$ должно иметь вид **0**0*0*, где * - 0 или 1.

Чтобы $x &65 = 0$ , $x$ должно иметь вид **0*****0, где * - 0 или 1.

Чтобы $x &A ⁄= 0$ , $x$ должно иметь как можно больше единиц, тогда для выполнения всех трех условий враги будут брать $x$ , который имеет вид $11...110110100$ , на месте ... стоят 1.

Друзья хотят, чтобы $x&A = 0$ и при этом $x$ было максимально, тогда им нужно обнулять все разряды $x$ , в которых стоят 1, и поставить 1 во все разряды, где у $x$ стоят нули.

Отсюда получаем, что $A$ имеет вид $00...001001011$ , на месте ... стоят 0.

$A = 1001011 = 75 2$ .

Решение 2 (прогой)

def f(a):
    for x in range(1000):
        if ((x & a == 0) or ((x & 74 == 0) <= (x & 65 != 0))) == 0:
            return False
    return True

for a in range(1000, 0, - 1):
    if f(a):
        print(a)
        break

Ответ: 75

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#29713

Обозначим через $m&n$ поразрядную конъюнкцию неотрицательных целых чисел $m$ и $n$ .

Так, например, $14&5 = 11102&01012 = 01002 = 4$ .

Для какого наибольшего целого числа $A$ формула

(x&A ⁄= 0) → ((x&25 = 0) → (x&17 ⁄= 0))

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

Показать ответ и решение

Преобразуем выражение к виду $Z25Z17 → ZA$ с помощью законов де Моргана:

(x&A = 0)∨ (x&25 ⁄= 0)∨ (x &17 ⁄= 0)

((x &25 = 0) ∧(x&17 = 0)) → (x&A = 0)

Для того, чтобы выражение вида $Z25Z17 → ZA$ являлось истинным, единичные биты, стоящие в правой части, должны являться единичными битами левой.

Запишем числа 25 и 17 в двоичной системе счисления:

$2510 = 110012$

$1710 = 100012$

Значит, $A$ обязательно должно содержать в себе единицу в нулевом, третьем и четвёртом разрядах. Так как ищем наибольшее $A$ , наш ответ $110012 = 2510$ .

Ответ: 25

Ошибка.
Попробуйте повторить позже

Задача 8#29712

Обозначим через $m&n$ поразрядную конъюнкцию неотрицательных целых чисел $m$ и $n$ .

Для какого наименьшего целого числа $A$ формула

(x&38 = 0) → (x&55 ⁄= 0 → x&A ⁄= 0)

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

Показать ответ и решение

Преобразуем выражение к виду $Z38ZA → Z55$ с помощью законов де Моргана:

(x&38 ⁄= 0)∨ (x&55 = 0) ∨(x&A ⁄= 0)

(x&38 ⁄= 0)∨ (x&A ⁄= 0)∨ (x &55 = 0)

(x&38 = 0 ∧x&A = 0) → (x&55 = 0)

Для того, чтобы выражение вида $Z38ZA → Z55$ являлось истинным, единичные биты, стоящие в правой части, должны являться единичными битами левой.

Запишем числа 38 и 55 в двоичной системе счисления:

$3810 = 1001102$ – левая часть

$5510 = 1101112$ – правая часть

Значит, $A$ обязательно должно содержать в себе единицу в четвертом и нулевом разряде. Так как ищем наименьшее $A$ , наш ответ $010001 = 17 2 10$ .

Ответ: 17

Ошибка.
Попробуйте повторить позже

Задача 9#29362

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

(x&A ⁄= 0)∧ (x&48 = 0)∧ (x &27 = 0)

тождественно ложно (то есть принимает значение $0$ при любом натуральном значении переменной $x$ ).

Показать ответ и решение

for A in range(1, 1000):
    p = True
    for x in range(1, 1000):
        f = (x & A != 0) and (x & 48 == 0) and (x & 27 == 0)
        if f == True:
            p = False
            break
    if p == True:
        print(A)

Ответ: 59

Ошибка.
Попробуйте повторить позже

Задача 10#25907

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

(x&A = 0)∧ (x&58 ⁄= 0)∧ (x &22 = 0)

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

Показать ответ и решение

def f(x, a):
    return ((x & a == 0) and (x & 58 != 0) and (x & 22 == 0))


for a in range(1, 1000):
    if all(f(x, a) == False for x in range(1, 100)):
        print(a)
        break

Ответ: 40

Ошибка.
Попробуйте повторить позже

Задача 11#24416

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

(x &125 ⁄= 1)∨ ((x&34 = 2) → (x&a = 0))

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

Показать ответ и решение

def f(a):
    for x in range(1, 1000):
        if ((x & 125 != 1) or ((x & 34 == 2) <= (x & a == 0))) == 0:
            return False
    return True
for a in range(1, 1000):
    if f(a):
        print(a)
        break

Ответ: 4

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 12#23189

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

(x &27 ⁄= 0) → ((x&83 = 0) → (x&a ⁄= 0))

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

Показать ответ и решение

def f(a):
    for x in range(1, 1000):
        if ((x & 27 != 0) <= ((x & 83 == 0) <= (x & a != 0))) == 0:
            return False
    return True
for a in range(1, 1000):
    if f(a):
        print(a)
        break

Ответ: 8

Ошибка.
Попробуйте повторить позже

Задача 13#22895

Определите наибольшее натуральное число A из интервала [10, 50] такое, что выражение

(((x&56 ⁄= 0) → (x&18 ⁄= 0)) ∨ (x &A ⁄= 0)) → ((x&18 = 0 ) ∧ (x&A = 0) ∧ (x&43 ⁄= 0))

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

Показать ответ и решение

for A in range(10, 50+1):
    flag = True
    for x in range(100000):
        f = (((x & 56 != 0) <= (x & 18 != 0)) or (x & A != 0)) <= (
            (x & 18 == 0) and (x & A == 0) and (x & 43 != 0))
        if f == 1:
            flag = False
            break
    if flag:
        maxim = A
print(maxim)

Ответ: 47

Ошибка.
Попробуйте повторить позже

Задача 14#22655

Обозначим через $a&b$ поразрядную конъюнкцию неотрицательных целых чисел a и b.

Так, например, $16&18 = 100002&100102 = 1610.$

Для какого наименьшего неотрицательного целого числа А формула

x&144 = 0 → (x&220 ⁄= 0 → x&A ⁄= 0)

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

Показать ответ и решение

def f(a):
    for x in range(1, 1000):
        if ((x & 144 == 0) <= ((x & 220 != 0) <= (x & a != 0))) == 0:
            return False
    return True
for a in range(1000):
    if f(a):
        print(a)
        break

Ответ: 76

Ошибка.
Попробуйте повторить позже

Задача 15#21464

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

(x&25 ⁄= 0) → ((x&17 = 0) → (x&A ⁄= 0))

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

Показать ответ и решение

Мечты врагов:

( |||{ x&25 ⁄= 0 x&17=0 ||| ( x&A=0

Переведем числа в $2$ -сс. $25 = 110012$ . $17 = 100012$ . Проведем поразрядную конъюнцию с $x$ . Получаем, что $x = 01∗ ∗02$ . Запишем мечты врагов: «Вот бы $x$ давал в поразрядной конъюнкции с $A$ нолик».

Теперь играем за друзей. Друзья не хотят, чтобы $x$ в поразрядной конъюнкции с $A$ давал ноль. Т.к. у нас требуют наименьшее число $A$ , на место звездочек ставим нули. Получаем число $10002 = 8$ .

Ответ: 8

Ошибка.
Попробуйте повторить позже

Задача 16#20052

((x&28 ⁄= 0)∨ (x&45 ⁄= 0)) → ((x&48 = 0) → (x&a ⁄= 0))

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

Показать ответ и решение

def f(x, A):
    return ((x & 28 != 0) or (x & 45 != 0)) <= ((x & 48 == 0) <= (x & A != 0))

for A in range(10000):
    met_false = False
    for x in range(1000):
        if not(f(x, A)):
            met_false = True
    if not(met_false):
        print(A)
        break

Ответ: 13

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 17#20051

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

(x&25 ⁄= 0) → ((x&17 = 0) → (x&A ⁄= 0))

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

Показать ответ и решение

def f(x, A):
    return (x & 25 != 0) <= ((x & 17 == 0) <= (x & A != 0))

for A in range(10000):
    met_false = False
    for x in range(1000):
        if not(f(x, A)):
            met_false = True
    if not(met_false):
        print(A)
        break

Ответ: 8

Ошибка.
Попробуйте повторить позже

Задача 18#18143

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

(((x&13 ⁄= 0)∨ (x&39 = 0)) → (x&13 ⁄= 0))∨((x&A = 0) ∧(x&13 = 0))

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

Показать ответ и решение

Враги хотят чтобы одновременно $x&39 = 0$ , $x&13 = 0$ , $x&A ⁄= 0$ .

$1310 = 0011012$

$39 = 100111 10 2$

Для выполнения первого условия $x$ должен иметь вид _ _ _ _ 0 0 _ 0. На месте _ может стоять 1 или 0.

Для выполнения и второго условия $x$ должен иметь вид _ _ 0 _ 0 0 0 0.

Для выполнения третьего условия единиц в $x$ должно быть как можно больше. Тогда он имеет вид ...1 1 0 1 0 0 0 0.

Друзья хотят такое максимальное $A$ чтобы $x&A = 0$ . Тогда на местах с единицами в $x$ будут нули, а на местах нулей будут единицы. Значит $A = 1011112 = 47$ .

Ответ: 47

Ошибка.
Попробуйте повторить позже

Задача 19#18142

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

(x&41 = 0) → ((x&119 ⁄= 0) → (x&A ⁄= 0))

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

Показать ответ и решение

Враги хотят чтобы одновременно $x&41 = 0$ , $x&119 ⁄= 0$ , $x&A = 0$ .

$4110 = 01010012$

$119 = 1110111 10 2$

Для выполнения первого условия $x$ должен иметь вид _ _ _ 0 _ 0 _ _ 0. На месте _ может стоять либо 0, либо 1.

Для выполнения и второго условия $x$ должен иметь вид _ _ * 0 * 0 * * 0. На месте хотя бы одной звездочки должна стоять единичка.

Для выполнения третьего условия единиц должно быть как можно меньше, значит $x$ должен иметь вид 0 0 * 0 * 0 * * 0. На месте только одной звездочки должна стоять единица.

Тогда друзья подберут такое минимальное $A$ чтобы $x&A ⁄= 0$ . Друзьям достаточно подставить единички в тех местах где они могут появиться в $x$ . Итоговое $A = 10101102 = 86$ .

Ответ: 86

Ошибка.
Попробуйте повторить позже

Задача 20#16316

Обозначим через $m&n$ поразрядную конъюнкцию неотрицательных целых чисел $m$ и $n.$

Так, например, $14&5 = 11102&01012 = 01002 = 4.$

Для какого наименьшего целого числа $\text{[math]}$ формула

x&65 = 0 → (x&91 ⁄= 0 → x&A ⁄= 0)

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

Показать ответ и решение

$6510 = 10000012$

$9110 = 10110112$

Враги хотят подобрать $x$ такой, что $x&65 = 0,x&91 ⁄= 0,x&A = 0$ . Тогда на всех разрядах где у 65 единички будут нули и в одном из разрядов или в двух одновременно (где у 65 в двоичной записи нули, а у 91 единички) будут единички. Во всех остальных разрядах будут нули чтобы была больше вероятность истинности $x&A = 0$ .

Тогда друзья чтобы $x&A ⁄= 0$ поставят единички где они гарантированно могут появится в $x$ . Это будет число $110102 = 26$ .

Ответ: 26

Предыдущий раздел

Следующий раздел