ЕГЭ–2026, информатика: задания, ответы, решения

Каталог заданий.
Побитовая конъюнкция

Пройти тестирование по этим заданиям
Вернуться к каталогу заданий
Версия для печати и копирования в MS Word

Тип Д15 № 9369 Добавить в вариант

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

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

x&25 ≠ 0 → (x&17 = 0 → x&А ≠ 0)

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

Решение.

Преобразуем выражение по законам алгебры логики:

¬Х → (Y → ¬Z) = Х + (Y → ¬Z) = Х + ¬Y + ¬Z = X + ¬(YZ) = YZ → X.

Далее применяем обозначения и реализуем способ решения, изложенный К. Ю. Поляковым в теоретических материалах (см., например, раздел «Теория» на нашем сайте) без дополнительных пояснений.

Имеем импликацию Z₁₇Z_A → Z₂₅ или Z_{(17 or A)} → Z₂₅. Запишем число 25 в двоичной системе счисления: 25₁₀  =  11001₂. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поскольку 17₁₀  =  10001₂, двоичная запись искомого числа А должна содержать единичный бит в третьем разряде (как обычно, считая справа налево, начиная с нуля).

Тем самым, наименьшее А = 1000₂  =  8₁₀.

Приведём другое решение.

Решим задание с помощью языка программирования PascalABC методом перебора:

var

A, x: integer;

B: boolean;

begin

for A := 0 to 31 do begin

B := True;

for x := 0 to 31 do

if not (((x and 25) = 0) or ((x and 17) <> 0) or ((x and A) <> 0)) then

B := False;

if B then begin

writeln(A);

break;

end;

end.

Приведём решение на языке Python.

for A in range(32):
    B = True
    for x in range(32):
        if ((x&25==0) or (x&17!=0) or (x&A!=0))==0:
            B=False
    if B:
        print(A)
        break

Заметим, что можно не перебирать числа, большие 31, поскольку для записи чисел 25 и 17 хватит пяти разрядов. Программа выведет ответ 8.

Ответ: 8.

Источник: Демонстрационная версия ЕГЭ—2016 по информатике

Решение · Помощь

Тип Д15 № 9768 Добавить в вариант

Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14 & 5 = 1110₂ & 0101₂ = 0100₂ = 4. Для какого наименьшего неотрицательного целого числа А формула

x & 29 ≠ 0 → (x & 12 = 0 → x & А ≠ 0)

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

Решение.

Преобразуем выражение по законам алгебры логики:

¬Х → (Y → ¬Z) = Х + (Y → ¬Z) = Х + ¬Y + ¬Z = X + ¬(YZ) = YZ → X.

Далее применяем обозначения и реализуем способ решения, изложенный К. Ю. Поляковым в теоретических материалах (см., например, раздел «Теория» на нашем сайте), без дополнительных пояснений.

Имеем импликацию Z₁₂Z_A → Z₂₉ или Z_{(12 or A)} → Z₂₉. Запишем число 29 в двоичной системе счисления: 29₁₀  =  11101₂. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поскольку 12₁₀  =  01100₂, двоичная запись искомого числа А должна содержать единичные биты в нулевом и четвертом разрядах (как обычно, считая справа налево, начиная с нуля).

Тем самым, наименьшее А = 10001₂  =  17₁₀.

Приведём другое решение.

Решим задание с помощью языка программирования PascalABC методом перебора:

var

A, x: integer;

B: boolean;

begin

for A := 0 to 31 do begin

B := True;

for x := 0 to 31 do

if not (((x and 29) = 0) or ((x and 12) <> 0) or ((x and A) <> 0)) then

B := False;

if B then begin

writeln(A);

break;

end;

end.

Приведём решение на языке Python.

for A in range(32):
    B = True
    for x in range(32):
        if ((x&29==0) or (x&12!=0) or (x&A!=0))==0:
            B=False
    if B:
        print(A)
        break

Заметим, что можно не перебирать числа, большие 31, поскольку для записи чисел 29 и 12 хватит пяти разрядов. Программа выведет ответ 17.

Ответ: 17.

Решение · Помощь

Тип Д15 № 10392 Добавить в вариант

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

Так, например, 14&5  =  1110₂&0101₂ = 0100₂ = 4.

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

$левая круглая скобка левая круглая скобка x\28 не равно 0 правая круглая скобка \vee левая круглая скобка x\45 не равно 0 правая круглая скобка правая круглая скобка arrow левая круглая скобка левая круглая скобка x\17=0 правая круглая скобка arrow левая круглая скобка x\A не равно 0 правая круглая скобка правая круглая скобка$

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

Решение.

Преобразуем выражение по законам алгебры логики:

(¬Х + ¬Y) → (W → ¬Z) = ¬(¬Х + ¬Y) + (¬W + ¬Z) = ХY + ¬(WZ) = WZ → XY.

Имеем импликацию Z₁₇Z_A → Z₂₈Z₄₅ или Z_{(17 or А)} → Z_{(28 or 45)}. Поскольку 28₁₀  =  11100₂, 45₁₀  =  101101₂, для побитовой дизъюнкции имеем: 28or45  =  111101. Тогда Z_{(17 or А)} = Z₆₁.

Импликация принимает вид Z_{(17 or A)} → Z₆₁. Единичные биты двоичной записи числа 61, должны являться единичными битами левой части. Поэтому в побитовой дизъюнкции 17orA единицы должны стоять на нулевой, второй, третьей, четвертой и пятой позициях (как обычно, считая справа налево, начиная с нуля). Запишем числа 17, А и 61 в двоичной системе счисления, и выясним, что наименьшее число, дающее при поразрядной дизъюнкции единицы на указанных позициях:

17: 010001

 A:  1?110?

61: 111101

В записи наименьшего числа, дающего при поразрядной дизъюнкции с числом 17 единицы в необходимых разрядах, на месте знаков ? должны стоять нули. Тем самым, искомым числом является А  =  101100₂  =  44₁₀.

Приведём другое решение.

Решим задание с помощью языка программирования PascalABC методом перебора:

var

A, x: integer;

B: boolean;

begin

for A := 0 to 63 do begin

B := True;

for x := 0 to 63 do

if not (((x and 28) = 0) and ((x and 45) = 0) or ((x and 17) <> 0) or ((x and A) <> 0)) then

B := False;

if B then begin

writeln(A);

break;

end;

end.

Приведем аналогичную программу на языке Python.

for A in range(64):
    B = True
    for x in range(64):
        if ((x&28==0) and (x&45==0) or (x&17!=0) or (x&A!=0))==0:
            B=False
    if B:
        print(A)
        break

Заметим, что можно не перебирать числа, большие 63, поскольку для записи чисел 28, 45 и 17 хватит шести разрядов. Программа выведет ответ 44.

Ответ: 44.

Решение · Помощь

Тип Д15 № 13494 Добавить в вариант

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

Например, 14&5 = 1110₂&0101₂ = 0100₂ = 4.

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

x&25 ≠ 0 → (x&9 = 0 → x&А ≠ 0)

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

Решение.

Преобразуем выражение по законам алгебры логики:

¬Х → (Y → ¬Z) = Х + (Y → ¬Z) = Х + ¬Y + ¬Z = X + ¬(YZ) = YZ → X.

Имеем импликацию Z₉Z_A → Z₂₅ или Z_{(9 or A)} → Z₂₅. Запишем число 25 в двоичной системе счисления: 25₁₀  =  11001₂. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поскольку 9₁₀  =  01001₂, двоичная запись искомого числа А должна содержать единичный бит в четвертом разряде (как обычно, считая справа налево, начиная с нуля).

Тем самым, наименьшее А = 10000₂  =  16₁₀.

Приведём другое решение.

Решим задание с помощью языка программирования PascalABC методом перебора:

var

A, x: integer;

B: boolean;

begin

for A := 0 to 31 do begin

B := True;

for x := 0 to 31 do

if not (((x and 25) = 0) or ((x and 9) <> 0) or ((x and A) <> 0)) then

B := False;

if B then begin

writeln(A);

break;

end;

end.

Приведём аналогичное решение на языке Python.

for A in range(32):
    B = True
    for x in range(32):
        if ((x&25==0) or (x&9!=0) or (x&A!=0))==0:
            B=False
    if B:
        print(A)
        break

Заметим, что можно не перебирать числа, большие 31, поскольку для записи чисел 25 и 9 хватит пяти разрядов. Программа выведет ответ 16.

Ответ: 16.

Решение · Помощь

Тип Д15 № 13521 Добавить в вариант

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

Например, 14&5 = 1110₂&0101₂ = 0100₂ = 4.

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

x&25 ≠ 0 → (x&19 = 0 → x&А ≠ 0)

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

Решение.

Преобразуем выражение по законам алгебры логики:

¬Х → (Y → ¬Z) = Х + (Y → ¬Z) = Х + ¬Y + ¬Z = X + ¬(YZ) = YZ → X.

Имеем импликацию Z₁₉Z_A → Z₂₅ или Z_{(19 or A)} → Z₂₅. Запишем число 25 в двоичной системе счисления: 25₁₀  =  11001₂. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поскольку 19₁₀  =  10011₂, двоичная запись искомого числа А должна содержать единичный бит в третьем разряде (как обычно, считая справа налево, начиная с нуля).

Тем самым, наименьшее А = 1000₂  =  8₁₀.

Приведём другое решение.

Решим задание с помощью языка программирования PascalABC методом перебора:

var

A, x: integer;

B: boolean;

begin

for A := 0 to 31 do begin

B := True;

for x := 0 to 31 do

if not (((x and 25) = 0) or ((x and 19) <> 0) or ((x and A) <> 0)) then

B := False;

if B then begin

writeln(A);

break;

end;

end.

Приведём аналогичное решение на языке Python.

for A in range(32):
    B = True
    for x in range(32):
        if ((x&25==0) or (x&19!=0) or (x&A!=0))==0:
            B=False
    if B:
        print(A)
        break

Заметим, что можно не перебирать числа, большие 31, поскольку для записи чисел 25 и 19 хватит пяти разрядов. Программа выведет ответ 8.

Ответ: 8.

Источник: Тренировочная работа по ИНФОРМАТИКЕ 11 класс 29 ноября 2016 года Вариант ИН10204

Решение · Помощь

Пройти тестирование по этим заданиям