Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Информатика / Другие методич. материалы / Решение задачи на выполнение логических операций над множествами с поразрядной конъюнкцией.

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


  • Информатика

Поделитесь материалом с коллегами:

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


Краткое описание документа:

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

Автор
Дата добавления 24.05.2016
Раздел Информатика
Подраздел Другие методич. материалы
Просмотров559
Номер материала ДБ-096624
Получить свидетельство о публикации

Похожие материалы

Включите уведомления прямо сейчас и мы сразу сообщим Вам о важных новостях. Не волнуйтесь, мы будем отправлять только самое главное.
Специальное предложение
Вверх