Логическая формула

Задание

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

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

(x & A=0∧x & 58≠0)→x & 34≠0

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

Решение

Примем следующие обозначения:

"И" - истинное значение выражений,

"Л" - ложное значение выражений,

"∗"  - последовательность цифр 0 или 1 (в том числе пустая),

"?"  - одна цифра 1 или 0.

(x & A=0∧x & 58≠0)→x & 34≠0 ≡И, ∀x  в двух случаях:

1)  x & A=0∧x & 58≠0≡Л,∀x 

Для выполнения этого тождества достаточно взять число А = 58 (в бинарной системе:  1110102 ):

x & 58=0  и x & 58≠0  противоречат друг другу  ⟹ x & 58=0∧x & 58≠0≡Л, ∀x .

Тождество будет верным для всех чисел  A вида ∗1110102  в бинарной системе:

11110102 (58 + 64 = 122),  101110102 (58 + 128 = 186) и т.д.

2)  (x & A=0∧x & 58≠0≡И)∧(x & 34≠0 ≡И), ∀x 

x & 58≠0≡И  для тех чисел, которые в бинарной системе имеют вид: 

1?????2; ?1????2; ??1???2; ????1?2 (1).

x & 34≠0≡И для тех чисел, которые в бинарной системе имеют вид: 

1?????2; ????1?2 (2).

Для того, чтобы (1) и (2) совпали, достаточно из первого множества исключить числа вида: 

?1????2; ??1???2,

а значит это должны быть числа вида:

?0????2; ??0???2.

Осталось подобрать А из x & A=0≡И так, чтобы  при ∀x ему удовлетворяли числа вида: 

?0????2; ??0???2.

Для этого А в бинарной системе должно принимать значения ∗11???2.

А значит, минимально возможное А в бинарной системе равно 110002 (или 24 - в десятичной системе).

Ответ: 24