Презентация по информатике "Множества и логика в задачах ЕГЭ. Побитовые операции."

• 1 слайд

  Множества и логика Решение задач ЕГЭ (А18, побитовые операции).

• 2 слайд

  Базовые понятия. Задача1 Каким должно быть множество A, чтобы

• 3 слайд

  Базовые понятия. Задача 2 Каким должно быть множество A, чтобы A B

• 4 слайд

  Задача 1 Определите наименьшее натуральное число A такое, что выражение (x & 53 ≠ 0) → ((x & 41 = 0) → (x & A ≠ 0)) тождественно истинно. Решение: Обозначим через DN множество натуральных чисел, для которых побитовая конъюнкция с числом N дает ненулевое значение. DN={x: x & N ≠ 0 }

• 5 слайд

  Преобразуем исходное выражение: Используя правило Моргана получаем:

• 6 слайд

  Таким образом, мы пришли к базовой задаче.

• 7 слайд

  Переведем числа 53 и 41 в двоичную систему счисления. 53=110101 41=101001

• 8 слайд

  Номер бита 5 4 3 2 1 0 53 = 1 1 0 1 0 1 x = a b c d e f x&53 = a b 0 d 0 f Если x & 53 ≠ 0, значит среди битов (5,4,2,0) есть ненулевые

• 9 слайд

  Номер бита 5 4 3 2 1 0 41 = 1 0 1 0 0 1 x = a b c d e f x&41 = a 0 c 0 0 f Если x & 41 = 0, значит биты (5,3,0) числа x нулевые.

• 10 слайд

  Среди битов (4,2) числа x есть ненулевые. Для всех таких чисел x & A ≠ 0, где A может быть любым числом, у которого биты 4 и 2 равны 1. Минимальное из таких чисел 24 + 22 = 20

• 11 слайд

  Задача 2 Определите наибольшее натуральное число A такое, что выражение (x & A ≠ 0) → ((x & 20 = 0) → (x & 5 ≠ 0)) тождественно истинно. Решение: Обозначим через DN множество натуральных чисел, для которых побитовая конъюнкция с числом N дает ненулевое значение. DN={x: x & N ≠ 0 }

• 12 слайд

• 13 слайд

  Переведем числа 53 и 41 в двоичную систему счисления. 20 = 10100 5 = 101

• 14 слайд

  Номер бита 4 3 2 1 0 20 = 1 0 1 0 0 x = b c d e f x&20 = b 0 d 0 0 Если x & 20 ≠ 0, значит биты (4,2) числа x ненулевые.

• 15 слайд

  Номер бита 2 1 0 5 = 1 0 1 x = a b c x& 5 = a 0 c Если x & 5 ≠ 0, значит биты (2,0) числа x ненулевые.

• 16 слайд

  Объединение этих множеств – это множество чисел, в двоичной записи которых среди битов {4,2,0} есть ненулевые. Это (максимальное) множество определяется условием x & A ≠ 0. Биты (0, 2, 4) числа А могут быть 0 и 1. Чтобы А было максимальным они должны быть равны 1. А= 20+22+24=1+4+16=21

• 17 слайд

  Задачи для самостоятельного решения 1. Для какого наименьшего неотрицательного целого числа А формула (x & 25 ≠ 0) ((x & 17 = 0)  (x & A ≠ 0 )) тождественна истинна, то есть принимает значение 1 при любом неотрицательном целом значении переменной x. Ответ: А = 8

• 18 слайд

  Задачи для самостоятельного решения 2. Определите наименьшее натуральное число А, такое что выражение (x & 15 ≠ 0) ((x & 35 ≠ 0 )  (x & A ≠ 0 )) тождественно истинно. Ответ А=3

• 19 слайд

  Задачи для самостоятельного решения 3. Определите наименьшее натуральное число А, такое что выражение (x & 50 = 0) ((x & 35 ≠ 0 )  (x & A ≠ 0 )) тождественно истинно. Ответ А=16

• 20 слайд

  Задачи для самостоятельного решения 4. Определите наибольшее натуральное число А, такое что выражение (((x & A ≠ 0 )  (x &12 = 0))  ((x & A = 0) (x & 21 ≠ 0) )) v ((x & 21 = 0)  (x & 12 = 0)) тождественно истинно. Ответ А=12

• 21 слайд

  Используемые источники Поляков К.Ю. Подготовка к ЕГЭ по информатике. [Электронный ресурс] / URL: http//www.kpolyakov.spb.ru/school/ege.htm Поляков К.Ю. Множества и логика в задачах ЕГЭ. // Информатика №10, 2015, с. 38-43.