Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Свидетельство о публикации

Автоматическая выдача свидетельства о публикации в официальном СМИ сразу после добавления материала на сайт - Бесплатно

Добавить свой материал

За каждый опубликованный материал Вы получите бесплатное свидетельство о публикации от проекта «Инфоурок»

(Свидетельство о регистрации СМИ: Эл №ФС77-60625 от 20.01.2015)

Инфоурок / Информатика / Другие методич. материалы / Решение задачи на выполнение логических операций над множествами с поразрядной конъюнкцией.
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 28 июня.

Подать заявку на курс
  • Информатика

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

библиотека
материалов

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


Подайте заявку сейчас на любой интересующий Вас курс переподготовки, чтобы получить диплом со скидкой 50% уже осенью 2017 года.


Выберите специальность, которую Вы хотите получить:

Обучение проходит дистанционно на сайте проекта "Инфоурок".
По итогам обучения слушателям выдаются печатные дипломы установленного образца.

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ

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

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

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

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