РЕШУ ЕГЭ — информатика

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

Обозначим через 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.

Обозначим через 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.

Обозначим через 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.

Обозначим через 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.

Обозначим через 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.

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

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

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

x&77 ≠ 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₇₇. Запишем число 77 в двоичной системе счисления: 77₁₀  =  1001101₂. Единичные биты, стоящие в правой части, должны являться единичными битами левой. Поскольку 12₁₀  =  0001100₂, двоичная запись искомого числа А должна содержать единичные биты в нулевом и шестом разрядах (как обычно, считая справа налево, начиная с нуля).

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

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

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

var

A, x: integer;

B: boolean;

begin

for A := 0 to 127 do begin

B := True;

for x := 0 to 127 do

if not (((x and 77) = 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(128):
    B = True
    for x in range(128):
        if ((x&77==0) or (x&12!=0) or (x&A!=0))==0:
            B=False
    if B:
        print(A)
        break

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

Ответ: 65.

Обозначим через 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.

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

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

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

x&49 ≠ 0 → (x&41 = 0 → x&А ≠ 0)

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

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

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

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

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

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

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

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

Ответ: 16.

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

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

Для какого наименьшего неотрицательного целого числа А формула x&41 ≠ 0 → (x&33 = 0 → x&А ≠ 0)

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

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

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

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

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

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

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

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

Ответ: 8.

10.  

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

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

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

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

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

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

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

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

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

48: 110000

 A:  ??1101

61: 111101

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

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

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

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

Ответ: 13.

11.  

Обозначим через 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.

12.  

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

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

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

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

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

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

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

Тем самым, наибольшее А = 100110₂  =  38₁₀.

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

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

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

Ответ: 38.

13.  

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

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

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

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

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

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

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

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

Решим задание с помощью языка программирования 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 9) <> 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&9!=0) or (x&19==0) or (x&A!=0))==0:
            B=False
    if B:
        print(A)
        break

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

Ответ: 18.

14.  

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

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

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

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

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

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

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

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

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

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

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

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

Ответ: 12.

15.  

Обозначим через 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₁₀.

Примечание.

Ответ 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₂

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

Следовательно, при x = 22 и A = 45 логическое выражение x&51 = 0 ∨ (x&41 = 0 → x&А = 0) ложно.

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

Выражение 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.

16.  

Обозначим через 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).

 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 ложно.

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

Ответ: 0.

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

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

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

Решим задание с помощью языка программирования 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 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&51==0) or (x&41!=0) or (x&A==0))==0:
            B=False
    if B:
        print(A)
        break

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

Ответ: 0.

№ п/п	№ задания	Ответ
1	9369	8
2	9768	17
3	10392	44
4	13494	16
5	13521	8
6	13548	65
7	13575	12
8	13602	16
9	13629	8
10	10419	13
11	10481	11
12	10508	38
13	11247	18
14	11274	12
15	13695	41
16	13727	0

Ключ