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

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

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

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

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

Так, например, 14 & 5  =  1110₂ & 0101₂  =  0100₂  =  4. Для какого наименьшего неотрицательного целого числа А формула

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

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

Решение.

Приведем аналитическое решение Юрия Красильникова.

Преобразуем исходное выражение x & 29 ≠ 0 → (x & 17 = 0 → x & А ≠ 0),

исключив импликацию: (x & 29 = 0) ∨ (x & 17 ≠ 0) ∨ (x & А ≠ 0).

Число 29 в двоичном представлении  — это 11101.

Если число x не содержит единиц в разрядах 0, 2, 3 и 4, то выражение (x & 29  =  0) будет истинно, а значит, истинной будет и вся формула. (Разряды считаем справа налево, начиная с нуля.)

С другой стороны, если единицы будут в разрядах числа 17 (двоичное 10001), то есть в разрядах 0 и 4, то выражение (x & 17 ≠ 0) и вся формула будут истинны.

Следовательно, два левых выражения будут ложными, если в числе x есть единицы в разрядах, которые есть в числе 29, но которых нет в числе 17, то есть в разрядах 2 и 3. В таком случае должно быть истинным выражение (x & А ≠ 0). Поэтому число A должно обязательно содержать единицы в разрядах 2 и 3. Это число в двоичной записи  — 1100, в десятичной  — 12.

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

var

A, x: integer;

B: boolean;

begin

for A := 0 to 32 do begin

B := True;

for x := 0 to 32 do

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

B := False;

if B then begin

writeln(A);

break;

end;

end.

Ответ: 12.

Приведем аналогичную программу на языке Python (Владимир Юрьевич Ламок).

ok=1

A=set()

for a in range (1, 65):

   ok=1

   for x in range (0, 65):

      if ((x & 29 != 0) <= ((x & 17 == 0) <= (x & a != 0))) == 0:

         ok=0

   if ok:

      A.add(a)

      break

print(min(A))

Заметим, что можно было перебирать числа не до 64, а до 32, поскольку представляют интерес только биты, которые могут быть установлены в числах 29 и 17.

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

for A in range(0, 1000):

flag = True

for x in range(1000):

f = (x & 29 != 0) <= ((x & 17 == 0) <= (x & A != 0))

if not(f):

flag = False

break

if flag:

print(A)

break

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

for a in range(0, 1000):

k = 0

for x in range(0, 1000):

if (x & 29 != 0) <= ((x & 17 == 0) <= (x & a != 0)):

k += 1

if k == 1000:

print(a)

break

Приведём решение Ильи Андрианова на языке Python.

def F(x, A):

return (x & 29 != 0) <= ((x & 17 == 0) <= (x & A != 0))

for A in range(0, 1000):

if all(F(x, A) for x in range(0, 10000)):

print(A)

break

Приведём решение Сергея Донец на языке PascalABC.NET.

begin
(0..55).Where(A->(0..55).all(x->
x and 29 <> 0 <= (x and 17 = 0 <= (x and A <> 0))
)).first.println;
end.

Аналоги к заданию № 9804: 34506 34508 34510 ... Все

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

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

Обозначим через 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 должны являться единичными битами левой части. Поэтому в побитовой дизъюнкции 17 or A единицы должны стоять на нулевой, второй, третьей, четвертой и пятой позициях (как обычно, считая справа налево, начиная с нуля). Запишем числа 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.

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

Приведём другое решение на языке 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

Ответ: 44.

Приведём решение Сергея Донец на PascalABC.NET:

begin

(0..88).Where(A->(0..88).all(x->

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

)).First.Print;

end.

Аналоги к заданию № 34509: 34516 55602 55632 ...34516 55602 55632 56515 56543 Все

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

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

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

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

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

x&33 = 0 → (x&45≠0 → x&А ≠ 0)

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

Решение.

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

Х → (¬Y → ¬Z) = ¬Х + (¬Y → ¬Z) = ¬Х + Y + ¬Z = Y + ¬(XZ) = XZ → Y.

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

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

Таким образом, наименьшее А  =  001100₂  =  12₁₀.

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

Решим задание с помощью языка программирования 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 33) <> 0) or ((x and 45) = 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&33!=0) or (x&45==0) or (x&A!=0))==0:

B=False

if B:

print(A)

break

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

Ответ: 12.

Приведём решение Сергея Донец на PascalABC.NET:

begin

(0..90).Where(A->(0..90).all(x->

x and 33=0<=(x and 45<>0<=(x and A<>0))

)).First.Print;

end.

Аналоги к заданию № 34513: 34519 34520 35989 ...34519 34520 35989 36870 38949 39244 Все

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

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

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

Так, например, 12&6  =  1100₂&0110₂  =  0100₂  =  4.

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

х&А $не равно 0$ → (x&10 = 0 → х&3 $не равно 0$ )

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

Решение.

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

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

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

Имеем импликацию Z₁₀Z₃ → Z_A или Z_{(10 or 3)} → Z_A. Запишем числа 10 и 3 в двоичной системе счисления: 10₁₀  =  1010₂, 3₁₀  =  11₂, найдем побитовую дизъюнкцию: 1011. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поэтому в правой части единичными битами независимо друг от друга могут быть (а могут не быть) только нулевой, первый и третий биты (как обычно, считая справа налево, начиная с нуля).

Таким образом, наибольшее А  =  1011₂  =  11₁₀.

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

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

var

A, x: integer;

B: boolean;

begin

for A := 0 to 15 do begin

B := True;

for x := 0 to 15 do

if not (((x and 3) <> 0) or ((x and 10) <> 0) or ((x and (15-A)) = 0)) then

B := False;

if B then begin

writeln((15-A));

break;

end;

end.

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

for A in range(16):

B = True

for x in range(16):

if ((x&(15-A)==0) or (x&10!=0) or (x&3!=0))==0:

B=False

if B:

print(15-A)

break

Заметим, что можно не перебирать числа, большие 15, поскольку для записи чисел 3 и 10 хватит четырёх разрядов. Программа выведет ответ 11.

Ответ: 11.

Приведём решение Сергея Донец на PascalABC.NET:

begin

(0..22).Where(A->(0..22).all(x->

(x and A<>0)<=(x and 10=0<=(x and 3<>0))

)).Last.Print;

end.

Аналоги к заданию № 34517: 34518 Все

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

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

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

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

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

x&51 = 0 ∨ (x&41 = 0 → x&А = 0)

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

Решение.

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

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

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

Заметим, что первое слагаемое логической суммы является импликацией Z₄₁ → Z₅₁, которая не является истинной для всех х (см. ниже). Тогда необходимо и достаточно, чтобы второе слагаемое логической суммы было тождественно истинным.

Действительно, например, для х  =  2 поразрядная конъюнкция с числом 41 дает 0, а с числом 51 дает 2. Поэтому импликация (2&41) → (2&51) принимает вид 1 → 0  — ложь.

 2:      000010

41:     101001

2&41: 000000, то есть 2&41  =  0. Высказывание 2&41  =  0 истинно.

 2:      000010

51:     110011

2&51: 000010  =  2, то есть 2&51  =  2. Высказывание 2&51  =  0 ложно.

Итак, импликация Z₄₁ → Z_A должна быть тождественно истинной. Запишем число 41 в двоичной системе счисления: 41₁₀  =  101001₂. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поэтому в правой части единичными битами независимо друг от друга могут быть (а могут не быть) только нулевой, третий и пятый биты (как обычно, считая справа налево, начиная с нуля).

Таким образом, наибольшее А  =  101001₂  =  41₁₀.

Ответ: 41.

Примечание.

Ответ 45 не подходит. Пусть A  =  45, а x  =  22₁₀  =  10110₂, тогда:

51:       110011₂

22:       010110₂

51&22: 010010₂, то есть высказывание 22&51  =  0 ложно;

41:       101001₂

22:       010110₂

41&22: 000000₂, то есть высказывание 22&41  ≠  0 ложно;

45:       101101₂

22:       010110₂

51&22: 000100₂, то есть высказывание 22&45  =  0 ложно.

Следовательно, при x  =  22 и A  =  45 логическое выражение ложно.

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

Выражение x&51  =  0 ∨ (x&41  =  0 → x&А  =  0) должно быть истинным для любого х. Возьмем такое х, в котором установлены все биты, кроме тех, которые установлены в числе 41, например, для однобайтового представления х  =  11010110₂.

Выражение x&51  =  0 будет ложно, поскольку и в числе х, и в числе 51 установлен первый бит (биты считаем справа налево, начиная с нуля).

Следовательно, истинной должна быть импликация во второй скобке. Но левая часть импликации x&41  =  0 истинна, поскольку ни один из битов, установленных в числе 41, в числе х не установлен.

Тогда истинной должна быть и правая часть импликации x&А  =  0. Следовательно, в числе А могут быть установлены только те биты, которые не установлены в числе х, то есть нулевой, третий и пятый биты. Таким образом, наибольшее А  =  101001₂  =  41₁₀.

При таком А левая и правая части импликации одинаковы. Следовательно, импликация в правой скобке истинна, а значит, истинно и все выражение.

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

Решим задание с помощью языка программирования 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 51) = 0) or ((x and 41) <> 0) or ((x and (63-A)) = 0)) then

B := False;

if B then begin

writeln((63-A));

break;

end;

end.

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

for A in range(64):

B = True

for x in range(64):

if ((x&51==0) or (x&41!=0) or (x&(63-A)==0))==0:

B=False

if B:

print(63-A)

break

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

Ответ: 41.

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

for a in range(100, 0, -1):

k = 0

for x in range(100, 0, -1):

if (x & 51 == 0) or (not(x & 41 == 0) or (x & a == 0)):

k += 1

if k == 100:

print(a)

break

Приведём решение Ильи Андрианова на языке Python.

def F(x, A):

return (x&51 == 0) or ((x&41 == 0) <= (x&A == 0))

R = []

for A in range(0, 10_000):

if all(F(x, A) for x in range(0, 10_000)):

R.append(A)

print(max(R))

Приведём решение Сергея Донец на PascalABC.NET:

begin

(0..111).Where(A->(0..111).all(x->

(x and 51=0)or(x and 41=0<=(x and A=0))

)).Last.Print;

end.

Аналоги к заданию № 34521: 34522 Все

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

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