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

Автор публикации:

Дата публикации:

Краткое описание: Разобран оригинальный способ решения одного из наиболее сложных заданий части В в ЕГЭ по Информатике - задания 18 с поразрядной конъюнкцией (побитовыми операциями) над целыми числами. Особенностью данного способа является минимальное возрастание сложности решения от уве�...


ЕГЭ ПО ИНФОРМАТИКЕ 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→(CD) ≡ 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