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

ЕГЭ ПО ИНФОРМАТИКЕ 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 для каждого двоичного разряда возможного числа х, помня, что для слагаемого   это значение противоположно:

Таким образом получаем:

-  для первого разряда числа х  с двоичной единицей 000001 выражение ложно, то есть равно нулю, значит в первом разряде числа А  стоит 0;

- для второго разряда  числа х  с двоичной двойкой 000010  выражение ложно, то есть равно нулю, значит во втором разряде числа А  стоит 0;

- для третьего разряда  числа х  с двоичной четверкой 000100  выражение истинно, то есть не равно нулю, значит в третьем разряде числа А  стоит 1;

- для четвертого разряда  числа х  с двоичной восьмеркой 001000  выражение ложно, то есть равно нулю, значит в четвертом разряде числа А  стоит 0;

- для пятого разряда  числа х  с двоичным шестнадцать  010000  выражение истинно, то есть не равно нулю, значит в пятом разряде числа А  стоит 1;

- для шестого разряда  числа х  с двоичным 32 = 000010  выражение ложно, то есть равно нулю, значит в шестом разряде числа А  стоит 0;

Т.к. по условию число А наименьшее, то независимо от значений разрядов числа х старше шестого в остальных разрядах числа А стоят нули. Следовательно,  А = 101002 = 2010.

Ответ:  20.

Примечание: подобную логику можно использовать для решения задач, в которых логическое выражение, связанное конъюнкцией, тождественно равно нулю. Тогда нужно использовать закон противоречия и приводить выражение к виду .