ЕГЭ ПО ИНФОРМАТИКЕ 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.
Для решения задачи воспользуемся законом исключения третьего , преобразовав исходное выражение с помощью логических законов. Для простоты можно обозначить высказывания с побитовыми операциями (логические переменные) буквами, например:
B→(C→D) ≡ 1,
где B = (x & 53 ≠ 0), C =( x & 41 =0), D = (x & A ≠ 0), тогда после выражения импликации через базовые логические операции: инверсию и дизъюнкцию, получим:
Следовательно, согласно ассоциативному (сочетательному) закону дизъюнкции:
.
Вернемся к исходному выражению, выполнив нужные операции инверсии:
.
Обозначим P = (x & 53 = 0) U (x & 41 ≠ 0), следовательно
Переведем десятичные числа 53 и 41 в двоичные: 5310= 1101012; 4110=1010012 .
Т.к. число А поразрядно (т.е. побитно) умножается с соответствующими разрядами (битами) числа х, то определим значение слагаемого P для каждого двоичного разряда возможного числа х, помня, что для слагаемого это значение противоположно:
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
Истина
Истина
Ложь (
1
0
0
0
1
0
0
0
0
Ложь
1
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 выражение ложно, то есть равно нулю, значит в первом разряде числа А стоит 0;
- для второго разряда числа х с двоичной двойкой 000010 выражение ложно, то есть равно нулю, значит во втором разряде числа А стоит 0;
- для третьего разряда числа х с двоичной четверкой 000100 выражение истинно, то есть не равно нулю, значит в третьем разряде числа А стоит 1;
- для четвертого разряда числа х с двоичной восьмеркой 001000 выражение ложно, то есть равно нулю, значит в четвертом разряде числа А стоит 0;
- для пятого разряда числа х с двоичным шестнадцать 010000 выражение истинно, то есть не равно нулю, значит в пятом разряде числа А стоит 1;
- для шестого разряда числа х с двоичным 32 = 000010 выражение ложно, то есть равно нулю, значит в шестом разряде числа А стоит 0;
Т.к. по условию число А наименьшее, то независимо от значений разрядов числа х старше шестого в остальных разрядах числа А стоят нули. Следовательно, А = 101002 = 2010.
Ответ: 20.
Примечание: подобную логику можно использовать для решения задач, в которых логическое выражение, связанное конъюнкцией, тождественно равно нулю. Тогда нужно использовать закон противоречия и приводить выражение к виду .
2
