Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел т и п. Например, 14&5 = 11102&01012 = 01002 = 4. Для какого наименьшего неотрицательного целого числа А формула (x&114 # 0 V x&94 # 0) -> (x&73 = 0 -> x&A # 0) тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной х)?

Для того чтобы формула была тождественно истинной, необходимо, чтобы при любом неотрицательном целом значении переменной x выполнялись два условия:

1. (x&114 # 0 V x&94 # 0) - должно быть истинным
2. (x&73 = 0 -> x&A # 0) - должно быть истинным

Для первого условия рассмотрим выражение (x&114 # 0 V x&94 # 0). Число 114 в двоичной системе счисления равно 1110010, число 94 равно 1011110. Проведем поразрядную конъюнкцию для этих чисел:

x&114 = xxxxxxx x&94 = xxxxxx0

x&114 # 0 = 0xxxxxx x&94 # 0 = xxxxxx0

Таким образом, выражение (x&114 # 0 V x&94 # 0) будет истинным только в случае, если х имеет второй бит равный 1.

Для второго условия рассмотрим выражение (x&73 = 0 -> x&A # 0). Число 73 в двоичной системе счисления равно 1001001. Проведем поразрядную конъюнкцию для этого числа:

x&73 = xxx0xxx

Таким образом, выражение (x&73 = 0 -> x&A # 0) будет истинным только в случае, если х имеет четвертый бит равный 0.

Из двух условий видно, что число A должно иметь первый и четвертый бит равные 1. Наименьшее неотрицательное целое число, удовлетворяющее этому условию, это 9 (в двоичной системе 1001).

Таким образом, наименьшее неотрицательное целое число A, для которого формула тождественно истинна, равно 9.