Решение задачи на выполнение логических операций над множествами с поразрядной конъюнкцией.

ЕГЭ ПО ИНФОРМАТИКЕ 2016
Задание 18. Логические операции над множествами с поразрядной конъюнкцией.
Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Например, 14&5 = 11102&01012 = 01002 = 4.
Для какого наименьшего неотрицательного числа А формула (x & 53 ≠ 0)→((x & 41 =0)→(x & A ≠ 0) тождественно истинна (т.е. принимает значение 1 при любом неотрицательном целом значении переменной х)?
Решение :По условию:
(x & 53 ≠ 0)→((x & 41 =0)→(x & A ≠ 0) ≡ 1 для любого целого х ≥ 0.Для решения задачи воспользуемся законом исключения третьего P & P=1, преобразовав исходное выражение с помощью логических законов. Для простоты можно обозначить высказывания с побитовыми операциями (логические переменные) буквами, например:
B→(C→D) ≡ 1,
где B = (x & 53 ≠ 0), C =( x & 41 =0), D = (x & A ≠ 0), тогда после выражения импликации через базовые логические операции: инверсию и дизъюнкцию, получим:
B ∪C ∪D≡1,
Следовательно, согласно ассоциативному (сочетательному) закону дизъюнкции:
B∪ C∪D≡1.
Вернемся к исходному выражению, выполнив нужные операции инверсии:
((x & 53=0)∪x & 41 ≠ 0)) ∪(x & A ≠ 0≡1.
Обозначим P = (x & 53 = 0) U (x & 41 ≠ 0), следовательно P=(x & A ≠0)Переведем десятичные числа 53 и 41 в двоичные: 5310= 1101012; 4110=1010012 .
Т.к. число А поразрядно (т.е. побитно) умножается с соответствующими разрядами (битами) числа х, то определим значение слагаемого P для каждого двоичного разряда возможного числа х, помня, что для слагаемого P это значение противоположно:
53 = 1 1 0 1 0 1 = 0 41 = 1 0 1 0 0 1 ≠ 0 PP=(x & A ≠0)0 1 0 1 0 0
Х= 1 Ложь ИЛИ X= 1 Истина Истина Ложь (= 0) X= 1
1 0 Истина 1 0 Ложь Истина Ложь (= 0) 1 0
1 0 0 Ложь 1 0 0 Ложь Ложь Истина (≠0) 1 0 0
1 0 0 0 Истина 1 0 0 0 Истина Истина Ложь (=0)1 0 0 0
1 0 0 0 0 Ложь 1 0 0 0 0 Ложь Ложь Истина (≠0)1 0 0 0 0
1 0 0 0 0 0 Ложь 1 0 0 0 0 0 Истина Истина Ложь (= 0) 1 0 0 0 0 0
Таким образом получаем:
- для первого разряда числа х с двоичной единицей 000001 выражение P=x & A ≠0 ложно, то есть равно нулю, значит в первом разряде числа А стоит 0;
- для второго разряда числа х с двоичной двойкой 000010 выражение P=x & A ≠0 ложно, то есть равно нулю, значит во втором разряде числа А стоит 0;
- для третьего разряда числа х с двоичной четверкой 000100 выражение P=x & A ≠0 истинно, то есть не равно нулю, значит в третьем разряде числа А стоит 1;
- для четвертого разряда числа х с двоичной восьмеркой 001000 выражение P=x & A ≠0 ложно, то есть равно нулю, значит в четвертом разряде числа А стоит 0;
- для пятого разряда числа х с двоичным шестнадцать 010000 выражение P=x & A ≠0 истинно, то есть не равно нулю, значит в пятом разряде числа А стоит 1;
- для шестого разряда числа х с двоичным 32 = 000010 выражение P=x & A ≠0 ложно, то есть равно нулю, значит в шестом разряде числа А стоит 0;
Т.к. по условию число А наименьшее, то независимо от значений разрядов числа х старше шестого в остальных разрядах числа А стоят нули. Следовательно, А = 101002 = 2010.
Ответ: 20.
Примечание: подобную логику можно использовать для решения задач, в которых логическое выражение, связанное конъюнкцией, тождественно равно нулю. Тогда нужно использовать закон противоречия и приводить выражение к виду A & A=0.