Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14&5 = 1110₂&0101₂ = 0100₂ = 4. Для какого наибольшего целого числа А формула x&51 = 0 v (x&41 = 0 → x&A = 0) тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной х)?

Решение:

Формула \( x&51 = 0 \lor (x&41 = 0 \rightarrow x&A = 0) \) должна быть истинной для любого неотрицательного целого \( x \). Разложим числа 51 и 41 в двоичную систему счисления:

• \( 51 = 32 + 16 + 2 + 1 = 110011_2 \)
• \( 41 = 32 + 8 + 1 = 101001_2 \)

Пусть \( F \) — заданная формула. \( F \) истинна, если \( x&51 = 0 \) истинно, или если \( x&41 = 0 \) ложно, или если \( x&A = 0 \) истинно.

Рассмотрим случай, когда \( x&51
e 0 \). Это значит, что хотя бы одна из единиц в двоичном представлении \( x \) совпадает с единицей в \( 110011_2 \).

Рассмотрим случай, когда \( x&41 = 0 \). Это означает, что для всех позиций, где в \( 41 (101001_2) \) стоят единицы, в \( x \) должны стоять нули. То есть, \( x \) должен иметь нули в 1, 8 и 32 позициях (считая справа, начиная с 0).

Пусть \( x&41 = 0 \) ложно. Это значит, что \( x \) имеет единицу хотя бы на одной из позиций 1, 8, 32.

Теперь рассмотрим вторую часть формулы: \( (x&41 = 0 \rightarrow x&A = 0) \). Эта импликация ложна только тогда, когда \( x&41 = 0 \) истинно, а \( x&A = 0 \) ложно. Чтобы вся формула была истинна, нам нужно, чтобы случай, когда \( x&41 = 0 \) истинно, приводил к тому, что \( x&A = 0 \) тоже истинно.

Пусть \( x&41=0 \) истинно. Это значит, что \( x \) имеет нули там, где \( 41 \) имеет единицы. Для того чтобы \( x&A=0 \) было истинно, \( x \) должен иметь нули там, где \( A \) имеет единицы.

Нам нужно найти наибольшее \( A \) такое, что если \( x&41=0 \) (т.е. \( x \) имеет нули в позициях 1, 8, 32), то \( x&A=0 \) (т.е. \( x \) имеет нули в позициях, где \( A \) имеет единицы).

Это означает, что все единицы в \( A \) должны совпадать с нулями в \( x \), когда \( x&41=0 \). То есть, если \( x \) имеет единицы только там, где \( 41 \) имеет нули, то \( x \) должен иметь нули там, где \( A \) имеет единицы.

Позиции единиц в \( 41 \) (101001₂): 0, 3, 5.

Позиции нулей в \( x \) при \( x&41=0 \) — это позиции 0, 3, 5. Все остальные позиции могут быть единицами.

Чтобы \( x&A=0 \) было истинно, \( A \) должно содержать единицы там, где \( x \) имеет единицы, и нули там, где \( x \) имеет нули.

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

Если \( x&41=0 \) (т.е. \( x \) имеет нули на позициях 0, 3, 5), то \( x&A=0 \). Это означает, что \( A \) должно быть таким, что \( x&A=0 \) для таких \( x \). Чтобы \( x&A=0 \) было истинно, \( A \) должно «обнулять» все единицы в \( x \). Это значит, что \( A \) должно иметь единицы на всех позициях, где \( x \) может иметь единицы.

Рассмотрим \( x&51 = 0 \). Это значит, что \( x \) имеет нули там, где \( 51 (110011_2) \) имеет единицы. То есть, \( x \) должен иметь нули на позициях 0, 1, 4, 5.

Если \( x&51 = 0 \) истинно, то формула истинна. Это происходит, когда \( x \) имеет нули на позициях 0, 1, 4, 5.

Если \( x&51
e 0 \), то \( (x&41 = 0 \rightarrow x&A = 0) \) должно быть истинно.

Пусть \( x&41=0 \) истинно (нули на позициях 0, 3, 5). Тогда \( x&A=0 \) должно быть истинно. Это означает, что \( A \) должно иметь единицы на всех позициях, где \( x \) может иметь единицы, когда \( x&41=0 \). Наибольшее такое \( A \) будет иметь единицы на всех позициях, кроме 0, 3, 5. Но \( A \) не может иметь единицы там, где \( x \) имеет нули.

Рассмотрим \( A=41 \). Тогда \( x&41=0 \rightarrow x&41=0 \) — это всегда истинно. Это также означает, что \( x&51=0 \) должно быть истинно для всех \( x \) где \( x&41
e 0 \) (чтобы формула была истинной).

Если \( A=41 \), то \( x&41=0 \rightarrow x&41=0 \) — всегда верно. Тогда условие сводится к \( x&51=0 \). Но нам нужно, чтобы формула была истинной для любого \( x \). Не подходит.

Рассмотрим \( A=12 \). \( 12 = 1100_2 \). Позиции единиц: 2, 3.

Если \( x&41=0 \) (нули на 0, 3, 5), то \( x&12=0 \) должно быть истинно. Это означает, что \( x \) должен иметь нули на позициях 2 и 3.

Позиции единиц в \( x \) при \( x&41=0 \) — это все позиции, кроме 0, 3, 5. Если \( x \) имеет единицу на позиции 2 или 3, то \( x&12
e 0 \). Это нарушает условие.

Идея в том, что \( A \) должно